前言

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

正文

鏈表是以線性讶迁、單向順序排列的值的集合治唤。與 Swift Array 等連續(xù)存儲(chǔ)選項(xiàng)相比岗照，鏈表具有一些理論上的優(yōu)勢(shì)：

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

? 可靠的性能特征。

一個(gè)單鏈表

如圖所示尺迂，鏈表是一個(gè)節(jié)點(diǎn)鏈具温。節(jié)點(diǎn)有兩個(gè)職責(zé)：

1. 持有價(jià)值。

2. 持有對(duì)下一個(gè)節(jié)點(diǎn)的引用癞揉。 nil 值表示列表的結(jié)尾纸肉。

一個(gè)值為12的節(jié)點(diǎn)

打開(kāi)本章的starter playground预吆，開(kāi)始擼代碼！

胳泉！節(jié)點(diǎn)

在 Sources 目錄中創(chuàng)建一個(gè)新的 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) + " " 
    }
}

導(dǎo)航到 Playground 頁(yè)面并添加以下內(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)建了三個(gè)節(jié)點(diǎn)并將它們連接起來(lái)：

包含值 1岩遗、2 和 3 的鏈表

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

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

就實(shí)用性而言凤瘦，當(dāng)前構(gòu)建列表的方法還有很多不足之處宿礁。我們可以很容易地看到以這種方式構(gòu)建長(zhǎng)列表是不切實(shí)際的。緩解此問(wèn)題的常用方法是構(gòu)建一個(gè)管理 Node 對(duì)象的 LinkedList蔬芥。

鏈表

在 Sources 目錄中創(chuàng)建一個(gè)新文件并將其命名為 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) 
  } 
}

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

頭節(jié)點(diǎn)和尾節(jié)點(diǎn)

將值添加到列表

如前所述笔诵，我們將提供一個(gè)接口來(lái)管理 Node 對(duì)象返吻。我們將首先處理添加值。向鏈表添加值的方法有三種乎婿，每種方法都具有獨(dú)特的性能特征：

1. push：在列表的前面添加一個(gè)值测僵。

2. append：在列表末尾添加一個(gè)值。

3. insert(after:)：在特定列表節(jié)點(diǎn)之后添加一個(gè)值谢翎。

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

push操作

在列表的前面添加一個(gè)值稱為push操作。這也稱為頭先插入森逮。它的代碼非常簡(jiǎn)單榨婆。

將以下方法添加到 LinkedList：

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

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

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

example(of: "push") {

  var list = LinkedList<Int>()

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

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

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

append操作

下一個(gè)操作是append。這會(huì)在列表末尾添加一個(gè)值闷供，稱為尾端插入烟央。

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

這段代碼比較簡(jiǎn)單：

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

2. 在所有其他情況下，我們?cè)谖补?jié)點(diǎn)之后創(chuàng)建一個(gè)新節(jié)點(diǎn)移怯。由于使用上述guard !isEmpty香璃，因此可以保證強(qiáng)制解包成功。

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

example(of: "append") {

var list = LinkedList<Int>()

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

print(list)
}

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

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

insert(after:)操作

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

1. 在列表中查找特定節(jié)點(diǎn)眯牧。

2. 插入新節(jié)點(diǎn)蹋岩。

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

在 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é)點(diǎn)。由于我們只能從頭節(jié)點(diǎn)訪問(wèn)列表的節(jié)點(diǎn)版确，因此必須進(jìn)行迭代遍歷扣囊。下面是具體操作方式：

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

2. 使用 while 循環(huán)绒疗，將引用向下移動(dòng)到列表中侵歇，直到到達(dá)所需的索引∠拍ⅲ空列表或越界索引將導(dǎo)致 nil 返回值惕虑。

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

在 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)用者忽略此方法的返回值士修，而編譯器不會(huì)跳來(lái)跳去警告你枷遂。

2. 如果這個(gè)方法與尾節(jié)點(diǎn)一起調(diào)用樱衷，我們將調(diào)用功能等效的 append方法棋嘲。這將負(fù)責(zé)更新尾部。

