用Swift实现LinkedList（双向链表结构的集合）

1. 什么是双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。 所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。---维基百科

2. 集合有哪些功能

• 添加元素
• 删除元素
• 更新元素
• 查找元素
• 查找元素的位置

3. 文章中要实现的功能

• 2中的特性
• for in 遍历
• 通过下标进行取值赋值
  *[字面量赋值
• 把集合转成数组
• 复制
• 自定义打印

4.未实现的功能

• 未把list定义成结构体
• 若把list改成结构体则,未实现写时复制

原因:为了了解Swift中的集合以及学习链表，所以就简单的来了。

5. 如何实现

定义链表结构如下

• size代表链表的长度
• firstNode 表示第一个节点
• lastNode 表示最后一个节点
• Node 表示节点的类型
• 通过序列初始化list
  1. 遍历序列，通过序列里的值生成节点newNode。
  2. 遍历到首个元素时，让firstNode和lastNode都指向newNode
  3. 遍历到其他元素时,把lastNode的next指向newNode，把newNode的prev指向lastNode,最后把lastNode指向newNode
  4. 每次遍历都把size += 1

final public class LinkedList<E>  {
    private var size = 0
    private var firstNode:Node<E>?
    private var lastNode:Node<E>?
    
    /// 初始化一个空list
    public init() { }
    
     /// 通过序列初始化一个list
    public init<S>(_ s: S) where Element == S.Element, S : Sequence {
        for (index,item) in s.enumerated() {
            let newNode = Node(element: item)
            if index == 0 {
                firstNode = newNode
                lastNode = newNode
            }else {
                newNode.prev = lastNode
                lastNode?.next = newNode
                lastNode = newNode
            }
            size += 1
        }
    }
}
/// 节点
fileprivate class Node<Element> {
    /// 节点元素的值
    var item:Element
    /// 下一个节点
    var next:Node<Element>?
    /// 上一个节点
    var prev:Node<Element>?
    init(element:Element, next:Node<Element>? = nil, prev:Node<Element>? = nil) {
        self.item = element
        self.next = next
        self.prev = prev
    }
}

<span id="search">如何查找指定位置的元素</span>

如果查找的位置在前半部分就顺序查找，否则就逆序查找，以顺序查找为例，从首个节点开始，一直取next节点，直到要查找的位置。在查找之前首先要判断查找的位置是有效的，即index>=0 && index < size。

由于对使用者来说并不关心节点，只关心节点里的值，而且也不允许使用者修改节点的前后节点，所以对外暴露的是对外节点里的值，而不是节点。所以下面的方法定义为私有的。在文章的下面利用下标来进行取值和赋值

// MARK: - private
extension LinkedList {
    /// 通过下标找到对应的节点
    private func node(at index:Int) -> Node<E> {
        //如果下标位置无效，则直接报错
        if !indexIsVaild(index) {
            fatalError("Index out of range:\(index) not belong 0..<\(size)")
        }
        //如果节点在前一半顺序查找，否则逆序查找
        if index < (size >> 1) {
            var node = firstNode
            for _ in 0..<index {
                node = node?.next
            }
            return node!
        }else {
            var node = lastNode
            for _ in stride(from: size - 1, to: index, by: -1) {
                node = node?.prev
            }
            return node!
        }
    }
    /// 下标是否是有效的
    private func indexIsVaild(_ index:Int) -> Bool {
        return index >= 0 && index < size
    }
}

<span id="add">如何追加和插入元素</span>

追加单个元素
只需要把lastNode的next指向要追加的节点，把要追加的节点的prev指向lastNode,最后把lastNode指向要追加的节点，并且把size+1。若追加时list为空，需要把firstNode也指向要追加的节点

插入单个元素

1. 若插入的位置为0并且list长度为0时，直接把firstNode和lastNode都指向newNode；
2. 获取插入位置的节点insertNode,把newNode的next指向要insertNode，把insertNode的prev指向newNode，把newNode的prev指向要insertNode的prev，把insertNode的prev的next指向newNode，若插入的位置为0，则把firstNode指向newNode，更新size的值

追加多个元素
只需要依次追加单个元素即可

插入多个元素

1. 若插入的位置为0并且list长度为0时，则直接调用追加多个元素
2. 把多个元素的节点连接起来，连接思路同如何通过一个序列初始化一个list。并记录下连接起来后的firstNode和lastNode，更新size的值
3. 获取插入位置的节点insertNode,把lastNode的next指向insertNode，把insertNode的prev指向lastNode，把firstNode的prev指向要insertNode的prev，把insertNode的prev的next指向firstNode。若插入的位置为0，则把list的firstNode指向firstNode

// MARK: - 添加元素
extension LinkedList {
    /// 追加单个元素
    public func append(_ newElement: E) {
        let newNode = Node(element: newElement, next: nil, prev: lastNode)
        if lastNode == nil {
            firstNode = newNode
        }
        lastNode?.next = newNode
        lastNode = newNode
        size += 1
    }
    
    /// 追加多个元素
    public func append<S>(contentsOf newElements: S) where S : Sequence, E == S.Element {
        for item in newElements {
            append(item)
        }
    }
    
    /// 插入单个元素
    public func insert(_ newElement: E, at i: Int){
        let newNode = Node(element: newElement, next: nil, prev: nil)
        if i == 0 && size == 0{
            firstNode = newNode
            lastNode = newNode
        }else {
            let insertNode = node(at: i)
            newNode.next = insertNode
            insertNode.prev = newNode
            newNode.prev = insertNode.prev
            insertNode.prev?.next = newNode
            if i == 0 {
                firstNode = newNode
            }
        }
        size += 1
    }
    
    /// 插入多个元素
    public func insert<S>(contentsOf newElements: S, at i: Int) where S : Collection, E == S.Element {
        if i == 0 && size == 0 {
            append(contentsOf: newElements)
        }else {
            let insertNode = node(at: i)
            var firstNode:Node<E>?
            var lastNode:Node<E>?
            for (index,item) in newElements.enumerated() {
                let newNode = Node(element: item, next: nil, prev: nil)
                if index == 0 {
                    firstNode = newNode
                    lastNode = newNode
                }else {
                    newNode.prev = lastNode
                    lastNode?.next = newNode
                    lastNode = newNode
                }
                size += 1
            }
            firstNode?.prev = insertNode.prev
            lastNode?.next = insertNode
            insertNode.prev?.next = firstNode
            insertNode.prev = lastNode
            if i == 0 {
                self.firstNode = firstNode
            }
        }
    }
}

<span id="remove">删除元素</span>

删除指定位置的元素

1. 获取指定位置的元素removeNode
2. 把removeNode的prev的next指向removeNode的next
3. 把removeNode的netx的prev指向removeNode的prev
4. 把size -= 1

删除所有元素

1. 获取首个节点node
2. 若node不为空，取node的next为tmp，然后node的next和prev置nil
3. 把node指向tmp，重复第二步

// MARK: - 删除元素
extension LinkedList {
    /// 删除指定位置的元素
    @discardableResult
    public func remove(at position: Int) -> E {
        let removeNode = node(at: position)
        removeNode.prev?.next = removeNode.next
        removeNode.next?.prev = removeNode.prev
        size -= 1
        return removeNode.item
    }
    /// 删除第一个元素
    @discardableResult
    public func removefirstNode() -> E? {
        return firstNode == nil ? nil : remove(at: 0)
    }
    /// 删除最后一个元素
    @discardableResult
    public func removelastNode() -> E? {
        return lastNode == nil ? nil : remove(at: size - 1)
    }
    /// 删除所有元素
    public func removeAll() {
        var next = firstNode
        while next != nil {
            let tmp = next
            next?.next = nil
            next?.prev = nil
            next = tmp
        }
        firstNode = nil
        lastNode = nil
        size = 0
    }
}

<span id="collection">实现Collection协议</span>

实现Collection协议，就能拥有Collection协议里的方法。Collection协议里有很多方法，如isEmpty,count,map,filter,dropLast...等方法
Collection参考喵神翻译的书swift进阶第2章这里不详细介绍了

for in 遍历的原理是，本质是遍历一个迭代器，一直取next，而实现Collection协议时，已经返回了一个迭代器，所以实现Collection协议之后已经实现了for in ,forEach遍历

链表的迭代器：从首个元素可以，一直遍历next，直到next为nil

如何实现Collection协议
需要实现以下方法

• public var startIndex: Int { get } 开始位置
• public var endIndex: Int { get } 结束位置
• public func index(after i: Int) -> Int 给定位置后面的索引值
• public func makeIterator() -> Iterator 遍历时需要的迭代器
• public subscript(position: Int) -> E 通过下标存取元素

// MARK: - 实现Collection协议
extension LinkedList : Collection {
    /// 开始位置
    public var startIndex: Int {  return 0 }
    /// 结束位置
    public var endIndex: Int { return size }
    /// 给定位置后面的索引值
    public func index(after i: Int) -> Int {
        return i + 1
    }
    /// 返回指定的迭代器
    public func makeIterator() -> Iterator {
        return Iterator(self)
    }
    /// 通过下标存取元素
    public subscript(position: Int) -> E {
        get {
            return node(at: position).item
        }
        set {
            node(at: position).item = newValue
        }
    }
}

// MARK: - 迭代器
extension LinkedList {
    public struct Iterator: IteratorProtocol {
        let list: LinkedList
        var index: Int
        private var nextNode:Node<E>?
        init(_ list: LinkedList) {
            self.list = list
            self.index = 0
            self.nextNode = list.firstNode
        }
        /// 获取下一个元素，在for in里若返回nil，则停止循环
        public mutating func next() -> E? {
            let item = nextNode?.item
            nextNode = nextNode?.next
            return item
        }
    }
}

<span id="searchIndex">查找满足特定条件的元素的位置和查找元素的位置</span>

查找满足特定条件的元素的位置
只需要遍历，若遇到满足条件的直接返回index

查找元素的位置
其实就是满足要元素和列表的某一元素相等，所有需要元素遵循Equatable协议，然后调用查找满足特定条件的元素的位置的方法即可

// MARK: - 通过条件查找位置
extension LinkedList {
    /// 顺序查找
    public func firstIndex(where predicate: (E) throws -> Bool) rethrows -> Int? {
        for (index,item) in self.enumerated() {
            if try predicate(item) {
                return index
            }
        }
        return nil
    }
    
    /// 倒序查找
    public func lastIndex(where predicate: (E) throws -> Bool) rethrows -> Int? {
        var prev = lastNode
        var currentIndex = size - 1
        while prev != nil {
            if try predicate(prev!.item) {
                return currentIndex
            }
            currentIndex -= 1
            prev = prev?.prev
        }
        return nil
    }
    
    /// 是否包含
    public func contains(where predicate: (E) throws -> Bool) rethrows -> Bool {
        for item in self{
            if try predicate(item) {
                return true
            }
        }
        return false
    }
}
// MARK: - 通过元素查找位置
extension LinkedList where E : Equatable {
    public func firstIndex(of element: E) -> Int? {
        return firstIndex { (item) -> Bool in
            return item == element
        }
    }
    public func lastIndex(of element: E) -> Int? {
        return lastIndex(where: { (item) -> Bool in
            return item == element
        })
    }
    
    public func contains(_ element: E) -> Bool {
        return contains(where: { (item) -> Bool in
            return item == element
        })
    }
}

<span id="literal">实现字面量赋值</span>

只需要实现ExpressibleByArrayLiteral即可

extension LinkedList : ExpressibleByArrayLiteral {
    public convenience init(arrayLiteral elements: E...) {
        //这里是调用通过序列初始化链表
        self.init(elements)
    }
}

<span id="toArray">把链表转成数组</span>

利用map方法

extension LinkedList {
    public func toArray() -> [E] {
        return self.map({ (item) -> E in
            return item
        })
    }
}

<span id="copy">实现copy</span>

// MARK: - Copy
extension LinkedList {
    public func copy() -> LinkedList {
        let copyList = LinkedList()
        copyList.size = self.size
        if let firstNode = firstNode {
            copyList.firstNode = Node(element: firstNode.item, next: nil, prev: nil)
            copyList.lastNode = copyList.firstNode
        }
        var nextNode = firstNode?.next
        while nextNode != nil {
            let newNode = Node(element: nextNode!.item)
            copyList.lastNode?.next = newNode
            newNode.prev = copyList.lastNode
            copyList.lastNode = newNode
            nextNode = nextNode?.next
        }
        return copyList
    }
}

<span id="print">实现自定义打印</span>

只需要实现CustomDebugStringConvertible即可

extension LinkedList : CustomDebugStringConvertible {
    public var debugDescription: String {
        var desc = ""
        if size > 0 {
            for item in self.dropLast() {
                desc += "\(item)-->"
            }
            desc += "\(lastNode!.item)"
        }
        return desc
    }
}

demo地址