鏈表簡(jiǎn)單的來(lái)說(shuō)就是一條鏈子, 鐵鏈子大家都知道, 環(huán)環(huán)相扣, 首尾的環(huán)扣空出來(lái), 中間的環(huán)扣, 一個(gè)一個(gè)的首位相連, 這就是鏈表. 官方的定義是, 一個(gè)結(jié)構(gòu)體里面有兩個(gè)值, 一個(gè)值(value)是存儲(chǔ)當(dāng)前節(jié)點(diǎn)的值, 一個(gè)值(p)是存儲(chǔ)下一個(gè)節(jié)點(diǎn)的位置(指針的地址), 最后一個(gè)節(jié)點(diǎn)的p沒(méi)有值.
鏈表是一種物理存儲(chǔ)單元上非連續(xù)欧瘪、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的设哗。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成原环，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成谁帕。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。 相比于線性表順序結(jié)構(gòu)淋纲，操作復(fù)雜。由于不必須按順序存儲(chǔ)院究，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度洽瞬，比另一種線性表順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間业汰，而線性表和順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)伙窃。
如圖所示，鏈表是一系列節(jié)點(diǎn)样漆。 節(jié)點(diǎn)有兩個(gè)職責(zé)：
1.存儲(chǔ)一個(gè)值为障。
2.保持對(duì)下一個(gè)節(jié)點(diǎn)的引用。 nil值表示列表的結(jié)尾氛濒。
理論上我覺(jué)得理解起來(lái)還是不難的, 當(dāng)初老師教的時(shí)候也聽(tīng)懂了, 但是用C語(yǔ)言寫的時(shí)候, 那個(gè)是一臉的蒙圈, 現(xiàn)在想想, C語(yǔ)言的指針雖然靈活, 但是理解起來(lái)還是挺繞的, 無(wú)形的給學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)增加了難度.
Open
新建一個(gè)playground, 然后打開(kāi)source新建一個(gè)Helpers.swift文件, 鍵入一下代碼
public func example(of description: String, action: () -> Void) {
print("---Example of \(description)---")
action()
print()
}
這里注意函數(shù)前面一定要加 public , 否則在playground中會(huì)找不到該方法.
該方法的參數(shù)是一個(gè)閉包, 是為了方便我們打印輸出log
Next
接下來(lái)在playground的source里面新建一個(gè)Node.swift, 這個(gè)文件是用來(lái)存儲(chǔ)節(jié)點(diǎn)數(shù)據(jù)的.
/// 這個(gè)是一個(gè)泛型類型, value 存儲(chǔ)值, next 存儲(chǔ)指向下一個(gè)節(jié)點(diǎn), 為可選類型, 因?yàn)樽詈笠粋€(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為nil
public class Node<Value> {
public var value: Value
public var next: Node?
public init(value: Value, next: Node? = nil) {
self.value = value
self.next = next
}
}
/// CustomStringConvertible 是Swift 標(biāo)準(zhǔn)庫(kù)的一個(gè)協(xié)議, 這個(gè)協(xié)議的作用就是自定義打印輸出的內(nèi)容
extension Node: CustomStringConvertible {
public var description: String {
/// 使用 guard 進(jìn)行 next為空值的判斷, 如果為空, 則不指向下一個(gè)節(jié)點(diǎn)
guard let next = next else {
return "\(value)"
}
return "\(value) -> " + String(describing: next) + " "
}
}
回到playground, 創(chuàng)建節(jié)點(diǎn)
example(of: "creating and linking nodes") {
let node1 = Node(value: 1)
let node2 = Node(value: 2)
let node3 = Node(value: 3)
node1.next = node2
node2.next = node3
print(node1)
}
/// ---Example of creating and linking nodes---
/// 1 -> 2 -> 3
這個(gè)鏈表使用起來(lái)不夠方便, 每添加一個(gè)節(jié)點(diǎn), 還需要手動(dòng)的去指向下一個(gè)節(jié)點(diǎn), 正常的因該是, 不關(guān)心內(nèi)部怎么關(guān)聯(lián), 使用者只需要添加刪除就可以了, 就像數(shù)組一樣.
提供管理Node對(duì)象的接口产场。 向鏈表添加值有三種方法，每種方法都有自己獨(dú)特的性能特征：
- push：在列表的前面添加一個(gè)值舞竿。
- append：在列表末尾添加一個(gè)值京景。
- insert（after :)：在列表的特定節(jié)點(diǎn)之后添加一個(gè)值。
push
public struct LinkedList<Value> {
public var head: Node<Value>?
public var tail: Node<Value>?
public init() {
}
/// 判斷鏈表是否為空
public var isEmpty: Bool {
return head == nil
}
/// 如果鏈表是空的話, 第一個(gè)節(jié)點(diǎn)既是頭部也是尾部, push 操作是往頭部插入的, 每次新插入的一個(gè)元素都會(huì)被放在頭部
/// struct 和enum 的值在內(nèi)部是不能修改的, 如果要修改需要在方法前面添加 mutating 修飾符
public mutating func push(_ value: Value) {
head = Node(value: value, next: head)
/// 當(dāng)tail 為nil是, 頭部和尾部是同一個(gè), 這樣當(dāng)鏈表里面再進(jìn)來(lái)一個(gè)值的時(shí)候, 新值被賦值給了我head節(jié)點(diǎn), 舊值被賦值給了tail節(jié)點(diǎn), 并且新值的next指向了舊值, 依次類推
if tail == nil {
tail = head
}
}
}
extension LinkedList: CustomStringConvertible {
public var description: String {
guard let head = head else {
return "Empty list"
}
return String(describing: head)
}
}
playground 中輸入
example(of: "push") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print(list)
}
/// ---Example of push---
/// 1 -> 2 -> 3
append
public mutating func append(_ value: Value) {
// 1 如果鏈表為空, 先進(jìn)行push操作, 創(chuàng)建一個(gè)新的節(jié)點(diǎn)
if isEmpty {
push(value)
return
}
let node = Node(value: value)
// 2 由于第一步執(zhí)行了push操作, tail 一定可以強(qiáng)制解包成功, 鏈表中的尾部節(jié)點(diǎn)的next賦值為添加的新節(jié)點(diǎn)
tail!.next = node
// 3 把新的節(jié)點(diǎn)的值再賦值給鏈表中的尾部節(jié)點(diǎn)
tail = node
}
playground 輸入
example(of: "append") {
var list = LinkedList<Int>()
list.append(1)
list.append(2)
list.append(3)
print(list)
}
/// ---Example of append---
/// 1 -> 2 -> 3
insert(after:)
添加值的操作是insert（after :)骗奖。 此操作在列表中的特定位置插入值确徙，并且需要兩個(gè)步驟：
1.在列表中查找特定節(jié)點(diǎn)醒串。
2.插入新節(jié)點(diǎn)。
首先鄙皇，實(shí)現(xiàn)代碼以查找要插入值的節(jié)點(diǎn)芜赌。
node（at :)將嘗試根據(jù)給定的索引檢索列表中的節(jié)點(diǎn)。 由于您只能從頭節(jié)點(diǎn)訪問(wèn)列表的節(jié)點(diǎn)伴逸，因此您必須進(jìn)行迭代遍歷缠沈。
/// 查找某個(gè)位置的node
public func node(at index: Int) -> Node<Value>? {
// 1 由于目前只能從頭結(jié)點(diǎn)開(kāi)始訪問(wèn), 先獲取頭結(jié)點(diǎn)的值, 并記錄下標(biāo)
var currentNode = head
var currentIndex = 0
// 2 使用while循環(huán)，將引用向下移動(dòng)到列表中错蝴，直到達(dá)到所需的索引洲愤。 空列表或越界索引將導(dǎo)致nil返回值。
while currentNode != nil && currentIndex < index {
currentNode = currentNode!.next
currentIndex += 1
}
return currentNode
}
插入一個(gè)節(jié)點(diǎn)
// 1 @discardableResult讓調(diào)用者忽略此方法的返回值顷锰，而編譯器不會(huì)向上和向下跳過(guò)警告柬赐。
@discardableResult
public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {
// 2 如果是尾部節(jié)點(diǎn), 調(diào)用append方法。 這將負(fù)責(zé)更新尾部官紫。
guard tail !== node else {
append(value)
return tail!
}
// 3 否則肛宋，只需將新節(jié)點(diǎn)與列表的其余部分鏈接起來(lái)，然后返回新節(jié)點(diǎn)束世。
node.next = Node(value: value, next: node.next)
return node.next!
}
playground輸入
example(of: "inserting at index") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("Before inserting: \(list)")
var middleNode = list.node(at: 1)!
middleNode = list.insert(10, after: middleNode)
print("After inserting: \(list)")
}
/// Before inserting: 1 -> 2 -> 3
/// After inserting: 1 -> 2 -> 10 -> 3
從鏈表中移除節(jié)點(diǎn)
刪除節(jié)點(diǎn)有三個(gè)主要操作:
- pop：刪除列表前面的值酝陈。
- removeLast：刪除列表末尾的值。
- remove（at :)：刪除列表中任何位置的值毁涉。
1. pop：刪除列表前面的值后添。
/// 1.
@discardableResult
//2.
public mutating func pop() -> Value? {
// 5.
defer {
//3.
head = head?.next
// 4.
if isEmpty {
tail = nil
}
}
return head?.value
}
- 刪除列表最前面的值稱為pop
- 返回值為一個(gè)可選值, 因?yàn)? 如果鏈表為空, 則返回值為nil
3.如果刪除成功, 則將頭部指向下一個(gè)節(jié)點(diǎn)
4.如果為空, 為節(jié)點(diǎn)置為nil
5.defer 為推遲執(zhí)行, defer 里面的block會(huì)在方法體內(nèi)的代碼執(zhí)行完畢之后, 最后執(zhí)行
playground 輸入
example(of: "pop") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("pop 之前: \(list)")
let poppedValue = list.pop()
print("pop 之后: \(list)")
print("Popped 值: " + String(describing: poppedValue))
}
pop 之前: 1 -> 2 -> 3
pop 之后: 2 -> 3
Popped 值: Optional(1)
2. removeLast：刪除列表末尾的值。
刪除列表的最后一個(gè)節(jié)點(diǎn)有點(diǎn)不方便薪丁。 盡管您有對(duì)尾節(jié)點(diǎn)的引用遇西，但如果沒(méi)有引用它之前的節(jié)點(diǎn)，則無(wú)法將其刪除严嗜。 因此粱檀，你將不得不進(jìn)行遍歷。
//#removeLast
@discardableResult
public mutating func removeLast() -> Value? {
// 1
guard let head = head else {
return nil
}
// 2
guard head.next != nil else {
return pop()
}
// 3
var prev = head
var current = head
while let next = current.next {
prev = current
current = next
}
// 4
prev.next = nil
tail = prev
return current.value
}
1.如果頭部為nil漫玄，則無(wú)需移除任何東西茄蚯，因此您返回nil。
2.如果列表只包含一個(gè)節(jié)點(diǎn)睦优，則removeLast在功能上等同于pop渗常。 由于pop將處理更新頭部和尾部引用，因此您只需將此工作交給它汗盘。
3.您繼續(xù)搜索下一個(gè)節(jié)點(diǎn)皱碘，直到current.next為nil。這表示當(dāng)前是列表的最后一個(gè)節(jié)點(diǎn)隐孽。
4.由于current是最后一個(gè)節(jié)點(diǎn)癌椿，因此只需使用prev.next引用將其斷開(kāi)即可健蕊。 還要確保更新尾部參考。
example(of: "removing the last node") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("移除最后一個(gè)節(jié)點(diǎn)之前: \(list)")
let removedValue = list.removeLast()
print("移除最后一個(gè)節(jié)點(diǎn)之后: \(list)")
print("移除的值: " + String(describing: removedValue))
}
輸出值
移除最后一個(gè)節(jié)點(diǎn)之前: 1 -> 2 -> 3
移除最后一個(gè)節(jié)點(diǎn)之后: 1 -> 2
移除的值: Optional(3)
removeLast需要一直遍歷列表踢俄。 這樣做性能極地, 后面改進(jìn)
3. remove（at :)：刪除列表中任何位置的值缩功。
刪除操作是刪除列表中特定節(jié)點(diǎn)。 這很像在任意位置插入一個(gè)節(jié)點(diǎn); 首先在要?jiǎng)h除的節(jié)點(diǎn)之前找到該節(jié)點(diǎn)都办，然后取消引用嫡锌。
@discardableResult
public mutating func remove(after node: Node<Value>) -> Value? {
defer {
if node.next === tail {
tail = node
}
node.next = node.next?.next
}
return node.next?.value
}
playground 輸入
example(of: "removing a node after a particular node") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("Before removing at particular index: \(list)")
let index = 1
let node = list.node(at: index - 1)!
let removedValue = list.remove(after: node)
print("After removing at index \(index): \(list)")
print("Removed value: " + String(describing: removedValue))
}
Before removing at particular index: 1 -> 2 -> 3
After removing at index 1: 1 -> 3
Removed value: Optional(2)
Swift 集合協(xié)議 在鏈表中的使用
Swift標(biāo)準(zhǔn)庫(kù)有一組協(xié)議，可幫助定義特定的類型琳钉。 這些協(xié)議中的每一個(gè)都對(duì)特性和性能提供了某些保證世舰。 在這些協(xié)議集中，有四個(gè)被稱為集合協(xié)議槽卫。
- Sequence : 序列類型提供對(duì)其元素的順序訪問(wèn)
- Collection: 集合類型是一種提供額外保證的序列類型。集合類型是有限的胰蝠，允許重復(fù)的非破壞性順序訪問(wèn)歼培。
- Bidirectional Colllection 雙向集合: 集合類型可以是雙向集合類型，可以允許在序列中上下雙向移動(dòng)茸塞。 這對(duì)于鏈表是不可能的躲庄，因?yàn)槟阒荒軓念^到尾，而不是相反钾虐。
- RandomAccessCollection: 如果它可以保證訪問(wèn)特定索引處的元素將花費(fèi)與訪問(wèn)任何其他索引處的元素一樣長(zhǎng)的時(shí)間噪窘。該雙向集合類型就是隨機(jī)訪問(wèn)集合類型， 這對(duì)于鏈表來(lái)說(shuō)是不可能的效扫，因?yàn)樵L問(wèn)列表前面附近的節(jié)點(diǎn)比列表下方的節(jié)點(diǎn)快得多倔监。
so, 鏈表可以適用于Swift集合協(xié)議中的兩個(gè)。
首先菌仁，由于鏈表是一組序列浩习，采用Sequence協(xié)議是可以的。 其次济丘，由于鏈表是有限序列谱秽，因此采用Collection協(xié)議是可以的。
變成Swift集合
如何實(shí)現(xiàn)Collection協(xié)議摹迷。 集合類型是有限序列疟赊，并提供非破壞性順序訪問(wèn)。 Swift Collection還允許通過(guò)下標(biāo)進(jìn)行訪問(wèn), 使用索引可以映射到集合中的值峡碉。
自定義集合的索引(Custom collection indexes)
衡量Collection協(xié)議方法性能的指標(biāo)是Index映射到值的速度近哟。 與其他存儲(chǔ)類型（如Swift Array）不同，鏈表無(wú)法使用整數(shù)索引實(shí)現(xiàn)O（1）下標(biāo)操作鲫寄。 因此椅挣，自定義下標(biāo)是定義包含對(duì)其各自節(jié)點(diǎn)的引用的索引头岔。
實(shí)現(xiàn)集合協(xié)議
extension LinkedList: Collection {
public struct Index: Comparable {
public var node: Node<Value>?
// 1. 自定義結(jié)構(gòu)體不能進(jìn)行==操作, 接受Comparable協(xié)議, 并實(shí)現(xiàn)方法
static public func ==(lhs: Index, rhs: Index) -> Bool {
switch (lhs.node, rhs.node) {
case let (left?, right?):
return left.next === right.next
case (nil, nil):
return true
default:
return false
}
}
// 2. 第一個(gè)參數(shù)是否小于第二個(gè)參數(shù)
static public func <(lhs: Index, rhs: Index) -> Bool {
// 如果相等, 返回false, 否則繼續(xù)
guard lhs != rhs else {
return false
}
// 3. 從鏈表的一個(gè)節(jié)點(diǎn)移動(dòng)到根節(jié)點(diǎn)
/**
* sequence函數(shù)式以first值為開(kāi)始, 依次返回每一個(gè)元素, 方法體里面是對(duì)這個(gè)元素操作之后的結(jié)果, 每次返回的nodes都會(huì)執(zhí)行contains操作
* 雖然contains是在sequence方法之后, 但是執(zhí)行順序是沒(méi)執(zhí)行一次sequence方法, 緊接著執(zhí)行contains, 再執(zhí)行sequence, 再執(zhí)行contains, 以此類推, 直到contains滿足條件, 退出序列
*/
// 從lhs節(jié)點(diǎn)開(kāi)始一直遍歷到尾部節(jié)點(diǎn)
let nodes = sequence(first: lhs.node) {
$0?.next
}
// 4. 循環(huán)遍歷所有的節(jié)點(diǎn), 判斷是否包含rhs.node (=== 等價(jià), 檢測(cè)兩個(gè)常量或者變量是否引用同一個(gè)實(shí)例)
// 因?yàn)轭愂且妙愋停锌赡苡卸鄠€(gè)常量和變量在幕后同時(shí)引用同一個(gè)類實(shí)例鼠证。（對(duì)于結(jié)構(gòu)體和枚舉來(lái)說(shuō)峡竣，這并不成立。因?yàn)樗鼈冏鳛橹殿愋土烤牛诒毁x予到常量适掰、變量或者傳遞到函數(shù)時(shí)，其值總是會(huì)被拷貝荠列。）
// 判斷從lhs開(kāi)始一直到尾部節(jié)點(diǎn), 是否包含 === rhs的節(jié)點(diǎn)值, 如果存在, 則說(shuō)明, lhs > rhs, 否則 lhs < rhs
return nodes.contains {
$0 === rhs.node
}
}
}
// ## --- 以下四個(gè)是實(shí)現(xiàn)Collection協(xié)議
// 1 頭結(jié)點(diǎn)
public var startIndex: Index {
return Index(node: head)
}
// 2 尾部節(jié)點(diǎn)
public var endIndex: Index {
return Index(node: tail?.next)
}
// 3 提供下一個(gè)節(jié)點(diǎn)的索引
public func index(after i: Index) -> Index {
return Index(node: i.node?.next)
}
// 4 下標(biāo)用于將索引映射到集合中的值类浪。 已經(jīng)創(chuàng)建了自定義索引，因此可以通過(guò)引用節(jié)點(diǎn)的值輕松地在恒定時(shí)間內(nèi)實(shí)現(xiàn)此目的肌似。
public subscript(position: Index) -> Value {
return position.node!.value
}
}
playground 輸入
example(of: "using collection") {
var list = LinkedList<Int>()
for i in 0...9 {
list.append(i)
}
print("鏈表: \(list)")
print("第一個(gè)元素: \(list[list.startIndex])")
print("前三個(gè)元素: \(Array(list.prefix(3)))")
print("后三個(gè)元素: \(Array(list.suffix(3)))")
let sum = list.reduce(0, +)
print("求和: \(sum)")
}
鏈表: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
第一個(gè)元素: 0
前三個(gè)元素: [0, 1, 2]
后三個(gè)元素: [7, 8, 9]
求和: 45
