原文鏈接： Swift Algorithm Club: Swift Linked List Data Structure
翻譯： coderJoey
在這本教程中，你將學(xué)習用Swift3實現(xiàn)鏈表數(shù)據(jù)結(jié)構(gòu)许溅。
開始吧
鏈表是由數(shù)據(jù)項組成的一個序列僚祷，其中每個數(shù)據(jù)項被稱為節(jié)點吓笙。
鏈表有兩種主要類型：
單鏈表 每一個節(jié)點只包含一個指向鏈表中下一個節(jié)點的指針（引用）。
雙鏈表 每個節(jié)點包含兩個指針（引用）陪蜻，一個指向前一個節(jié)點，一個指向后一個節(jié)點眼虱。
通常我們用head和tail指針來記錄鏈表的頭和尾。
鏈表數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)（Swift 3語法）
在本節(jié)中席纽，你將用swift 3的語法來實現(xiàn)鏈表捏悬。
記住一個鏈表數(shù)據(jù)結(jié)構(gòu)是由節(jié)點組成的，所以首先我們創(chuàng)建一個基本的節(jié)點類润梯。創(chuàng)建一個新的Swift playground 項目过牙，并添加下面的空類。
public class Node {
}
Value
每個節(jié)點需要一個與之關(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é)點都需要一個指向下一個節(jié)點的指針锥累。
所以需要為我們的類中添加一個next屬性：
var next: Node?
我們添加的是一個類型為Node缘挑，名為next的屬性。注意這里的next是可選類型揩悄，這是因為鏈表中最后一個節(jié)點不會指向其他的節(jié)點了卖哎。
Previous
你需要實現(xiàn)的是一個雙鏈表數(shù)據(jù)結(jié)構(gòu)，所以我們還需要為節(jié)點添加最后一個屬性：
weak var previous: Node?
注意：為了避免循環(huán)引用删性，我們將previous的指針聲明為weak（弱引用）亏娜。例如現(xiàn)在在一個鏈表中，節(jié)點B在節(jié)點A后面蹬挺，這樣A是指向B的维贺。假如現(xiàn)在節(jié)點B也指向節(jié)點A，這就導(dǎo)致A和B互相強引用巴帮。在某些情況下,這種所有權(quán)循環(huán)（ownership cycle）會使得即使你刪除它們溯泣，節(jié)點依然存活著（也就是所謂的內(nèi)存泄露）。所以我們需要將其中一個指針設(shè)置為weak榕茧，用來打破這種循環(huán)垃沦。
了解更多關(guān)于所有權(quán)循環(huán)的知識，請看ARC and Memory Management in Swift 教程用押。
鏈表
至此已經(jīng)完成了節(jié)點類的創(chuàng)建肢簿，你還需要記錄鏈表的起點和終點。
現(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
}
}
該類將記錄鏈表的起點和終點。它還將提供一些輔助函數(shù)池充。
添加
為了能在鏈表中添加一個新的節(jié)點桩引，你需要在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é)點收夸。注意坑匠，Node類的作用是讓鏈表中的每一個數(shù)據(jù)項能指向前一個節(jié)點以及后一個節(jié)點。
如果tailNode不為空卧惜，則表明該鏈表擁有節(jié)點厘灼。如果是這樣的話，那么就將新添加進來的節(jié)點的頭指針（previous）指向鏈表的尾部（tailNode）咽瓷。與此同時手幢，將tailNode的next指針指向新的節(jié)點。
最后將新的節(jié)點設(shè)置成鏈表尾部節(jié)點忱详。
打印鏈表
讓我們實踐一下上面完成的鏈表围来。我們添加如下代碼到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 + "]"
}
}
上面代碼做了什么:
聲明了一個** LinkedList 類的擴展胀蛮，而且遵守了CustomStringConvertable 協(xié)議。這個協(xié)議希望你實現(xiàn)String類型的description糯钙，這里的description為計算型屬性（computed property）**粪狼。
定義description屬性，它的返回類型是String任岸，而且是只讀的再榄。
定義一個將輸出所有內(nèi)容的text變量，目前只包含鏈表內(nèi)容的開頭字符‘’[‘’享潜。
循環(huán)添加每一個節(jié)點的內(nèi)容困鸥。
添加‘’]‘’到text尾部。
現(xiàn)在打印LinkedList的內(nèi)容剑按，你將看到不錯的結(jié)果：
"[Labrador, Bulldog, Beagle, Husky]"
訪問節(jié)點
當你通過先后順序來移動節(jié)點時疾就，鏈表表現(xiàn)的相當高效，然而有時候通過索引來訪問節(jié)點卻是相當困難的艺蝴。
下面我們將通過給LinkedList類添加一個** nodeAt(index:) 方法來實現(xiàn)通過索引來訪問節(jié)點猬腰。該方法的返回值是指定位置的節(jié)點**。
更新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
}
上面代碼做了什么:
- 循環(huán)鏈表中的節(jié)點姑荷，直到循環(huán)到指定的索引處的節(jié)點并返回該節(jié)點侮攀。
- 如果index小于0或者大于鏈表的節(jié)點數(shù)就返回nil。
刪除所有的節(jié)點
刪除所有的節(jié)點很簡單,只需要將head和tail置為nil：
public func removeAll() {
head = nil
tail = nil
}
刪除單個節(jié)點
刪除單個節(jié)點要考慮三種情況：
-
刪除鏈表的第一個節(jié)點厢拭。head指針和previous指針需要更新。
RemovalHead-480x73.png -
刪除鏈表中間的一個節(jié)點撇叁。previous指針和next指針需要更新供鸠。
Removal-480x94.png -
刪除鏈表的最后一個節(jié)點。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
}
上面的方法做了什么：
- 如果你移除的不是鏈表的第一個節(jié)點，那么就更新next指針趋厉。
- 如果你移除的是鏈表的第一個節(jié)點寨闹，那么就更新head指針。
- 將previous指針指向被移除的節(jié)點的previous指針君账。
- 如果你移除的是鏈表的最后一個節(jié)點繁堡，那么就更新tail指針。
- 將移除的節(jié)點的previous和next指針置為nil乡数。
- 返回移除的節(jié)點椭蹄。
泛型
到目前為止，你已經(jīng)實現(xiàn)了一個存儲String值的通用鏈表净赴， 并提供了在LinkedList類中添加绳矩，刪除和訪問節(jié)點的函數(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
}
}
上面代碼做了什么：
- 將Node類的聲明更改為通用類型T。
- 你的目標是允許Node類接受任何類型的值金度，因此將value屬性定義為泛型T而不是String应媚。
- 將構(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)
何去何從
希望你對制作鏈表的這套教程感到滿意扎筒！
上面的代碼可點擊這里下載。你還可以去往這里查看其它鏈表的實現(xiàn)方式以及鏈表的相關(guān)討論酬姆。
