§ 1 · 흩어진 노드연결 리스트란
연결 리스트(linked list)는 배열처럼 항목들의 목록이다. 그러나 내부 구현이 다르다. 배열은 메모리에 연속된 셀로 저장되지만, 연결 리스트의 셀들—노드(node)—은 메모리 전역에 흩어질 수 있다.
흩어진 노드들이 어떻게 같은 리스트로 묶일까? 핵심은 이것이다 — 각 노드는 자기 데이터 외에 다음 노드의 메모리 주소를 저장한다. 이 추가 데이터를 링크(link)라 한다.
class Node attr_accessor :data, :next_node def initialize(data) @data = data end end class LinkedList attr_accessor :first_node def initialize(first_node) @first_node = first_node end end
null이다.
§ 2 · 링크를 따라읽기와 검색
배열에서 인덱스 2 읽기는 O(1)이었다. 연결 리스트에서는 그렇지 않다. 노드들이 메모리 어디에 있을지 알 수 없으므로, 첫 노드부터 링크를 하나씩 따라가야 한다. 읽기는 O(N)이다 — 배열에 비해 큰 단점이다.
검색은 배열과 동등하다. 둘 다 첫 셀부터 하나씩 보며 찾으므로 O(N)이다.
§ 3 · 거울상삽입과 삭제
여기서 연결 리스트가 빛난다. 배열은 시작에 삽입할 때 모든 데이터를 밀어야 해 O(N)이지만, 연결 리스트는 새 노드를 만들어 링크만 바꾸면 되니 시작 삽입이 O(1)이다.
흥미롭게도 배열과 연결 리스트는 정확히 거울상이다.
| 시나리오 | 배열 | 연결 리스트 |
|---|---|---|
| 시작에 삽입/삭제 | 최악의 경우 | 최고의 경우 |
| 중간에 삽입/삭제 | 평균 경우 | 평균 경우 |
| 끝에 삽입/삭제 | 최고의 경우 | 최악의 경우 |
| 연산 | 배열 | 연결 리스트 |
|---|---|---|
| 읽기 | O(1) | O(N) |
| 검색 | O(N) | O(N) |
| 삽입 | O(N) · 끝은 O(1) | O(N) · 시작은 O(1) |
| 삭제 | O(N) · 끝은 O(1) | O(N) · 시작은 O(1) |
§ 4 · 다중 삭제연결 리스트의 활약
읽기는 배열이 압도적인데, 왜 연결 리스트를 쓸까? 연결 리스트가 빛나는 경우 — 리스트를 한 번 훑으며 많은 요소를 삭제할 때다.
유효하지 않은 이메일 주소를 걸러내는 프로그램을 보자. 1,000개 목록에 100개가 무효라고 하자.
- 배열 — 삭제할 때마다 데이터를 왼쪽으로 미는 O(N). 읽기 1,000단계 + 삭제 100 × N ≈ 100,000단계.
- 연결 리스트 — 삭제는 링크만 바꾸면 되는 O(1). 읽기 1,000단계 + 삭제 100단계 = 1,100단계.
§ 5 · 양방향 링크이중 연결 리스트
이중 연결 리스트(doubly linked list)는 각 노드가 두 개의 링크를 가진다 — 다음 노드와 이전 노드. 또 첫 번째와 마지막 노드를 모두 추적한다.
덕분에 양쪽 끝에 각각 O(1)로 접근할 수 있다. 끝에 O(1)로 삽입하고, 앞에서 O(1)로 삭제할 수 있다 — 이는 큐의 완벽한 기반이 된다.
class Queue def initialize @queue = DoublyLinkedList.new end def enque(value) @queue.insert_at_end(value) # O(1) end def deque removed_node = @queue.remove_from_front # O(1) return removed_node.data end end
§ 6 · 정리이 장이 남긴 것
연결 리스트는 특정 상황에서 성능을 향상시킨다. 핵심은 선택지를 갖는 것, 그리고 올바른 시점에 올바른 선택을 하는 것이다. 다음 장에서는 더 복잡한 노드 기반 자료구조 — 이진 트리를 만난다.