列表
链表(Linked List)
这个主题已经有辅导文章
链表是一系列数据项，就像数组一样。 数组分配了一大块内存来存储对象，而链表中的元素在内存中是完全独立的对象，并通过链接连接：
+--------+ +--------+ +--------+ +--------+
| | | | | | | |
| node 0 |--->| node 1 |--->| node 2 |--->| node 3 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+链表的元素称为 节点。 上图显示了 单链表，其中每个节点只有一个引用 - 或叫做“指针” - 到下一个节点。 在 双向链表中，如下所示，节点还有指向前一个节点的指针：
+--------+ +--------+ +--------+ +--------+
| |--->| |--->| |--->| |
| node 0 | | node 1 | | node 2 | | node 3 |
| |<---| |<---| |<---| |
+--------+ +--------+ +--------+ +--------+您需要跟踪链表的开始位置。 这通常用一个名为 head 的指针完成：
+--------+ +--------+ +--------+ +--------+
head --->| |--->| |--->| |--->| |---> nil
| node 0 | | node 1 | | node 2 | | node 3 |
nil <---| |<---| |<---| |<---| |<--- tail
+--------+ +--------+ +--------+ +--------+引用链表末尾也很有用，称为 tail。 注意，最后一个节点的“下一个”指针是nil，第一个节点的“前一个”指针也是nil。
链表的性能
链表上的大多数操作时间复杂度都是 O(n) ，因此链表通常比数组慢。但是，它们也更加灵活 —— 而不是像数组一样复制大块内存，链表上的许多操作只需要更改几个指针。
时间复杂度是O(n)的原因是你不能简单地写list[2]来从链表中访问节点2。 如果你已经没有对该节点的引用，你必须从head开始，然后按照next指针逐个访问（或者从tail开始，使用previous指针，逐个访问并找到指定节点）。
但是一旦你有一个节点的引用，插入和删除等操作真的很快。 只是寻找节点慢。
这意味着当您处理链表时，应尽可能在前面插入新项目。 这是O(1)操作。 如果你跟踪tail指针，同样可以在后面插入。
单链表 vs 双链表
单链表使用比双链表使用更少的内存，因为它不需要存储所有那些previous指针。
但是如果你需要找到一个节点以前的节点，你就搞砸了。 您必须从头部开始并遍历整个链表，直到到达正确的节点。
对于许多任务，双向链表使事情变得更容易。
为什么使用链表？
使用链表的典型示例是队列。 使用数组，从队列前面删除元素很慢，因为它需要向下移动内存中的所有其他元素。 但是通过链接链表，只需将head更改为指向第二个元素即可。 快多了。
但说实话，现在你几乎不需要编写自己的链表。 不过，了解它们的工作方式仍然很有用; 将对象链接在一起的原则也与树和图一起使用。
代码
我们首先定义一个描述节点的类型：
public class LinkedListNode<T> {
var value: T
var next: LinkedListNode?
weak var previous: LinkedListNode?
public init(value: T) {
self.value = value
}
}这是一种泛型类型，因此T可以是您想要存储在节点中的任何类型的数据。 我们将在后面的示例中使用字符串。
这边定义的是一个双向链表，每个节点都有一个next和previous指针。 如果没有下一个或前一个节点，则这些可以是nil，因此这些变量必须是可选项。 （在下文中，我将指出哪些函数需要更改，如果这只是单个而不是双向链表。）
注意： 为避免循环强引用，我们声明previous指针为弱。 如果链表中有一个节点A后面跟着节点B，那么A指向B，而B指向A。 在某些情况下，即使在删除节点后，此循环强引用也可能导致节点保持活动状态。 我们不希望这样，所以我们使其中一个指针weak来打破循环。
让我们开始构建LinkedList。 这是第一点：
public class LinkedList<T> {
public typealias Node = LinkedListNode<T>
private var head: Node?
public var isEmpty: Bool {
return head == nil
}
public var first: Node? {
return head
}
}理想情况下，我们希望类名尽可能具有描述性，但是，我们不希望每次要使用类时都打长名称，因此，我们在LinkedList中给LinkedListNode<T>定义了一个短的别名Node。
这个链表只有一个head指针，没有尾部。 添加尾指针留给读者练习。 （如果我们还有一个尾指针，我会指出哪些函数会有所不同。）
如果head为nil，则链表为空。 因为head是一个私有变量，所以我添加了属性first来返回对链表中第一个节点的引用。
在playground中测试：
let list = LinkedList<String>()
list.isEmpty // true
list.first // nil我们还添加一个属性，为您提供链表中的最后一个节点。 这是将开始变得有趣了：
public var last: Node? {
guard var node = head else {
return nil
}
while let next = node.next {
node = next
}
return node
}如果你是Swift的新手，你可能已经看过if let但也许不是if var。 它做了同样的事情 - 它解开head可选项并将结果放入一个名为node的新局部变量中。 区别在于node不是常量而是当前运行环境下的变量，因此我们可以在循环内更改它。
循环也做了一些Swift魔法。 while let next = node.next保持循环，直到node.next为nil。 您可以写如下：
var node: Node? = head
while node != nil && node!.next != nil {
node = node!.next
}但这对我来说并不是很开心。 我们可以很好地利用Swift对解包选项的内置支持。 你会在随后的代码中看到一堆这样的循环。
注意： 如果我们保留一个尾指针，last只会做return tail。 但我们没有，所以它必须从头到尾逐步完成整个链表。这是一项昂贵的操作，特别是如果链表很长的话。
当然，last只返回nil，因为链表中没有任何节点。 让我们添加一个方法，将新节点添加到链表的末尾：
public func append(value: T) {
let newNode = Node(value: value)
if let lastNode = last {
newNode.previous = lastNode
lastNode.next = newNode
} else {
head = newNode
}
}append()方法首先创建一个新的Node对象，然后请求我们刚刚添加的最后一个节点last属性。 如果没有这样的节点，链表仍然是空的，我们使head指向这个新的Node。但是如果我们确实找到了一个有效的最后节点对象，我们连接next和previous指针将这个新节点链接到链中。许多链表代码涉及这种next和previous指针操作。
在playground中测试：
list.append("Hello")
list.isEmpty // false
list.first!.value // "Hello"
list.last!.value // "Hello"The list looks like this:
这个链表目前看上去是：
+---------+
head --->| |---> nil
| "Hello" |
nil <---| |
+---------+增加第二个节点：
list.append("World")
list.first!.value // "Hello"
list.last!.value // "World"现在链表看上去是：
+---------+ +---------+
head --->| |--->| |---> nil
| "Hello" | | "World" |
nil <---| |<---| |
+---------+ +---------+您可以通过查看next和previous指针来自行验证：
list.first!.previous // nil
list.first!.next!.value // "World"
list.last!.previous!.value // "Hello"
list.last!.next // nil让我们添加一个方法来计算链表中有多少个节点。 这与我们已经完成的工作非常相似：
public var count: Int {
guard var node = head else {
return 0
}
var count = 1
while let next = node.next {
node = next
count += 1
}
return count
}它以相同的方式循环遍历链表，但这次增加了一个计数器。
注意： 加快获得count的速度（从O(n)到O(1)）的一种方法是跟踪一个计算链表中有多少节点的变量。 无论何时添加或删除节点，都会更新此变量。如果我们想在链表中的特定索引处找到节点，该怎么办？使用数组我们可以编写一个O(1)操作array[index]。这更多地涉及链接链表，但代码遵循类似的模式：
public func node(atIndex index: Int) -> Node {
if index == 0 {
return head!
} else {
var node = head!.next
for _ in 1..<index {
node = node?.next
if node == nil { //(*1)
break
}
}
return node!
}
}首先，我们检查给定的索引是否为0。 因为如果它是0，它会按原样返回head。
但是，当给定索引大于0时，它从头开始，然后继续追踪node.next指针逐步执行链表。
与此时计数方法的不同之处在于存在两种终止条件。
一种是当for循环语句到达索引时，我们能够获取给定索引的节点。
第二个是for-loop语句中的node.next返回nil并导致break。（*1）
这意味着给定的索引超出范围并导致崩溃。
测试一下：
list.nodeAt(0)!.value // "Hello"
list.nodeAt(1)!.value // "World"
// list.nodeAt(2) // crash为了好玩，我们也可以实现subscript（下标）方法：
public subscript(index: Int) -> T {
let node = node(atIndex: index)
return node.value
}现在可以编写如下内容：
list[0] // "Hello"
list[1] // "World"
list[2] // crash!它在list [2]上崩溃，因为该索引上没有节点。
到目前为止，我们已经编写了将新节点添加到链表末尾的代码，但这很慢，因为您需要先找到链表的末尾。（如果我们使用尾指针会很快。）因此，如果链表中项目的顺序无关紧要，则应在链表的前面执行插入操作。 这总是一个O(1)操作。
让我们编写一个方法，允许您在链表中的任何索引处插入新节点。
public func insert(_ node: Node, at index: Int) {
let newNode = node
if index == 0 {
newNode.next = head
head?.previous = newNode
head = newNode
} else {
let prev = self.node(at: index-1)
let next = prev.next
newNode.previous = prev
newNode.next = prev.next
prev.next = newNode
next?.previous = newNode
}
}与node(at:)方法一样，insert(_:at:)方法也会根据索引参数是否为0进行判断。
首先让我们来看看前一种情况（译注：也就是index == 0，插入最前面的情况）。 假设我们有以下链表和新节点（C）。
+---------+ +---------+
head --->| |---->| |-----//----->
| A | | B |
nil <---| |<----| |<----//------
+---------+ +---------+
[0] [1]
+---------+
new --->| |----> nil
| C |
| |
+---------+
现在将新节点放在第一个节点之前。 通过这种方式：
new.next = head
head.previous = new
+---------+ +---------+ +---------+
new --->| |--> head -->| |---->| |-----//----->
| C | | A | | B |
| |<-----------| |<----| |<----//------
+---------+ +---------+ +---------+
最后，用新节点作为头部。
head = new
+---------+ +---------+ +---------+
head --->| |--->| |---->| |-----//----->
| C | | A | | B |
nil <---| |<---| |<----| |<----//------
+---------+ +---------+ +---------+
[0] [1] [2]
但是，当给定索引大于0时，必须获取节点的上一个和下一个索引并在它们之间插入。
您还可以使用node(at:)获取上一个和下一个节点，如下所示：
+---------+ +---------+ +---------+
head --->| |---//--->| |---->| |----
| | | A | | B |
nil <---| |---//<---| |<----| |<---
+---------+ +---------+ +---------+
[0] [index-1] [index]
^ ^
| |
prev next
prev = node(at: index-1)
next = prev.next现在在prev和next之间插入新节点。
new.prev = prev; prev.next = new // connect prev and new.
new.next = next; next.prev = new // connect new and next.
+---------+ +---------+ +---------+ +---------+
head --->| |---//--->| |---->| |---->| |
| | | A | | C | | B |
nil <---| |---//<---| |<----| |<----| |
+---------+ +---------+ +---------+ +---------+
[0] [index-1] [index] [index+1]
^ ^ ^
| | |
prev new next
测试：
list.insert(LinedListNode(value: "Swift"), at: 1)
list[0] // "Hello"
list[1] // "Swift"
list[2] // "World
还可以尝试在链表的前面和后面添加新节点，以验证其是否正常工作。
注意：node(at:)和insert(_:at:)函数也可以与单链表一起使用，因为我们不依赖于节点的previous指针来查找前一个元素。
我们还需要什么？ 当然要删除节点！ 首先我们要做removeAll()，这很简单：
public func removeAll() {
head = nil
}
如果你有一个尾指针，你也可以在这里设置为nil。
接下来，我们将添加一些可以删除单个节点的函数。 如果你已经有了对节点的引用，那么使用remove()是最优的，因为你不需要遍历链表来首先找到节点。
public func remove(node: Node) -> T {
let prev = node.previous
let next = node.next
if let prev = prev {
prev.next = next
} else {
head = next
}
next?.previous = prev
node.previous = nil
node.next = nil
return node.value
}
当我们将此节点从链表中取出时，我们将断开指向上一个节点和下一个节点的链接。 要使链表再次完整，我们必须将前一个节点链接到下一个节点。
不要忘记head指针！ 如果这是链表中的第一个节点，则需要更新head以指向下一个节点。 （同样，当你有一个尾指针，这是最后一个节点）。 当然，如果没有剩余的节点，head应该变为nil。
尝试一下：
list.remove(node: list.first!) // "Hello"
list.count // 2
list[0] // "Swift"
list[1] // "World"如果你没有对节点的引用，你可以使用removeLast()或 removeAt()：
public func removeLast() -> T {
assert(!isEmpty)
return remove(node: last!)
}
public func remove(at index: Int) -> T {
let node = self.node(at: index)
return remove(node: node)
}所有这些删除函数都返回已删除元素的值。
list.removeLast() // "World"
list.count // 1
list[0] // "Swift"
list.remove(at: 0) // "Swift"
list.count // 0
注意： 对于单链表，删除最后一个节点稍微复杂一些。 您不能只使用last来查找链表的末尾，因为您还需要对倒数第二个节点的引用。 相反，使用nodesBeforeAndAfter()辅助方法。 如果链表有一个尾指针，那么removeLast()非常快，但你需要记住让tail指向前一个节点。
我们的LinkedList类还可以做一些有趣的事情。 一些很方便可读的调试输出：
extension LinkedList: CustomStringConvertible {
public var description: String {
var s = "["
var node = head
while node != nil {
s += "\(node!.value)"
node = node!.next
if node != nil { s += ", " }
}
return s + "]"
}
}这将如下形式打印链表：
[Hello, Swift, World]如何反转链表，使头部成为尾部，反之亦然？ 有一个非常快速的算法：
public func reverse() {
var node = head
tail = node // If you had a tail pointer
while let currentNode = node {
node = currentNode.next
swap(¤tNode.next, ¤tNode.previous)
head = currentNode
}
}这循环遍历整个链表，并简单地交换每个节点的next和previous指针。 它还将head指针移动到最后一个元素。 （如果你有一个尾部指针，你还需要更新它。）你最终得到这样的东西：
+--------+ +--------+ +--------+ +--------+
tail --->| |<---| |<---| |<---| |---> nil
| node 0 | | node 1 | | node 2 | | node 3 |
nil <---| |--->| |--->| |--->| |<--- head
+--------+ +--------+ +--------+ +--------+数组有map()和filter()函数，那么没有理由说链接链表没有。
public func map<U>(transform: (T) -> U) -> LinkedList<U> {
let result = LinkedList<U>()
var node = head
while node != nil {
result.append(transform(node!.value))
node = node!.next
}
return result
}使用如下：（译注：创建一个新链表，用来存放之前链表中字符串的长度）
let list = LinkedList<String>()
list.append("Hello")
list.append("Swifty")
list.append("Universe")
let m = list.map { s in s.count }
m // [5, 6, 8]filter()函数：
public func filter(predicate: (T) -> Bool) -> LinkedList<T> {
let result = LinkedList<T>()
var node = head
while node != nil {
if predicate(node!.value) {
result.append(node!.value)
}
node = node!.next
}
return result
}一个简单的使用例子：（译注：筛选出链表中字符串长度大于5的元素并组成新的链表）
let f = list.filter { s in s.count > 5 }
f // [Universe, Swifty]为读者练习：map() 和filter() 的这些实现不是很快，因为它们将新节点追加到新链表的末尾。 回想一下，append是O(n)，因为它需要扫描整个链表以找到最后一个节点。 你能加快速度吗？ （提示：跟踪您添加的最后一个节点。）
另一种方法
到目前为止，您看到的LinkedList版本使用的是类，具有引用语义。 这没有什么不对，但这确实使它们比Swift的其他集合（例如Array和Dictionary）更重要。(译注： 这里应该是想表达，Array和Dictionary都是结构体，链表也可以使用结构体和枚举实现)
可以使用枚举实现具有值语义的链表。 这看起来有点像这样：
enum ListNode<T> {
indirect case node(T, next: ListNode<T>)
case end
}与基于类的版本的最大区别在于，您对此链表所做的任何修改都将导致创建新副本。 这是否是您想要的取决于应用程序。
[如果有需求，我可能会更详细地填写此部分。]
符合Collection协议
符合Sequence协议的类型，其元素可以多次遍历。非破坏性地通过索引的下标访问，应该符合Swift标准库中定义的Collection协议。
这样做可以访问处理数据集合时常见的大量属性和操作。 除此之外，它还允许自定义类型遵循Swift开发人员常用的模式。
为了符合这个协议，类需要提供：
1 startIndex和endIndex属性。
2 对元素的下标访问为O(1)。 需要记录这种时间复杂性的变化。
/// The position of the first element in a nonempty collection.
public var startIndex: Index {
get {
return LinkedListIndex<T>(node: head, tag: 0)
}
}
/// The collection's "past the end" position---that is, the position one
/// greater than the last valid subscript argument.
/// - Complexity: O(n), where n is the number of elements in the list.
/// This diverts from the protocol's expectation.
public var endIndex: Index {
get {
if let h = self.head {
return LinkedListIndex<T>(node: h, tag: count)
} else {
return LinkedListIndex<T>(node: nil, tag: startIndex.tag)
}
}
}public subscript(position: Index) -> T {
get {
return position.node!.value
}
}因为集合负责管理自己的索引，下面的实现保留对链表中节点的引用。 索引中的标记属性表示链表中节点的位置。
/// Custom index type that contains a reference to the node at index 'tag'
public struct LinkedListIndex<T> : Comparable
{
fileprivate let node: LinkedList<T>.LinkedListNode<T>?
fileprivate let tag: Int
public static func==<T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool {
return (lhs.tag == rhs.tag)
}
public static func< <T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool {
return (lhs.tag < rhs.tag)
}
}最后，链接能够通过以下实现计算给定的索引之后的索引。
public func index(after idx: Index) -> Index {
return LinkedListIndex<T>(node: idx.node?.next, tag: idx.tag+1)
}要注意的一些事情
链接链表是灵活的，但许多操作是O(n)。
在链表上执行操作时，您总是需要小心更新相关的next和previous指针，还可能更新head和tail指针。 如果你搞砸了，你的链表将不再正确，你的程序可能会在某些时候崩溃。 小心！
处理链表时，通常可以使用递归：处理第一个元素，然后在链表的其余部分再次递归调用该函数。 当没有下一个元素时你就完成了。 这就是链表是LISP等函数式编程语言的基础的原因。
跳表(Skip List)
Skip List is a probablistic data-structure with same logarithmic time bound and
efficiency as AVL/ or Red-Black tree and provides a clever compromise to
efficiently support search and update operations and is relatively simpler to
implement compared to other map data structures.
跳表是一个概率数据结构，具有相同的对数时间限制和作为AVL或红黑树的效率，并提供了一个聪明的妥协有效地支持搜索和更新操作，并且相对简单与其他映射数据结构相比，实现。
A skip list S consists of series of sorted linked lists {L0, ..., Ln},
layered hierarchicaly and each layer L stores a subset of items in layer L0
in incremental order. The items in layers {L1, ... Ln} are chosen at random
based on a coin flipping function with probability 1/2 . For traversing, every
item in a layer hold references to the node below and the next node. This
layers serve as express lanes to the layer underneath them, effectively making
fast O(log n) searching possible by skipping lanes and reducing travel distance
and in worse case searching degrades to O (n), as expected with regular linked
list.
跳表 S 由一系列排序链表 {L0, ..., Ln} 组成，分层次的层次结构和每一层 L 存储图层中的项目子集 L0 按增量顺序。层 {L1, ... Ln} 中的项目是随机选择的基于硬币翻转功能，概率为1/2。为了遍历，每一个图层中的项目包含对下面节点和下一个节点的引用。这个层作为快速通道到它们下面的层，有效地制作快速O(log n) 搜索可以通过跳过车道和减少行驶距离并且在更糟糕的情况下，搜索降级为O(n)，正如预期的那样经常链接名单。
For a skip list S:
对于跳表 S
List L0 contains every inserted item.
For lists {L1, ..., Ln}, Li contains a randomly generated subset of the
items in Li-1Height is determined by coin-flipping.
链表 L0 包含每个插入的项目。
对于列表{L1, ..., Ln}，Li 包含随机生成的子集物品Li-1
高度由硬币翻转决定。
Figure 1
搜索
Searching for element N starts by traversing from top most layer Ln until L0.
搜索元素N首先从最顶层Ln遍历到L0。
Our objective is to find an element K such that its value at the rightmost
position of current layer, is less-than target item and its subsequent node has
a greater-equal value or nil ( K.key < N.key <= (K.next.key or nil) ). if
value of K.next is equal to N, search is terminated and we return K.next,
otherwise drop underneath using K.down to the node below ( at layer Ln-1 ) and
repeat the process until L0 where K.down is nil which indicates that level
is L0 and item doesn't exists.
我们的目标是找到一个元素 K，使其在最右边的值当前层的位置，小于目标项及其后续节点大于等于或等于零 ( K.key < N.key <= (K.next.key or nil) 。 如果 K.next 的值等于 N，搜索终止，我们返回 K.next，否则使用K.down下面到下面的节点（在层Ln-1）和重复该过程，直到L0，其中K.down为nil，表示该级别是L0且项目不存在。
例子：
插入
Inserting element N has a similar process as searching. It starts by
traversing from top most layer Ln until L0. We need to keep track of our
traversal path using a stack. It helps us to traverse the path upward when
coin-flipping starts, so we can insert our new element and update references to
it.
插入元素 N 具有与搜索类似的过程。 它开始于从最顶层穿过Ln直到L0。 我们需要跟踪我们的情况使用堆栈的遍历路径。 它有助于我们在向上穿越路径硬币翻转开始，所以我们可以插入我们的新元素并更新引用它。
Our objective is to find a element K such that its value at the rightmost
position of layer Ln, is less-than new item and its subsequent node has a
greater-equal value or nil ( K.key < N.key < (K.next.key or nil) ). Push
element K to the stack and with element K, go down using K.down to the
node below ( at layer Ln-1 ) and repeat the process ( forward searching ) up
until L0 where K.down is nil which indicates that level is L0. We
terminate the process when K.down is nil.
我们的目标是找到一个元素K，使其在最右边的值层的位置 Ln 小于新项，其后续节点有一个大于等于或等于 ( K.key < N.key < (K.next.key or nil) )。 推元素K到堆栈并使用元素K，使用K.down向下移动到下面的节点（在层Ln-1）并重复该过程（向前搜索）直到L0，其中K.down是nil，表示该等级是L0。 我们K.down为零时终止进程。
At L0, N can be inserted after K.
在 L0，N可以在K之后插入。
Here is the interesting part. We use coin flipping function to randomly create
layers.
这是有趣的部分。 我们使用硬币翻转功能随机创建层。
When coin flip function returns 0, the whole process is finished but when
returns 1, there are two possibilities:
当硬币翻转功能返回0时，整个过程结束但是何时返回1，有两种可能性：
Stack is empty ( Level is L0 /- Ln or at uninitialized stage)
Stack has items ( traversing upward is possible )
堆栈为空（级别为L0 / - Ln或未初始化阶段）
堆栈有物品（可以向上移动）
In case 1:
A new layer M* is created with a head node NM referencing head node of layer
below and NM.next referencing new element N. New element N referecing
element N at previous layer.
创建一个新的层M，其头节点NM引用层的头节点下面和NM.next引用新元素N。 新元素N* referecing元素前一层的N。
In case 2:
repeat until stack is empty Pop an item F from stack and update the references
accordingly. F.next will be K.next and K.next will be F
重复直到堆栈为空从堆栈中弹出项目F并更新引用因此。 F.next将是K.next和K.next将是F
when stack is empty Create a new layer consisintg of a head node NM
referencing head node of layer below and NM.next referencing new element
N. New element N referencing element N at previous layer.
当stack为空时创建一个头节点的新层consisintg NM 引用下面层的头节点和NM.next引用新元素N。 新元素N在前一层引用元素N。
例子：
Inserting 13. with coin flips (0)
Inserting 20. with 4 times coin flips (1) 
删除
删除工作类似于插入过程。