用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
    }
}

如何查找指定位置的元素

如果查找的位置在前半部分就顺序查找，否则就逆序查找，以顺序查找为例，从首个节点开始，一直取 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
    }
}

如何追加和插入元素

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

插入单个元素

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

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

插入多个元素

若插入的位置为 0 并且 list 长度为 0 时，则直接调用追加多个元素
把多个元素的节点连接起来，连接思路同如何通过一个序列初始化一个 list。并记录下连接起来后的 firstNode 和 lastNode，更新 size 的值
获取插入位置的节点 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
            }
        }
    }
}

删除元素

删除指定位置的元素

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

删除所有元素

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

// MARK: - 删除元素
extension LinkedList {
    /// 删除指定位置的元素
    @discardableResult
    public func remove(at position: Int) -> E {
        if (position >= 0 && position < size){
            let removeNode = node(at: position)
            removeNode.prev?.next = removeNode.next
            removeNode.next?.prev = removeNode.prev
            if (position == 0) {
                firstNode = firstNode.next
            }else if (position == size - 1){
                lastNode = lastNode.prev
            }
            size -= 1
            return removeNode.item
        }else {
            return nil
      }
    }
    /// 删除第一个元素
    @discardableResult
    public func removefirstNode() -> E? {
        if ()
        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
    }
}

实现 Collection 协议

实现 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
        }
    }
}

查找满足特定条件的元素的位置和查找元素的位置

查找满足特定条件的元素的位置
只需要遍历，若遇到满足条件的直接返回 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
        })
    }
}

实现字面量赋值

只需要实现 ExpressibleByArrayLiteral 即可

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

把链表转成数组

利用 map 方法

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

实现 copy

// 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
    }
}

实现自定义打印

只需要实现 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
    }
}

1	// MARK: - 添加元素
2	extension LinkedList {
3	/// 追加单个元素
4	public func append(_ newElement: E) {
5	let newNode = Node(element: newElement, next: nil, prev: lastNode)
6	if lastNode == nil {
7	firstNode = newNode
8	}
9	lastNode?.next = newNode
10	lastNode = newNode
11	size += 1
12	}
13
14	/// 追加多个元素
15	public func append<S>(contentsOf newElements: S) where S : Sequence, E == S.Element {
16	for item in newElements {
17	append(item)
18	}
19	}
20
21	/// 插入单个元素
22	public func insert(_ newElement: E, at i: Int){
23	let newNode = Node(element: newElement, next: nil, prev: nil)
24	if i == 0 && size == 0{
25	firstNode = newNode
26	lastNode = newNode
27	}else {
28	let insertNode = node(at: i)
29	newNode.next = insertNode
30	insertNode.prev = newNode
31	newNode.prev = insertNode.prev
32	insertNode.prev?.next = newNode
33	if i == 0 {
34	firstNode = newNode
35	}
36	}
37	size += 1
38	}
39
40	/// 插入多个元素
41	public func insert<S>(contentsOf newElements: S, at i: Int) where S : Collection, E == S.Element {
42	if i == 0 && size == 0 {
43	append(contentsOf: newElements)
44	}else {
45	let insertNode = node(at: i)
46	var firstNode:Node<E>?
47	var lastNode:Node<E>?
48	for (index,item) in newElements.enumerated() {
49	let newNode = Node(element: item, next: nil, prev: nil)
50	if index == 0 {
51	firstNode = newNode
52	lastNode = newNode
53	}else {
54	newNode.prev = lastNode
55	lastNode?.next = newNode
56	lastNode = newNode
57	}
58	size += 1
59	}
60	firstNode?.prev = insertNode.prev
61	lastNode?.next = insertNode
62	insertNode.prev?.next = firstNode
63	insertNode.prev = lastNode
64	if i == 0 {
65	self.firstNode = firstNode
66	}
67	}
68	}
69	}

1	// MARK: - 实现Collection协议
2	extension LinkedList : Collection {
3	/// 开始位置
4	public var startIndex: Int { return 0 }
5	/// 结束位置
6	public var endIndex: Int { return size }
7	/// 给定位置后面的索引值
8	public func index(after i: Int) -> Int {
9	return i + 1
10	}
11	/// 返回指定的迭代器
12	public func makeIterator() -> Iterator {
13	return Iterator(self)
14	}
15	/// 通过下标存取元素
16	public subscript(position: Int) -> E {
17	get {
18	return node(at: position).item
19	}
20	set {
21	node(at: position).item = newValue
22	}
23	}
24	}
25
26	// MARK: - 迭代器
27	extension LinkedList {
28	public struct Iterator: IteratorProtocol {
29	let list: LinkedList
30	var index: Int
31	private var nextNode:Node<E>?
32	init(_ list: LinkedList) {
33	self.list = list
34	self.index = 0
35	self.nextNode = list.firstNode
36	}
37	/// 获取下一个元素，在for in里若返回nil，则停止循环
38	public mutating func next() -> E? {
39	let item = nextNode?.item
40	nextNode = nextNode?.next
41	return item
42	}
43	}
44	}

