[Data Structures & Algorithms in Swift] Chapter 6: Linked List

https://www.kodeco.com/books/data-structures-algorithms-in-swift

Data Structures & Algorithms in Swift

 

 

Chapter 1: Why Learn Data Structures & Algorithms?

Chapter 2: Complexity

Chapter 3: Swift Standard Library

Chapter 4: Stack Data Structure

Chapter 5: Stack Challenges

Chapter 6: Linked List

---

 

연결 리스트(Linked List)는 단방향 sequence로 배열되어 있는 값들의 모음이다. 이론적으로 연결 리스트는 배열(Array)에 비해 몇 가지 장점이 있다.

• 리스트의 front에서 insert, remove 할 때 상수 시간(Constant time) 시간복잡도를 가진다.
• 안정적인 성능

A linked list

 

다이어그램에서 알 수 있듯이 연결 리스트는 연결된 일련의 노드들이다(chain of nodes). 노드는 두 가지 역할을 한다.

1. 값(value)을 유지(hold)한다.
2. 다음 노드에 대한 참조(reference)를 유지한다. 해당 참조가 nil이라면 해당 노드가 리스트의 끝임을 의미이다.

A node holding the value 12

 

여기서는 연결 리스트와 이에 관련된 연산외에도, Swift의 간결한 기능 중 하나인 COW(copy-on-write)를 구현한다.

 

Node

public class Node<Value> {
    public var value: Value
    public var next: Node?
    
    public init(value: Value, next: Node? = nil) {
        self.value = value
        self.next = next
    }
}

extension Node: CustomStringConvertible {
    public var description: String {
        guard let next = next else { 
            //next가 존재하지 않으면, 해당 value만 출력(Linked List에서의 마지막 node)
            return "\(value)"
        }
        
        return "\(value) -> " + String(describing: next) + " "
    }
}

연결 리스트를 생성하고 출력해 본다.

example(of: "creating and linking nodes") {
    let node1 = Node(value: 1)
    let node2 = Node(value: 2)
    let node3 = Node(value: 3)

    node1.next = node2
    node2.next = node3

    print(node1) // 1 -> 2 -> 3
}

세 개의 노드를 생성하고 연결한다.

A linked list containing values 1, 2, and 3

 

출력은 다음과 같다.

---Example of creating and linking nodes---
1 -> 2 -> 3

하지만, 노드가 많아지면 위와 같은 방식으로 노드를 연결하는 것이 힘들어진다. 이 문제를 해결하는 일반적인 방법은 노드 객체를 관리하는 LinkedList를 작성하는 것이다.

 

LinkedList

public struct LinkedList<Value> {
    public var head: Node<Value>?
    public var tail: Node<Value>?
    
    public init() {}
    
    public var isEmpty: Bool {
        head == nil
    }
}

extension LinkedList: CustomStringConvertible {
    public var description: String {
        guard let head = head else {
          return "Empty list"
        }
        
        return String(describing: head)
    }
}

Linked List는 head와 tail을 가지고 있으며, 각각 리스트의 첫 노드와 마지막 노드를 가리킨다.

The head and tail of the list

 

Adding values to the list

Node 객체를 관리하는 인터페이스(interface)를 만들어야 한다. 먼저, 값을 추가할 수 있어야 한다. Linked List에 value를 추가하는 세 가지 방법이 있다.

1. push : list의 앞에 node를 추가한다.
2. append : list의 뒤에 node를 추가한다.
3. insert(after:) : list의 특정 node 뒤에 node를 추가한다.

각 항목을 구현하고, 성능을 분석한다.

 

push operations

push는 list의 앞에 value를 추가한다. 이를 head-first insertion 이라고도 한다.

extension LinkedList {
    public mutating func push(_ value: Value) {
        head = Node(value: value, next: head)
        
        if tail == nil { //빈 list에 push하는 경우, 새 node는 head이자, tail이 된다.
            tail = head
        }
    }
}

구현을 확인해 본다.

example(of: "push") {
    var list = LinkedList<Int>()
    list.push(3)
    list.push(2)
    list.push(1)
    
    print(list) // 1 -> 2 -> 3
}

해당 코드의 출력은 다음과 같다.

---Example of push---
1 -> 2 -> 3

 

append operations

