本文是對 Swift Algorithm Club 翻譯的一篇文章。
Swift Algorithm Club是 raywenderlich.com網(wǎng)站出品的用Swift實現(xiàn)算法和數(shù)據(jù)結(jié)構(gòu)的開源項目，目前在GitHub上有18000+??，我初略統(tǒng)計了一下，大概有一百左右個的算法和數(shù)據(jù)結(jié)構(gòu)，基本上常見的都包含了，是iOSer學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)不錯的資源。
??andyRon/swift-algorithm-club-cn是我對Swift Algorithm Club，邊學(xué)習(xí)邊翻譯的項目。由于能力有限，如發(fā)現(xiàn)錯誤或翻譯不妥，請指正，歡迎pull request。也歡迎有興趣、有時間的小伙伴一起參與翻譯和學(xué)習(xí)??。當(dāng)然也歡迎加??，??????????。
本文的翻譯原文和代碼可以查看??swift-algorithm-club-cn/Linked List

鏈表(Linked List)

這個主題已經(jīng)有輔導(dǎo)文章

鏈表是一系列數(shù)據(jù)項，就像數(shù)組一樣。 數(shù)組分配了一大塊內(nèi)存來存儲對象，而鏈表中的元素在內(nèi)存中是完全獨立的對象，并通過鏈接連接：

+--------+    +--------+    +--------+    +--------+
|        |    |        |    |        |    |        |
| node 0 |--->| node 1 |--->| node 2 |--->| node 3 |
|        |    |        |    |        |    |        |
+--------+    +--------+    +--------+    +--------+

鏈表的元素稱為 節(jié)點。 上圖顯示了 單鏈表，其中每個節(jié)點只有一個引用 - 或叫做“指針” - 到下一個節(jié)點。 在 雙向鏈表中，如下所示，節(jié)點還有指向前一個節(jié)點的指針：

+--------+    +--------+    +--------+    +--------+
|        |--->|        |--->|        |--->|        |
| node 0 |    | node 1 |    | node 2 |    | node 3 |
|        |<---|        |<---|        |<---|        |
+--------+    +--------+    +--------+    +--------+

您需要跟蹤鏈表的開始位置。 這通常用一個名為 head 的指針完成：

         +--------+    +--------+    +--------+    +--------+
head --->|        |--->|        |--->|        |--->|        |---> nil
         | node 0 |    | node 1 |    | node 2 |    | node 3 |
 nil <---|        |<---|        |<---|        |<---|        |<--- tail
         +--------+    +--------+    +--------+    +--------+

引用鏈表末尾也很有用，稱為 tail。 注意，最后一個節(jié)點的“下一個”指針是nil，第一個節(jié)點的“前一個”指針也是nil。

鏈表的性能

鏈表上的大多數(shù)操作時間復(fù)雜度都是 O(n) ，因此鏈表通常比數(shù)組慢。但是，它們也更加靈活 —— 而不是像數(shù)組一樣復(fù)制大塊內(nèi)存，鏈表上的許多操作只需要更改幾個指針。

時間復(fù)雜度是O(n)的原因是你不能簡單地寫list[2]來從鏈表中訪問節(jié)點2。 如果你已經(jīng)沒有對該節(jié)點的引用，你必須從head開始，然后按照next指針逐個訪問（或者從tail開始，使用previous指針，逐個訪問并找到指定節(jié)點）。

但是一旦你有一個節(jié)點的引用，插入和刪除等操作真的很快。 只是尋找節(jié)點慢。

這意味著當(dāng)您處理鏈表時，應(yīng)盡可能在前面插入新項目。 這是O(1)操作。 如果你跟蹤tail指針，同樣可以在后面插入。

單鏈表 vs 雙鏈表

單鏈表使用比雙鏈表使用更少的內(nèi)存，因為它不需要存儲所有那些previous指針。

但是如果你需要找到一個節(jié)點以前的節(jié)點，你就搞砸了。 您必須從頭部開始并遍歷整個鏈表，直到到達(dá)正確的節(jié)點。

對于許多任務(wù)，雙向鏈表使事情變得更容易。

為什么使用鏈表？

