鏈表簡單的來說就是一條鏈子, 鐵鏈子大家都知道, 環(huán)環(huán)相扣, 首尾的環(huán)扣空出來, 中間的環(huán)扣, 一個一個的首位相連, 這就是鏈表. 官方的定義是, 一個結構體里面有兩個值, 一個值(value)是存儲當前節(jié)點的值, 一個值(p)是存儲下一個節(jié)點的位置(指針的地址), 最后一個節(jié)點的p沒有值.
鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序實現(xiàn)的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態(tài)生成。每個結點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結點地址的指針域。 相比于線性表順序結構，操作復雜。由于不必須按順序存儲，鏈表在插入的時候可以達到O(1)的復雜度，比另一種線性表順序表快得多，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間，而線性表和順序表相應的時間復雜度分別是O(logn)和O(1)。
如圖所示，鏈表是一系列節(jié)點。 節(jié)點有兩個職責：
1.存儲一個值。
2.保持對下一個節(jié)點的引用。 nil值表示列表的結尾。
理論上我覺得理解起來還是不難的, 當初老師教的時候也聽懂了, 但是用C語言寫的時候, 那個是一臉的蒙圈, 現(xiàn)在想想, C語言的指針雖然靈活, 但是理解起來還是挺繞的, 無形的給學習數(shù)據(jù)結構增加了難度.
Open
新建一個playground, 然后打開source新建一個Helpers.swift文件, 鍵入一下代碼
public func example(of description: String, action: () -> Void) {
print("---Example of \(description)---")
action()
print()
}
這里注意函數(shù)前面一定要加 public , 否則在playground中會找不到該方法.
該方法的參數(shù)是一個閉包, 是為了方便我們打印輸出log
Next
接下來在playground的source里面新建一個Node.swift, 這個文件是用來存儲節(jié)點數(shù)據(jù)的.
/// 這個是一個泛型類型, value 存儲值, next 存儲指向下一個節(jié)點, 為可選類型, 因為最后一個節(jié)點的下一個節(jié)點為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 標準庫的一個協(xié)議, 這個協(xié)議的作用就是自定義打印輸出的內容
extension Node: CustomStringConvertible {
public var description: String {
/// 使用 guard 進行 next為空值的判斷, 如果為空, 則不指向下一個節(jié)點
guard let next = next else {
return "\(value)"
}
return "\(value) -> " + String(describing: next) + " "
}
}
回到playground, 創(chuàng)建節(jié)點
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
這個鏈表使用起來不夠方便, 每添加一個節(jié)點, 還需要手動的去指向下一個節(jié)點, 正常的因該是, 不關心內部怎么關聯(lián), 使用者只需要添加刪除就可以了, 就像數(shù)組一樣.
提供管理Node對象的接口。 向鏈表添加值有三種方法，每種方法都有自己獨特的性能特征：
- push：在列表的前面添加一個值。
- append：在列表末尾添加一個值。
- insert（after :)：在列表的特定節(jié)點之后添加一個值。
push
public struct LinkedList<Value> {
public var head: Node<Value>?
public var tail: Node<Value>?
public init() {
}
/// 判斷鏈表是否為空
public var isEmpty: Bool {
return head == nil
}
/// 如果鏈表是空的話, 第一個節(jié)點既是頭部也是尾部, push 操作是往頭部插入的, 每次新插入的一個元素都會被放在頭部
/// struct 和enum 的值在內部是不能修改的, 如果要修改需要在方法前面添加 mutating 修飾符
public mutating func push(_ value: Value) {
head = Node(value: value, next: head)
/// 當tail 為nil是, 頭部和尾部是同一個, 這樣當鏈表里面再進來一個值的時候, 新值被賦值給了我head節(jié)點, 舊值被賦值給了tail節(jié)點, 并且新值的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 如果鏈表為空, 先進行push操作, 創(chuàng)建一個新的節(jié)點
if isEmpty {
push(value)
return
}
let node = Node(value: value)
// 2 由于第一步執(zhí)行了push操作, tail 一定可以強制解包成功, 鏈表中的尾部節(jié)點的next賦值為添加的新節(jié)點
tail!.next = node
// 3 把新的節(jié)點的值再賦值給鏈表中的尾部節(jié)點
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 :)。 此操作在列表中的特定位置插入值，并且需要兩個步驟：
1.在列表中查找特定節(jié)點。
2.插入新節(jié)點。
首先，實現(xiàn)代碼以查找要插入值的節(jié)點。
node（at :)將嘗試根據(jù)給定的索引檢索列表中的節(jié)點。 由于您只能從頭節(jié)點訪問列表的節(jié)點，因此您必須進行迭代遍歷。
/// 查找某個位置的node
public func node(at index: Int) -> Node<Value>? {
// 1 由于目前只能從頭結點開始訪問, 先獲取頭結點的值, 并記錄下標
var currentNode = head
var currentIndex = 0
// 2 使用while循環(huán)，將引用向下移動到列表中，直到達到所需的索引。 空列表或越界索引將導致nil返回值。
while currentNode != nil && currentIndex < index {
currentNode = currentNode!.next
currentIndex += 1
}
return currentNode
}
插入一個節(jié)點
// 1 @discardableResult讓調用者忽略此方法的返回值，而編譯器不會向上和向下跳過警告。
@discardableResult
public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {
// 2 如果是尾部節(jié)點, 調用append方法。 這將負責更新尾部。
guard tail !== node else {
append(value)
return tail!
}
// 3 否則，只需將新節(jié)點與列表的其余部分鏈接起來，然后返回新節(jié)點。
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é)點
刪除節(jié)點有三個主要操作:
- 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
- 返回值為一個可選值, 因為, 如果鏈表為空, 則返回值為nil
3.如果刪除成功, 則將頭部指向下一個節(jié)點
4.如果為空, 為節(jié)點置為nil
5.defer 為推遲執(zhí)行, defer 里面的block會在方法體內的代碼執(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：刪除列表末尾的值。
刪除列表的最后一個節(jié)點有點不方便。 盡管您有對尾節(jié)點的引用，但如果沒有引用它之前的節(jié)點，則無法將其刪除。 因此，你將不得不進行遍歷。
//#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，則無需移除任何東西，因此您返回nil。
2.如果列表只包含一個節(jié)點，則removeLast在功能上等同于pop。 由于pop將處理更新頭部和尾部引用，因此您只需將此工作交給它。
3.您繼續(xù)搜索下一個節(jié)點，直到current.next為nil。這表示當前是列表的最后一個節(jié)點。
4.由于current是最后一個節(jié)點，因此只需使用prev.next引用將其斷開即可。 還要確保更新尾部參考。
example(of: "removing the last node") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("移除最后一個節(jié)點之前: \(list)")
let removedValue = list.removeLast()
print("移除最后一個節(jié)點之后: \(list)")
print("移除的值: " + String(describing: removedValue))
}
輸出值
移除最后一個節(jié)點之前: 1 -> 2 -> 3
移除最后一個節(jié)點之后: 1 -> 2
移除的值: Optional(3)
removeLast需要一直遍歷列表。 這樣做性能極地, 后面改進
3. remove（at :)：刪除列表中任何位置的值。
刪除操作是刪除列表中特定節(jié)點。 這很像在任意位置插入一個節(jié)點; 首先在要刪除的節(jié)點之前找到該節(jié)點，然后取消引用。
@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標準庫有一組協(xié)議，可幫助定義特定的類型。 這些協(xié)議中的每一個都對特性和性能提供了某些保證。 在這些協(xié)議集中，有四個被稱為集合協(xié)議。
- Sequence : 序列類型提供對其元素的順序訪問
- Collection: 集合類型是一種提供額外保證的序列類型。集合類型是有限的，允許重復的非破壞性順序訪問。
- Bidirectional Colllection 雙向集合: 集合類型可以是雙向集合類型，可以允許在序列中上下雙向移動。 這對于鏈表是不可能的，因為你只能從頭到尾，而不是相反。
- RandomAccessCollection: 如果它可以保證訪問特定索引處的元素將花費與訪問任何其他索引處的元素一樣長的時間。該雙向集合類型就是隨機訪問集合類型， 這對于鏈表來說是不可能的，因為訪問列表前面附近的節(jié)點比列表下方的節(jié)點快得多。
so, 鏈表可以適用于Swift集合協(xié)議中的兩個。
首先，由于鏈表是一組序列，采用Sequence協(xié)議是可以的。 其次，由于鏈表是有限序列，因此采用Collection協(xié)議是可以的。
變成Swift集合
如何實現(xiàn)Collection協(xié)議。 集合類型是有限序列，并提供非破壞性順序訪問。 Swift Collection還允許通過下標進行訪問, 使用索引可以映射到集合中的值。
自定義集合的索引(Custom collection indexes)
衡量Collection協(xié)議方法性能的指標是Index映射到值的速度。 與其他存儲類型（如Swift Array）不同，鏈表無法使用整數(shù)索引實現(xiàn)O（1）下標操作。 因此，自定義下標是定義包含對其各自節(jié)點的引用的索引。
實現(xiàn)集合協(xié)議
extension LinkedList: Collection {
public struct Index: Comparable {
public var node: Node<Value>?
// 1. 自定義結構體不能進行==操作, 接受Comparable協(xié)議, 并實現(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. 第一個參數(shù)是否小于第二個參數(shù)
static public func <(lhs: Index, rhs: Index) -> Bool {
// 如果相等, 返回false, 否則繼續(xù)
guard lhs != rhs else {
return false
}
// 3. 從鏈表的一個節(jié)點移動到根節(jié)點
/**
* sequence函數(shù)式以first值為開始, 依次返回每一個元素, 方法體里面是對這個元素操作之后的結果, 每次返回的nodes都會執(zhí)行contains操作
* 雖然contains是在sequence方法之后, 但是執(zhí)行順序是沒執(zhí)行一次sequence方法, 緊接著執(zhí)行contains, 再執(zhí)行sequence, 再執(zhí)行contains, 以此類推, 直到contains滿足條件, 退出序列
*/
// 從lhs節(jié)點開始一直遍歷到尾部節(jié)點
let nodes = sequence(first: lhs.node) {
$0?.next
}
// 4. 循環(huán)遍歷所有的節(jié)點, 判斷是否包含rhs.node (=== 等價, 檢測兩個常量或者變量是否引用同一個實例)
// 因為類是引用類型，有可能有多個常量和變量在幕后同時引用同一個類實例。（對于結構體和枚舉來說，這并不成立。因為它們作為值類型，在被賦予到常量、變量或者傳遞到函數(shù)時，其值總是會被拷貝。）
// 判斷從lhs開始一直到尾部節(jié)點, 是否包含 === rhs的節(jié)點值, 如果存在, 則說明, lhs > rhs, 否則 lhs < rhs
return nodes.contains {
$0 === rhs.node
}
}
}
// ## --- 以下四個是實現(xiàn)Collection協(xié)議
// 1 頭結點
public var startIndex: Index {
return Index(node: head)
}
// 2 尾部節(jié)點
public var endIndex: Index {
return Index(node: tail?.next)
}
// 3 提供下一個節(jié)點的索引
public func index(after i: Index) -> Index {
return Index(node: i.node?.next)
}
// 4 下標用于將索引映射到集合中的值。 已經創(chuàng)建了自定義索引，因此可以通過引用節(jié)點的值輕松地在恒定時間內實現(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("第一個元素: \(list[list.startIndex])")
print("前三個元素: \(Array(list.prefix(3)))")
print("后三個元素: \(Array(list.suffix(3)))")
let sum = list.reduce(0, +)
print("求和: \(sum)")
}
鏈表: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
第一個元素: 0
前三個元素: [0, 1, 2]
后三個元素: [7, 8, 9]
求和: 45