append는 list의 끝에 value를 추가한다. 이를 tail-end insertion 이라고도 한다.

extension LinkedList {
    public mutating func append(_ value: Value) {
        guard !isEmpty else { 
            //list가 비어 있는 경우에는 push와 같다(head와 tail을 동일한 새 Node로 업데이트 한다).
            push(value)
            return
        }
        
        tail!.next = Node(value: value)
        //빈 list에 append하는 경우가 아니라면, 새 Node를 생성하고 tail Node의 next에 연결한다.
        //위의 guard 구문에서 list가 비어 있지 않다는 것을 확인했기 때문에 Force unwrapping을 사용한다.
        
        tail = tail!.next
        //새 Node를 tail로 지정한다.
    }
}

구현을 확인해 본다.

example(of: "append") {
    var list = LinkedList<Int>()
    list.append(1)
    list.append(2)
    list.append(3)
    
    print(list) // 1 -> 2 -> 3
}

해당 코드의 출력은 다음과 같다.

---Example of append---
1 -> 2 -> 3

 

insert(after:) operations

insert(after:) 는 list의 특정 위치에 value를 삽입하며, 두 단계로 이루어진다.

1. list에서 특정 node를 찾는다.
2. 새 node를 삽입(insert) 한다.

먼저 삽입할 노드를 찾는 코드를 구현한다.

extension LinkedList {
    public func node(at index: Int) -> Node<Value>? { //값을 insert할 node를 찾는다.
        //주어진 index로 list에서 node를 검색한다.
        //LinkedList는 head Node에서만 list의 Node에 액세스할 수 있으므로 반복 순회를 해야 한다.
        
        var currentNode = head
        var currentIndex = 0
        //현재 Node와 Index를 트래킹할 변수를 생성하고 값을 head로 할당한다.
        
        while currentNode != nil && currentIndex < index { //원하는 index에 도달할 때까지 list의 참조를 이동한다.
            //비어 있는 list이거나, index가 범위를 벗어날 경우에는 nil을 반환하게 된다(tail Node의 next가 nil 이므로).
            currentNode = currentNode!.next
            currentIndex += 1
        }
        
        return currentNode
    }
}

node(at:)은 주어진 index로 node를 검색한다. 이제, 새 노드를 삽입하는 코드를 추가한다.

extension LinkedList {
    @discardableResult 
    //@discardableResult 주석을 달면, 메서드의 반환값을 변수로 받지 않아도 warning이 호출되지 않는다.
    public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {
        guard tail !== node else { 
            //insert 하는 index가 list의 마지막이라면(tail Node), append와 같다.
            //메모리 주소값을 비교 해야 한다.
            append(value)
            return tail!
        }
        
        node.next = Node(value: value, next: node.next)
        //찾은 Node의 next로 새 Node를 생성하고, 새 Node를 index로 찾은 Node의 next로 연결한다.
        
        return node.next!
    }
}

구현을 확인해 본다.

example(of: "inserting at a particular index") {
    var list = LinkedList<Int>()
    list.push(3)
    list.push(2)
    list.push(1)
    
    print("Before inserting: \(list)") 
    // Before inserting: 1 -> 2 -> 3
    
    var middleNode = list.node(at: 1)!
    
    for _ in 1...4 { //1, 2, 3, 4
        middleNode = list.insert(-1, after: middleNode)
    }
    
    print("After inserting: \(list)") 
    // After inserting: 1 -> 2 -> -1 -> -1 -> -1 -> -1 -> 3
}

출력은 다음과 같다.

---Example of inserting at a particular index---
Before inserting: 1 -> 2 -> 3
After inserting: 1 -> 2 -> -1 -> -1 -> -1 -> -1 -> 3

 

Performance analysis

연결 리스트에 값을 추가하는 세 가지 연산자(operation)를 구현했다. 

	push	append	insert(after:)	node(at:)
작동 (Behavior)	head에 node 추가	tail에 node 추가	after node 뒤에  node 추가	해당 index의 node 반환
시간 복잡도 (Time complexity)	O(1)	O(1)	O(1)	O(i), i는 주어진 index

 

Removing values from the list

Linked List에서 node를 삭제하는 세 가지 방법이 있다.

