[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터6-2. 연결리스트

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터6-2. 연결리스트  (스위프트 콜렉션 프로토콜, 밸류 시맨틱, COW(카피-온-라이트))

Raywenderlich.com 에서 나온 Data Structures & Algorithms in Swift 책의 데모 공개본을 번역하였습니다. 즐겁게 봐주세요. 

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

 

---

 

섹션 2. 기초 자료구조 Elementary Data Structure

챕터 6. 연결 리스트 Linked Lists 

스위프트 콜렉션 프로토콜 Swift collection protocols

스위프트 표준 라이브러리에 있는 프로토콜들은 특정 타입에 대해 예상되는 것을 정의하도록 도와줍니다. 이 프로토콜들은 특성 및 성능에 대해 보장을 제공합니다. 이 프로토콜 세트에서 콜렉션과 관계된 4가지 프로토콜에 초점을 맞출 것입니다.

각 프로토콜이 하는 일에 대해 간략히 요약하자면

• 1 계층(Tier 1), 시퀀스 (Sequence) : 시퀀스 타입은 요소에 순차적 접근을 제공합니다. 주의해야 될 중요한 부분이 있습니다. 순차적 접근은 요소들을 파괴적으로 소모하므로 다시 방문할 수 없습니다.
• 2 계층(Tier 2), 콜렉션(Collection) : 콜렉션 타입은 추가적인 보장이 제공되는 시퀀스 타입입니다. 콜렉션 타임은 유한하며, 반복적인 비파괴적 순차 접근을 허용합니다.
• 3 계층(Tier 3), 양방향 콜렉션(BidirectionalCollection) : 콜렉션 타입은, 이름에서 알 수 있듯이 시퀀스를 위아래 양방향으로 이동할 수 있는 양방향 콜렉션 타입이 될 수 있습니다. 연결리스트는 오직 head에서 tail 로만 이동할 수 있으므로 연결리스트에서는 불가능합니다.
• 4 계층(Tier 4), 랜덤 액세스 콜렉션(RandomAccessCollection) : 양방향 콜렉션은 특정 인덱스에 위치한 요소에 접근하는 것이 다른 인덱스에 위치한 요소에 접근하는 것만큼 걸린다는 것이 보장될 경우 랜덤 액세스 콜렉션 타입이 될 수 있습니다. 리스트 앞쪽에 가까운 노드에 접근하는 것이 리스트 뒷쪽에 있는 요소에 접근하는 것보다 훨씬 빠르기 때문에 연결리스트에서는 불가능합니다.

각각에 대해서는 더 많은 내용이 있습니다. 여러분은 각각의 적합성에 대해 작성하면서 이를 배워가게 될 것입니다.

연결리스트는 스위프트 콜렉션 프로토콜에서 두 가지 자격을 얻을 수 있습니다. 첫번째로, 연결리스트는 노드의 체인이므로 Sequence 프로토콜을 채택하는 것이 합리적이며 둘째로 노드의 체인은 유한한 시퀀스이므로 Collection 프로토콜을 채택하는 것이 합리적입니다.

 

 

스위프트 콜렉션 구현하기

이번 섹션에서 여러분은 Collection 프로토콜을 구현하는 것을 살펴보겠습니다. 콜렉션 타입은 유한한 시퀀스로 비파괴적인 순차 접근을 제공합니다. 스위프트의 Collection 은 인덱스를 컬렉션의 값에 매핑할 수 있는 멋진 용어, 첨자(subscript)를 통해 접근할 수 있습니다.

스위프트 배열에서 첨자를 사용한 예제입니다.

 

array[5]

배열의 인덱스는 Int 값입니다. 위 예제에서는 5가 그 값입니다. 첨자 연산은 [ 대괄호 ]로 정의되어 있습니다. 인덱스로 첨자를 이용하면 콜렉션의 값을 반환합니다.

 

커스텀 콜렉션 인덱스

Collection 프로토콜 메서드의 성능을 측정하는 항목은 Index 에 값을 매핑하는 속도입니다. Array 와 같은 다른 스토리지 옵션과 다르게 연결리스트는 정수 인덱스를 사용하여 O(1) 첨자 연산을 수행할 수 없습니다. 그러므로 여러분의 목표는 해당 노드에 대한 레퍼런스를 포함하는 커스텀 인덱스를 정의하는 것입니다.

 

LinkedList.swift 에 아래 extension 을 추가합니다.

 

extension LinkedList: Collection {

  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 }
    }
  }
}

Collection 요구사항을 만족하는 커스텀을 사용할 것입니다. 아래 내용을 extension 안에 넣어 완성하세요.

// 1
public var startIndex: Index {
  Index(node: head)
}
// 2
public var endIndex: Index {
  Index(node: tail?.next)
}
// 3
public func index(after i: Index) -> Index {
  Index(node: i.node?.next)
}
// 4
public subscript(position: Index) -> Value {
  position.node!.value
}

