概念 链表（Linked list）是一组数据元素（又称为节点：node）在一个线性序列中的集合，它和数组一样都是一种线性结构，但与数组不同的是，数组内元素的逻辑次序和物理存储地址是对应的，而链表则不是，相邻元素的存储地址未必相邻。为了知道每个元素的地址，上一个元素中会存储下一个元素的地址。因此相比数组访问元素是通过“寻秩访问”（call-by-rank），链表则是“循位置访问”（call-by-position），或者“循链接访问”（call-by-link）。
链表又分为单向链表、双向链表、循环链表，单链表是只有一个前进方向，只能从一个节点链接到下一个节点，而双向链表既可以链接到下一个节点，也可以链接到上一个节点。循环列表则是链表首尾也是链接的。这里只实现单向链表。
性能 链表的元素读取性能是O(n)，在最坏的情况下，需要遍历所有的元素，才能访问到需要的元素。
Swift实现 根据上面的定义，我们可以知道，链表里的元素除了自身的值外，还需要指向下一个元素，所以我们可以定义Node类如下：
1 2 3 4 5 6 7 8 9 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 } }
同时为了方便打印数据，我们为Node实现CustomStringConvertible协议
1 2 3 4 5 6 7 8 9 extension Node: CustomStringConvertible { public var description: String { guard let next = next else { return "\(value)" } return "\(value) -> " + String(describing: next) + " " } }
接下来我们实现一个LinkedList类，这个类有head、trail、count三个属性，为了保护数据安全，这三个属性不允许外界直接设置，同样为其实现`CustomStringConvertible``协议：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public class LinkedList<Value> { public private(set) var head: Node<Value>? public private(set) var tail: Node<Value>? public private(set) var count: Int = 0 public init(value: Value? = nil) { if let value = value { head = Node(value: value) tail = head count = 1 } } public var isEmpty: Bool { return count == 0 } } extension LinkedList: CustomStringConvertible { public var description: String { guard let head = head else { return "Empty list" } return String(describing: head) } }
如此，一个链表就定义好了，但现在只有初始化init方法，还没有查找、插入、删除等操作的方法，接下来我们来一一添加这些方法。
查找： 为了后续操作的方便，我们先添加一个查找方法，通过位置查找对应的节点。上面概念部分已经讲到，链表的存储位置和逻辑秩序是没有对应关系的，要查找某个位置的节点，只能通过前驱节点一步步找下一个节点。因此耗时是O(n)，在最坏的情况下需要查找n次。具体实现如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public func node(at index: Int) -> Node<Value>? { guard index < count else { return 0 } var currentIndex = 0 var currentNode = head while currentIndex < index, currentNode != nil { currentIndex += 1 currentNode = currentNode?.next } return currentNode }
添加操作：
push：添加一个元素到链表头部
append：添加一个元素到链表尾部
insert(after:)：添加一个元素到特定节点后
做这三个操作的时候，需要注意要更新head、tail和count。
push 添加元素到头部，有两种情况:
最后count加1。
1 2 3 4 5 6 7 8 public func push(_ value: Value) { let newNode = Node(value: value, next: head) head = newNode if tail == nil { tail = head } count += 1 }
append 添加元素到尾部，也是有两种情况：
1 2 3 4 5 6 7 8 9 10 11 12 public func append(_ value: Value) { if isEmpty { push(value) return } let newNode = Node(value: value) tail?.next = newNode tail = newNode count += 1 }
insert(after:) 添加元素到某个节点后面，需要先把该节点的next设置为新节点的next，再把新节点设为该节点的next。此时链表不为空，head不需要更新，但是要考虑是否需要更新tail，如果是添加在tail后面，那就和append操作一样，可以直接调用append方法，具体实现如下：
1 2 3 4 5 6 7 8 9 10 11 public func insert(_ value: Value, after node: Node<Value>) -> Node<Value> { if node === tail { append(value) return tail! } node.next = Node(value: value, next: node.next) return node.next! }
insert(at:) 此外还可以添加节点到某个位置index，利用我们上面的查找方法，先找出index-1位置的节点，再调用上面的insert方法。此时就需要注意index == 0的情况：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 @discardableResult public func insert(_ value: Value, at index: Int) -> Node<Value>? { guard count > 0 else { push(value) return head! } guard index > 0 else { insert(value, after: head!) return head!.next! } if let node = node(at: index - 1) { return insert(value, after: node) } return nil }
删除操作： 删除操作也主要是有三个：
pop：删除头部节点，即head
removeLast：删除尾部节点：即tail
remove(after:)：删除某个节点的下一个节点
remove(at:)：删除某个位置的节点
删除操作也需要考虑是否需要更新head和tail，同时需要给count做减1操作
以上三个删除操作中1、3的性能是O(1)，2的性能是O(n)。
pop 删除头部节点，删除后，需要把head.next设置为新head，实际只需要重新设置head即可。另外需要注意tail是否需要更新，当只有一个节点时，删除一个后，tail也需要设置为nil。
1 2 3 4 5 6 7 8 9 10 11 12 @discardableResult public func pop() -> Value? { guard !isEmpty else { return nil } let oldHead = head head = oldHead?.next count -= 1 if tail === oldHead { tail = nil } return oldHead?.value }
removeLast 删除最后一个节点，其实是要做两件事，一是把tail的前驱节点的next设为nil，再tail设置为前驱节点。因此这里就涉及到要找tail的前驱节点，这个查找操作就需要O(n)的时间。我们上面已经实现了一个查找方法，这里可以直接使用了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 @discardableResult public func removeLast() -> Value? { guard count > 1 else { return pop() } let removedNode = tail let pre = node(at: count - 2) pre?.next = nil tail = pre count -= 1 return removedNode?.value }
remove(after:) 删除一个节点的下一个节点，同样需要考虑删除的是否是尾节点，如果是，需要更新tail：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 @discardableResult public func remove(after node: Node<Value>) -> Value? { defer { if node.next === tail { tail = node } node.next = node.next?.next } if node.next != nil { count -= 1 } return node.next?.value }
remove(at:) 删除特定位置的节点，这个可以利用查找方法，找到前一个位置的node，再调用上面的remove(after:)方法即可，这里需要注意第0个位置时，需要特殊处理：
1 2 3 4 5 6 7 8 9 10 11 12 @discardableResult public func remove(at index: Int) -> Value? { guard index >= 0, index < count - 1 else { return nil } if index == 0 { return pop() } if let node = node(at: index - 1) { return remove(after: node) } return nil }