1. pop : list의 가장 앞 node를 제거한다.
2. removeLast : list 끝의 node를 제거한다.
3. remove(at:) : list의 특정 node를 제거한다.

세 가지를 모두 구현하고, 성능을 분석한다.

 

pop operations

pop은 list의 앞(front) node를 제거한다. push 만큼이나 간단하게 구현할 수 있다.

extension LinkedList {
    @discardableResult
    public mutating func pop() -> Value? {
        defer { //메서드에서 코드 흐름과 상관없이 가장 마지막에 defer 블록이 실행된다. //return 이후에 호출된다.
            head = head?.next //head를 두 번째 node(head의 next)로 할당한다.
            //더 이상 이전 head(첫 노드)에 참조가 없으므로 ARC가 제거한다.
            
            if isEmpty { //list가 비었다면, tail을 nil로 할당한다.
                tail = nil
            }
        }
        
        return head?.value //list에서 제거된 value를 반환한다.
        //목록이 비어 있을 수 있으므로, optional이어야 한다.
    }
}

pop은 목록(list)에서 제거된 값을 반환한다. 목록이 비어 있을 수 있으므로, 이 값은 optional이어야 한다.

example(of: "pop") {
    var list = LinkedList<Int>()
    list.push(3)
    list.push(2)
    list.push(1)
    
    print("Before popping list: \(list)") 
    // Before popping list: 1 -> 2 -> 3
    
    let poppedValue = list.pop()
    
    print("After popping list: \(list)") 
    // After popping list: 2 -> 3
    print("Popped value: " + String(describing: poppedValue)) 
    // Popped value: Optional(1)
}

출력은 다음과 같다.

---Example of pop---
Before popping list: 1 -> 2 -> 3
After popping list: 2 -> 3
Popped value: Optional(1)

 

removeLast operations

list의 마지막 node를 제거하는 것은 다소 복잡하다. tail node에 대한 참조가 있지만, 그 이전 node에 대한 참조가 없으면 제거할 수 없다(새로 tail node 지정해 줘야 하기 때문에).

extension LinkedList {
    @discardableResult
    public mutating func removeLast() -> Value? {
        guard let head = head else { 
            //list가 비어 있다면 반환할 것이 없으므로 nil 반환
            return nil
        }
        
        guard head.next != nil else { 
            //list에 node가 head 하나 뿐인 경우, pop으로 head(유일한 node) 반환
            return pop() //node가 하나인 경우에는 pop과 같다.
        }
        
        var prev = head
        var current = head
        
        while let next = current.next { 
            //current.next가 nil이 될 때까지(마지막 node 까지) 순회한다.
            //단순히 tail node만 가져오려면, tail로 접근하면 되지만 마지막 node를 제거하고 
            //마지막 이전 node를 새로 tail로 지정해줘야 하기 때문에 마지막 이전 node를 알아야 한다.
            prev = current
            current = next
        }
        
        //current는 마지막 node, prev는 마지막 이전 node가 된다.
        prev.next = nil //prev.next의 참조를 제거한다.
        tail = prev //tail의 참조를 업데이트 해 준다.
        
        return current.value
    }
}

구현을 확인해 본다.

example(of: "removing the last node") {
    var list = LinkedList<Int>()
    list.push(3)
    list.push(2)
    list.push(1)
    
    print("Before removing last node: \(list)") 
    // Before removing last node: 1 -> 2 -> 3
    
    let removedValue = list.removeLast()
    
    print("After removing last node: \(list)") 
    // After removing last node: 1 -> 2
    print("Removed value: " + String(describing: removedValue)) 
    // Removed value: Optional(3)
}

출력은 다음과 같다.

---Example of removing the last node---  
Before popping list: 1 -> 2 -> 3
After popping list: 1 -> 2 
Popped value: Optional(3)

removeLast는 list 전체를 순회해야 하므로, 비교적 시간복잡도가 큰 O(n) 연산이 필요하다.

 

remove(after:) operations

특정 node를 제거하는 remove(after:)는 insert(after :)와 유사하다. 먼저 제거하려는 node 바로 앞의 node를 찾은 다음 next연결을 해제해야 한다.

Removing the middle node

 