1. startIndex 는 연결리스트 head 에 의해 합리적으로 정의됩니다.
2. Collection 은  endIndex 를 마지막으로 접근가능한 값 다음 인덱스로 정의합니다. 그러므로 ail?.next 를 지정합니다.
3. index(after:) 는 인덱스를 증가시키는 방법을 나타냅니다. 단순히 다음노드의 인덱스를 지정하면 됩니다.
4. subscript 첨자는 콜렉션의 값을 Index 와 매핑시키기 위해 사용됩니다. 커스텀 인덱스를 생성했으므로 노드의 값을 참조하여 상수시간(constant time) 안에 쉽게 달성할 수 있습니다.

이제 Collection 을 채택하는 절차를 마칩니다. 플레이그라운드 페이지로 돌아가서 시운전을 해봅시다.

 

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

  print("List: \(list)")
  print("First element: \(list[list.startIndex])")
  print("Array containing first 3 elements: \(Array(list.prefix(3)))")
  print("Array containing last 3 elements: \(Array(list.suffix(3)))")

  let sum = list.reduce(0, +)
  print("Sum of all values: \(sum)")
}

아래 결과물을 볼 수 있습니다.

---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

 

스위프트 콜렉션의 또 다른 중요한 품질은 밸류 시맨틱을 가진다는 점입니다. 이는 카우(COW)라고 하는 카피-온-라이트를 사용하여 효율적으로 구현됩니다. 밸류 시맨틱의 개념을 알기 위해, 배열을 사용한 동작을 탐색할 것입니다.

 

아래 코드를 플레이그라운드 페이지 아래쪽에 작성합니다.

example(of: "array cow") {
  let array1 = [1, 2]
  var array2 = array1

  print("array1: \(array1)")
  print("array2: \(array2)")

  print("---After adding 3 to array 2---")
  array2.append(3)
  print("array1: \(array1)")
  print("array2: \(array2)")
}

아래 결과물을 볼 수 있습니다.

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

array2 가 수정될 때 array1 의 요소는 변하지 않습니다. 실제로는 array2 는 append 가 호출될 때 기본 저장소의 복사본을 만듭니다.

이제 연결리스트가 밸류 시맨틱을 가지고 있는지 확인합니다. 아래 내용을 플레이그라운드 페이지 아래에 작성합니다.

example(of: "linked list cow") {
  var list1 = LinkedList<Int>()
  list1.append(1)
  list1.append(2)
  var list2 = list1
  print("List1: \(list1)")
  print("List2: \(list2)")

  print("After appending 3 to list2")
  list2.append(3)
  print("List1: \(list1)")
  print("List2: \(list2)")
}

아래 결과물을 확인할 수 있습니다.

---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) 을 사용하고 있기 때문입니다. 이는 심각한 문제입니다. LinkedList 는 구조체이고 반드시 밸류 시맨틱을 사용해야되기 때문입니다. 카우(COW)를 구현하면 이 문제를 해결하게 됩니다.

 

카우(COW)를 사용하여 밸류 시맨틱을 달성하는 전략은 꽤나 단순합니다. 연결리스트의 콘텐츠를 복제하기 전에 기본저장소의 복사본을 수행하고 새로운 복사본에 모든 레퍼런스(head 와 tail)를 업데이트 하고자 합니다.

 

LinkedList.swift 에 아래 메서드를 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
}

 

이 메서드는 연결리스트의 기존 노드를 동일한 값을 가진 새로 할당된 것으로 교체합니다.

이제 mutating 키워드로 표시된 LinkedList 의 다른 모든 메서드를 찾고 모든 메서드의 상단에서 copyNodes 를 호출합니다.

총 6개의 메서드가 있습니다.

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

개조(retrofit)을 완료한 후 마지막 example 함수 호출은 아래 결과물을 보여주어야 합니다.

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

바로 여러분이 원한 것입니다. 아니면 모든 mutating 호출에 O(n) 오버헤드를 도입하거나요..

 

카우(COW) 최적화

모든 mutating 호출에 O(n) 오버헤드를 도입하는 것은 불가합니다. 두가지 전략이 이 문제를 완화하는 데 도움이 됩니다. 첫째는 노드가 한 명의 소유자만 있을 경우 복사를 방지하는 것입니다.

 

isKnownUniquelyReferenced

스위프트 표준 라이브러리에는 isKnownUniquelyReferenced 라는 이름의 함수가 있습니다. 이 함수는 오브젝트가 정확히 하나의 레퍼런스를 가지고 있는지 여부를 확인하는 데 사용됩니다. 링크드리스트 카우 예제에서 테스트하세요.

 

마지막 example 함수 호출에서  var list2 = list1 라고 작성한 부분에 아래 코드를 업데이트하세요.

 

print("List1 uniquely referenced: \(isKnownUniquelyReferenced(&list1.head))")
var list2 = list1
print("List1 uniquely referenced: \(isKnownUniquelyReferenced(&list1.head))")

 

콘솔에서 아래 두 줄이 보일 것입니다.

 

List1 uniquely referenced: true
List1 uniquely referenced: false

 

 isKnownUniquelyReferenced을 사용하여 기본 노드 객체가 공유된지 확인할 수 있습니다. 이 동작을 확인했으므로 두개의 print 구문을 삭제하세요. 길은 분명합니다. 아래의 조건문을 copyNodes 상단에 추가하세요.

 

