前言

有需要的同學可以訂閱專欄：Swift數(shù)據(jù)結(jié)構(gòu)和算法專題
代碼地址：Swift數(shù)據(jù)結(jié)構(gòu)和算法代碼

正文

鏈表是以線性、單向順序排列的值的集合。與 Swift Array 等連續(xù)存儲選項相比，鏈表具有一些理論上的優(yōu)勢：

? 從列表前面插入和刪除的時間是固定的的。

? 可靠的性能特征。

一個單鏈表

如圖所示，鏈表是一個節(jié)點鏈。節(jié)點有兩個職責：

1. 持有價值。

2. 持有對下一個節(jié)點的引用。 nil 值表示列表的結(jié)尾。

一個值為12的節(jié)點

打開本章的starter playground，開始擼代碼！

！節(jié)點

在 Sources 目錄中創(chuàng)建一個新的 Swift 文件并將其命名為 Node.swift。將以下內(nèi)容添加到文件中：

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 { 
      return "\(value)" 
      } 
      return "\(value) -> " + String(describing: next) + " " 
    }
}

導航到 Playground 頁面并添加以下內(nèi)容：

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

我們剛剛創(chuàng)建了三個節(jié)點并將它們連接起來：

包含值 1、2 和 3 的鏈表

在控制臺中，我們應(yīng)該看到以下輸出：

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

就實用性而言，當前構(gòu)建列表的方法還有很多不足之處。我們可以很容易地看到以這種方式構(gòu)建長列表是不切實際的。緩解此問題的常用方法是構(gòu)建一個管理 Node 對象的 LinkedList。

鏈表

在 Sources 目錄中創(chuàng)建一個新文件并將其命名為 LinkedList.swift。將以下內(nèi)容添加到文件中：

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

鏈表有頭尾的概念，分別指鏈表的第一個和最后一個節(jié)點：

頭節(jié)點和尾節(jié)點

將值添加到列表

如前所述，我們將提供一個接口來管理 Node 對象。我們將首先處理添加值。向鏈表添加值的方法有三種，每種方法都具有獨特的性能特征：

1. push：在列表的前面添加一個值。

2. append：在列表末尾添加一個值。

3. insert(after:)：在特定列表節(jié)點之后添加一個值。

我們將在后面實現(xiàn)其中的每一個并分析它們的性能特征。

push操作

在列表的前面添加一個值稱為push操作。這也稱為頭先插入。它的代碼非常簡單。

將以下方法添加到 LinkedList：

public mutating func push(_ value: Value) { 
  head = Node(value: value, next: head) 
  if tail == nil { 
    tail = head 
  } 
}

如果我們要推入一個空列表，則新節(jié)點既是列表的頭部也是尾部。

在 Playground頁面中，添加以下內(nèi)容：

example(of: "push") {

  var list = LinkedList<Int>()

  list.push(3) 
  list.push(2) 
  list.push(1)
 
 print(list)
}

控制臺輸出應(yīng)顯示如下：

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

append操作

下一個操作是append。這會在列表末尾添加一個值，稱為尾端插入。

在 LinkedList.swift 中，在 push下方添加以下代碼：

public mutating func append(_ value: Value) {

  // 1 
  guard !isEmpty else {
    push(value)
    return 
  }

  // 2 
  tail!.next = Node(value: value)

  // 3 
  tail = tail!.next
}

這段代碼比較簡單：

1. 和之前一樣，如果列表為空，則需要將 head和tail都更新為新節(jié)點。由于在空列表上追加在功能上與push相同，因此調(diào)用puah來完成工作。

2. 在所有其他情況下，我們在尾節(jié)點之后創(chuàng)建一個新節(jié)點。由于使用上述guard !isEmpty，因此可以保證強制解包成功。

3. 由于這是尾端插入，因此新節(jié)點也是列表的尾部。跳回操場并在底部寫下以下內(nèi)容：