extension LinkedList {
    @discardableResult
    //@discardableResult 주석을 달면, 메서드의 반환값을 변수로 받지 않아도 warning이 호출되지 않는다.
    public mutating func remove(after node: Node<Value>) -> Value? {
        defer { //메서드에서 코드 흐름과 상관없이 가장 마지막에 defer 블록이 실행된다. //return 이후에 호출된다.
            //defer 블록에서 Node를 연결 해제해 준다.
            if node.next === tail { 
                //tail를 제거하는 경우에는 tail 참조를 새로 업데이트 해 줘야 한다.
                //메모리 주소를 비교 해야 한다.
                tail = node
            }
            node.next = node.next?.next
            //제거하려는 node 바로 앞의 node를 찾아 next 참조를 새로 업데이트 해 준다.
            //삭제하는 node(node의 이전 next)는 더 이상 참조가 없으므로 ARC가 제거한다.
        }

        return node.next?.value
    }
}

노드의 연결 해제는 defer 블록에서 발생한다. 제거하는 노드가 tail인 경우에는 참조를 업데이트 해야 하므로 주의가 필요하다. 

example(of: "removing a node after a particular node") {
    var list = LinkedList<Int>()
    list.push(3)
    list.push(2)
    list.push(1)
    

    print("Before removing at particular index: \(list)") 
    // Before removing at particular index: 1 -> 2 -> 3
    
    let index = 1
    let node = list.node(at: index - 1)!
    let removedValue = list.remove(after: node)
    
    print("After removing at index \(index): \(list)") 
    // After removing at index 1: 1 -> 3
    print("Removed value: " + String(describing: removedValue)) 
    // Removed value: Optional(2)
}

출력은 다음과 같다.

---Example of removing a node after a particular node---
Before removing at particular index: 1 -> 2 -> 3
After removing at index 1: 1 -> 3
Removed value: Optional(2)

insert(at:)와 마찬가지로이 remove(after:) 시간 복잡도는 O(1) 이지만, 특정 노드에 대한 참조가 필요하므로(node(at:) 사용) 실질적인 시간 복잡도는 더 높아지게 된다.

 

Performance analysis

연결 리스트에 값을 제거하는 세 가지 연산자(operation)을 구현했다.

	pop	removeLast	remove(after:)
작동 (Behavior)	head의  node 삭제	tail의  node 삭제	after node 뒤의  node 삭제
시간 복잡도 (Time complexity)	O(1)	O(n)	O(1)

기본적인 LinkedList를 구현했지만, 이후부터는 Swift interface의 장점을 이용해 최대한 Swiftty한 구현을 추가한다.

 

Swift collection protocols

Swift 표준 라이브러리(standard library)에는 특정 유형(type)을 정의하는데 도움이 되는 일련의 프로토콜(protocol)이 있다. 이러한 각 프로토콜은 특정 특성과 성능을 보장한다. Swift의 Collection protocol 집합에는 4가지가 있다. 간단히 요약하면 다음과 같다.

• Tier 1, Sequence : 해당 요소에 대한 순차적 액세스를 한다. 순차 접근(sequential access) 시, 요소가 desctructive한 경우도 있으니 주의해야 한다.
• Tier 2, Collection : 추가적인 보증(guarantee)을 제공하는 Sequnce type이다. Collection type은 유한(finite)하며, 비파괴적 순차접근(nondestructive sequential access)를 허용한다.
• Tier 3, BidirectionalColllection : Sequence의 양방향(상하, 좌우)으로 이동할 수 있는 Collection type 이다. 연결 리스트(Linked List)는 head에서 tail로만 이동할 수 있고, 반대방향으로 순회할 수 없으므로 BidirectionalCollection이 아니다.
• Tier 4, RandomAccessCollection : BidirectionalColllection이 특정 index로 해당 요소에 액세스하는 시간이 다른 요소에 액세스하는 시간과 동일하다면 RandomAccessCollection이 될 수 있다. RandomAccess는 어느 요소에 액세스하더라도, 같은 시간 내에 호출되는 것으로, sequential access와는 대조된다. 연결 리스트는 head에 가까운 노드에 접근하는 것이 tail에 가까운 노드에 접근하는 것 보다 빠르기 때문에 RandomAccessCollection이 될 수 없다.