使用鏈表的典型示例是隊列。 使用數(shù)組，從隊列前面刪除元素很慢，因為它需要向下移動內(nèi)存中的所有其他元素。 但是通過鏈接鏈表，只需將head更改為指向第二個元素即可。 快多了。

但說實話，現(xiàn)在你幾乎不需要編寫自己的鏈表。 不過，了解它們的工作方式仍然很有用; 將對象鏈接在一起的原則也與樹和圖一起使用。

代碼

我們首先定義一個描述節(jié)點的類型：

public class LinkedListNode<T> {
  var value: T
  var next: LinkedListNode?
  weak var previous: LinkedListNode?

  public init(value: T) {
    self.value = value
  }
}

這是一種泛型類型，因此T可以是您想要存儲在節(jié)點中的任何類型的數(shù)據(jù)。 我們將在后面的示例中使用字符串。

這邊定義的是一個雙向鏈表，每個節(jié)點都有一個next和previous指針。 如果沒有下一個或前一個節(jié)點，則這些可以是nil，因此這些變量必須是可選項。 （在下文中，我將指出哪些函數(shù)需要更改，如果這只是單個而不是雙向鏈表。）

注意： 為避免循環(huán)強(qiáng)引用，我們聲明previous指針為弱。 如果鏈表中有一個節(jié)點A后面跟著節(jié)點B，那么A指向B，而B指向A。 在某些情況下，即使在刪除節(jié)點后，此循環(huán)強(qiáng)引用也可能導(dǎo)致節(jié)點保持活動狀態(tài)。 我們不希望這樣，所以我們使其中一個指針weak來打破循環(huán)。

讓我們開始構(gòu)建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指針，沒有尾部。 添加尾指針留給讀者練習(xí)。 （如果我們還有一個尾指針，我會指出哪些函數(shù)會有所不同。）

如果head為nil，則鏈表為空。 因為head是一個私有變量，所以我添加了屬性first來返回對鏈表中第一個節(jié)點的引用。

在playground中測試：

let list = LinkedList<String>()
list.isEmpty   // true
list.first     // nil

我們還添加一個屬性，為您提供鏈表中的最后一個節(jié)點。 這是將開始變得有趣了：

  public var last: Node? {
    guard var node = head else {
      return nil
    }
  
    while let next = node.next {
      node = next
    }
    return node
  }

如果你是Swift的新手，你可能已經(jīng)看過if let但也許不是if var。 它做了同樣的事情 - 它解開head可選項并將結(jié)果放入一個名為node的新局部變量中。 區(qū)別在于node不是常量而是當(dāng)前運行環(huán)境下的變量，因此我們可以在循環(huán)內(nèi)更改它。

循環(huán)也做了一些Swift魔法。 while let next = node.next保持循環(huán)，直到node.next為nil。 您可以寫如下：

      var node: Node? = head
      while node != nil && node!.next != nil {
        node = node!.next
      }

但這對我來說并不是很開心。 我們可以很好地利用Swift對解包選項的內(nèi)置支持。 你會在隨后的代碼中看到一堆這樣的循環(huán)。

注意： 如果我們保留一個尾指針，last只會做return tail。 但我們沒有，所以它必須從頭到尾逐步完成整個鏈表。這是一項昂貴的操作，特別是如果鏈表很長的話。

當(dāng)然，last只返回nil，因為鏈表中沒有任何節(jié)點。 讓我們添加一個方法，將新節(jié)點添加到鏈表的末尾：

  public func append(value: T) {
    let newNode = Node(value: value)
    if let lastNode = last {
      newNode.previous = lastNode
      lastNode.next = newNode
    } else {
      head = newNode
    }
  }

append()方法首先創(chuàng)建一個新的Node對象，然后請求我們剛剛添加的最后一個節(jié)點last屬性。 如果沒有這樣的節(jié)點，鏈表仍然是空的，我們使head指向這個新的Node。但是如果我們確實找到了一個有效的最后節(jié)點對象，我們連接next和previous指針將這個新節(jié)點鏈接到鏈中。許多鏈表代碼涉及這種next和previous指針操作。

在playground中測試：

list.append("Hello")
list.isEmpty         // false
list.first!.value    // "Hello"
list.last!.value     // "Hello"

The list looks like this:
這個鏈表目前看上去是：

         +---------+
