Swift算法俱樂(lè)部：Swift 鏈表數(shù)據(jù)結(jié)構(gòu)@(Swift)在本教程中获搏，我們將會(huì)在Swift 3中實(shí)現(xiàn)鏈表常熙。##Getting Started鏈表是一個(gè)序列化的數(shù)據(jù)項(xiàng)，每一個(gè)項(xiàng)目都作為節(jié)點(diǎn)（node）被引用裸卫。有兩個(gè)主要類型的鏈表：?jiǎn)蜗蜴湵砟够撸總€(gè)節(jié)點(diǎn)有一個(gè)指向到下一個(gè)節(jié)點(diǎn)的引用。

Alt text

雙向鏈表队伟，每個(gè)節(jié)點(diǎn)各有一個(gè)向前和向后的節(jié)點(diǎn)的引用幽勒。

Alt text

我們還需要去跟蹤鏈表的開頭和結(jié)尾，通常管這兩個(gè)指針叫做head和tail锈颗。

Alt text

##Swift 3中實(shí)現(xiàn)鏈表這部分咪惠，我們將會(huì)在Swift 3中實(shí)現(xiàn)鏈表。記滓逃怠：鏈表是由節(jié)點(diǎn)組成的渠鸽。所以需要先創(chuàng)建基本節(jié)點(diǎn)類。創(chuàng)建一個(gè)全新的Swift Playground并且添加一個(gè)Class：swiftpublic class Node {}###值節(jié)點(diǎn)需要關(guān)聯(lián)一個(gè)值憨奸，在Node類的中括號(hào)中添加下面的代碼：swiftvar value: String init(value: String) { self.value = value}聲明了一個(gè)屬性凿试，它的名字叫做value似芝，是String類型板甘。在我們的app中這可能是你想存儲(chǔ)的類型。還聲明了一個(gè)初始化方法寞奸，需要初始化所有非可選的屬性在跳。###Next另外，還需要一個(gè)值瓷翻，每個(gè)節(jié)點(diǎn)都需要一個(gè)指針指向到鏈表中的下一個(gè)節(jié)點(diǎn)齐帚。在類中添加另外一個(gè)屬性：swiftvar next: Node?這里聲明了一個(gè)next屬性，它是Node類型童谒。注意next屬性是可選沪羔，因?yàn)樵阪湵碇械淖詈笠粋€(gè)節(jié)點(diǎn)不會(huì)指向任何的節(jié)點(diǎn)蔫饰。###Previous我們將會(huì)實(shí)現(xiàn)一個(gè)雙向鏈表愉豺，所以我們還需要一個(gè)指向之前節(jié)點(diǎn)的指針。在類中添加另外一個(gè)屬性：swiftweak var previous: Node?>注意：為了避免所有權(quán)的循環(huán)引用杖剪，聲明的previous指針是弱引用驰贷。如果你有一個(gè)節(jié)點(diǎn)A括袒，它的下一個(gè)節(jié)點(diǎn)是B，這樣A指向B锹锰，B也指向A漓库。在某些的情況下渺蒿，這樣會(huì)導(dǎo)致節(jié)點(diǎn)即使在被刪除以后還會(huì)存在的情況蘸嘶。這是我們所不希望的陪汽，所以需要讓其中的一個(gè)指針為弱引用來(lái)避免出現(xiàn)這樣的問(wèn)題。###鏈表現(xiàn)在已經(jīng)創(chuàng)建的節(jié)點(diǎn)還需要確定它的起點(diǎn)和終點(diǎn)况增。添加新的LinkedList類到playground的底部：swiftpublic 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 }}這個(gè)類將會(huì)跟蹤鏈表的開頭和結(jié)尾训挡，同樣也會(huì)提供幾個(gè)有用的方法。###Append處理添加一個(gè)新的節(jié)點(diǎn)到鏈表为肮，我們將會(huì)在LinkedList類中聲明一個(gè)append(value:)方法颊艳。swiftpublic 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)建一個(gè)包含值的節(jié)點(diǎn)。記住忘分，創(chuàng)建Node類的目的是讓每一個(gè)項(xiàng)目都可以指向到之前或之后的節(jié)點(diǎn)妒峦。如果tailNode不為空，就意味著鏈表中有些東西窥浪，配置這個(gè)新的項(xiàng)目的previous指向到鏈表的tailNode笛丙，并且配置tailNode的next指向到新的項(xiàng)目。最后符相，設(shè)置鏈表的tail為最新創(chuàng)建的項(xiàng)目對(duì)象啊终。###打印鏈表讓我們?cè)囍敵鲦湵怼Ｔ贚inkedList類的外面：swiftlet dogBreeds = LinkedList()dogBreeds.append(value: "Labrador")dogBreeds.append(value: "Bulldog")dogBreeds.append(value: "Beagle")dogBreeds.append(value: "Husky")在定義鏈表的后面趟脂，嘗試打永堋：swiftprint(dogBreeds)你可以通過(guò)組合鍵：Command-Shift-Y啟動(dòng)調(diào)式控制臺(tái)佛玄，可以看到下面的輸出：LinkedList這種輸出沒(méi)有任何的價(jià)值，要想顯示更多的有用的文字信息般贼，可以讓LinkedList類采用CustomStringConvertable協(xié)議奥吩。在LinkedList類中實(shí)現(xiàn)下面的代碼：swift// 1extension 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ò)展哼蛆，并且采用CustomStringConvertible協(xié)議。這個(gè)協(xié)議希望你實(shí)現(xiàn)一個(gè)計(jì)算屬性description霞赫，該屬性是String類型腮介。2. 聲明的description屬性是計(jì)算屬性，它是一個(gè)只讀的并且返回字符串的屬性端衰。3. 聲明的text變量叠洗，它會(huì)生成整個(gè)的字符串。現(xiàn)在它包含一個(gè)左中括號(hào)靴迫，然后是鏈表的開始惕味。4. 通過(guò)循環(huán)鏈表楼誓，將鏈表中項(xiàng)目的值依次添加到text中玉锌。5. 添加一個(gè)右中括號(hào)到text變量∨备現(xiàn)在榄融，當(dāng)你調(diào)用LinkedList類的print方法涎才，將會(huì)看到一個(gè)非常美妙的鏈表描述："[Labrador, Bulldog, Beagle, Husky]"###訪問(wèn)節(jié)點(diǎn)盡管通過(guò)鏈表的next和previous方法可以很有效的去按順序獲取每個(gè)節(jié)點(diǎn)耍铜，但有的時(shí)候通過(guò)索引的方式對(duì)于我們來(lái)說(shuō)可能會(huì)更加的簡(jiǎn)單棕兼。我們會(huì)在LinkedList類中聲明一個(gè)nodeAt(index: )方法靶衍，它將返回一個(gè)指定索引的節(jié)點(diǎn)颅眶。 修改LinkedList中的代碼：swiftpublic 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. 添加對(duì)指定索引值的檢測(cè)帚呼，看它是否為非負(fù)數(shù)。這樣可以防止負(fù)數(shù)出現(xiàn)的無(wú)限循環(huán)沈自。2. 循環(huán)節(jié)點(diǎn)枯途，直到到達(dá)了那個(gè)指定索引值的節(jié)點(diǎn)酪夷，就會(huì)返回這個(gè)node晚岭。3. 如果索引值小于0，或者是大于鏈表的項(xiàng)目數(shù)片择，則會(huì)返回nil字管。###移除所有節(jié)點(diǎn)移除所有節(jié)點(diǎn)脐供，我們只需要讓head和tail為nil即可政己。swiftpublic func removeAll() { head = nil tail = nil}###移除單個(gè)節(jié)點(diǎn)移除單個(gè)節(jié)點(diǎn)，我們需要考慮下面的三種情況：1. 移除第一個(gè)節(jié)點(diǎn)沦泌，需要修改head和previous指針：