example(of: "append") {

var list = LinkedList<Int>()

list.append(1)
list.append(2) 
list.append(3)

print(list)
}

我們將會在控制臺看到如下的輸出結(jié)果：

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

insert(after:)操作

添加值的第三個也是最后一個操作是 insert(after:)。此操作在列表中的特定位置插入一個值，需要兩個步驟：

1. 在列表中查找特定節(jié)點。

2. 插入新節(jié)點。

首先，我們需要將實現(xiàn)代碼以查找要插入值的節(jié)點。

在 LinkedList.swift 中，在 append的正下方添加以下代碼：

public func node(at index: Int) -> Node<Value>? { 
  // 1 
  var currentNode = head 
  var currentIndex = 0
  // 2 
 while currentNode != nil && currentIndex < index {
    currentNode = currentNode!.next
    currentIndex += 1 
 }
 return currentNode
}

node(at:) 將嘗試根據(jù)給定索引檢索列表中的節(jié)點。由于我們只能從頭節(jié)點訪問列表的節(jié)點，因此必須進行迭代遍歷。下面是具體操作方式：

1. 創(chuàng)建一個新的 head 引用并跟蹤當前的遍歷次數(shù)。

2. 使用 while 循環(huán)，將引用向下移動到列表中，直到到達所需的索引。空列表或越界索引將導致 nil 返回值。

現(xiàn)在我們需要插入新節(jié)點。

在 node(at:) 正下方添加以下方法：

// 1 
@discardableResult 
public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> { 
  // 2 
  guard tail !== node else {
    append(value)
    return tail!
  } 
  // 3 
  node.next = Node(value: value, next: node.next) 
  return node.next!
}

解析一下上述代碼：

1. @discardableResult讓調(diào)用者忽略此方法的返回值，而編譯器不會跳來跳去警告你。

2. 如果這個方法與尾節(jié)點一起調(diào)用，我們將調(diào)用功能等效的 append方法。這將負責更新尾部。

3. 否則，我們只需將新節(jié)點與列表的其余部分連接起來并返回新節(jié)點。

跳回操場頁面進行測試。將以下內(nèi)容添加到playground底部：

example(of: "inserting at a particular index") {

  var list = LinkedList<Int>()
  list.push(3) list.push(2) list.push(1)

  print("Before inserting: \(list)") 
  var middleNode = list.node(at: 1)!
  for _ in 1...4 { 
    middleNode = list.insert(-1, after: middleNode) 
  } 
  print("After inserting: \(list)")
}

執(zhí)行代碼，我們將會在控制臺看到如下輸出結(jié)果：

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

性能分析

我們已經(jīng)實現(xiàn)了將值添加到鏈表的三個操作以及在特定索引處查找節(jié)點的方法。

接下來，我們將專注于相反的操作：移除操作。

從鏈表中刪除Value

刪除節(jié)點主要有以下三種操作：

1. pop：移除列表最前面的值。

2. removeLast：刪除列表末尾的值。

3. remove(at:)：刪除列表中任意位置的值。

我們接下來將實現(xiàn)這三個并分析它們的性能特征。

pop操作

刪除列表前面的值通常稱為 pop。這個操作幾乎和 push 一樣簡單，所以直接進入主題。

將以下方法添加到 LinkedList：

@discardableResult 
public mutating func pop() -> Value? { 
  defer { 
    head = head?.next 
    if isEmpty { 
      tail = nil 
    } 
  } 
  return head?.value 
}

pop 返回從列表中刪除的值。此值是可選的，因為列表可能為空。

通過將頭部向下移動一個節(jié)點，我們已經(jīng)有效地刪除了列表的第一個節(jié)點。一旦方法完成，ARC 將從內(nèi)存中刪除舊節(jié)點，因為不再有引用附加到它。如果列表為空，則將 tail 設(shè)置為 nil?；氐?code>playground頁面并通過在底部添加以下代碼來測試它：