head --->|         |---> nil
         | "Hello" |
 nil <---|         |
         +---------+

增加第二個節(jié)點：

list.append("World")
list.first!.value    // "Hello"
list.last!.value     // "World"

現(xiàn)在鏈表看上去是：

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

讓我們添加一個方法來計算鏈表中有多少個節(jié)點。 這與我們已經(jīng)完成的工作非常相似：

  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
  }

它以相同的方式循環(huán)遍歷鏈表，但這次增加了一個計數(shù)器。

注意： 加快獲得count的速度（從O(n)到O(1)）的一種方法是跟蹤一個計算鏈表中有多少節(jié)點的變量。 無論何時添加或刪除節(jié)點，都會更新此變量。

如果我們想在鏈表中的特定索引處找到節(jié)點，該怎么辦？使用數(shù)組我們可以編寫一個O(1)操作array[index]。這更多地涉及鏈接鏈表，但代碼遵循類似的模式：

  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。
但是，當(dāng)給定索引大于0時，它從頭開始，然后繼續(xù)追蹤node.next指針逐步執(zhí)行鏈表。
與此時計數(shù)方法的不同之處在于存在兩種終止條件。
一種是當(dāng)for循環(huán)語句到達(dá)索引時，我們能夠獲取給定索引的節(jié)點。
第二個是for-loop語句中的node.next返回nil并導(dǎo)致break。（*1）
這意味著給定的索引超出范圍并導(dǎo)致崩潰。

測試一下：

list.nodeAt(0)!.value    // "Hello"
list.nodeAt(1)!.value    // "World"
// list.nodeAt(2)           // crash

為了好玩，我們也可以實現(xiàn)subscript（下標(biāo)）方法：

  public subscript(index: Int) -> T {
    let node = node(atIndex: index)
    return node.value
  }

現(xiàn)在可以編寫如下內(nèi)容：

list[0]   // "Hello"
list[1]   // "World"
list[2]   // crash!

它在list [2]上崩潰，因為該索引上沒有節(jié)點。

到目前為止，我們已經(jīng)編寫了將新節(jié)點添加到鏈表末尾的代碼，但這很慢，因為您需要先找到鏈表的末尾。（如果我們使用尾指針會很快。）因此，如果鏈表中項目的順序無關(guān)緊要，則應(yīng)在鏈表的前面執(zhí)行插入操作。 這總是一個O(1)操作。

讓我們編寫一個方法，允許您在鏈表中的任何索引處插入新節(jié)點。

    public func insert(_ node: Node, at index: Int) {
        let newNode = node
        if index == 0 {
            newNode.next = head
            head?.previous = newNode
            head = newNode
        } else {
            let prev = self.node(at: index-1)
            let next = prev.next
            
            newNode.previous = prev
            newNode.next = prev.next
            prev.next = newNode
            next?.previous = newNode
        }
    }

與node(at:)方法一樣，insert(_:at:)方法也會根據(jù)索引參數(shù)是否為0進(jìn)行判斷。
首先讓我們來看看前一種情況（譯注：也就是index == 0，插入最前面的情況）。 假設(shè)我們有以下鏈表和新節(jié)點（C）。

         +---------+     +---------+
head --->|         |---->|         |-----//----->
         |    A    |     |    B    |
 nil <---|         |<----|         |<----//------
         +---------+     +---------+ 
             [0]             [1]
              
              
         +---------+ 
 new --->|         |----> nil
         |    C    |
         |         |
         +---------+

現(xiàn)在將新節(jié)點放在第一個節(jié)點之前。 通過這種方式：

new.next = head
head.previous = new

         +---------+            +---------+     +---------+
 new --->|         |--> head -->|         |---->|         |-----//----->
         |    C    |            |    A    |     |    B    |
         |         |<-----------|         |<----|         |<----//------
         +---------+            +---------+     +---------+ 

最后，用新節(jié)點作為頭部。

head = new

         +---------+    +---------+     +---------+
head --->|         |--->|         |---->|         |-----//----->
         |    C    |    |    A    |     |    B    |
 nil <---|         |<---|         |<----|         |<----//------
         +---------+    +---------+     +---------+ 
             [0]            [1]             [2]