value type에서 for in loop를 사용하는 경우, iterator는 사본이 되기 때문에 nondestructive하다. 하지만, reference type의 경우에는 for in loop 시, iterator가 자기 자신을 참조하기 때문에, 순회 이후 desctructive하다. 즉, Sequence는 특정 시점에서 다음 지점의 원소를 꺼내 쓰는 것일 뿐, 다음 순회에서 재시작할지, 이어서 진행할지의 조건은 보증하지 않는다.
https://soooprmx.com/archives/7047
nondestructive를 지원하려면, Collection을 구현해야 한다.
https://developer.apple.com/documentation/swift/sequence

연결 리스트(Linked List)는 Swift Collection protocol에서 두 가지 경우에 해당한다.

1. LinkedList는 Node들의 연결이므로, Sequence protocol을 채택한다.
2. Node들의 연결은 유한한(finite) sequence이므로, Collection protocol을 채택한다.

Becoming a Swift collection

Collection protocol은 유한(finite) sequence이며, 피파괴적 순차 접근(nondestructive sequential access)를 제공한다. Swift Collection은 여기에 추가적으로 subscript 접근을 허용하는데, 이는 index에 collection의 value를 매핑시킨다.

array[5]

subscript는 대괄호로 정의되고, index와 함께 사용해 Collection의 value를 반환한다.

 

Custom collection indexes

Collection protocol의 메서드의 성능은 index의 value에 매핑하는 속도로 정의된다. Swift 배열(Array)과 달리, 연결 리스트(Linked List)는 기본적으로 subscript 연산자를 사용하여 O(1) 연산을 할 수 없다. 따라서 LinkedList에서 subscript 연산자를 사용하기 위해서는 해당 Node에 대한 참조가 포함된 custom index를 정의해야 한다.

https://developer.apple.com/documentation/swift/collection

extension LinkedList {
    public struct Index: Comparable {
        public var node: Node<Value>?
        
        static public func ==(lhs: Index, rhs: Index) -> Bool {
            switch (lhs.node, rhs.node) {
            case let (left?, right?):
                return left.next === right.next
            case (nil, nil):
                return true
            default:
                return false
            }
        }
        
        static public func <(lhs: Index, rhs: Index) -> Bool {
            guard lhs != rhs else {
                return false
            }

            let nodes = sequence(first: lhs.node) { $0?.next }
            
            return nodes.contains { $0 === rhs.node }
        }
    }
}

이 Custom Index를 사용하여 Collection의 요구사항(requirement)을 구현한다.

extension LinkedList: Collection { //Collection 구현을 위해서는 다음 변수와 메서드를 구현해야 한다.
    public var startIndex: Index { //처음 index
        Index(node: head)
        //head를 반환한다.
    }
    
    public var endIndex: Index { //마지막으로 접근 가능한 value의 바로 뒤 index
        Index(node: tail?.next)
        //tail.next을 반환한다.
        //마지막으로 액세스 가능한 값 바로 다음 node를 endIndex로 지정한다.
    }
    
    public func index(after i: Index) -> Index { //index 증가시키는 방법을 정의한다.
        Index(node: i.node?.next) //바로 다음 Node의 index를 반환한다.
    }
    
    public subscript(position: Index) -> Value {
        //subscript는 index를 Collection의 value에 매핑하는 데 사용한다.
        position.node!.value
        //Custom으로 구현한 Index로 해당 node에 접근할 수 있다.
        //해당 node의 value를 반환한다.
    }
}

구현을 확인한다.

example(of: "using collection") {
    var list = LinkedList<Int>()
    
    for i in 0...9 {
        list.append(i)
    }

    print("List: \(list)") 
    // List: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
    print("First element: \(list[list.startIndex])") 
    // First element: 0
    print("Array containing first 3 elements: \(Array(list.prefix(3)))") 
    // Array containing first 3 elements: [0, 1, 2]
    print("Array containing last 3 elements: \(Array(list.suffix(3)))") 
    // Array containing last 3 elements: [7, 8, 9]

    let sum = list.reduce(0, +)

    print("Sum of all values: \(sum)") // Sum of all values: 45
}

출력은 다음과 같다.

---Example of using collection---
List: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
First element: 0
Array containing first 3 elements: [0, 1, 2]
Array containing last 3 elements: [7, 8, 9]
Sum of all values: 45

 

Value semantics and copy-on-write