example(of: "pop") {
  var list = LinkedList<Int>()
  list.push(3) 
  list.push(2) 
  list.push(1)

  print("Before popping list: \(list)")
  let poppedValue = list.pop() 
  print("After popping list: \(list)") 
  print("Popped value: " + String(describing: poppedValue))
}

我們將會看到如下輸出結(jié)果：

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

removeLast 操作

刪除列表的最后一個節(jié)點有點不方便。盡管我們有對尾節(jié)點的引用，但如果沒有對它之前的節(jié)點的引用，我們就無法將其刪除。因此，我們將不得不進行艱苦的遍歷。在 pop 下方添加以下代碼：

@discardableResult 
public mutating func removeLast() -> Value? { 
  // 1 
  guard let head = head else { 
    return nil 
  } 
  // 2 
  guard head.next != nil else { 
    return pop() 
  } 
  // 3 
  var prev = head 
  var current = head

  while let next = current.next { 
   prev = current 
    current = next 
  } 
  // 4 
  prev.next = nil 
  tail = prev 
  return current.value
}

以下是代碼中發(fā)生的事情：

1. 如果 head 為 nil，則沒有要刪除的內(nèi)容，因此返回 nil。

2.如果列表只包含一個節(jié)點，removeLast在功能上等同于pop。由于 pop 將處理更新 head和 tail 引用，因此我們只需將這項工作委托給它。

3. 我們一直在尋找下一個節(jié)點，直到 current.next 為 nil。這表示 current 是列表的最后一個節(jié)點。

4. 由于 current是最后一個節(jié)點，我們只需使用 prev.next 引用斷開它。我們還要確保更新尾部引用。

回到playground頁面并在底部添加以下內(nèi)容：

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)") 
  let removedValue = list.removeLast()

  print("After removing last node: \(list)") 
  print("Removed value: " + String(describing: removedValue))
}

在控制臺底部，我們會看到如下的輸出結(jié)果：

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

removeLast要求我們一直遍歷列表。這使得 O(n) 操作相對低效。

remove(after:)操作

最后的刪除操作是刪除列表中特定點的特定節(jié)點。這很像 insert(after:);我們將首先找到要刪除的節(jié)點之前的節(jié)點，然后取消鏈接。

刪除中間的節(jié)點

回到LinkedList.swift文件，并且在removeLast后面添加如下代碼：

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

節(jié)點的取消鏈接發(fā)生在延遲塊中。如果刪除的節(jié)點是尾節(jié)點，則需要特別注意，因為尾引用必須更新。

回到playground添加如下測試代碼：

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)") 
  let index = 1 
  let node = list.node(at: index - 1)!
  let removedValue = list.remove(after: node)

 print("After removing at index \(index): \(list)") 
 print("Removed value: " + String(describing: removedValue))
}

我們會在控制臺看到如下輸出結(jié)果：

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

嘗試添加更多元素并使用 index 的值。與 insert(at:)類似，此操作的時間復(fù)雜度為 O(1)，但它需要我們事先對特定節(jié)點進行引用。

性能分析

我們已經(jīng)到達另一個檢查站！回顧一下，我們已經(jīng)實現(xiàn)了從鏈表中刪除值的三個操作：

至此，我們已經(jīng)為世界上大多數(shù)程序員都可以關(guān)聯(lián)的鏈表定義了一個接口。但是，要修飾 Swift語義還有很多工作要做。后面會有更詳細地講解。

Swift collection 協(xié)議

Swift 標準庫有一組協(xié)議來幫助定義對特定類型的期望。這些協(xié)議中的每一個都為特性和性能提供了一定的保證。從這組協(xié)議中，我們將專注于四個與集合相關(guān)的協(xié)議。

以下是每個協(xié)議功能的快速摘要：

• 第 1 層，Sequence：序列類型提供對其元素的順序訪問。它帶有一個重要的警告：使用順序訪問可能會破壞性地消耗元素，因此我們無法重新訪問它們。

