Fork me on GitHub

【译】Swift算法俱乐部-链表

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Clubraywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下,大概有一百左右个的算法和数据结构,基本上常见的都包含了,是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club,边学习边翻译的项目。由于能力有限,如发现错误或翻译不妥,请指正,欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️,🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Linked List


链表(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更改为指向第二个元素即可。 快多了。

但说实话,现在你几乎不需要编写自己的链表。 不过,了解它们的工作方式仍然很有用; 将对象链接在一起的原则也与一起使用。

代码

我们首先定义一个描述节点的类型:

1
2
3
4
5
6
7
8
9
public class LinkedListNode<T> {
var value: T
var next: LinkedListNode?
weak var previous: LinkedListNode?

public init(value: T) {
self.value = value
}
}

这是一种泛型类型,因此T可以是您想要存储在节点中的任何类型的数据。 我们将在后面的示例中使用字符串。

这边定义的是一个双向链表,每个节点都有一个nextprevious指针。 如果没有下一个或前一个节点,则这些可以是nil,因此这些变量必须是可选项。 (在下文中,我将指出哪些函数需要更改,如果这只是单个而不是双向链表。)

注意: 为避免循环强引用,我们声明previous指针为弱。 如果链表中有一个节点A后面跟着节点B,那么A指向B,而B指向A。 在某些情况下,即使在删除节点后,此循环强引用也可能导致节点保持活动状态。 我们不希望这样,所以我们使其中一个指针weak来打破循环。

让我们开始构建LinkedList。 这是第一点:

1
2
3
4
5
6
7
8
9
10
11
12
13
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中测试:

1
2
3
let list = LinkedList<String>()
list.isEmpty // true
list.first // nil

我们还添加一个属性,为您提供链表中的最后一个节点。 这是将开始变得有趣了:

1
2
3
4
5
6
7
8
9
10
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.nextnil。 您可以写如下:

1
2
3
4
var node: Node? = head
while node != nil && node!.next != nil {
node = node!.next
}

但这对我来说并不是很开心。 我们可以很好地利用Swift对解包选项的内置支持。 你会在随后的代码中看到一堆这样的循环。

注意: 如果我们保留一个尾指针,last只会做return tail。 但我们没有,所以它必须从头到尾逐步完成整个链表。这是一项昂贵的操作,特别是如果链表很长的话。

当然,last只返回nil,因为链表中没有任何节点。 让我们添加一个方法,将新节点添加到链表的末尾:

1
2
3
4
5
6
7
8
9
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。但是如果我们确实找到了一个有效的最后节点对象,我们连接nextprevious指针将这个新节点链接到链中。许多链表代码涉及这种nextprevious指针操作。

在playground中测试:

1
2
3
4
list.append("Hello")
list.isEmpty // false
list.first!.value // "Hello"
list.last!.value // "Hello"

The list looks like this:
这个链表目前看上去是:

         +---------+
head --->|         |---> nil
         | "Hello" |
 nil <---|         |
         +---------+

增加第二个节点:

1
2
3
list.append("World")
list.first!.value // "Hello"
list.last!.value // "World"

现在链表看上去是:

         +---------+    +---------+
head --->|         |--->|         |---> nil
         | "Hello" |    | "World" |
 nil <---|         |<---|         |
         +---------+    +---------+

您可以通过查看nextprevious指针来自行验证:

1
2
3
4
list.first!.previous          // nil
list.first!.next!.value // "World"
list.last!.previous!.value // "Hello"
list.last!.next // nil

让我们添加一个方法来计算链表中有多少个节点。 这与我们已经完成的工作非常相似:

1
2
3
4
5
6
7
8
9
10
11
12
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]。这更多地涉及链接链表,但代码遵循类似的模式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
这意味着给定的索引超出范围并导致崩溃。

测试一下:

1
2
3
list.nodeAt(0)!.value    // "Hello"
list.nodeAt(1)!.value // "World"
// list.nodeAt(2) // crash

为了好玩,我们也可以实现subscript(下标)方法:

1
2
3
4
public subscript(index: Int) -> T {
let node = node(atIndex: index)
return node.value
}

现在可以编写如下内容:

1
2
3
list[0]   // "Hello"
list[1] // "World"
list[2] // crash!

它在list [2]上崩溃,因为该索引上没有节点。

到目前为止,我们已经编写了将新节点添加到链表末尾的代码,但这很慢,因为您需要先找到链表的末尾。(如果我们使用尾指针会很快。)因此,如果链表中项目的顺序无关紧要,则应在链表的前面执行插入操作。 这总是一个O(1)操作。

让我们编写一个方法,允许您在链表中的任何索引处插入新节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

测试:

1
2
3
4
list.insert(LinedListNode(value: "Swift"), at: 1)
list[0] // "Hello"
list[1] // "Swift"
list[2] // "World

还可以尝试在链表的前面和后面添加新节点,以验证其是否正常工作。

注意: node(at:)insert(_:at:)函数也可以与单链表一起使用,因为我们不依赖于节点的previous指针来查找前一个元素。

我们还需要什么? 当然要删除节点! 首先我们要做removeAll(),这很简单:

1
2
3
public func removeAll() {
head = nil
}

如果你有一个尾指针,你也可以在这里设置为nil

