与数组一样，链表也是存储元素的集合。
链表的分类
单向链表
单向链表的节点存储了下一个节点的地址。如下图：
+--------+ +--------+ +--------+ +--------+
| | | | | | | |
| node 0 |--->| node 1 |--->| node 2 |--->| node 3 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
双向链表
双向链表的节点存储了上一个和下一个节点的地址。如下图：
+--------+ +--------+ +--------+ +--------+
| |--->| |--->| |--->| |
| node 0 | | node 1 | | node 2 | | node 3 |
| |<---| |<---| |<---| |
+--------+ +--------+ +--------+ +--------+
单向链表和双向链表的对比
单向链表占用更少的内存，因为它不用存储上一个节点的地址；但如果我们需要访问上一个节点，单向链表会非常麻烦，需要从头开始找，而双向链表会非常容易。很多情况下，双向链表会比较容易使用。
链表的实现
这里我们以单向链表为例。
LinkedListNode
因为链表是由一系列的节点组成，所以我们先要定义一个节点类型。
final class LinkedListNode<T> {
var value: T
var next: LinkedListNode?
init(value: T, next: LinkedListNode? = nil) {
self.value = value
self.next = next
}
}
extension LinkedListNode: CustomStringConvertible {
var description: String {
guard let next = next else { return "\(value)" }
return "\(value) -> \(String(describing: next)) "
}
}
把节点定义为泛型，这样可以存储任何类型的数据；有两个属性，当前节点的值和下一个节点；实现了CustomStringConvertible协议，打印链表的时候更好看。
我们来尝试使用一下：
let node1 = LinkedListNode(value: 1)
let node2 = LinkedListNode(value: 2)
let node3 = LinkedListNode(value: 3)
node1.next = node2
node2.next = node3
print(node1)
// 结果
1 -> 2 -> 3
LinkedList
我们把LinkedList定义为Struct类型，同时也是泛型。
struct LinkedList<T> {
var head: LinkedListNode<T>?
var tail: LinkedListNode<T>?
init() { }
}
extension LinkedList: CustomStringConvertible {
var description: String {
guard let head = head else { return "Empty list" }
return String(describing: head)
}
}
extension LinkedList {
var isEmpty: Bool {
return head == nil
}
}
head是第一个元素；tail是最后一个元素。另外还添加了isEmpty属性，方便后续使用。
添加元素
这里我们定义两种添加元素的方法：1）append()：在链表后面添加元素；2）insert(after:)：在某个节点后面添加元素。
extension LinkedList {
mutating func append(_ value: T) {
guard !isEmpty else {
let node = LinkedListNode(value: value)
head = node
tail = node
return
}
let next = LinkedListNode(value: value)
tail?.next = next
tail = next
}
mutating func insert(_ value: T, after node: LinkedListNode<T>) {
guard tail !== node else { append(value); return }
node.next = LinkedListNode(value: value, next: node.next)
}
}
-
append(): 首先判断是否为空，如果为空，那么head和tail都是当前添加的元素；如果不为空，更新tail?.next为当前添加的元素，最后在把tail更新为当前添加的元素。 -
insert(after:)：首先判断node是有已经是最后一个元素，如果是，直接调用append()添加即可；否则，更新node.next。
移除元素
这里我们定义与添加元素对应的移除方法：1）removeLast()：移除链表的最后一个元素；2）remove(after:)：移除某个节点后面的元素。
extension LinkedList {
mutating func removeLast() -> T? {
guard let head = head else { return nil }
guard head.next != nil else {
let headValue = head.value
self.head = nil
tail = nil
return headValue
}
var prev = head
var current = head
while let next = current.next {
prev = current
current = next
}
prev.next = nil
tail = prev
return current.value
}
mutating func remove(after node: LinkedListNode<T>) -> T? {
defer {
if node.next === tail {
tail = node
}
node.next = node.next?.next
}
return node.next?.value
}
}
-
removeLast()：判断元素是否为空，如果为空，直接返回nil；head.next != nil判断是否只有一个元素，如果是，先定义一个变量存储head.value，把head和tail都设置为nil，并返回headValue；链表有多个元素，用while循环找到最后一个元素，把倒数第二个元素的next设置为nil，tail设置为倒数第二元素，返回最后一个元素的value。 -
remove(after:)：defer里面的代码会在return语句执行之后运行，所以在return node.next?.value之后，判断node的下一个元素是否是最后一个元素，如果是，最后一个元素就变成了node；因为我们删除了node的下一个元素，所以node.next变成了node.next?.next。
访问元素
extension LinkedList {
func node(at index: Int) -> LinkedListNode<T>? {
var currentNode = head
var currentIndex = 0
while currentNode != nil && currentIndex < index {
currentNode = currentNode!.next
currentIndex += 1
}
return currentNode
}
}
这里我们指实现一个方法：查找在某个index的元素。用while循环从头开始找，知道currentIndex == index，那么index对应的节点就是currentNode。
性能分析
| 方法名 | 方法概述 | 时间复杂度 |
|---|---|---|
append() |
在最后面添加元素 | O(1) |
insert(after:) |
在某个节点后面添加元素 | O(1) |
removeLast() |
移除最后一个元素 | O(n)，n是元素个数，因为要从头开始找才能找到最后一个元素，所以为O(n) |
remove(after:) |
移除某一节点后面的元素 | O(1) |
node(at:) |
查找某个index对应的元素 |
O(i)，i是指index，因为要从头开始找，所以为O(i) |
实现Swift的Collection协议
为什么要实现Collection协议？首先链表能存储了一系列的元素，实现Sequence协议是很合理的；并且链表的元素是有限的，这也非常符合Collection协议的要求。实现Collection协议之后，我们能使用for-in循环，能得到很多方便使用的方法。因为Collection继承于Sequence，所以我们实现Collection即可。Sequence和Collection这两个协议，大家可以看看官方文档去理解一下。
我们在苹果的文档中可以看到，实现Collection协议需要提供：1) startIndex和endIndex属性；2）下标的实现；3）index(after:)的实现。另外还要求访问startIndex和endIndex属性、通过下标访问元素的时间复杂度为O(1)。但是在链表里面，通过index去访问元素的时间复杂度是O(i)，无法满足Collection协议的要求。所以我们自定义了一个Index类型来存储对应的Node，这样就可以满足Collection协议的要求。
extension LinkedList: Collection {
struct Index: Comparable {
var node: LinkedListNode<T>?
static 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
}
}
static func <(lhs: Index, rhs: Index) -> Bool {
guard lhs != rhs else { return false }
let nodes = sequence(first: lhs.node) { $0?.next }
return nodes.contains { $0 === rhs.node }
}
}
var startIndex: Index {
return Index(node: head)
}
var endIndex: Index {
return Index(node: tail?.next)
}
func index(after i: Index) -> Index {
return Index(node: i.node?.next)
}
subscript(index: Index) -> T {
return index.node!.value
}
}
在上面的代码中，我们首先定义了一个Index类型，然后实现Collection协议要求的属性和方法。
把LinkedList变成值类型
熟悉Swift的朋友都知道，Swift标准库的很多类型都是值类型。我们以数组为例：
var array1 = [1, 2, 3, 4, 5]
let array2 = array1
print(array1)
print(array2)
print("========分割线========")
array1.append(6)
print(array1)
print(array2)
// 结果
array1: [1, 2, 3, 4, 5]
array2: [1, 2, 3, 4, 5]
========分割线========
array1: [1, 2, 3, 4, 5, 6]
array2: [1, 2, 3, 4, 5]
先定义了一个array1，再把array1赋值给array2，毫无疑问，这时array1和array2是相同的；接着在array1后面加了一个6，再来看打印结果，array1多了一个6，但是array2没变。这证明了数组是一个值类型。
回到LinkedList，我们把他定义为了Struct类型。在我们的印象中，Struct类型应该都是值类型。我们先模仿刚刚那个数组的例子来看看结果：
var list1 = LinkedList<Int>()
list1.append(1)
list1.append(2)
list1.append(3)
let list2 = list1
print("list1: \(list1)")
print("list2: \(list2)")
print("========分割线========")
list1.append(4)
print("list1: \(list1)")
print("list2: \(list2)")
// 结果
list1: 1 -> 2 -> 3
list2: 1 -> 2 -> 3
========分割线========
list1: 1 -> 2 -> 3 -> 4
list2: 1 -> 2 -> 3 -> 4
结果：改变其中一个list，会影响另外一个list。说明目前我们的LinkedList是引用类型。造成这种现象的原因是我们底层存储节点的LinkedListNode是Class类型，是一个引用类型。
为了修复这个问题，我们需要在所有改变链表元素的方法里面，在对元素进行操作之前，先复制一份LinkedListNode，这样就不会造成多个LinkedListNode变量引用着同一个实例。实现的方法如下：
mutating func copyNodes() {
guard !isKnownUniquelyReferenced(&head) else { return }
guard var oldNode = head else { return }
head = LinkedListNode(value: oldNode.value)
var newNode = head
while let nextOldNode = oldNode.next {
let nextNewNode = LinkedListNode(value: nextOldNode.value)
newNode?.next = nextNewNode
newNode = nextNewNode
oldNode = nextOldNode
}
tail = newNode
}
这个方法对所有链表的节点进行了复制。其中guard !isKnownUniquelyReferenced(&head) else { return }是用来判断当前的链表是否只被一个变量引用，如果是，则无需复制；否则会继续执行，对所有节点进行复制。
把copyNodes()方法添加到所有改变链表元素的方法最上面，方法包括：append()、insert(after:)、removeLast()和remove(after:)。例如：
mutating func append(_ value: T) {
copyNodes()
guard !isEmpty else {
let node = LinkedListNode(value: value)
head = node
tail = node
return
}
let next = LinkedListNode(value: value)
tail?.next = next
tail = next
}
一个简单的链表就这样完成了。
总结
本文主要讲解了链表的一些特性，并简单实现了链表。目前添加和移除元素的方法比较少，如果有兴趣的话，可以添加更多的方法，例如append一个链表、insert一个链表等等。
完整代码 >>
参考资料
Data Structures and Algorithms in Swift --- raywenderlich.com，如果想看原版书籍，请点击链接购买。
完
欢迎加入我管理的Swift开发群：536353151。