Swift Collection의 또 다른 중요한 점은 value semantic(의미론)을 가진다는 것이다. 이는 copy-on-write(COW)를 사용해 구현한다. COW의 개념을 배열(Array)로 확인하면 다음과 같다.

Value Semantics
    값을 복사해서 사용
    스택에서 자동 변수로 처리
    참조 계산하지 않는다. 자기 자신을 소유.
    값을 그대로 참조. 불변 상태 유지.
    copy-on-write: 복사 이후에 값 변경하지 전까지는 이전 값을 그대로 사용
    함수 중심 프로그래밍에 적합

Reference Semantics
    reference에 대한 포인터만 복사
    힙에서 포인터 변수로 처리
    ARC(자동 레퍼런스 계산) 방식 활용
    언제든지 값이 변경될 수 있음
    병렬 처리 제한, 최적화 한계
    함수 중심 프로그래밍에 부적합

https://oaksong.github.io/2017/12/29/value-semantics-vs-reference-semantics/
https://en.wikipedia.org/wiki/Value_semantics

example(of: "array cow") {
    let array1 = [1, 2]
    var array2 = array1 //여기에서는 값을 복사하지 않고 참조를 가지고 있는다.
    
    print("array1: \(array1)") // array1: [1, 2]
    print("array2: \(array2)") // array2: [1, 2]
    
    print("---After adding 3 to array 2---")
    array2.append(3) //array2가 수정 될 때, array1의 요소는 변경되지 않는다.
    //처음 할당할 때가 아닌 append가 호출될 때, 사본을 만든다.
    print("array1: \(array1)") // array1: [1, 2]
    print("array2: \(array2)") // array2: [1, 2, 3]
}

출력은 다음과 같다.

---Example of array cow---
array1: [1, 2]
array1: [1, 2]
---After adding 3 to array 2---
array1: [1, 2]
array1: [1, 2, 3]

array2가 수정 될 때, array1의 요소는 변경되지 않는다. 처음 할당할 때가 아닌 append가 호출될 때, 사본을 만든다.

 

이제, 연결 리스트(Linked List)의 value semantic를 확인한다.

example(of: "linked list cow") {
    var list1 = LinkedList<Int>()
    list1.append(1)
    list1.append(2)
    
    var list2 = list1
    
    print("List1: \(list1)") // List1: 1 -> 2
    print("List2: \(list2)") // List2: 1 -> 2
    
    print("After appending 3 to list2")
    
    list2.append(3)
    print("List1: \(list1)") 
    //COW 구현 전 List1: 1 -> 2 -> 3     //COW 구현 후 List1: 1 -> 2
    print("List2: \(list2)") // List2: 1 -> 2 -> 3
}

출력은 다음과 같다.

---Example of linked list cow---
List1: 1 -> 2
List2: 1 -> 2
After appending 3 to list2
List1: 1 -> 2 -> 3
List2: 1 -> 2 -> 3

Node가 class로 구현되었기 때문에 LinkedList에서는 value semantic이 구현되지 않는다. 하지만, LinkedList는 struct로 구현했기 때문에 value semantic이 적용되지 않는 것은 심각한 문제이다. COW를 구현하면 이 문제가 해결된다. COW로 value semantic을 구현하는 방법은 매우 간단하다. LinkedList의 내용을 변경하기 전에, 복사본을 만들고 모든 참조(head, tail)를 복사본으로 업데이트 하면 된다.

extension LinkedList {
    private mutating func copyNodes() { //복사본을 만든다.
        guard var oldNode = head else {
            return
        }

        head = Node(value: oldNode.value)
        var newNode = head

        while let nextOldNode = oldNode.next {
            newNode!.next = Node(value: nextOldNode.value)
            newNode = newNode!.next

            oldNode = nextOldNode
        }

        tail = newNode
    }
}

위 메서드는 연결 리스트의 기존 노드를 동일한 값으로 새로 할당된 노드로 대체한다. 그리고, LinkedList에서 mutating 키워드를 가진 모든 메서드를 찾고, 이 메서드의 시작부에 copyNodes를 호출 시키는 코드를 추가해 준다. 수정해야 할 메서드 들의 목록은 다음과 같다.

• push
• append
• insert(after:)
• pop
• removeLast
• remove(after:)

