Swift 算法俱樂部：鏈表

數(shù)據(jù)結(jié)構(gòu)：鏈表

原文鏈接： Swift Algorithm Club: Swift Linked List Data Structure
翻譯： coderJoey

在這本教程中，你將學(xué)習(xí)用Swift3實現(xiàn)鏈表數(shù)據(jù)結(jié)構(gòu)。

開始吧

鏈表是由數(shù)據(jù)項組成的一個序列，其中每個數(shù)據(jù)項被稱為節(jié)點(diǎn)。
鏈表有兩種主要類型：
單鏈表 每一個節(jié)點(diǎn)只包含一個指向鏈表中下一個節(jié)點(diǎn)的指針（引用）。

單鏈表

雙鏈表 每個節(jié)點(diǎn)包含兩個指針（引用），一個指向前一個節(jié)點(diǎn)，一個指向后一個節(jié)點(diǎn)。
雙鏈表

通常我們用head和tail指針來記錄鏈表的頭和尾。
鏈表頭尾標(biāo)記

鏈表數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)（Swift 3語法）

在本節(jié)中，你將用swift 3的語法來實現(xiàn)鏈表。
記住一個鏈表數(shù)據(jù)結(jié)構(gòu)是由節(jié)點(diǎn)組成的，所以首先我們創(chuàng)建一個基本的節(jié)點(diǎn)類。創(chuàng)建一個新的Swift playground 項目，并添加下面的空類。

public class Node {

}

Value

每個節(jié)點(diǎn)需要一個與之關(guān)聯(lián)的數(shù)據(jù)（value）。將下面的代碼添加到大括號內(nèi)：

var value: String
 
init(value: String) {
  self.value = value
}

你已經(jīng)了聲明一個類型為String，名為value的屬性。在自己的app里，你可以用鏈表來儲存任何數(shù)據(jù)類型。
同時，也聲明了一個構(gòu)造函數(shù)：此函數(shù)里面需要初始化所有類的非可選類型（non-optional）的屬性。

Next

在鏈表中，除了數(shù)據(jù)之外，每一個節(jié)點(diǎn)都需要一個指向下一個節(jié)點(diǎn)的指針。
所以需要為我們的類中添加一個next屬性：

var next: Node?

我們添加的是一個類型為Node，名為next的屬性。注意這里的next是可選類型，這是因為鏈表中最后一個節(jié)點(diǎn)不會指向其他的節(jié)點(diǎn)了。

Previous

你需要實現(xiàn)的是一個雙鏈表數(shù)據(jù)結(jié)構(gòu)，所以我們還需要為節(jié)點(diǎn)添加最后一個屬性：

weak var previous: Node?

注意：為了避免循環(huán)引用，我們將previous的指針聲明為weak（弱引用）。例如現(xiàn)在在一個鏈表中，節(jié)點(diǎn)B在節(jié)點(diǎn)A后面，這樣A是指向B的。假如現(xiàn)在節(jié)點(diǎn)B也指向節(jié)點(diǎn)A，這就導(dǎo)致A和B互相強(qiáng)引用。在某些情況下,這種所有權(quán)循環(huán)（ownership cycle）會使得即使你刪除它們，節(jié)點(diǎn)依然存活著（也就是所謂的內(nèi)存泄露）。所以我們需要將其中一個指針設(shè)置為weak，用來打破這種循環(huán)。
了解更多關(guān)于所有權(quán)循環(huán)的知識，請看ARC and Memory Management in Swift 教程。

鏈表

至此已經(jīng)完成了節(jié)點(diǎn)類的創(chuàng)建，你還需要記錄鏈表的起點(diǎn)和終點(diǎn)。
現(xiàn)在我們將鏈表（LinkedList）類添加到playground中：

public class LinkedList {
  fileprivate var head: Node?
  private var tail: Node?

  public var isEmpty: Bool {
    return head == nil
  }

  public var first: Node? {
    return head
  }

  public var last: Node? {
    return tail
  }
}

該類將記錄鏈表的起點(diǎn)和終點(diǎn)。它還將提供一些輔助函數(shù)。

添加

為了能在鏈表中添加一個新的節(jié)點(diǎn)，你需要在LinkedList類中聲明一個**append(value:) **方法。

