参考链接

• 基本数据结构：链表（list）

线性表

线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表有两种存储方式，一种是顺序存储结构，另一种是链式存储结构。

顺序存储结构就是两个相邻的元素在内存中也是相邻的。

• 这种存储方式的优点是查询的时间复杂度为O(1)，通过首地址和偏移量就可以直接访问到某元素，

  • 关于查找的适配算法很多，最快可以达到O(logn)。

• 缺点是插入和删除的时间复杂度最坏能达到O(n)，

  • 如果你在第一个位置插入一个元素，你需要把数组的每一个元素向后移动一位，
  • 如果你在第一个位置删除一个元素，你需要把数组的每一个元素向前移动一位。

• 还有一个缺点，就是当你不确定元素的数量时，你开的数组必须保证能够放下元素最大数量，遗憾的是如果实际数量比最大数量少很多时，你开的数组没有用到的内存就只能浪费掉了。

我们常用的数组就是一种典型的顺序存储结构，如图1。

image

链式存储结构就是两个相邻的元素在内存中不是相邻的，每一个元素都有一个指针域，指针域一般是存储着到下一个元素的指针。

• 这种存储方式的优点是插入和删除的时间复杂度为O(1)，
  • 不会浪费太多内存，添加元素的时候才会申请内存，删除元素会释放内存。
• 缺点是访问的时间复杂度最坏为O(n)，
  • 关于查找的算法很少，一般只能遍历，这样时间复杂度也是线性（O(n)）的了，
  • 频繁的申请和释放内存也会消耗时间。

链表就是链式存储的线性表。根据指针域的不同，链表分为单向链表、双向链表、循环链表等等。

一、 单向链表

链表中最简单的一种是单向链表，每个元素包含两个域，值域和指针域，我们把这样的元素称之为节点。每个节点的指针域内有一个指针，指向下一个节点，而最后一个节点则指向一个空值。如图2就是一个单向链表。

img

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

首先我们要写一个节点类，链表中的每一个节点就是一个节点类的对象。如图3。

img

下面是一些必要方法的思路：

delete()函数，删除第一个值为x的节点，如图4。

img

insert()和insertHead()函数，在p节点后插入值为x的节点。如图5。

img

二、 双向链表

双向链表的指针域有两个指针，每个数据结点分别指向直接后继和直接前驱。

• 单向链表只能从表头开始向后遍历，而双向链表不但可以从前向后遍历，也可以从后向前遍历。
• 双向链表的删除的时间复杂度会降为O（1），
  • 因为直接通过目的指针就可以找到前驱节点，单向链表得从表头开始遍历寻找前驱节点。
• 缺点是每个节点多了一个指针的空间开销。

如图6就是一个双向链表。

img

下面是Swift实现：

需要注意Node中prev属性需要设置为weak，否则node间会出现循环引用

public weak var prev: Node?

public struct YYList<T>: Sequence {
    public private(set) var head: Node?
    public private(set) var tail: Node?
    public private(set) var length = 0
    public var isEmpty: Bool { length == 0 }
    
    /// for T in list { $0 }
    public func makeIterator() -> AnyIterator<T> {
        var node = head
        return AnyIterator {
            let value = node?.value
            node = node?.next
            return value
        }
    }
}

public extension YYList {
    mutating func insertHead(_ value: T) {
        insertHead(node: .init(value: value))
    }
    
    mutating func append(_ value: T) {
        append(node: .init(value: value))
    }
    
    @discardableResult
    mutating func pop() -> T? {
        head != nil ? remove(node: head!).value : nil
    }
    
    @discardableResult
    mutating func popLast() -> T? {
        tail != nil ? remove(node: tail!).value : nil
    }
    
    func allValues() -> [T] {
        map { $0 }
    }
    
    func forEachReversed(_ handler: (T) -> Void) {
        var temp = tail
        while temp != nil {
            let current = temp!
            temp = temp?.prev
            /// avoid node.unbind() in handler
            handler(current.value)
        }
    }
    
    mutating func cleanup() {
        head = nil
        tail = nil
        length = 0
    }
}

public extension YYList {
    func echo() {
        print("---echo---")
        forEach { print($0) }
        print("---echo---")
    }
}

// MARK: - Equatable

extension YYList where T: Equatable {
    public func hasValue(_ value: T) -> Bool {
        search(value) != nil
    }
    
    @discardableResult
    public mutating func remove(_ value: T) -> Bool {
        if let node = search(value) {
            remove(node: node)
            return true
        }
        
        return false
    }
    
    func search(_ value: T) -> Node? {
        var temp = head
        while temp != nil {
            if temp!.value == value {
                return temp
            }
            temp = temp?.next
        }
        
        return nil
    }
}

// MARK: - Private

private extension YYList {
    mutating func insertHead(node: Node) {
        node.unbind()
        node.before(head)
        head = node
        if tail == nil {
            tail = node
        }
        length += 1
    }
    
    mutating func append(node: Node) {
        node.unbind()
        node.after(tail)
        tail = node
        if head == nil {
            head = node
        }
        length += 1
    }
    
    @discardableResult
    mutating func remove(node: Node) -> Node {
        node.next?.prev = node.prev
        node.prev?.next = node.next
        
        if node === head {
            head = node.next
        }
        
        if node === tail {
            tail = node.prev
        }
        
        node.cleanup()
        length -= 1
        return node
    }
    
    func travel(_ handler: @escaping (Node) -> Void) {
        var temp = head
        while temp != nil {
            let current = temp!
            temp = temp?.next
            /// avoid node.unbind() in handler
            handler(current)
        }
    }
}

// MARK: - Node

extension YYList {
    public final class Node {
        public let value: T
        /// avoid retain cycle
        public weak var prev: Node?
        public var next: Node?
        
        public init(value: T) {
            self.value = value
        }
        
        public func before(_ node: Node?) {
            node?.prev?.next = self
            prev = node?.prev
            node?.prev = self
            next = node
        }
        
        public func after(_ node: Node?) {
            node?.next?.prev = self
            next = node?.next
            node?.next = self
            prev = node
        }
        
        public func unbind() {
            next = nil
            prev = nil
        }
        
        public func cleanup() {
            unbind()
        }
    }
}

简单测试：

var list = YYList<Int>()
list.append(2)
list.append(4)
list.insertHead(3)
list.insertHead(1)
list.append(5)
list.remove(2)
list.echo() /// 1 3 4 5
list.pop() /// 1
list.echo() /// 3 4 5
list.popLast() /// 5
list.echo() /// 3 4

三、 循环链表

循环链表就是让链表的最后一个节点指向第一个节点，这样就形成了一个圆环，可以循环遍历。单向循环链表可以单向循环遍历，双向循环链表的头节点的指针也要指向最后一个节点，这样的可以双向循环遍历。如图7就是一个双向循环链表。

img