수정 이후, 다시 linked list cow 예제를 실행하면 출력은 다음과 같다.

---Example of linked list cow--- 
List1: 1 -> 2
List2: 1 -> 2
After appending 3 to list2 
List1: 1 -> 2
List2: 1 -> 2 -> 3

COW로 value semantic이 구현되었지만, 해당 메서드 사용시 copyNodes()가 먼저 호출되어 복사가 일어나므로 O(n) 의 오버헤드가 추가된다.

 

Optimizing COW

이 추가적인 오버헤드를 완화하기 위한 두 가지 방법이 있다. 첫 번째는 LinkedList의 node를 참조하는 owner가 오직 하나(one)라면, 복사를 하지 않는 것이다.

 

isKnownUniquelyReferenced

Swift standard library에는 isKnownUniquelyReferenced 함수가 있다. 이 함수는 객체에 정확히 하나의 참조가 있는지 여부를 확인한다.

example(of: "isKnownUniquelyReferenced") {
    var list1 = LinkedList<Int>()
    list1.append(1)
    //연결 리스트에 요소가 하나만 있을 경우에는 head가 동시에 tail이기 때문에 
    //isKnownUniquelyReferenced(&list1.head)이 false가 된다.
    list1.append(2)
    
    print("List1 uniquely referenced: \(isKnownUniquelyReferenced(&list1.head))") 
    //List1 uniquely referenced: true
    var list2 = list1
    print("List1 uniquely referenced: \(isKnownUniquelyReferenced(&list1.head))") 
    //List1 uniquely referenced: false
}

출력은 다음과 같다.

List1 uniquely referenced: true
List1 uniquely referenced: false

isKnownUniquelyReferenced를 사용해, node 객체가 공유되는지 여부를 확인할 수 있다. copyNode 메서드에 guard 문을 추가해 준다.

extension LinkedList {
    private mutating func copyNodes() { //복사본을 만든다.
        guard !isKnownUniquelyReferenced(&head) else { //Optimizing COW
            //참조하고 있는 owner의 수를 확인해 최적화 해 준다.
            //하나의 list만 가지고 계속 작업하는 경우에는(LinkedList를 복사할 필요가 없는 경우)
            //이 guard에서 종료되므로, 복사가 일어나지 않아 오버헤드를 줄일 수 있다.
            return
        }

        guard var oldNode = head else {
            return
        }

        head = Node(value: oldNode.value)
        var newNode = head

        while let nextOldNode = oldNode.next {
            newNode!.next = Node(value: nextOldNode.value)
            newNode = newNode!.next
            oldNode = nextOldNode
        }

        tail = newNode
    }
}

예제를 실행해보면, COW는 여전히 유효한 것을 알 수 있다. 

 

A minor predicament

이전 예제에 코드를 추가한다.

example(of: "A minor predicament") {
    var list1 = LinkedList<Int>()
    list1.append(1)
    list1.append(2)
    
    var list2 = list1
    
    print("List1: \(list1)") // List1: 1 -> 2
    print("List2: \(list2)") // List2: 1 -> 2
    
    print("After appending 3 to list2")
    
    list2.append(3)
    print("List1: \(list1)") //List2: 1 -> 2
    print("List2: \(list2)") // List2: 1 -> 2 -> 3
    
    print("Removing middle node on list2") //COW
    
    if let node = list2.node(at: 0) {
        list2.remove(after: node)
    }

    print("List2: \(list2)") //List2: 1 -> 2 -> 3
}

출력은 다음과 같다.

---Example of linked list cow---
List1: 1 -> 2
List2: 1 -> 2
After appending 3 to list2
List1: 1 -> 2
List2: 1 -> 2 -> 3
Removing middle node on list2
List2: 1 -> 2 -> 3

COW 최적화 이후로, remove 메서드가 더 이상 정상적으로 작동하지 않는다. 그 이유는, 모든 mutating 메서드는 copyNodes()로 node들을 복사할 수 있으므로, remove(after:) 실행 시에 복사되어 잘못된 node 집합에서 삭제 된다. 이를 수정하기 위해 새로운 버전의 copyNodes() 메서드를 작성해야 한다.