public func append(value: String) {
  // 1
  let newNode = Node(value: value)
  // 2
  if let tailNode = tail {
    newNode.previous = tailNode
    tailNode.next = newNode
  } 
  // 3
  else {
    head = newNode
  }
  // 4
  tail = newNode
}

來看看上面做了什么：

  • 創(chuàng)建一個新的Node來接收需要添加的節(jié)點(diǎn)。注意，Node類的作用是讓鏈表中的每一個數(shù)據(jù)項能指向前一個節(jié)點(diǎn)以及后一個節(jié)點(diǎn)。

  • 如果tailNode不為空，則表明該鏈表擁有節(jié)點(diǎn)。如果是這樣的話，那么就將新添加進(jìn)來的節(jié)點(diǎn)的頭指針（previous）指向鏈表的尾部（tailNode）。與此同時，將tailNode的next指針指向新的節(jié)點(diǎn)。

  • 最后將新的節(jié)點(diǎn)設(shè)置成鏈表尾部節(jié)點(diǎn)。

打印鏈表

讓我們實踐一下上面完成的鏈表。我們添加如下代碼到playground（注意：代碼要添加到LinkedList類的外面）

let dogBreeds = LinkedList()
dogBreeds.append(value: "Labrador")
dogBreeds.append(value: "Bulldog")
dogBreeds.append(value: "Beagle")
dogBreeds.append(value: "Husky")

定義鏈表后,我們試著將鏈表的內(nèi)容打印到控制臺:

print(dogBreeds)

你可以使用組合鍵 Command-Shift-Y喚起控制臺。然而你看到的打印結(jié)果是：

LinkedList

這顯然沒什么用。要使打印的字符串更具可讀性，你需要讓LinkedList遵守CustomStringConvertable 協(xié)議。我們將下面的代碼添加到LinkedList 類的下面。

// 1
extension LinkedList: CustomStringConvertible {
  // 2
  public var description: String {
    // 3
    var text = "["
    var node = head
    // 4
    while node != nil {
      text += "\(node!.value)"
      node = node!.next
      if node != nil { text += ", " }
    }
    // 5
    return text + "]"
  }
}

上面代碼做了什么:

  1. 聲明了一個** LinkedList 類的擴(kuò)展，而且遵守了CustomStringConvertable 協(xié)議。這個協(xié)議希望你實現(xiàn)String類型的description，這里的description為計算型屬性（computed property）**。

  2. 定義description屬性，它的返回類型是String，而且是只讀的。

  3. 定義一個將輸出所有內(nèi)容的text變量，目前只包含鏈表內(nèi)容的開頭字符‘’[‘’。

  4. 循環(huán)添加每一個節(jié)點(diǎn)的內(nèi)容。

  5. 添加‘’]‘’到text尾部。

現(xiàn)在打印LinkedList的內(nèi)容，你將看到不錯的結(jié)果：

"[Labrador, Bulldog, Beagle, Husky]"

訪問節(jié)點(diǎn)

當(dāng)你通過先后順序來移動節(jié)點(diǎn)時，鏈表表現(xiàn)的相當(dāng)高效，然而有時候通過索引來訪問節(jié)點(diǎn)卻是相當(dāng)困難的。
下面我們將通過給LinkedList類添加一個** nodeAt(index:) 方法來實現(xiàn)通過索引來訪問節(jié)點(diǎn)。該方法的返回值是指定位置的節(jié)點(diǎn)**。

更新LinkedList類，將下面的方法添加到該類中：

public func nodeAt(index: Int) -> Node? {
  // 1
  if index >= 0 {
    var node = head
    var i = index
    // 2
    while node != nil {
      if i == 0 { return node }
      i -= 1
      node = node!.next
    }
  }
  // 3
  return nil
}

上面代碼做了什么:

  1. 循環(huán)鏈表中的節(jié)點(diǎn)，直到循環(huán)到指定的索引處的節(jié)點(diǎn)并返回該節(jié)點(diǎn)。
  2. 如果index小于0或者大于鏈表的節(jié)點(diǎn)數(shù)就返回nil。

刪除所有的節(jié)點(diǎn)

刪除所有的節(jié)點(diǎn)很簡單,只需要將head和tail置為nil：

public func removeAll() {
  head = nil
  tail = nil
}

刪除單個節(jié)點(diǎn)