3. 否則矩桂，我們只需將新節(jié)點(diǎn)與列表的其余部分連接起來(lái)并返回新節(jié)點(diǎn)傻铣。

跳回操場(chǎng)頁(yè)面進(jìn)行測(cè)試锭环。將以下內(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í)行代碼，我們將會(huì)在控制臺(tái)看到如下輸出結(jié)果：

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

性能分析

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

接下來(lái)己沛，我們將專注于相反的操作：移除操作。

從鏈表中刪除Value

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

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

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

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

我們接下來(lái)將實(shí)現(xiàn)這三個(gè)并分析它們的性能特征桦山。

pop操作

刪除列表前面的值通常稱為 pop攒射。這個(gè)操作幾乎和 push 一樣簡(jiǎn)單，所以直接進(jìn)入主題恒水。

將以下方法添加到 LinkedList：

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

pop 返回從列表中刪除的值会放。此值是可選的，因?yàn)榱斜砜赡転榭铡?/p>

通過(guò)將頭部向下移動(dòng)一個(gè)節(jié)點(diǎn)钉凌，我們已經(jīng)有效地刪除了列表的第一個(gè)節(jié)點(diǎn)咧最。一旦方法完成，ARC 將從內(nèi)存中刪除舊節(jié)點(diǎn)，因?yàn)椴辉儆幸酶郊拥剿秆亍Ｈ绻斜頌榭绽拇睿瑒t將 tail 設(shè)置為 nil〉肪ǎ回到playground頁(yè)面并通過(guò)在底部添加以下代碼來(lái)測(cè)試它：

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

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

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

removeLast 操作

刪除列表的最后一個(gè)節(jié)點(diǎn)有點(diǎn)不方便论熙。盡管我們有對(duì)尾節(jié)點(diǎn)的引用，但如果沒(méi)有對(duì)它之前的節(jié)點(diǎn)的引用摄狱，我們就無(wú)法將其刪除脓诡。因此，我們將不得不進(jìn)行艱苦的遍歷媒役。在 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祝谚，則沒(méi)有要?jiǎng)h除的內(nèi)容，因此返回 nil酣衷。

2.如果列表只包含一個(gè)節(jié)點(diǎn)交惯，removeLast在功能上等同于pop。由于 pop 將處理更新 head和 tail 引用穿仪，因此我們只需將這項(xiàng)工作委托給它席爽。

3. 我們一直在尋找下一個(gè)節(jié)點(diǎn)，直到 current.next 為 nil啊片。這表示 current 是列表的最后一個(gè)節(jié)點(diǎn)只锻。

4. 由于 current是最后一個(gè)節(jié)點(diǎn)，我們只需使用 prev.next 引用斷開(kāi)它紫谷。我們還要確保更新尾部引用齐饮。

回到playground頁(yè)面并在底部添加以下內(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))
}

在控制臺(tái)底部，我們會(huì)看到如下的輸出結(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) 操作相對(duì)低效祖驱。

remove(after:)操作

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

刪除中間的節(jié)點(diǎn)

回到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é)點(diǎn)的取消鏈接發(fā)生在延遲塊中崇裁。如果刪除的節(jié)點(diǎn)是尾節(jié)點(diǎn)匕坯，則需要特別注意，因?yàn)槲惨帽仨毟隆?/p>

回到playground添加如下測(cè)試代碼：

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

我們會(huì)在控制臺(tái)看到如下輸出結(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:)類似醒颖，此操作的時(shí)間復(fù)雜度為 O(1)，但它需要我們事先對(duì)特定節(jié)點(diǎn)進(jìn)行引用壳炎。

性能分析

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

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

Swift collection 協(xié)議

Swift 標(biāo)準(zhǔn)庫(kù)有一組協(xié)議來(lái)幫助定義對(duì)特定類型的期望晰赞。這些協(xié)議中的每一個(gè)都為特性和性能提供了一定的保證。從這組協(xié)議中选侨，我們將專注于四個(gè)與集合相關(guān)的協(xié)議掖鱼。

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

• 第 1 層，Sequence：序列類型提供對(duì)其元素的順序訪問(wèn)援制。它帶有一個(gè)重要的警告：使用順序訪問(wèn)可能會(huì)破壞性地消耗元素戏挡，因此我們無(wú)法重新訪問(wèn)它們。

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

