연결 리스트(Linked List)

• 리스트의 항목들을 노드(Node)라고 하는 곳에 분산해서 저장
• Node 구성
  • Data Field
    • 리스트의 원소(데이터 값을 저장하는 곳)
  • Link Field
    • 다른 노드의 주소값을 저장하는 장소(포인터)

LinkedList feature

1. 수행도중 크기를 늘리거나 줄이기 가능
2. 삽입, 삭제 과정이 단순
3. Overhead가 발생(포인터 정보)
4. Locality가 낮음

Array feature

1. 접근 시간이 빠르고 일정
2. 삽입, 삭제 과정이 복잡
3. 리스트의 크기가 고정(Compile-Time)
4. Locality가 높음

헤드 포인터와 노드의 생성

• 시작점의 주소는?
  • 헤드 포인터
• 끝 지점의 위치는?
  • 끝 노드의 링크 필드의 주소값은 NULL

연결 리스트의 종류