Alt text

2. 移除中間的節(jié)點(diǎn)谢谦，需要修改previous和next：

Alt text

3. 移除最后節(jié)點(diǎn)回挽，需要修改next和tail指針：

Alt text

修改LinkedList類：swiftpublic 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)不是第一節(jié)點(diǎn)則修改next指針。2. 如果移除的節(jié)點(diǎn)是第一節(jié)點(diǎn)則修改head墙牌。3. 修改刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的previous喜滨。4. 如果刪除的是最后一個(gè)節(jié)點(diǎn)，修改tail焰情。5. 給刪除節(jié)點(diǎn)的previous和next賦值nil。6. 返回移除節(jié)點(diǎn)的值初橘。##Generics之前耕蝉，我們已經(jīng)實(shí)現(xiàn)了可以存儲(chǔ)字符串的基本鏈表類垒在。已經(jīng)提供了添加、移除和訪問(wèn)節(jié)點(diǎn)的功能踢关。這部分签舞，我們將會(huì)使用范式抽象出所有的類型鏈表。修改之前的Node類：swift// 1public class Node<T> { // 2 var value: T var next: Node<T>? weak var previous: Node<T>? // 3 init(value: T) { self.value = value }}1. 改變Node類的聲明為范式類型T师妙。2. 我們的目的是允許Node類存儲(chǔ)任何的類型默穴，所以構(gòu)建value的類型也為T蓄诽，而不是之前的String。3. 修改初始化方法锯岖。修改LinkedList類使用范式出吹。swift// 1. Change the declaration of the Node class to take a generic type Tpublic class LinkedList<T> { // 2. Change the head and tail variables to be constrained to type T fileprivate var head: Node<T>? private var tail: Node<T>? public var isEmpty: Bool { return head == nil } // 3. Change the return type to be a node constrained to type T public var first: Node<T>? { return head } // 4. Change the return type to be a node constrained to type T public var last: Node<T>? { 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<T>? { 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>) -> 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 }}所有代碼已經(jīng)完成秋麸，可以實(shí)地測(cè)試了：swiftlet dogBreeds = LinkedList<String>()dogBreeds.append(value: "Labrador")dogBreeds.append(value: "Bulldog")dogBreeds.append(value: "Beagle")dogBreeds.append(value: "Husky") let numbers = LinkedList<Int>()numbers.append(value: 5)numbers.append(value: 10)numbers.append(value: 15)