• 第2 層，Collection：集合類型是提供額外保證的序列類型。集合類型是有限的，允許重復(fù)的非破壞性順序訪問。

• 第 3 層，BidirectionalColllection：集合類型可以是雙向集合類型，如果顧名思義，它可以允許在序列中上下雙向移動。這對于鏈表是不可能的，因為我們只能從頭到尾，反之則不行。

• 第 4 層，RandomAccessCollection：雙向集合類型可以是隨機訪問集合類型，如果它可以保證訪問特定索引處的元素所花費的時間與訪問任何其他索引處的元素所花費的時間一樣長。這對于鏈表來說是不可能的，因為訪問靠近鏈表前面的節(jié)點比訪問鏈表后面的節(jié)點要快得多。

對于這些，還有更多要說的。當我們?yōu)樗鼈兙帉懸恢滦詴r，我們將了解更多關(guān)于它們的信息。

一個鏈表可以得到 Swift collection協(xié)議中的兩個限定條件。首先，由于鏈表是一個節(jié)點鏈，因此采用 Sequence協(xié)議是有意義的。其次，由于節(jié)點鏈是一個有限序列，因此采用 Collection 協(xié)議是有意義的。

成為一個 Swift collection

在本節(jié)中， 我們將研究實現(xiàn) Collection 協(xié)議。Collection 類型是有限序列并提供非破壞性順序訪問。 Swift 集合還允許通過下標進行訪問，這是一個花哨的術(shù)語，表示索引可以映射到集合中的值。

下面是一個使用 Swift 數(shù)組下標的例子：

array[5]

數(shù)組的索引是一個 Int 值——本例中的值為 5。下標操作用方括號定義。使用帶有索引的下標將從集合中返回一個值。

自定義collection索引

Collection協(xié)議方法性能的定義指標是將索引映射到值的速度。與 Swift Array等其他存儲選項不同，鏈表無法使用整數(shù)索引實現(xiàn) O(1) 下標操作。因此，我們的目標是定義一個自定義索引，其中包含對其各自節(jié)點的引用。

在LinkedList.swift中，添加以下擴展：

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要求。在擴展中寫入以下內(nèi)容以完成它：

// 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 由鏈表的頭部合理定義。

2. Collection 將 endIndex 定義為最后一個可訪問值之后的索引，所以你給它 tail?.next。

3. index(after:)指示如何增加索引。我們只需為其提供下一個節(jié)點的索引。

4.下標用于將Index映射到集合中的值。由于我們已經(jīng)創(chuàng)建了自定義索引，因此我們可以通過引用節(jié)點的值輕松地在恒定時間內(nèi)實現(xiàn)此目的。

以上就是采用Collection的程序。導航回 Playground頁面并繼續(xù)：

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

值語義和寫時復(fù)制

Swift 集合的另一個重要品質(zhì)是它具有值語義。這是使用寫時復(fù)制有效地實現(xiàn)的，在此稱為 COW。為了說明值語義的概念，我們將使用數(shù)組來探索行為。

在 Playground 頁面的底部寫下以下內(nèi)容：

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

我們會看到如下的輸出結(jié)果：

---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 在調(diào)用 append 時會復(fù)制底層存儲：

現(xiàn)在，檢查我們的鏈表是否具有值語義。在 Playground頁面的底部寫下以下內(nèi)容：

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

我們將會看到如下的輸出結(jié)果：

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

不幸的是，我們的鏈表沒有值語義！這是因為我們的底層存儲使用引用類型（節(jié)點）。這是一個嚴重的問題，因為 LinkedList是一個結(jié)構(gòu)并且應(yīng)該使用值語義。實施 COW 將解決此問題。

使用 COW實現(xiàn)價值語義的策略相當簡單。在改變鏈表的內(nèi)容之前，我們想要執(zhí)行底層存儲的副本并將所有引用（頭和尾）更新到新副本。

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