接下来,我们将添加一些可以删除单个节点的函数。 如果你已经有了对节点的引用,那么使用remove()是最优的,因为你不需要遍历链表来首先找到节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

尝试一下:

1
2
3
4
list.remove(node: list.first!)   // "Hello"
list.count // 2
list[0] // "Swift"
list[1] // "World"

如果你没有对节点的引用,你可以使用removeLast()removeAt()

1
2
3
4
5
6
7
8
9
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)
}

所有这些删除函数都返回已删除元素的值。

1
2
3
4
5
6
list.removeLast()              // "World"
list.count // 1
list[0] // "Swift"

list.remove(at: 0) // "Swift"
list.count // 0

注意: 对于单链表,删除最后一个节点稍微复杂一些。 您不能只使用last来查找链表的末尾,因为您还需要对倒数第二个节点的引用。 相反,使用nodesBeforeAndAfter()辅助方法。 如果链表有一个尾指针,那么removeLast()非常快,但你需要记住让tail指向前一个节点。

我们的LinkedList类还可以做一些有趣的事情。 一些很方便可读的调试输出:

1
2
3
4
5
6
7
8
9
10
11
12
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]

如何反转链表,使头部成为尾部,反之亦然? 有一个非常快速的算法:

1
2
3
4
5
6
7
8
9
public func reverse() {
var node = head
tail = node // If you had a tail pointer
while let currentNode = node {
node = currentNode.next
swap(&currentNode.next, &currentNode.previous)
head = currentNode
}
}

这循环遍历整个链表,并简单地交换每个节点的nextprevious指针。 它还将head指针移动到最后一个元素。 (如果你有一个尾部指针,你还需要更新它。)你最终得到这样的东西:

         +--------+    +--------+    +--------+    +--------+
tail --->|        |<---|        |<---|        |<---|        |---> nil
         | node 0 |    | node 1 |    | node 2 |    | node 3 |
 nil <---|        |--->|        |--->|        |--->|        |<--- head
         +--------+    +--------+    +--------+    +--------+

数组有map()filter()函数,那么没有理由说链接链表没有。

1
2
3
4
5
6
7
8
9
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
}

使用如下:(译注:创建一个新链表,用来存放之前链表中字符串的长度)

1
2
3
4
5
6
7
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()函数:

1
2
3
4
5
6
7
8
9
10
11
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的元素并组成新的链表)

1
2
let f = list.filter { s in s.count > 5 }
f // [Universe, Swifty]

为读者练习:map()filter() 的这些实现不是很快,因为它们将新节点追加到新链表的末尾。 回想一下,append是O(n),因为它需要扫描整个链表以找到最后一个节点。 你能加快速度吗? (提示:跟踪您添加的最后一个节点。)

另一种方法

到目前为止,您看到的LinkedList版本使用的是类,具有引用语义。 这没有什么不对,但这确实使它们比Swift的其他集合(例如ArrayDictionary)更重要。(译注: 这里应该是想表达,ArrayDictionary都是结构体,链表也可以使用结构体和枚举实现)

可以使用枚举实现具有值语义的链表。 这看起来有点像这样:

1
2
3
4
enum ListNode<T> {
indirect case node(T, next: ListNode<T>)
case end
}

与基于类的版本的最大区别在于,您对此链表所做的任何修改都将导致创建新副本。 这是否是您想要的取决于应用程序。

[如果有需求,我可能会更详细地填写此部分。]

符合Collection协议

符合Sequence协议的类型,其元素可以多次遍历。非破坏性地通过索引的下标访问,应该符合Swift标准库中定义的Collection协议。

这样做可以访问处理数据集合时常见的大量属性和操作。 除此之外,它还允许自定义类型遵循Swift开发人员常用的模式。

为了符合这个协议,类需要提供:
1 startIndexendIndex属性。
2 对元素的下标访问为O(1)。 需要记录这种时间复杂性的变化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/// 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)
}
}
}
1
2
3
4
5
public subscript(position: Index) -> T {
get {
return position.node!.value
}
}

因为集合负责管理自己的索引,下面的实现保留对链表中节点的引用。 索引中的标记属性表示链表中节点的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/// 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)
}
}

最后,链接能够通过以下实现计算给定的索引之后的索引。

1
2
3
public func index(after idx: Index) -> Index {
return LinkedListIndex<T>(node: idx.node?.next, tag: idx.tag+1)
}

要注意的一些事情

链接链表是灵活的,但许多操作是O(n)

在链表上执行操作时,您总是需要小心更新相关的nextprevious指针,还可能更新headtail指针。 如果你搞砸了,你的链表将不再正确,你的程序可能会在某些时候崩溃。 小心!

处理链表时,通常可以使用递归:处理第一个元素,然后在链表的其余部分再次递归调用该函数。 当没有下一个元素时你就完成了。 这就是链表是LISP等函数式编程语言的基础的原因。

作者:Matthijs Hollemans
翻译:Andy Ron
校对:Andy Ron

坚持原创技术分享,您的支持将鼓励我继续创作!
  • 本文标题: 【译】Swift算法俱乐部-链表
  • 本文作者: AndyRon
  • 发布时间: 2018年11月08日 - 18:33
  • 最后更新: 2018年11月08日 - 18:37
  • 本文链接: http://andyron.com/2018/Swift算法俱乐部-链表.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!