이 글은 "Ruby로 배우는 실용적인 컴퓨터 과학" 시리즈의 세 번째 포스팅입니다. 오늘은 연결 리스트(Linked List)에 대해 알아보겠습니다.
그렇다면 연결 리스트란 무엇일까요?
이름 그대로, 연결 리스트는 데이터를 리스트 형태로 저장하는 자료 구조입니다.
'연결(Linked)'이라는 이름은 데이터가 노드(Node) 단위로 저장되고, 이 노드들이 순서대로 서로 연결되어 있다는 데서 유래했습니다.
연결 리스트 vs 배열
연결 리스트는 배열과 다른 성능 특성을 가지고 있습니다. 바로 이 차이 때문에 상황에 따라 둘 중 하나를 선택하게 됩니다.
즉, 특정 작업에서는 배열보다 연결 리스트가 더 효율적일 수 있다는 의미입니다.
연결 리스트에는 인덱싱이 없고 무작위 접근(random access)도 지원하지 않습니다. 다시 말해 리스트 중간에 있는 요소에 곧바로 접근할 수 없습니다.
원하는 노드를 찾으려면 리스트의 헤드(head)에서 시작해 링크를 하나씩 따라가며 탐색해야 하며, 찾지 못하면 리스트 끝까지 가야 합니다.
반면, 연결 리스트의 중간에서 요소를 추가하거나 삭제하는 작업은 훨씬 빠릅니다.
노드 하나의 'next' 포인터만 변경하면 되기 때문입니다.
하지만 배열의 중간에서 요소를 삭제하면 빈 공간이 생기고, 이 공간을 메우려면 삭제된 요소 오른쪽의 모든 요소를 한 칸씩 이동시켜야 합니다.
이런 작업을 자주 수행해야 한다면 상당히 비효율적입니다!
마찬가지로 배열 중간에 요소를 삽입할 때도 빈 자리를 만들기 위해 뒤쪽의 모든 요소를 밀어내야 합니다.
코드 예제를 통해 확인해 보겠습니다:
a = [1,2,3,4,5,6,7,8]
def insert(arr, item, pos)
tmp = arr[pos]
arr[pos] = item
arr.replace(arr[0..pos] + [tmp] + arr[pos+1..-1])
end
insert(a, 99, 3)
p a참고: Ruby에는 내장
Array#insert메서드가 이미 존재하지만, 이번 예제에서는 해당 메서드가 내부적으로 어떻게 동작하는지 보여드리기 위해 직접 구현했습니다.
그렇다면 리스트 중간에 요소를 삽입할 때 성능 차이는 어느 정도일까요?
다음은 벤치마크 결과입니다:
Comparison:
LinkedList: 1815407.9 i/s
Array: 18090.3 i/s - 100.35x slower무려 100배 이상의 차이가 나지만, 노드를 먼저 검색해야 하므로 LinkedList의 크기에 따라 결과가 크게 달라질 수 있습니다.
두 자료 구조를 비교하는 또 다른 방법은 시간 복잡도 표를 확인하는 것입니다 (삽입·삭제 시 노드 탐색이 필요 없다는 전제):
| 자료 구조 | 접근 | 검색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열(Array) | O(1) | O(n) | O(n) | O(n) |
| 연결 리스트(Linked List) | O(n) | O(n) | O(1) | O(1) |
실제 활용 사례가 궁금하신가요?
Aaron Patterson이 연결 리스트를 활용해 RubyGems의 성능을 개선한 풀 리퀘스트(Pull Request)가 실제로 존재합니다:
https://github.com/rubygems/rubygems/pull/1188
연결 리스트 구현하기
Ruby는 기본적으로 LinkedList 클래스를 제공하지 않으므로 직접 구현해야 합니다.
우리는 다음과 같은 연산들이 가능하길 원합니다:
append— 리스트 끝에 요소 추가append_after— 특정 노드 뒤에 요소 삽입delete— 요소 삭제find— 요소 검색
가능한 구현 방법 중 하나는 다음과 같습니다:
class LinkedList
def initialize
@head = nil
end
def append(value)
if @head
find_tail.next = Node.new(value)
else
@head = Node.new(value)
end
end
def find_tail
node = @head
return node if !node.next
return node if !node.next while (node = node.next)
end
def append_after(target, value)
node = find(target)
return unless node
old_next = node.next
node.next = Node.new(value)
node.next.next = old_next
end
def find(value)
node = @head
return false if !node.next
return node if node.value == value
while (node = node.next)
return node if node.value == value
end
end
def delete(value)
if @head.value == value
@head = @head.next
return
end
node = find_before(value)
node.next = node.next.next
end
def find_before(value)
node = @head
return false if !node.next
return node if node.next.value == value
while (node = node.next)
return node if node.next && node.next.value == value
end
end
def print
node = @head
puts node
while (node = node.next)
puts node
end
end
end이 구현은 꼬리(tail) 노드를 별도로 추적하지 않고, 새 항목을 추가할 때마다 꼬리를 찾습니다. 그렇기 때문에 append 연산의 시간 복잡도는 선형 시간(O(n))이 됩니다.
그리고 노드 클래스(Node Class)는 다음과 같습니다:
class Node
attr_accessor :next
attr_reader :value
def initialize(value)
@value = value
@next = nil
end
def to_s
"Node with value: #{@value}"
end
end실제 사용 방법은 다음과 같습니다:
list = LinkedList.new
list.append(10)
list.append(20)
list.append(30)
list.append_after(10, 15)
list.append_after(20, 25)
list.print지금까지 살펴본 것은 기본적인 "단일 연결 리스트(Singly-Linked List)" 구현입니다.
연결 리스트에는 여러 종류가 있습니다:
- 이중 연결 리스트(Doubly-Linked List)
- 원형 연결 리스트(Circular Linked List)
이중 연결 리스트에서는 각 노드가 두 개의 포인터를 가집니다. 하나는 다음 노드(next node)를 가리키고, 다른 하나는 이전 노드(previous node)를 가리킵니다.
이 덕분에 리스트를 양방향으로 탐색할 수 있어 검색이 더 유연해지지만, 리스트를 변경할 때는 두 포인터를 모두 관리해야 하므로 추가 작업이 필요합니다.
원형 연결 리스트는 마지막 노드가 다시 헤드(head) 노드와 연결되어 리스트 전체가 하나의 원을 이루는 형태입니다.
정리
이번 글에서는 연결 리스트(Linked List)에 대해 배웠습니다. 배열 중간에서 요소를 자주 추가하고 삭제하는 작업이 많다면 연결 리스트가 좋은 대안이 될 수 있습니다.
또한 코딩 인터뷰에서도 자주 등장하는 주제이므로, 그 목적만으로도 배워둘 가치가 충분합니다.
아래 공유 버튼을 눌러 이 글을 널리 퍼뜨려 주세요. 더 많은 분들이 이 지식의 혜택을 받을 수 있습니다 🙂