guard !isKnownUniquelyReferenced(&head) else {
  return
}

카우(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)의 이점을 가진 채 이전의 성능을 회복하게 됩니다.

 

약간의 곤란 A minor predicament

아래 코드를 이전의 예제 코드 안에 추가하세요.

print("Removing middle node on list2")
if let node = list2.node(at: 0) {
  list2.remove(after: node)
}
print("List2: \(list2)")

콘솔에서 아래 결과물이 보여야합니다.

 

---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(after:) 구현은 잘못된 노드 세트에서 제거를 수행합니다. 이를 수정하기 위해서는 copyNodes 메서드의 특별한 버전을 작성해야 합니다. Sources 디렉토리에 작성한 LinkedList.swift 로 돌아가서 아래 내용을 copyNodes 메서드 아래에 작성합니다.

 

private mutating func copyNodes(returningCopyOf node: Node<Value>?) -> Node<Value>? {
  guard !isKnownUniquelyReferenced(&head) else {
    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
}

 

이 메서드는 이전에 구현한 것과 많은 유사성을 공유합니다. 주요 차이점은 전달된 파라미터를 기반으로 새롭게 복사된 노드를 반환한다는 것입니다. remove(after:) 메서드를 아래와 같이 업데이트합니다.

 

@discardableResult
public mutating func remove(after node: Node<Value>) -> Value? {
  guard let node = copyNodes(returningCopyOf: node) else { return nil }
  defer {
    if node.next === tail {
      tail = node
    }
    node.next = node.next?.next
  }
  return node.next?.value
}

 

이제 좀전에 만든 메서드를 사용하여 새로 복사한 노드에서 제거연산을 수행합니다.

 

노드 공유

두번째 최적화는 노드의 부분 공유입니다. 결과적으로 복사를 피할 수 있는 특정 시나리오가 있습니다. 모든 시나리에 대한 포괄적인 평가는 책의 범위를 벗어나지만 관련된 내용에 대한 아이디어를 여러분에게 제공할 것입니다.

아래 예제를 살펴보세요. (따라서 작성할 필요는 없습니다.)

 

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

 

카우(COW)가 비활성화된 상태에서 list2 에서 푸시 연산을 수행한 결과를 고려해보세요.

 

list2.push(0)

 

 

list1 이 list2 에서 수행된 push 연산에 영향을 받을까요? 이 경우에는 아닙니다. 

두 리스트를 출력하면 아래 결과물을 보게 될 것입니다.

 

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

 

list1에  100을 푸시하는 이 경우도 안전합니다.

 

list1.push(100)

 

 

 

지금 두 리스트를 인쇄하면 아래 결과를 볼 수 있습니다.

 

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

 

연결리스트의 일방향적인 특성은 head-first 삽입이 “카우(COW)의 부담(tax)“을 무시할 수 있음을 의미합니다.

 

핵심요약 Key points

• 연결리스트는 선형적이고 일방향적입니다. 레퍼런스를 이동하는 즉시 뒤로 돌아갈 수 없습니다.
• 연결리스트는 head-first 삽입의 경우 O(1) 시간복잡도를 가집니다. 배열의 경우 O(n) 시간복잡도를 가집니다.
• Sequence 와 Collection 과 같은 스위프트 콜렉션 프로토콜을 준수하면 자동적으로 많은 유용한 메서드에 접근할 수 있습니다.
• 카피-온-라이트는 좋은 성능을 유지하면서 밸류 시맨틱을 달성하도록 합니다.

 

---

🔗 번역 시리즈 링크

0️⃣ 섹션 0. 시작하기전에

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 0. 시작하기 전에

1️⃣ 섹션 1. 소개 Introduction

> 챕터 1.왜 자료구조와 알고리즘을 배워야할까요? / 챕터 2. 복잡도  Complexity

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 1. 소개 - 챕터1. 왜 자료구조와 알고리즘을

> 챕터3. 스위프트 표준 라이브러리 Swift Standard Library

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 1. 소개 - 챕터3. 스위프트 표준 라이브러리 S

 

1️⃣ 섹션 2. 기초 자료구조 Elementary Data Structure

> 챕터 4. 스택 Stacks /  챕터 5. 스택 도전과제 Stack Challenges

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터4~5. 스택, 스택 도전

> 챕터 6-1. 연결리스트 Linked List (연결리스트 정의, 요소 추가, 삭제)

 

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터6-1. 연결리스트 (정

> 챕터 6-2. 연결리스트 Linked List (스위프트 표준 라이브러리의 콜렉션 프로토콜, 카우 Copy-On-Write,  밸류 시맨틱)

 

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터6-2. 연결리스트

 

> 챕터 7. 연결리스트 도전과제 Linked List Challenges

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터7. 연결리스트 도전

 

---

마치며 

 

오늘도 읽어주셔서 감사합니다.

 

궁금한 점이 있다면 댓글로, 도움이 되셨다면 공감 부탁드립니다.

혹시 수정하거나 피드백하실  내용 있다면 언제든 댓글로 부탁드립니다.

 

감사합니다.