日韩12345区,亚州精品久久中文

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

鏈表(Linked List)

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

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

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

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

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

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

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

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

鏈表的性能

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

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

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

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

單鏈表 vs 雙鏈表

單鏈表使用比雙鏈表使用更少的內(nèi)存，因?yàn)樗恍枰鎯λ心切?code>previous指針。

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

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

為什么使用鏈表？

使用鏈表的典型示例是隊(duì)列。使用數(shù)組，從隊(duì)列前面刪除元素很慢，因?yàn)樗枰蛳乱苿?dòng)內(nèi)存中的所有其他元素。但是通過鏈接鏈表，只需將head更改為指向第二個(gè)元素即可。快多了。

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

代碼

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

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

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

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

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

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

讓我們開始構(gòu)建LinkedList。這是第一點(diǎn)：

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

理想情況下，我們希望類名盡可能具有描述性，但是，我們不希望每次要使用類時(shí)都打長名稱，因此，我們在LinkedList中給LinkedListNode<T>定義了一個(gè)短的別名Node。

這個(gè)鏈表只有一個(gè)head指針，沒有尾部。添加尾指針留給讀者練習(xí)。（如果我們還有一個(gè)尾指針，我會指出哪些函數(shù)會有所不同。）

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

在playground中測試：

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

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

  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可選項(xiàng)并將結(jié)果放入一個(gè)名為node的新局部變量中。區(qū)別在于node不是常量而是當(dāng)前運(yùn)行環(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對解包選項(xiàng)的內(nèi)置支持。你會在隨后的代碼中看到一堆這樣的循環(huán)。

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

當(dāng)然，last只返回nil，因?yàn)殒湵碇袥]有任何節(jié)點(diǎn)。讓我們添加一個(gè)方法，將新節(jié)點(diǎn)添加到鏈表的末尾：

  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)建一個(gè)新的Node對象，然后請求我們剛剛添加的最后一個(gè)節(jié)點(diǎn)last屬性。如果沒有這樣的節(jié)點(diǎn)，鏈表仍然是空的，我們使head指向這個(gè)新的Node。但是如果我們確實(shí)找到了一個(gè)有效的最后節(jié)點(diǎn)對象，我們連接next和previous指針將這個(gè)新節(jié)點(diǎn)鏈接到鏈中。許多鏈表代碼涉及這種next和previous指針操作。

在playground中測試：

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

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

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

增加第二個(gè)節(jié)點(diǎn)：

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

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

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

您可以通過查看next和previous指針來自行驗(yàn)證：

list.first!.previous          // nil
list.first!.next!.value       // "World"
list.last!.previous!.value    // "Hello"
list.last!.next               // nil

讓我們添加一個(gè)方法來計(jì)算鏈表中有多少個(gè)節(jié)點(diǎn)。這與我們已經(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)遍歷鏈表，但這次增加了一個(gè)計(jì)數(shù)器。

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

如果我們想在鏈表中的特定索引處找到節(jié)點(diǎn)，該怎么辦？使用數(shù)組我們可以編寫一個(gè)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。因?yàn)槿绻?，它會按原樣返回head。
但是，當(dāng)給定索引大于0時(shí)，它從頭開始，然后繼續(xù)追蹤node.next指針逐步執(zhí)行鏈表。
與此時(shí)計(jì)數(shù)方法的不同之處在于存在兩種終止條件。
一種是當(dāng)for循環(huán)語句到達(dá)索引時(shí)，我們能夠獲取給定索引的節(jié)點(diǎn)。
第二個(gè)是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

為了好玩，我們也可以實(shí)現(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]上崩潰，因?yàn)樵撍饕蠜]有節(jié)點(diǎn)。

到目前為止，我們已經(jīng)編寫了將新節(jié)點(diǎn)添加到鏈表末尾的代碼，但這很慢，因?yàn)槟枰日业芥湵淼哪┪?。（如果我們使用尾指針會很快。）因此，如果鏈表中?xiàng)目的順序無關(guān)緊要，則應(yīng)在鏈表的前面執(zhí)行插入操作。這總是一個(gè)O(1)操作。

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

    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é)點(diǎn)（C）。

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

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

new.next = head
head.previous = new

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

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

head = new

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

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

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

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

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

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é)點(diǎn)，以驗(yàn)證其是否正常工作。

注意： node(at:) 和 insert(_:at:)函數(shù)也可以與單鏈表一起使用，因?yàn)槲覀儾灰蕾囉诠?jié)點(diǎn)的previous指針來查找前一個(gè)元素。

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

  public func removeAll() {
    head = nil
  }

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

接下來，我們將添加一些可以刪除單個(gè)節(jié)點(diǎn)的函數(shù)。如果你已經(jīng)有了對節(jié)點(diǎn)的引用，那么使用remove()是最優(yōu)的，因?yàn)槟悴恍枰闅v鏈表來首先找到節(jié)點(diǎn)。

  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é)點(diǎn)從鏈表中取出時(shí)，我們將斷開指向上一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)的鏈接。要使鏈表再次完整，我們必須將前一個(gè)節(jié)點(diǎn)鏈接到下一個(gè)節(jié)點(diǎn)。

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

嘗試一下：

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

如果你沒有對節(jié)點(diǎn)的引用，你可以使用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

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

我們的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)鏈表，使頭部成為尾部，反之亦然？有一個(gè)非?？焖俚乃惴ǎ?/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)遍歷整個(gè)鏈表，并簡單地交換每個(gè)節(jié)點(diǎn)的next和previous指針。它還將head指針移動(dòng)到最后一個(gè)元素。（如果你有一個(gè)尾部指針，你還需要更新它。）你最終得到這樣的東西：

         +--------+    +--------+    +--------+    +--------+
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)建一個(gè)新鏈表，用來存放之前鏈表中字符串的長度）

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
    }

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

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

為讀者練習(xí)：map() 和filter() 的這些實(shí)現(xiàn)不是很快，因?yàn)樗鼈儗⑿鹿?jié)點(diǎn)追加到新鏈表的末尾。回想一下，append是O(n)，因?yàn)樗枰獟呙枵麄€(gè)鏈表以找到最后一個(gè)節(jié)點(diǎn)。你能加快速度嗎？（提示：跟蹤您添加的最后一個(gè)節(jié)點(diǎn)。）

另一種方法

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

可以使用枚舉實(shí)現(xiàn)具有值語義的鏈表。這看起來有點(diǎ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ù)集合時(shí)常見的大量屬性和操作。除此之外，它還允許自定義類型遵循Swift開發(fā)人員常用的模式。

為了符合這個(gè)協(xié)議，類需要提供：
1 startIndex和endIndex屬性。
2 對元素的下標(biāo)訪問為O(1)。需要記錄這種時(shí)間復(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
  }
}

因?yàn)榧县?fù)責(zé)管理自己的索引，下面的實(shí)現(xiàn)保留對鏈表中節(jié)點(diǎn)的引用。索引中的標(biāo)記屬性表示鏈表中節(jié)點(diǎn)的位置。

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

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

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

要注意的一些事情

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

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

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

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

【譯】Swift算法俱樂部-鏈表

【譯】Swift算法俱樂部-鏈表

鏈表的性能

單鏈表 vs 雙鏈表

為什么使用鏈表？

代碼

另一種方法

符合Collection協(xié)議

要注意的一些事情

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

【譯】Swift算法俱樂部-鏈表

鏈表的性能

單鏈表 vs 雙鏈表

為什么使用鏈表？

代碼

另一種方法

符合Collection協(xié)議

要注意的一些事情

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av