• 第 3 層妥凳，BidirectionalColllection：集合類型可以是雙向集合類型，如果顧名思義答捕，它可以允許在序列中上下雙向移動(dòng)逝钥。這對(duì)于鏈表是不可能的，因?yàn)槲覀冎荒軓念^到尾噪珊，反之則不行晌缘。

• 第 4 層齐莲，RandomAccessCollection：雙向集合類型可以是隨機(jī)訪問(wèn)集合類型痢站，如果它可以保證訪問(wèn)特定索引處的元素所花費(fèi)的時(shí)間與訪問(wèn)任何其他索引處的元素所花費(fèi)的時(shí)間一樣長(zhǎng)。這對(duì)于鏈表來(lái)說(shuō)是不可能的选酗，因?yàn)樵L問(wèn)靠近鏈表前面的節(jié)點(diǎn)比訪問(wèn)鏈表后面的節(jié)點(diǎn)要快得多阵难。

對(duì)于這些，還有更多要說(shuō)的芒填。當(dāng)我們?yōu)樗鼈兙帉?xiě)一致性時(shí)呜叫，我們將了解更多關(guān)于它們的信息。

一個(gè)鏈表可以得到 Swift collection協(xié)議中的兩個(gè)限定條件殿衰。首先朱庆，由于鏈表是一個(gè)節(jié)點(diǎn)鏈，因此采用 Sequence協(xié)議是有意義的闷祥。其次娱颊，由于節(jié)點(diǎn)鏈?zhǔn)且粋€(gè)有限序列，因此采用 Collection 協(xié)議是有意義的。

成為一個(gè) Swift collection

在本節(jié)中箱硕， 我們將研究實(shí)現(xiàn) Collection 協(xié)議拴竹。Collection 類型是有限序列并提供非破壞性順序訪問(wèn)。 Swift 集合還允許通過(guò)下標(biāo)進(jìn)行訪問(wèn)剧罩，這是一個(gè)花哨的術(shù)語(yǔ)栓拜，表示索引可以映射到集合中的值。

下面是一個(gè)使用 Swift 數(shù)組下標(biāo)的例子：

array[5]

數(shù)組的索引是一個(gè) Int 值——本例中的值為 5惠昔。下標(biāo)操作用方括號(hào)定義幕与。使用帶有索引的下標(biāo)將從集合中返回一個(gè)值。

自定義collection索引

Collection協(xié)議方法性能的定義指標(biāo)是將索引映射到值的速度镇防。與 Swift Array等其他存儲(chǔ)選項(xiàng)不同纽门，鏈表無(wú)法使用整數(shù)索引實(shí)現(xiàn) O(1) 下標(biāo)操作。因此营罢，我們的目標(biāo)是定義一個(gè)自定義索引赏陵，其中包含對(duì)其各自節(jié)點(diǎn)的引用。

在LinkedList.swift中饲漾，添加以下擴(kuò)展：

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

我們將使用此自定義索引來(lái)滿足 Collection要求蝙搔。在擴(kuò)展中寫(xiě)入以下內(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 定義為最后一個(gè)可訪問(wèn)值之后的索引考传，所以你給它 tail?.next吃型。

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

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

以上就是采用Collection的程序赐写。導(dǎo)航回 Playground頁(yè)面并繼續(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)")
}

我們會(huì)在控制臺(tái)看到下面的輸出：

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

值語(yǔ)義和寫(xiě)時(shí)復(fù)制

Swift 集合的另一個(gè)重要品質(zhì)是它具有值語(yǔ)義。這是使用寫(xiě)時(shí)復(fù)制有效地實(shí)現(xiàn)的膜赃，在此稱為 COW挺邀。為了說(shuō)明值語(yǔ)義的概念，我們將使用數(shù)組來(lái)探索行為跳座。

在 Playground 頁(yè)面的底部寫(xiě)下以下內(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)")
}