extension LinkedList {
    //remove(after:)에서 제대로 동작하지 않기 때문에 수정해 준다.
    private mutating func copyNodes(returningCopyOf node: Node<Value>?) -> Node<Value>? {
        guard !isKnownUniquelyReferenced(&head) else { //Optimizing COW
            //참조하고 있는 owner의 수를 확인해 최적화 해 준다.
            //하나의 list만 가지고 계속 작업하는 경우에는(LinkedList를 복사할 필요가 없는 경우)
            //이 guard에서 종료되므로, 복사가 일어나지 않아 오버헤드를 줄일 수 있다.
            return nil
        }
        
        guard var oldNode = head else {
            return nil
        }
        
        head = Node(value: oldNode.value)
        var newNode = head
        var nodeCopy: Node<Value>?
        
        while let nextOldNode = oldNode.next {
            if oldNode === node {
                nodeCopy = newNode
            }
            
            newNode!.next = Node(value: nextOldNode.value)
            newNode = newNode!.next
            oldNode = nextOldNode
        }
        
        return nodeCopy
    }
}

copyNodes(returningCopyOf:) 메서드는 복사된 Node를 반환한다. remove(after:) 메서드도 수정해 줘야 한다.

extension LinkedList {
    @discardableResult
    public mutating func remove(after node: Node<Value>) -> Value? {
        //COW 적용 이후, 제대로 동작하지 않는 점을 수정해 준다.
        guard let node = copyNodes(returningCopyOf: node) else { 
        //새로운 copyNodes(returningCopyOf:) 메서드를 사용한다.
            return nil
        }
        
        defer { //메서드에서 코드 흐름과 상관없이 가장 마지막에 defer 블록이 실행된다. //return 이후에 호출된다.
            //defer 블록에서 Node를 연결 해제해 준다.
            if node.next === tail { //tail를 제거하는 경우에는 tail 참조를 업데이트 해 줘야 한다.
                //메모리 주소를 비교 해야 한다.
                tail = node
            }
            node.next = node.next?.next
            //제거하려는 node 바로 앞의 node를 찾아 next 참조를 새로 업데이트 해 준다.
            //삭제하는 node(node의 이전 next)는 더 이상 참조가 없으므로 ARC가 제거한다.
        }
        
        return node.next?.value
    }
}

copyNodes() 대신, copyNodes(returningCopyOf:)를 사용해, 복사된 노드에서 remove(after:)를 사용하면, 원하는 대로 작동하게 된다.

 

Sharing nodes

오버헤드를 줄일 수 있는 두 번째 최적화 방법은 부분적으로 Node를 공유하는 것이다. 이 방법을 사용하면 복사본을 사용하지 않아도 되는 경우가 생긴다. 여기에서는 모든 경우를 확인하고 구현하기는 힘들지만, 몇 가지 경우를 구현하고, 어떤 방식으로 작동하는지 살펴본다.

var list1 = LinkedList<Int>()
(1...3).forEach{ list1.append($0) }
var list2 = list1

 

lsit1과 list2의 참조는 동일한 Node를 가리키고 있다. COW가 비활성화 된 상태에서, list2에 push를 수행한다.

list2.push(0)

 

list1이 list2의 push 연산에 영향을 받지 않아, list1과 list2는 서로 다른 참조를 가진다. 두 list 를 출력하면 다음과 같다.

List1: 1 -> 2 -> 3
List2: 0 -> 1 -> 2 -> 3

여기서 list1에 100을 push한다.

list1.push(100)

 

두 list를 출력하면 다음과 같다.

List1: 100 -> 1 -> 2 -> 3
List2: 0 -> 1 -> 2 -> 3

이와 같이 head-first insertion은 COW의 오버헤드에 영향 받지 않는다.

 

Key points

• 연결 리스트(Linked List)는 선형적(linear)이고 단방향적(unidirectional)이다. 한 노드에서 다른 노드로 참조를 이동하면 다시 돌아갈 수 없다.
• 연결 리스트의 head first insertion의 시간 복잡도는 O(1) 이다. 반면, 배열(Array)의 경우에는 O(n) 이다.
• Sequence와 Collection과 같은 Swift Collection protocol를 구현하면, 다양하고 유용한 메서드들을 사용할 수 있다.
• Copy-on-write을 사용해, value semantic을 구현할 수 있다.