연결 리스트

순차 (sequential) 표현

• 연속된 원소들이 일정한 거리만큼 떨어져서 저장
• 테이브에서 임의 원소 접근, 스택이나 큐의 원소 삽입/삭제에 적합
• 순서 리스트에서 임의 원소의 삽입/삭제 비용 큼

연결된 (linked) 표현

• 각 원소들이 기억 장소 내의 어떤 곳에나 위치
• 노드는 데이터와 링크(포인트)로 구성됨

노드 삽입

• 삽입 절차 (ex. GAT 삽입) 
  1. 현재 사용하고 있지 않은 노드 a 할당
  2. 노드 a의 data 필드에 GAT 설정
  3. a의 link 필드가 FAT 다음 노드, 즉 HAT를 가리키도록
  4. FAT를 포함한 노드의 link 필드가 a를 가리키도록
• 삽입할때 리스트에 있는 다른 원소들의 이동이 불필요
• link 필드를 위한 저장 공간이 추가로 사용

노드 삭제

• 삭제 절차 (ex. GAT 삭제)
  1. GAT 바로 앞에 있는 원소 FAT 찾기
  2. FAT의 link를 HAT의 위치로 설정

이중 연결 리스트

• 각 노드느 전방과 후방을 가리키는 두 개의 링크를 가짐