20220208 LinkedList

리스트

• 순서를 가진 데이터의 집합을 가리키는 추상자료형
  • 순차리스트 : 배열을 기반으로 구현된 리스트
  • 연결리스트 : 메모리의 동적할당을 기반으로 구현된 리스트

순차리스트

• 삽입/삭제 연산 관정에서 연속적인 메모리 배열을 위해 원소들을 이동해야함
• 원소의 개수가 많고 삽입/삭제 연산이 빈번할수록 소용시간 증가
• 배열의 크기가 정해진경우 실제로 사용될 메모리 보다 크게 할당하여 메모리 낭비 혹은 할당된 메모리보다 많은 자료를 사용하여 새롭게 배열을 구성해야함

연결리스트

• 자료의 논리적인 순서와 메모리상의 물리적인 순서가 일치하지 않음 개별적으로 위치한 각 원소를 연결하여 하나의 전체적인 자료구조를 생성
• 링크를 통해 원소에 접근
• 자료구조의 크기를 동적으로 조정가능해, 메모리의 효율적인 사용이 가능

노드

• 연결 리스트에서 하나의 원소를 표현하는 building block
• 구성요소
  • 데이터 필드
    • 원소의 값을 저장
    • 저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용
  • 링크 필드
    • 다음 노드의 참조값을 저장

헤드

• 연결 리스트의 첫 노드에 대한 참조값을 가지고 있음