但是，當(dāng)給定索引大于0時，必須獲取節(jié)點的上一個和下一個索引并在它們之間插入。
您還可以使用node(at:)獲取上一個和下一個節(jié)點，如下所示：

         +---------+         +---------+     +---------+    
head --->|         |---//--->|         |---->|         |----
         |         |         |    A    |     |    B    |    
 nil <---|         |---//<---|         |<----|         |<---
         +---------+         +---------+     +---------+    
             [0]              [index-1]        [index]      
                                  ^               ^ 
                                  |               | 
                                 prev            next

prev = node(at: index-1)
next = prev.next

現(xiàn)在在prev和next之間插入新節(jié)點。

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(LinedListNode(value: "Swift"), at: 1)
list[0]     // "Hello"
list[1]     // "Swift"
list[2]     // "World

還可以嘗試在鏈表的前面和后面添加新節(jié)點，以驗證其是否正常工作。

注意： node(at:) 和 insert(_:at:)函數(shù)也可以與單鏈表一起使用，因為我們不依賴于節(jié)點的previous指針來查找前一個元素。

我們還需要什么？ 當(dāng)然要刪除節(jié)點！ 首先我們要做removeAll()，這很簡單：

  public func removeAll() {
    head = nil
  }

如果你有一個尾指針，你也可以在這里設(shè)置為nil。

接下來，我們將添加一些可以刪除單個節(jié)點的函數(shù)。 如果你已經(jīng)有了對節(jié)點的引用，那么使用remove()是最優(yōu)的，因為你不需要遍歷鏈表來首先找到節(jié)點。

  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
  }

當(dāng)我們將此節(jié)點從鏈表中取出時，我們將斷開指向上一個節(jié)點和下一個節(jié)點的鏈接。 要使鏈表再次完整，我們必須將前一個節(jié)點鏈接到下一個節(jié)點。

不要忘記head指針！ 如果這是鏈表中的第一個節(jié)點，則需要更新head以指向下一個節(jié)點。 （同樣，當(dāng)你有一個尾指針，這是最后一個節(jié)點）。 當(dāng)然，如果沒有剩余的節(jié)點，head應(yīng)該變?yōu)?code>nil。

嘗試一下：

list.remove(node: list.first!)   // "Hello"
list.count                     // 2
list[0]                        // "Swift"
list[1]                        // "World"

如果你沒有對節(jié)點的引用，你可以使用removeLast()或 removeAt()：

    public func removeLast() -> T {
        assert(!isEmpty)
        return remove(node: last!)
    }
    
    public func remove(at index: Int) -> T {
        let node = self.node(at: index)
        return remove(node: node)
    }

所有這些刪除函數(shù)都返回已刪除元素的值。

list.removeLast()              // "World"
list.count                     // 1
list[0]                        // "Swift"

list.remove(at: 0)          // "Swift"
list.count                     // 0

注意： 對于單鏈表，刪除最后一個節(jié)點稍微復(fù)雜一些。 您不能只使用last來查找鏈表的末尾，因為您還需要對倒數(shù)第二個節(jié)點的引用。 相反，使用nodesBeforeAndAfter()輔助方法。 如果鏈表有一個尾指針，那么removeLast()非?？?，但你需要記住讓tail指向前一個節(jié)點。

我們的LinkedList類還可以做一些有趣的事情。 一些很方便可讀的調(diào)試輸出：

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]

如何反轉(zhuǎn)鏈表，使頭部成為尾部，反之亦然？ 有一個非?？焖俚乃惴ǎ?/p>

  public func reverse() {
    var node = head
    tail = node           // If you had a tail pointer
    while let currentNode = node {
      node = currentNode.next
      swap(&currentNode.next, &currentNode.previous)
      head = currentNode
    }
  }

這循環(huán)遍歷整個鏈表，并簡單地交換每個節(jié)點的next和previous指針。 它還將head指針移動到最后一個元素。 （如果你有一個尾部指針，你還需要更新它。）你最終得到這樣的東西：

         +--------+    +--------+    +--------+    +--------+
tail --->|        |<---|        |<---|        |<---|        |---> nil
         | node 0 |    | node 1 |    | node 2 |    | node 3 |
 nil <---|        |--->|        |--->|        |--->|        |<--- head
         +--------+    +--------+    +--------+    +--------+