我們會(huì)看到如下的輸出結(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 時(shí)端铛，array1 的元素不變。在底層疲眷，array2 在調(diào)用 append 時(shí)會(huì)復(fù)制底層存儲(chǔ)：

現(xiàn)在禾蚕，檢查我們的鏈表是否具有值語(yǔ)義。在 Playground頁(yè)面的底部寫(xiě)下以下內(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)")
}

我們將會(huì)看到如下的輸出結(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

不幸的是狂丝，我們的鏈表沒(méi)有值語(yǔ)義换淆！這是因?yàn)槲覀兊牡讓哟鎯?chǔ)使用引用類型（節(jié)點(diǎn)）虚倒。這是一個(gè)嚴(yán)重的問(wèn)題，因?yàn)?LinkedList是一個(gè)結(jié)構(gòu)并且應(yīng)該使用值語(yǔ)義产舞。實(shí)施 COW 將解決此問(wèn)題魂奥。

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

在 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é)點(diǎn)替換鏈表的現(xiàn)有節(jié)點(diǎn)准颓。

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

總共有六種方法：

• push

• append

• insert(after:)

• pop

• removeLast

• remove(after:)

完成改造后攘已，最后一個(gè)示例函數(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

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

優(yōu)化COW

每次變異調(diào)用的 O(n) 開(kāi)銷是不可接受的样勃。兩種策略有助于緩解這個(gè)問(wèn)題吠勘。第一個(gè)是當(dāng)節(jié)點(diǎn)只有一個(gè)所有者時(shí)避免復(fù)制。

isKnownUniquelyReferenced

在 Swift 標(biāo)準(zhǔn)庫(kù)中有一個(gè)名為 isKnownUniquelyReferenced的函數(shù)峡眶。此函數(shù)可用于確定對(duì)象是否只有一個(gè)對(duì)其的引用剧防。在鏈表 COW 示例中對(duì)此進(jìn)行測(cè)試。

在最后一個(gè)示例函數(shù)調(diào)用中辫樱，找到我們編寫(xiě) 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é)點(diǎn)對(duì)象是否共享峭拘！在 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

通過(guò)此更改，我們的鏈表性能將利用 COW的優(yōu)勢(shì)恢復(fù)其先前的性能狮暑。

一個(gè)小困境

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

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

我們會(huì)看到如下的輸出：

---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)化。因?yàn)槊總€(gè)突變都可以觸發(fā)節(jié)點(diǎn)的副本搬男，所以 remove(after:) 實(shí)現(xiàn)是在錯(cuò)誤的節(jié)點(diǎn)集上進(jìn)行刪除拣展。為了解決這個(gè)問(wèn)題，我們將編寫(xiě)一個(gè)專門(mén)版本的 copyNodes 方法止后。返回到 Sources目錄中的 LinkedList.swift并在 copyNodes 方法下方編寫(xiě)以下內(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
}

此方法與之前的實(shí)現(xiàn)有許多相似之處瞎惫。主要區(qū)別在于它將根據(jù)傳入的參數(shù)返回新復(fù)制的節(jié)點(diǎn)。將 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é)點(diǎn)上執(zhí)行刪除译株。

共享節(jié)點(diǎn)

第二個(gè)優(yōu)化是節(jié)點(diǎn)的部分共享。事實(shí)證明挺益，在某些情況下我們可以避免復(fù)制歉糜。對(duì)所有場(chǎng)景的全面評(píng)估超出了本書(shū)的范圍，但這會(huì)讓你對(duì)所涉及的內(nèi)容有所了解望众。

看下面的例子（這個(gè)不用寫(xiě)了）：

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

共享節(jié)點(diǎn)

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

list2.push(0)

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

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

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

list1.push(100)

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

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

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

關(guān)鍵點(diǎn)

• 鏈表是線性的和單向的踊兜。一旦將引用從一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)竿滨，就無(wú)法返回。

• 鏈表的頭部?jī)?yōu)先插入的時(shí)間復(fù)雜度為 O(1)捏境。數(shù)組對(duì)于頭先插入具有 O(n) 時(shí)間復(fù)雜度于游。

• 遵循 Swift collection協(xié)議（如 Sequence 和 Collection）會(huì)自動(dòng)讓我們?cè)L問(wèn)許多有用的方法。

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