数据结构和算法(二) - 链表

链表简单的来说就是一条链子, 铁链子大家都知道, 环环相扣, 首尾的环扣空出来, 中间的环扣, 一个一个的首位相连, 这就是链表. 官方的定义是, 一个结构体里面有两个值, 一个值(value)是存储当前节点的值, 一个值(p)是存储下一个节点的位置(指针的地址), 最后一个节点的p没有值.

---

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

如图所示，链表是一系列节点。 节点有两个职责：

屏幕快照 2018-12-04 下午9.10.18.png

1.存储一个值。
2.保持对下一个节点的引用。 nil值表示列表的结尾。

理论上我觉得理解起来还是不难的, 当初老师教的时候也听懂了, 但是用C语言写的时候, 那个是一脸的蒙圈, 现在想想, C语言的指针虽然灵活, 但是理解起来还是挺绕的, 无形的给学习数据结构增加了难度.

Open

新建一个playground, 然后打开source新建一个Helpers.swift文件, 键入一下代码

public func example(of description: String, action: () -> Void) {
  print("---Example of \(description)---")
  action()
  print()
}

这里注意函数前面一定要加 public , 否则在playground中会找不到该方法.
该方法的参数是一个闭包, 是为了方便我们打印输出log

Next

接下来在playground的source里面新建一个Node.swift, 这个文件是用来存储节点数据的.

/// 这个是一个泛型类型, value 存储值, next 存储指向下一个节点, 为可选类型, 因为最后一个节点的下一个节点为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 标准库的一个协议, 这个协议的作用就是自定义打印输出的内容
extension Node: CustomStringConvertible {
    public var description: String {
        ///  使用 guard 进行 next为空值的判断, 如果为空, 则不指向下一个节点
        guard let next = next else {
            return "\(value)"
        }
        return "\(value) -> " + String(describing: next) + " "
    }
}

回到playground, 创建节点

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  

屏幕快照 2018-12-04 下午9.31.34.png

这个链表使用起来不够方便, 每添加一个节点, 还需要手动的去指向下一个节点, 正常的因该是, 不关心内部怎么关联, 使用者只需要添加删除就可以了, 就像数组一样.

提供管理Node对象的接口。 向链表添加值有三种方法，每种方法都有自己独特的性能特征：

1. push：在列表的前面添加一个值。
2. append：在列表末尾添加一个值。
3. insert（after :)：在列表的特定节点之后添加一个值。

push

public struct LinkedList<Value> {
    public var head: Node<Value>?
    public var tail: Node<Value>?
    public init() {
        
    }
    /// 判断链表是否为空
    public var isEmpty: Bool {
        return head == nil
    }
    
    /// 如果链表是空的话, 第一个节点既是头部也是尾部, push 操作是往头部插入的, 每次新插入的一个元素都会被放在头部
    /// struct 和enum 的值在内部是不能修改的, 如果要修改需要在方法前面添加 mutating 修饰符
    public mutating func push(_ value: Value) {
        head = Node(value: value, next: head)
        /// 当tail 为nil是, 头部和尾部是同一个, 这样当链表里面再进来一个值的时候, 新值被赋值给了我head节点, 旧值被赋值给了tail节点, 并且新值的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操作, 创建一个新的节点
        if isEmpty {
            push(value)
            return
        }
        let node = Node(value: value)
        // 2 由于第一步执行了push操作, tail 一定可以强制解包成功, 链表中的尾部节点的next赋值为添加的新节点
        tail!.next = node
        
        // 3 把新的节点的值再赋值给链表中的尾部节点
        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.在列表中查找特定节点。
2.插入新节点。
首先，实现代码以查找要插入值的节点。

node（at :)将尝试根据给定的索引检索列表中的节点。 由于您只能从头节点访问列表的节点，因此您必须进行迭代遍历。

/// 查找某个位置的node
    public func node(at index: Int) -> Node<Value>? {
        // 1 由于目前只能从头结点开始访问, 先获取头结点的值, 并记录下标
        var currentNode = head
        var currentIndex = 0
        // 2 使用while循环，将引用向下移动到列表中，直到达到所需的索引。 空列表或越界索引将导致nil返回值。
        while currentNode != nil && currentIndex < index {
            currentNode = currentNode!.next
            currentIndex += 1
        }
        return currentNode
    }

插入一个节点

    // 1 @discardableResult让调用者忽略此方法的返回值，而编译器不会向上和向下跳过警告。
    @discardableResult
    public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {
        // 2 如果是尾部节点, 调用append方法。 这将负责更新尾部。
        guard tail !== node else {
            append(value)
            return tail!
        }
        // 3 否则，只需将新节点与列表的其余部分链接起来，然后返回新节点。
        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

从链表中移除节点

删除节点有三个主要操作:

1. pop：删除列表前面的值。
2. removeLast：删除列表末尾的值。
3. 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
    }

1. 删除列表最前面的值称为pop
2. 返回值为一个可选值, 因为, 如果链表为空, 则返回值为nil

3.如果删除成功, 则将头部指向下一个节点
4.如果为空, 为节点置为nil
5.defer 为推迟执行, defer 里面的block会在方法体内的代码执行完毕之后, 最后执行

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：删除列表末尾的值。

删除列表的最后一个节点有点不方便。 尽管您有对尾节点的引用，但如果没有引用它之前的节点，则无法将其删除。 因此，你将不得不进行遍历。

