오늘 배운 거슨…


연결리스트다!


연결리스트,

연결된 리스트라는 뜻!

그치만

이대로 끝내면 아쉬우니

연결 리스트의 몇가지 종류만 알아보자

단일 연결리스트

• 각 노드¹는 데이터와 다음 노드를 가리키는 포인터(next)를 가진다
  
  

마지막 노드의 next는 None 또는 null

[1 | next] → [2 | next] → [3 | None]

• 앞에서만 순차적으로 접근 가능

이중 연결 리스트

각 노드는 prev(이전 노드)와 next(다음 노드)를 가짐

None ← [1 | prev, next] ↔ [2 | prev, next] ↔ [3 | prev, None]

• 양방향 탐색 가능

원형 연결 리스트

마지막 노드의 next가 다시 첫 번째 노드를 가리킴

[1] → [2] → [3]
 ↑             ↓
 └─────────────┘

• 리스트의 어느 지점에서도 순환 가능

원형 이중 연결 리스트

• 이중 연결 리스트인데…

• 원형입니다!

head.prev는 tail, tail.next는 head를 가리킴

[1] ⇄ [2] ⇄ [3]
 ↑           ↓
 └───────⇄────┘

• 양방향 순환 가능

• 시작 노드가 어딘지 중요하지 않음 (노드끼리만 연결되어 있음)

정리표

___