此方法將用新分配的具有相同值的節(jié)點替換鏈表的現(xiàn)有節(jié)點。

現(xiàn)在找到 LinkedList 中標有 mutating 關(guān)鍵字的所有其他方法，并在每個方法的頂部調(diào)用 copyNodes。

總共有六種方法：

• push

• append

• insert(after:)

• pop

• removeLast

• remove(after:)

完成改造后，最后一個示例函數(shù)調(diào)用應(yīng)產(chǎn)生以下輸出：

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

這就是你想要的！好吧，除了在每個mutating調(diào)用中引入 O(n) 開銷......

優(yōu)化COW

每次變異調(diào)用的 O(n) 開銷是不可接受的。兩種策略有助于緩解這個問題。第一個是當節(jié)點只有一個所有者時避免復(fù)制。

isKnownUniquelyReferenced

在 Swift 標準庫中有一個名為 isKnownUniquelyReferenced的函數(shù)。此函數(shù)可用于確定對象是否只有一個對其的引用。在鏈表 COW 示例中對此進行測試。

在最后一個示例函數(shù)調(diào)用中，找到我們編寫 var list2 = list1 的行并將其更新為以下內(nèi)容：

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

結(jié)果如下：

List1 uniquely referenced: true 
List1 uniquely referenced: false

使用 isKnownUniquelyReferenced 可以檢查底層節(jié)點對象是否共享！在 copyNodes 的頂部添加以下條件：

guard !isKnownUniquelyReferenced(&head) else { 
  return 
}

現(xiàn)在可以發(fā)現(xiàn)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的優(yōu)勢恢復(fù)其先前的性能。

一個小困境

在之前的示例代碼中添加以下代碼：

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 優(yōu)化。因為每個突變都可以觸發(fā)節(jié)點的副本，所以 remove(after:) 實現(xiàn)是在錯誤的節(jié)點集上進行刪除。為了解決這個問題，我們將編寫一個專門版本的 copyNodes 方法。返回到 Sources目錄中的 LinkedList.swift并在 copyNodes 方法下方編寫以下內(nèi)容：

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
}

此方法與之前的實現(xiàn)有許多相似之處。主要區(qū)別在于它將根據(jù)傳入的參數(shù)返回新復(fù)制的節(jié)點。將 remove(after:)方法更新為以下內(nèi)容：

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

我們現(xiàn)在正在使用剛剛創(chuàng)建的方法并在新復(fù)制的節(jié)點上執(zhí)行刪除。

共享節(jié)點

第二個優(yōu)化是節(jié)點的部分共享。事實證明，在某些情況下我們可以避免復(fù)制。對所有場景的全面評估超出了本書的范圍，但這會讓你對所涉及的內(nèi)容有所了解。

看下面的例子（這個不用寫了）：

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

共享節(jié)點

現(xiàn)在考慮在禁用cow的情況下對 list2 執(zhí)行push操作的后果：

list2.push(0)

list1 是否受 list2 上的推送操作影響？在這種情況下不是！如果要打印這兩個列表，我們將獲得以下輸出：

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

在這種情況下，將 100 推送到 list1 的結(jié)果也是安全的：

list1.push(100)

如果我們現(xiàn)在要打印這兩個列表，將得到以下輸出：

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

鏈表的單向性意味著頭先插入可以忽略“COW ”！

關(guān)鍵點

• 鏈表是線性的和單向的。一旦將引用從一個節(jié)點移動到另一個節(jié)點，就無法返回。

• 鏈表的頭部優(yōu)先插入的時間復(fù)雜度為 O(1)。數(shù)組對于頭先插入具有 O(n) 時間復(fù)雜度。

• 遵循 Swift collection協(xié)議（如 Sequence 和 Collection）會自動讓我們訪問許多有用的方法。

• Copy-on-write 行為使我們能夠在保持良好性能的同時實現(xiàn)值語義。