 //#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.如果列表只包含一个节点，则removeLast在功能上等同于pop。 由于pop将处理更新头部和尾部引用，因此您只需将此工作交给它。

3.您继续搜索下一个节点，直到current.next为nil。这表示当前是列表的最后一个节点。

4.由于current是最后一个节点，因此只需使用prev.next引用将其断开即可。 还要确保更新尾部参考。

example(of: "removing the last node") {
    var list = LinkedList<Int>()
    list.push(3)
    list.push(2)
    list.push(1)
    
    print("移除最后一个节点之前: \(list)")
    let removedValue = list.removeLast()
    print("移除最后一个节点之后: \(list)")
    print("移除的值: " + String(describing: removedValue))
    
}

输出值

移除最后一个节点之前: 1 -> 2 -> 3  
移除最后一个节点之后: 1 -> 2 
移除的值: Optional(3)

removeLast需要一直遍历列表。 这样做性能极地, 后面改进

3. remove（at :)：删除列表中任何位置的值。

删除操作是删除列表中特定节点。 这很像在任意位置插入一个节点; 首先在要删除的节点之前找到该节点，然后取消引用。

屏幕快照 2018-12-09 下午8.47.06.png

@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 集合协议 在链表中的使用

Swift标准库有一组协议，可帮助定义特定的类型。 这些协议中的每一个都对特性和性能提供了某些保证。 在这些协议集中，有四个被称为集合协议。

1. Sequence : 序列类型提供对其元素的顺序访问
2. Collection: 集合类型是一种提供额外保证的序列类型。集合类型是有限的，允许重复的非破坏性顺序访问。
3. Bidirectional Colllection 双向集合: 集合类型可以是双向集合类型，可以允许在序列中上下双向移动。 这对于链表是不可能的，因为你只能从头到尾，而不是相反。
4. RandomAccessCollection: 如果它可以保证访问特定索引处的元素将花费与访问任何其他索引处的元素一样长的时间。该双向集合类型就是随机访问集合类型， 这对于链表来说是不可能的，因为访问列表前面附近的节点比列表下方的节点快得多。

so, 链表可以适用于Swift集合协议中的两个。
首先，由于链表是一组序列，采用Sequence协议是可以的。 其次，由于链表是有限序列，因此采用Collection协议是可以的。

变成Swift集合

如何实现Collection协议。 集合类型是有限序列，并提供非破坏性顺序访问。 Swift Collection还允许通过下标进行访问, 使用索引可以映射到集合中的值。

自定义集合的索引(Custom collection indexes)

衡量Collection协议方法性能的指标是Index映射到值的速度。 与其他存储类型（如Swift Array）不同，链表无法使用整数索引实现O（1）下标操作。 因此，自定义下标是定义包含对其各自节点的引用的索引。

实现集合协议

extension LinkedList: Collection {

    public struct Index: Comparable {

        public var node: Node<Value>?
        
        // 1. 自定义结构体不能进行==操作, 接受Comparable协议, 并实现方法
        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. 第一个参数是否小于第二个参数
        static public func <(lhs: Index, rhs: Index) -> Bool {
            // 如果相等, 返回false, 否则继续
            guard lhs != rhs else {
                return false
            }
            // 3.  从链表的一个节点移动到根节点
            /**
             * sequence函数式以first值为开始, 依次返回每一个元素, 方法体里面是对这个元素操作之后的结果, 每次返回的nodes都会执行contains操作
             * 虽然contains是在sequence方法之后, 但是执行顺序是没执行一次sequence方法, 紧接着执行contains, 再执行sequence, 再执行contains, 以此类推, 直到contains满足条件, 退出序列
             */
            // 从lhs节点开始一直遍历到尾部节点
            let nodes = sequence(first: lhs.node) {
                $0?.next
            }
            // 4. 循环遍历所有的节点, 判断是否包含rhs.node (=== 等价, 检测两个常量或者变量是否引用同一个实例)
            // 因为类是引用类型，有可能有多个常量和变量在幕后同时引用同一个类实例。（对于结构体和枚举来说，这并不成立。因为它们作为值类型，在被赋予到常量、变量或者传递到函数时，其值总是会被拷贝。）
            // 判断从lhs开始一直到尾部节点, 是否包含 === rhs的节点值, 如果存在, 则说明, lhs > rhs, 否则 lhs < rhs
            return nodes.contains {
                $0 === rhs.node
            }
        }
    }
    // ## --- 以下四个是实现Collection协议

    // 1 头结点
    public var startIndex: Index {
        return Index(node: head)
    }

    // 2 尾部节点
    public var endIndex: Index {
        return Index(node: tail?.next)
    }

    // 3  提供下一个节点的索引
    public func index(after i: Index) -> Index {
        return Index(node: i.node?.next)
    }

    // 4 下标用于将索引映射到集合中的值。 已经创建了自定义索引，因此可以通过引用节点的值轻松地在恒定时间内实现此目的。
    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