數(shù)組有map()和filter()函數(shù)，那么沒有理由說鏈接鏈表沒有。

    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
    }

使用如下：（譯注：創(chuàng)建一個新鏈表，用來存放之前鏈表中字符串的長度）

let list = LinkedList<String>()
list.append("Hello")
list.append("Swifty")
list.append("Universe")

let m = list.map { s in s.count }
m  // [5, 6, 8]

filter()函數(shù)：

    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
    }

一個簡單的使用例子：（譯注：篩選出鏈表中字符串長度大于5的元素并組成新的鏈表）

let f = list.filter { s in s.count > 5 }
f    // [Universe, Swifty]

為讀者練習(xí)：map() 和filter() 的這些實現(xiàn)不是很快，因為它們將新節(jié)點追加到新鏈表的末尾。 回想一下，append是O(n)，因為它需要掃描整個鏈表以找到最后一個節(jié)點。 你能加快速度嗎？ （提示：跟蹤您添加的最后一個節(jié)點。）

另一種方法

到目前為止，您看到的LinkedList版本使用的是類，具有引用語義。 這沒有什么不對，但這確實使它們比Swift的其他集合（例如Array和Dictionary）更重要。(譯注： 這里應(yīng)該是想表達(dá)，Array和Dictionary都是結(jié)構(gòu)體，鏈表也可以使用結(jié)構(gòu)體和枚舉實現(xiàn))

可以使用枚舉實現(xiàn)具有值語義的鏈表。 這看起來有點像這樣：

enum ListNode<T> {
  indirect case node(T, next: ListNode<T>)
  case end
}

與基于類的版本的最大區(qū)別在于，您對此鏈表所做的任何修改都將導(dǎo)致創(chuàng)建新副本。 這是否是您想要的取決于應(yīng)用程序。

[如果有需求，我可能會更詳細(xì)地填寫此部分。]

符合Collection協(xié)議

符合Sequence協(xié)議的類型，其元素可以多次遍歷。非破壞性地通過索引的下標(biāo)訪問，應(yīng)該符合Swift標(biāo)準(zhǔn)庫中定義的Collection協(xié)議。

這樣做可以訪問處理數(shù)據(jù)集合時常見的大量屬性和操作。 除此之外，它還允許自定義類型遵循Swift開發(fā)人員常用的模式。

為了符合這個協(xié)議，類需要提供：
1 startIndex和endIndex屬性。
2 對元素的下標(biāo)訪問為O(1)。 需要記錄這種時間復(fù)雜性的變化。

/// The position of the first element in a nonempty collection.
public var startIndex: Index {
  get {
    return LinkedListIndex<T>(node: head, tag: 0)
  }
}
  
/// The collection's "past the end" position---that is, the position one
/// greater than the last valid subscript argument.
/// - Complexity: O(n), where n is the number of elements in the list.
///   This diverts from the protocol's expectation.
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
  }
}

因為集合負(fù)責(zé)管理自己的索引，下面的實現(xiàn)保留對鏈表中節(jié)點的引用。 索引中的標(biāo)記屬性表示鏈表中節(jié)點的位置。

/// Custom index type that contains a reference to the node at index '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)
  }
}

最后，鏈接能夠通過以下實現(xiàn)計算給定的索引之后的索引。

public func index(after idx: Index) -> Index {
  return LinkedListIndex<T>(node: idx.node?.next, tag: idx.tag+1)
}

要注意的一些事情

鏈接鏈表是靈活的，但許多操作是O(n)。

在鏈表上執(zhí)行操作時，您總是需要小心更新相關(guān)的next和previous指針，還可能更新head和tail指針。 如果你搞砸了，你的鏈表將不再正確，你的程序可能會在某些時候崩潰。 小心！

處理鏈表時，通?？梢允褂眠f歸：處理第一個元素，然后在鏈表的其余部分再次遞歸調(diào)用該函數(shù)。 當(dāng)沒有下一個元素時你就完成了。 這就是鏈表是LISP等函數(shù)式編程語言的基礎(chǔ)的原因。

作者：Matthijs Hollemans
翻譯：Andy Ron
校對：Andy Ron