1	// MARK: - 通过条件查找位置
2	extension LinkedList {
3	/// 顺序查找
4	public func firstIndex(where predicate: (E) throws -> Bool) rethrows -> Int? {
5	for (index,item) in self.enumerated() {
6	if try predicate(item) {
7	return index
8	}
9	}
10	return nil
11	}
12
13	/// 倒序查找
14	public func lastIndex(where predicate: (E) throws -> Bool) rethrows -> Int? {
15	var prev = lastNode
16	var currentIndex = size - 1
17	while prev != nil {
18	if try predicate(prev!.item) {
19	return currentIndex
20	}
21	currentIndex -= 1
22	prev = prev?.prev
23	}
24	return nil
25	}
26
27	/// 是否包含
28	public func contains(where predicate: (E) throws -> Bool) rethrows -> Bool {
29	for item in self{
30	if try predicate(item) {
31	return true
32	}
33	}
34	return false
35	}
36	}
37	// MARK: - 通过元素查找位置
38	extension LinkedList where E : Equatable {
39	public func firstIndex(of element: E) -> Int? {
40	return firstIndex { (item) -> Bool in
41	return item == element
42	}
43	}
44	public func lastIndex(of element: E) -> Int? {
45	return lastIndex(where: { (item) -> Bool in
46	return item == element
47	})
48	}
49
50	public func contains(_ element: E) -> Bool {
51	return contains(where: { (item) -> Bool in
52	return item == element
53	})
54	}
55	}

1	final public class LinkedList<E> {
2	private var size = 0
3	private var firstNode:Node<E>?
4	private var lastNode:Node<E>?
5
6	/// 初始化一个空list
7	public init() { }
8
9	/// 通过序列初始化一个list
10	public init<S>(_ s: S) where Element == S.Element, S : Sequence {
11	for (index,item) in s.enumerated() {
12	let newNode = Node(element: item)
13	if index == 0 {
14	firstNode = newNode
15	lastNode = newNode
16	}else {
17	newNode.prev = lastNode
18	lastNode?.next = newNode
19	lastNode = newNode
20	}
21	size += 1
22	}
23	}
24	}
25	/// 节点
26	fileprivate class Node<Element> {
27	/// 节点元素的值
28	var item:Element
29	/// 下一个节点
30	var next:Node<Element>?
31	/// 上一个节点
32	var prev:Node<Element>?
33	init(element:Element, next:Node<Element>? = nil, prev:Node<Element>? = nil) {
34	self.item = element
35	self.next = next
36	self.prev = prev
37	}
38	}

1	// MARK: - private
2	extension LinkedList {
3	/// 通过下标找到对应的节点
4	private func node(at index:Int) -> Node<E> {
5	//如果下标位置无效，则直接报错
6	if !indexIsVaild(index) {
7	fatalError("Index out of range:\(index) not belong 0..<\(size)")
8	}
9	//如果节点在前一半顺序查找，否则逆序查找
10	if index < (size >> 1) {
11	var node = firstNode
12	for _ in 0..<index {
13	node = node?.next
14	}
15	return node!
16	}else {
17	var node = lastNode
18	for _ in stride(from: size - 1, to: index, by: -1) {
19	node = node?.prev
20	}
21	return node!
22	}
23	}
24	/// 下标是否是有效的
25	private func indexIsVaild(_ index:Int) -> Bool {
26	return index >= 0 && index < size
27	}
28	}

1	// MARK: - 删除元素
2	extension LinkedList {
3	/// 删除指定位置的元素
4	@discardableResult
5	public func remove(at position: Int) -> E {
6	if (position >= 0 && position < size){
7	let removeNode = node(at: position)
8	removeNode.prev?.next = removeNode.next
9	removeNode.next?.prev = removeNode.prev
10	if (position == 0) {
11	firstNode = firstNode.next
12	}else if (position == size - 1){
13	lastNode = lastNode.prev
14	}
15	size -= 1
16	return removeNode.item
17	}else {
18	return nil
19	}
20	}
21	/// 删除第一个元素
22	@discardableResult
23	public func removefirstNode() -> E? {
24	if ()
25	return firstNode == nil ? nil : remove(at: 0)
26	}
27	/// 删除最后一个元素
28	@discardableResult
29	public func removelastNode() -> E? {
30	return lastNode == nil ? nil : remove(at: size - 1)
31	}
32	/// 删除所有元素
33	public func removeAll() {
34	var next = firstNode
35	while next != nil {
36	let tmp = next
37	next?.next = nil
38	next?.prev = nil
39	next = tmp
40	}
41	firstNode = nil
42	lastNode = nil
43	size = 0
44	}
45	}

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

1	extension LinkedList {
2	public func toArray() -> [E] {
3	return self.map({ (item) -> E in
4	return item
5	})
6	}
7	}

1	// MARK: - Copy
2	extension LinkedList {
3	public func copy() -> LinkedList {
4	let copyList = LinkedList()
5	copyList.size = self.size
6	if let firstNode = firstNode {
7	copyList.firstNode = Node(element: firstNode.item, next: nil, prev: nil)
8	copyList.lastNode = copyList.firstNode
9	}
10	var nextNode = firstNode?.next
11	while nextNode != nil {
12	let newNode = Node(element: nextNode!.item)
13	copyList.lastNode?.next = newNode
14	newNode.prev = copyList.lastNode
15	copyList.lastNode = newNode
16	nextNode = nextNode?.next
17	}
18	return copyList
19	}
20	}

1	extension LinkedList : CustomDebugStringConvertible {
2	public var debugDescription: String {
3	var desc = ""
4	if size > 0 {
5	for item in self.dropLast() {
6	desc += "\(item)-->"
7	}
8	desc += "\(lastNode!.item)"
9	}
10	return desc
11	}
12	}