이 주제는 여기에서 자세히 다룬다.
연결 리스트는 배열과 마찬가지로 데이터 아이템의 연속된 시퀀스다. 하지만 배열은 객체를 저장하기 위해 큰 메모리 블록을 할당하는 반면, 연결 리스트의 각 요소는 메모리 상에서 완전히 분리된 객체이며 링크를 통해 연결된다:
+--------+ +--------+ +--------+ +--------+
| | | | | | | |
| node 0 |--->| node 1 |--->| node 2 |--->| node 3 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
연결 리스트의 요소를 노드라고 부른다. 위 그림은 단일 연결 리스트를 보여주는데, 각 노드는 다음 노드를 가리키는 참조(또는 "포인터")만 가지고 있다. 아래 그림과 같은 이중 연결 리스트에서는 노드가 이전 노드를 가리키는 포인터도 갖는다:
+--------+ +--------+ +--------+ +--------+
| |--->| |--->| |--->| |
| node 0 | | node 1 | | node 2 | | node 3 |
| |<---| |<---| |<---| |
+--------+ +--------+ +--------+ +--------+
리스트가 어디서 시작하는지 추적해야 한다. 일반적으로 헤드라는 포인터를 사용한다:
+--------+ +--------+ +--------+ +--------+
head --->| |--->| |--->| |--->| |---> nil
| node 0 | | node 1 | | node 2 | | node 3 |
nil <---| |<---| |<---| |<---| |<--- tail
+--------+ +--------+ +--------+ +--------+
리스트의 끝을 가리키는 테일 참조도 유용하다. 마지막 노드의 "다음" 포인터는 nil이며, 마찬가지로 첫 번째 노드의 "이전" 포인터도 nil이다.
대부분의 연결 리스트 연산은 O(n) 시간 복잡도를 가지므로, 일반적으로 배열보다 느리다. 하지만 연결 리스트는 훨씬 더 유연하다. 배열처럼 큰 메모리 덩어리를 복사할 필요 없이, 연결 리스트의 많은 연산은 단순히 몇 개의 포인터만 변경하면 된다.
O(n) 시간 복잡도의 이유는 리스트에서 두 번째 노드에 접근하기 위해 list[2]와 같은 간단한 방법을 사용할 수 없기 때문이다. 해당 노드에 대한 참조가 없다면, head에서 시작해 next 포인터를 따라가며 해당 노드를 찾아야 한다. 또는 tail에서 시작해 previous 포인터를 사용해 거꾸로 찾을 수도 있다.
하지만 한 번 노드에 대한 참조를 얻으면, 삽입이나 삭제 같은 연산은 매우 빠르다. 단지 노드를 찾는 과정이 느릴 뿐이다.
따라서 연결 리스트를 다룰 때는 가능한 한 앞쪽에 새로운 항목을 삽입하는 것이 좋다. 이는 O(1) 연산이다. 마찬가지로 tail 포인터를 추적하고 있다면 뒤쪽에 삽입하는 것도 O(1) 연산이다.
단일 연결 리스트는 previous 포인터를 저장할 필요가 없기 때문에 이중 연결 리스트보다 메모리를 조금 덜 사용한다.
하지만 특정 노드에서 이전 노드를 찾아야 한다면 문제가 생긴다. 리스트의 헤드부터 시작해서 원하는 노드에 도달할 때까지 전체 리스트를 순회해야 한다.
많은 작업에서 이중 연결 리스트를 사용하면 더 쉽게 처리할 수 있다.
연결 리스트를 사용하는 대표적인 예는 큐를 구현할 때다. 배열을 사용하면 큐의 앞쪽에서 요소를 제거할 때 메모리에서 다른 모든 요소를 한 칸씩 이동시켜야 하므로 속도가 느리다. 하지만 연결 리스트를 사용하면 head가 두 번째 요소를 가리키도록 변경하기만 하면 된다. 이 방법이 훨씬 빠르다.
하지만 요즘에는 직접 연결 리스트를 구현할 일이 거의 없다. 그래도 연결 리스트가 어떻게 동작하는지 이해하는 것은 유용하다. 객체를 서로 연결하는 원리는 트리나 그래프에서도 사용되기 때문이다.
먼저 노드를 정의하는 타입을 만들어 보자:
public class LinkedListNode<T> {
var value: T
var next: LinkedListNode?
weak var previous: LinkedListNode?
public init(value: T) {
self.value = value
}
}이 타입은 제네릭 타입이므로 T는 노드에 저장할 수 있는 모든 데이터 타입이 될 수 있다. 이후 예제에서는 문자열을 사용할 것이다.
이것은 이중 연결 리스트이며, 각 노드는 next와 previous 포인터를 갖는다. 이 포인터들은 다음이나 이전 노드가 없을 경우 nil이 될 수 있으므로 옵셔널로 선언한다. (이후 설명에서는 단일 연결 리스트일 경우 어떤 함수를 수정해야 하는지 언급할 것이다.)
참고: 소유권 순환을 피하기 위해
previous포인터를weak로 선언한다. 리스트에서 노드A가 노드B를 가리키면,A는B를 가리키고 동시에B도A를 가리킨다. 특정 상황에서 이 소유권 순환은 노드가 삭제된 후에도 계속 살아 있게 만들 수 있다. 이를 방지하기 위해 하나의 포인터를weak로 선언해 순환을 끊는다.
이제 LinkedList를 만들어 보자. 첫 번째 부분은 다음과 같다:
public class LinkedList<T> {
public typealias Node = LinkedListNode<T>
private var head: Node?
public var isEmpty: Bool {
return head == nil
}
public var first: Node? {
return head
}
}클래스 이름은 가능한 한 설명적이어야 하지만, 클래스를 사용할 때마다 긴 이름을 입력하고 싶지는 않다. 따라서 LinkedList 내부에서 LinkedListNode<T> 대신 더 짧은 Node를 사용할 수 있도록 타입 별칭을 정의한다.
이 연결 리스트는 head 포인터만 가지고 있으며, tail 포인터는 없다. tail 포인터를 추가하는 것은 독자에게 연습 문제로 남긴다. (이후 설명에서 tail 포인터가 있을 경우 어떤 함수가 달라지는지 언급할 것이다.)
리스트가 비어 있는지 확인하려면 head가 nil인지 확인하면 된다. head는 private 변수이므로, 리스트의 첫 번째 노드를 반환하는 first 프로퍼티를 추가했다.
플레이그라운드에서 다음과 같이 테스트할 수 있다:
let list = LinkedList<String>()
list.isEmpty // true
list.first // nil리스트의 마지막 노드를 반환하는 프로퍼티도 추가해 보자. 여기서부터 흥미로워진다:
public var last: Node? {
guard var node = head else {
return nil
}
while let next = node.next {
node = next
}
return node
}Swift를 처음 접한다면 if let은 봤을지 몰라도 if var는 처음 볼 수도 있다. 이는 head 옵셔널을 언래핑하고 결과를 node라는 새로운 로컬 변수에 넣는다는 점에서 동일하다. 차이점은 node가 상수가 아닌 변수이므로 루프 내에서 변경할 수 있다는 것이다.
이 루프는 Swift의 마법을 보여준다. while let next = node.next는 node.next가 nil이 될 때까지 계속 반복한다. 이를 다음과 같이 작성할 수도 있다:
var node: Node? = head
while node != nil && node!.next != nil {
node = node!.next
}하지만 이 방식은 Swift스럽지 않다. Swift의 옵셔널 언래핑 지원을 활용하는 것이 좋다. 이후 코드에서 이런 종류의 루프를 자주 볼 수 있다.
참고:
tail포인터를 유지했다면last는 단순히return tail을 하면 된다. 하지만 우리는tail포인터가 없으므로 리스트의 처음부터 끝까지 순회해야 한다. 이는 비용이 큰 연산이며, 특히 리스트가 길 경우 더욱 그렇다.
물론, last는 리스트에 노드가 없기 때문에 nil을 반환한다. 이제 리스트의 끝에 새 노드를 추가하는 메서드를 추가해 보자:
public func append(value: T) {
let newNode = Node(value: value)
if let lastNode = last {
newNode.previous = lastNode
lastNode.next = newNode
} else {
head = newNode
}
}append() 메서드는 먼저 새로운 Node 객체를 생성한 다음, 방금 추가한 last 프로퍼티를 사용해 마지막 노드를 찾는다. 만약 해당 노드가 없다면 리스트가 아직 비어 있는 상태이므로 head가 이 새로운 Node를 가리키도록 한다. 하지만 유효한 노드 객체를 찾았다면, next와 previous 포인터를 연결해 이 새 노드를 체인에 추가한다. 연결 리스트 코드의 많은 부분이 이런 next와 previous 포인터 조작을 포함한다.
플레이그라운드에서 테스트해 보자:
list.append("Hello")
list.isEmpty // false
list.first!.value // "Hello"
list.last!.value // "Hello"리스트는 다음과 같이 보인다:
+---------+
head --->| |---> nil
| "Hello" |
nil <---| |
+---------+
이제 두 번째 노드를 추가해 보자:
list.append("World")
list.first!.value // "Hello"
list.last!.value // "World"리스트는 다음과 같이 보인다:
+---------+ +---------+
head --->| |--->| |---> nil
| "Hello" | | "World" |
nil <---| |<---| |
+---------+ +---------+
next와 previous 포인터를 확인해 보면 다음과 같다:
list.first!.previous // nil
list.first!.next!.value // "World"
list.last!.previous!.value // "Hello"
list.last!.next // nil리스트에 있는 노드의 개수를 세는 메서드를 추가해 보자. 이는 이미 했던 것과 매우 유사하다:
public var count: Int {
guard var node = head else {
return 0
}
var count = 1
while let next = node.next {
node = next
count += 1
}
return count
}리스트를 순회하는 방식은 동일하지만, 이번에는 카운터도 증가시킨다.
참고:
count를 **O(n)**에서 **O(1)**로 빠르게 만드는 한 가지 방법은 리스트에 있는 노드의 개수를 추적하는 변수를 유지하는 것이다. 노드를 추가하거나 제거할 때마다 이 변수를 업데이트한다.
리스트에서 특정 인덱스의 노드를 찾고 싶다면 어떻게 해야 할까? 배열의 경우 array[index]를 쓰면 되고, 이는 O(1) 연산이다. 연결 리스트에서는 조금 더 복잡하지만, 코드는 비슷한 패턴을 따른다:
public func node(atIndex index: Int) -> Node {
if index == 0 {
return head!
} else {
var node = head!.next
for _ in 1..<index {
node = node?.next
if node == nil { //(*1)
break
}
}
return node!
}
}먼저 주어진 인덱스가 0인지 확인한다. 0이라면 head를 그대로 반환한다. 하지만 인덱스가 0보다 크다면 head에서 시작해 node.next 포인터를 따라 리스트를 순회한다. 이때 count 메서드와의 차이점은 두 가지 종료 조건이 있다는 것이다. 하나는 for-loop 문이 인덱스에 도달했을 때이며, 이때 주어진 인덱스의 노드를 얻을 수 있다. 두 번째는 for-loop 문에서 node.next가 nil을 반환해 break가 발생하는 경우이다. (*1) 이는 주어진 인덱스가 범위를 벗어났음을 의미하며, 이 경우 크래시가 발생한다.
테스트해 보자:
list.nodeAt(0)!.value // "Hello"
list.nodeAt(1)!.value // "World"
// list.nodeAt(2) // crash재미로 subscript 메서드도 구현해 보자:
public subscript(index: Int) -> T {
let node = node(atIndex: index)
return node.value
}이제 다음과 같이 작성할 수 있다:
list[0] // "Hello"
list[1] // "World"
list[2] // crash!list[2]는 해당 인덱스에 노드가 없기 때문에 크래시가 발생한다.
지금까지 리스트의 끝에 새 노드를 추가하는 코드를 작성했지만, 이는 리스트의 끝을 먼저 찾아야 하기 때문에 느리다. (만약 tail 포인터를 사용했다면 빠를 것이다.) 따라서 리스트의 항목 순서가 중요하지 않다면 리스트의 앞에 삽입하는 것이 좋다. 이는 항상 O(1) 연산이다.
리스트의 특정 인덱스에 새 노드를 삽입하는 메서드를 작성해 보자.
public func insert(_ node: Node, atIndex index: Int) {
let newNode = node
if index == 0 {
newNode.next = head
head?.previous = newNode
head = newNode
} else {
let prev = self.node(atIndex: index-1)
let next = prev.next
newNode.previous = prev
newNode.next = prev.next
prev.next = newNode
next?.previous = newNode
}
}node(atIndex:) 메서드와 마찬가지로 insert(_: at:) 메서드도 주어진 인덱스가 0인지 여부에 따라 분기한다. 먼저 첫 번째 경우를 살펴보자. 다음과 같은 리스트와 새 노드(C)가 있다고 가정하자.
+---------+ +---------+
head --->| |---->| |-----//----->
| A | | B |
nil <---| |<----| |<----//------
+---------+ +---------+
[0] [1]
+---------+
new --->| |----> nil
| C |
| |
+---------+
이제 새 노드를 첫 번째 노드 앞에 놓는다. 다음과 같이 한다:
new.next = head
head.previous = new
+---------+ +---------+ +---------+
new --->| |--> head -->| |---->| |-----//----->
| C | | A | | B |
| |<-----------| |<----| |<----//------
+---------+ +---------+ +---------+
마지막으로, head를 새 노드로 교체한다.
head = new
+---------+ +---------+ +---------+
head --->| |--->| |---->| |-----//----->
| C | | A | | B |
nil <---| |<---| |<----| |<----//------
+---------+ +---------+ +---------+
[0] [1] [2]
하지만 주어진 인덱스가 0보다 크다면, 이전과 다음 인덱스의 노드를 얻어 그 사이에 삽입해야 한다. node(atIndex:)를 사용해 이전과 다음 노드를 얻을 수 있다:
+---------+ +---------+ +---------+
head --->| |---//--->| |---->| |----
| | | A | | B |
nil <---| |---//<---| |<----| |<---
+---------+ +---------+ +---------+
[0] [index-1] [index]
^ ^
| |
prev next
prev = node(at: index-1)
next = prev.next
이제 새 노드를 prev와 next 사이에 삽입한다.
new.prev = prev; prev.next = new // connect prev and new.
new.next = next; next.prev = new // connect new and next.
+---------+ +---------+ +---------+ +---------+
head --->| |---//--->| |---->| |---->| |
| | | A | | C | | B |
nil <---| |---//<---| |<----| |<----| |
+---------+ +---------+ +---------+ +---------+
[0] [index-1] [index] [index+1]
^ ^ ^
| | |
prev new next
테스트해 보자:
list.insert("Swift", atIndex: 1)
list[0] // "Hello"
list[1] // "Swift"
list[2] // "World"또한 리스트의 앞과 뒤에 새 노드를 추가해 이 기능이 제대로 작동하는지 확인해 보자.
참고:
node(atIndex:)와insert(_: atIndex:)함수는 단일 연결 리스트에서도 사용할 수 있다. 이전 요소를 찾기 위해 노드의previous포인터에 의존하지 않기 때문이다.
또 무엇이 필요할까? 노드를 제거하는 기능이다! 먼저 removeAll()을 구현해 보자. 이는 매우 간단하다:
public func removeAll() {
head = nil
}만약 tail 포인터가 있다면 여기서도 nil로 설정해야 한다.
다음으로 개별 노드를 제거할 수 있는 함수를 추가해 보자. 이미 노드에 대한 참조가 있다면 remove()를 사용하는 것이 가장 최적이다. 리스트를 순회해 노드를 먼저 찾을 필요가 없기 때문이다.
public func remove(node: Node) -> T {
let prev = node.previous
let next = node.next
if let prev = prev {
prev.next = next
} else {
head = next
}
next?.previous = prev
node.previous = nil
node.next = nil
return node.value
}노드를 리스트에서 제거할 때, 이전 노드와 다음 노드에 대한 연결을 끊는다. 리스트를 다시 연결하려면 이전 노드를 다음 노드에 연결해야 한다.
head 포인터를 잊지 말자! 만약 이 노드가 리스트의 첫 번째 노드라면 head가 다음 노드를 가리키도록 업데이트해야 한다. (마찬가지로 tail 포인터가 있고 이 노드가 마지막 노드인 경우도 고려해야 한다.) 물론, 더 이상 노드가 없다면 head는 nil이 되어야 한다.
테스트해 보자:
list.remove(list.first!) // "Hello"
list.count // 2
list[0] // "Swift"
list[1] // "World"노드에 대한 참조가 없다면 removeLast()나 removeAt()을 사용할 수 있다:
public func removeLast() -> T {
assert(!isEmpty)
return remove(node: last!)
}
public func removeAt(_ index: Int) -> T {
let node = nodeAt(index)
assert(node != nil)
return remove(node: node!)
}이 모든 제거 함수는 제거된 요소의 값도 반환한다.
list.removeLast() // "World"
list.count // 1
list[0] // "Swift"
list.removeAt(0) // "Swift"
list.count // 0참고: 단일 연결 리스트의 경우 마지막 노드를 제거하는 것은 조금 더 복잡하다.
last만으로는 리스트의 끝을 찾을 수 없으며, 끝에서 두 번째 노드에 대한 참조도 필요하다. 대신nodesBeforeAndAfter()헬퍼 메서드를 사용한다. 만약 리스트에tail포인터가 있다면removeLast()는 매우 빠르지만,tail을 이전 노드로 가리키도록 업데이트해야 한다.
LinkedList 클래스로 할 수 있는 몇 가지 재미있는 작업이 더 있다. 읽기 쉬운 디버그 출력을 제공하는 것이 유용할 수 있다:
extension LinkedList: CustomStringConvertible {
public var description: String {
var s = "["
var node = head
while node != nil {
s += "\(node!.value)"
node = node!.next
if node != nil { s += ", " }
}
return s + "]"
}
}이렇게 하면 리스트를 다음과 같이 출력할 수 있다:
[Hello, Swift, World]
리스트를 뒤집어 head가 tail이 되고 그 반대로 만드는 것은 어떨까? 이를 위한 매우 빠른 알고리즘이 있다:
반복적 접근:
public func reverse() {
var node = head
tail = node // If you had a tail pointer
while let currentNode = node {
node = currentNode.next
swap(¤tNode.next, ¤tNode.previous)
head = currentNode
}
}재귀적 접근:
public func reverse(node: head) {
if !head || !head.next {
return head
}
let temp = reverse(head.next)
head.next.next = head
head.next = nil
return temp
}이 코드는 리스트 전체를 순회하며 각 노드의 next와 previous 포인터를 교환한다. 또한 head 포인터를 가장 마지막 요소로 이동시킨다. (만약 tail 포인터가 있다면 이 또한 업데이트해야 한다.) 결과는 다음과 같다:
+--------+ +--------+ +--------+ +--------+
tail --->| |<---| |<---| |<---| |---> nil
| node 0 | | node 1 | | node 2 | | node 3 |
nil <---| |--->| |--->| |--->| |<--- head
+--------+ +--------+ +--------+ +--------+
배열에는 map()과 filter() 함수가 있으며, 연결 리스트에도 이를 추가할 수 있다.
public func map<U>(transform: T -> U) -> LinkedList<U> {
let result = LinkedList<U>()
var node = head
while node != nil {
result.append(transform(node!.value))
node = node!.next
}
return result
}이를 다음과 같이 사용할 수 있다:
let list = LinkedList<String>()
list.append("Hello")
list.append("Swifty")
list.append("Universe")
let m = list.map { s in s.characters.count }
m // [5, 6, 8]그리고 여기 filter가 있다:
public func filter(predicate: T -> Bool) -> LinkedList<T> {
let result = LinkedList<T>()
var node = head
while node != nil {
if predicate(node!.value) {
result.append(node!.value)
}
node = node!.next
}
return result
}재미있는 예제:
let f = list.filter { s in s.count > 5 }
f // [Universe, Swifty]독자에게 남기는 연습 문제: map()과 filter()의 이 구현은 새 노드를 새 리스트의 끝에 추가하기 때문에 매우 빠르지 않다. append()는 O(n) 연산이며, 리스트의 마지막 노드를 찾기 위해 전체 리스트를 스캔해야 한다. 이를 더 빠르게 만들 수 있을까? (힌트: 추가한 마지막 노드를 추적한다.)
지금까지 살펴본 LinkedList 버전은 클래스로 구현된 노드를 사용한다. 따라서 참조 의미론(reference semantics)을 따른다. 이 방식이 잘못된 것은 아니지만, Array나 Dictionary 같은 Swift의 다른 컬렉션에 비해 다소 무거운 편이다.
열거형(enum)을 사용해 값 의미론(value semantics)을 따르는 연결 리스트를 구현할 수도 있다. 이 방식은 다음과 같이 표현할 수 있다:
enum ListNode<T> {
indirect case node(T, next: ListNode<T>)
case end
}열거형 기반 버전의 가장 큰 차이점은 Swift의 값 의미론 때문에 리스트를 수정할 때마다 새로운 복사본이 생성된다는 점이다. 이 방식이 적합한지 여부는 애플리케이션의 요구사항에 따라 다르다.
[이 섹션은 필요에 따라 더 자세히 설명할 예정이다.]
Swift의 표준 라이브러리에 정의된 Collection 프로토콜은 Sequence 프로토콜을 준수하며, 비파괴적으로 여러 번 순회할 수 있고 인덱스 서브스크립트로 요소에 접근할 수 있는 타입이 준수해야 한다.
이 프로토콜을 준수하면 데이터 컬렉션을 다룰 때 흔히 사용되는 다양한 프로퍼티와 연산에 접근할 수 있다. 또한 커스텀 타입이 Swift 개발자들이 익숙한 패턴을 따르도록 할 수 있다.
이 프로토콜을 준수하려면 클래스는 다음을 제공해야 한다:
startIndex와 endIndex 프로퍼티/// 비어 있지 않은 컬렉션에서 첫 번째 요소의 위치
public var startIndex: Index {
get {
return LinkedListIndex<T>(node: head, tag: 0)
}
}
/// 컬렉션의 "끝을 지난" 위치. 즉, 마지막 유효한 서브스크립트 인자의 다음 위치
/// - 복잡도: O(n), 여기서 n은 리스트의 요소 개수
/// 이는 프로토콜의 기대치에서 벗어난다.
public var endIndex: Index {
get {
if let h = self.head {
return LinkedListIndex<T>(node: h, tag: count)
} else {
return LinkedListIndex<T>(node: nil, tag: startIndex.tag)
}
}
}public subscript(position: Index) -> T {
get {
return position.node!.value
}
}컬렉션은 자신의 인덱스를 관리할 책임이 있으므로, 아래 구현은 리스트의 노드에 대한 참조를 유지한다. 인덱스의 tag 프로퍼티는 리스트에서 노드의 위치를 나타낸다.
/// 'tag' 인덱스에 있는 노드에 대한 참조를 포함하는 커스텀 인덱스 타입
public struct LinkedListIndex<T> : Comparable
{
fileprivate let node: LinkedList<T>.LinkedListNode<T>?
fileprivate let tag: Int
public static func==<T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool {
return (lhs.tag == rhs.tag)
}
public static func< <T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool {
return (lhs.tag < rhs.tag)
}
}마지막으로, 연결 리스트는 주어진 인덱스 다음의 인덱스를 다음과 같이 계산할 수 있다.
public func index(after idx: Index) -> Index {
return LinkedListIndex<T>(node: idx.node?.next, tag: idx.tag+1)
}연결 리스트는 유연하지만 많은 연산이 **O(n)**의 시간 복잡도를 가진다.
연결 리스트에서 연산을 수행할 때는 항상 관련된 next와 previous 포인터를 업데이트해야 하며, 경우에 따라 head와 tail 포인터도 업데이트해야 한다. 이를 잘못 처리하면 리스트가 올바르지 않게 되고, 프로그램이 어느 시점에서 크래시가 발생할 수 있다. 주의해야 한다!
리스트를 처리할 때는 종종 재귀를 사용할 수 있다. 첫 번째 엘리먼트를 처리한 후 나머지 리스트에 대해 같은 함수를 재귀적으로 호출한다. 다음 엘리먼트가 없을 때 작업이 완료된다. 이것이 연결 리스트가 LISP와 같은 함수형 프로그래밍 언어의 기초가 되는 이유다.
원문은 Matthijs Hollemans가 Ray Wenderlich의 Swift Algorithm Club을 위해 작성함