연결리스트의 조회는 순차적으로 이루어진다

May 13, 2025, 07:47 PM

…

연결리스트의 경우 노드들이 포인터로 연결되어 있는 구조다. 그러다보니 진입점이 명확한데, 바로 첫 번째 노드(head) 가 해당 리스트의 입구 역할을 하게된다.

  (head)
-----------     -----------     -----------
|  nodeA  | --> |  nodeB  | --> |  nodeC  |
-----------     -----------     -----------

입구는 단 하나이므로, 다른 노드들에 접근하기 위해서는 반드시 head부터 시작해서 하나씩 순차적으로 순회를 해야한다. 이는 연결리스트의 조회 혹은 탐색 연산이 O(n)의 시간복잡도를 가지게되는 이유다.

이중 연결리스트(Doubly Linked List)를 사용할 경우, 마지막 노드(tail) 역시 진입점이 되므로, 역순으로 순회가 가능하다. 하지만 평균 O(n)인 것은 동일하다.

확장 🌱

연결리스트 중간부터 접근할 수 있는 방법은 없을까?
- 노드를 연결할때마다 중간이 되는 위치의 노드를 기억하고 있다면 불가능할 것도 없지. head와 tail을 사용해서 리스트의 처음과 마지막을 기억하는 것 처럼. 하지만 해당 기능을 구현하므로써 얻는 이득은 딱히 없을 것 같다（コスパが悪い）.
Jagged List가 갑자기 떠올랐다. 어떤 구조였었지?
연결리스트의 입구가 망가져 버리면 남아있는 노드들은 어떻게 될까? → 250517213935