刪除單個節(jié)點(diǎn)要考慮三種情況：

  1. 刪除鏈表的第一個節(jié)點(diǎn)。head指針和previous指針需要更新。

    RemovalHead-480x73.png

  2. 刪除鏈表中間的一個節(jié)點(diǎn)。previous指針和next指針需要更新。

    Removal-480x94.png

  3. 刪除鏈表的最后一個節(jié)點(diǎn)。next指針和tail指針需要更新。

    RemovalTail-480x73.png

再次更新LinkedList類的實現(xiàn)，添加如下代碼：

public func remove(node: Node) -> String {
  let prev = node.previous
  let next = node.next

  if let prev = prev {
    prev.next = next // 1
  } else { 
    head = next // 2
  }
  next?.previous = prev // 3

  if next == nil { 
    tail = prev // 4
  }

  // 5
  node.previous = nil 
  node.next = nil

  // 6
  return node.value
}

上面的方法做了什么：

  1. 如果你移除的不是鏈表的第一個節(jié)點(diǎn)，那么就更新next指針。
  2. 如果你移除的是鏈表的第一個節(jié)點(diǎn)，那么就更新head指針。
  3. 將previous指針指向被移除的節(jié)點(diǎn)的previous指針。
  4. 如果你移除的是鏈表的最后一個節(jié)點(diǎn)，那么就更新tail指針。
  5. 將移除的節(jié)點(diǎn)的previous和next指針置為nil。
  6. 返回移除的節(jié)點(diǎn)。

泛型

到目前為止，你已經(jīng)實現(xiàn)了一個存儲String值的通用鏈表， 并提供了在LinkedList類中添加，刪除和訪問節(jié)點(diǎn)的函數(shù)。 在本節(jié)中，我們將使用泛型來滿足鏈表儲存抽象類型的要求。

更新Node類：

// 1
public class Node {
  // 2
  var value: T
  var next: Node?
  weak var previous: Node?

  // 3
  init(value: T) {
    self.value = value
  }
}

上面代碼做了什么：

  1. 將Node類的聲明更改為通用類型T。
  2. 你的目標(biāo)是允許Node類接受任何類型的值，因此將value屬性定義為泛型T而不是String。
  3. 將構(gòu)造器更新為接收任意類型。

泛型：挑戰(zhàn)

試著自己先完成LinkedList類的泛型實現(xiàn)。

解決方案：

// 1. Change the declaration of the Node class to take a generic type T
public class LinkedList {
  // 2. Change the head and tail variables to be constrained to type T
  fileprivate var head: Node?
  private var tail: Node?

  public var isEmpty: Bool {
    return head == nil
  }
  
  // 3. Change the return type to be a node constrained to type T
  public var first: Node? {
    return head
  }

  // 4. Change the return type to be a node constrained to type T
  public var last: Node? {
    return tail
  }

  // 5. Update the append function to take in a value of type T
  public func append(value: T) {
    let newNode = Node(value: value)
    if let tailNode = tail {
      newNode.previous = tailNode
      tailNode.next = newNode
    } else {
      head = newNode
    }
    tail = newNode
  }

  // 6. Update the nodeAt function to return a node constrained to type T
  public func nodeAt(index: Int) -> Node? {
    if index >= 0 {
      var node = head
      var i = index
      while node != nil {
        if i == 0 { return node }
        i -= 1
        node = node!.next
      }
    }
    return nil
  }

  public func removeAll() {
    head = nil
    tail = nil
  }

  // 7. Update the parameter of the remove function to take a node of type T. Update the return value to type T.
  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

    if next == nil {
      tail = prev
    }

    node.previous = nil
    node.next = nil
    
    return node.value
  }
}

至此你的代碼應(yīng)該可以通過編譯了，那我們來測試一下！在playground底部添加如下代碼來驗證一下泛型鏈表是否可用。

let dogBreeds = LinkedList()
dogBreeds.append(value: "Labrador")
dogBreeds.append(value: "Bulldog")
dogBreeds.append(value: "Beagle")
dogBreeds.append(value: "Husky")

let numbers = LinkedList()
numbers.append(value: 5)
numbers.append(value: 10)
numbers.append(value: 15)

何去何從

希望你對制作鏈表的這套教程感到滿意！
上面的代碼可點(diǎn)擊這里下載。你還可以去往這里查看其它鏈表的實現(xiàn)方式以及鏈表的相關(guān)討論。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

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

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