Swift数据结构和算法04_链表初级

作者: 张芳涛 | 来源:发表于2022-02-26 02:27 被阅读0次

前言

有需要的同学可以订阅专栏：Swift数据结构和算法专题
代码地址：Swift数据结构和算法代码

正文

链表是以线性、单向顺序排列的值的集合。与 Swift Array 等连续存储选项相比，链表具有一些理论上的优势：

• 从列表前面插入和删除的时间是固定的的。

• 可靠的性能特征。

一个单链表

如图所示，链表是一个节点链。节点有两个职责：

持有价值。
持有对下一个节点的引用。 nil 值表示列表的结尾。

一个值为12的节点
在本章中，我们将实现一个链表并了解与之相关的常见操作。我们将了解每个操作的时间复杂度，并实现一个简洁的 Swift 小功能，称为copy-on-write。

打开本章的starter playground，开始撸代码！

！节点

在 Sources 目录中创建一个新的 Swift 文件并将其命名为 Node.swift。将以下内容添加到文件中：

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

extension Node: CustomStringConvertible {

  public var description: String { 
    guard let next = next else { 
      return "\(value)" 
      } 
      return "\(value) -> " + String(describing: next) + " " 
    }
}

导航到 Playground 页面并添加以下内容：

example(of: "creating and linking nodes") { 
  let node1 = Node(value: 1) 
  let node2 = Node(value: 2) 
  let node3 = Node(value: 3)

  node1.next = node2 
  node2.next = node3

 print(node1)
}

我们刚刚创建了三个节点并将它们连接起来：

包含值 1、2 和 3 的链表

在控制台中，我们应该看到以下输出：

---Example of creating and linking nodes---
1 -> 2 -> 3

就实用性而言，当前构建列表的方法还有很多不足之处。我们可以很容易地看到以这种方式构建长列表是不切实际的。缓解此问题的常用方法是构建一个管理 Node 对象的 LinkedList。

链表

在 Sources 目录中创建一个新文件并将其命名为 LinkedList.swift。将以下内容添加到文件中：

public struct LinkedList<Value> { 

  public var head: Node<Value>? 
  public var tail: Node<Value>? 
  public init() {} 
  public var isEmpty: Bool { 
    head == nil 
  }
} 

extension LinkedList: CustomStringConvertible { 
    public var description: String { 
      guard let head = head else { 
        return "Empty list" 
      } 
    return String(describing: head) 
  } 
}

链表有头尾的概念，分别指链表的第一个和最后一个节点：

头节点和尾节点

将值添加到列表

如前所述，我们将提供一个接口来管理 Node 对象。我们将首先处理添加值。向链表添加值的方法有三种，每种方法都具有独特的性能特征：

push：在列表的前面添加一个值。
append：在列表末尾添加一个值。
insert(after:)：在特定列表节点之后添加一个值。

我们将在后面实现其中的每一个并分析它们的性能特征。

push操作

在列表的前面添加一个值称为push操作。这也称为头先插入。它的代码非常简单。

将以下方法添加到 LinkedList：

public mutating func push(_ value: Value) { 
  head = Node(value: value, next: head) 
  if tail == nil { 
    tail = head 
  } 
}

如果我们要推入一个空列表，则新节点既是列表的头部也是尾部。

在 Playground页面中，添加以下内容：

example(of: "push") {

  var list = LinkedList<Int>()

  list.push(3) 
  list.push(2) 
  list.push(1)
 
 print(list)
}

控制台输出应显示如下：

---Example of push---
1 -> 2 -> 3

append操作

下一个操作是append。这会在列表末尾添加一个值，称为尾端插入。

在 LinkedList.swift 中，在 push下方添加以下代码：

public mutating func append(_ value: Value) {

  // 1 
  guard !isEmpty else {
    push(value)
    return 
  }

  // 2 
  tail!.next = Node(value: value)

  // 3 
  tail = tail!.next
}

这段代码比较简单：

和之前一样，如果列表为空，则需要将 head和tail都更新为新节点。由于在空列表上追加在功能上与push相同，因此调用puah来完成工作。
在所有其他情况下，我们在尾节点之后创建一个新节点。由于使用上述guard !isEmpty，因此可以保证强制解包成功。
由于这是尾端插入，因此新节点也是列表的尾部。跳回操场并在底部写下以下内容：

example(of: "append") {

var list = LinkedList<Int>()

list.append(1)
list.append(2) 
list.append(3)

print(list)
}

我们将会在控制台看到如下的输出结果：

---Example of append---
1 -> 2 -> 3

insert(after:)操作

添加值的第三个也是最后一个操作是 insert(after:)。此操作在列表中的特定位置插入一个值，需要两个步骤：

在列表中查找特定节点。
插入新节点。

首先，我们需要将实现代码以查找要插入值的节点。

在 LinkedList.swift 中，在 append的正下方添加以下代码：

public func node(at index: Int) -> Node<Value>? { 
  // 1 
  var currentNode = head 
  var currentIndex = 0
  // 2 
 while currentNode != nil && currentIndex < index {
    currentNode = currentNode!.next
    currentIndex += 1 
 }
 return currentNode
}

node(at:) 将尝试根据给定索引检索列表中的节点。由于我们只能从头节点访问列表的节点，因此必须进行迭代遍历。下面是具体操作方式：

创建一个新的 head 引用并跟踪当前的遍历次数。
使用 while 循环，将引用向下移动到列表中，直到到达所需的索引。空列表或越界索引将导致 nil 返回值。

现在我们需要插入新节点。

在 node(at:) 正下方添加以下方法：

// 1 
@discardableResult 
public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> { 
  // 2 
  guard tail !== node else {
    append(value)
    return tail!
  } 
  // 3 
  node.next = Node(value: value, next: node.next) 
  return node.next!
}

解析一下上述代码：

@discardableResult让调用者忽略此方法的返回值，而编译器不会跳来跳去警告你。
如果这个方法与尾节点一起调用，我们将调用功能等效的 append方法。这将负责更新尾部。
否则，我们只需将新节点与列表的其余部分连接起来并返回新节点。

跳回操场页面进行测试。将以下内容添加到playground底部：

example(of: "inserting at a particular index") {

  var list = LinkedList<Int>()
  list.push(3) list.push(2) list.push(1)

  print("Before inserting: \(list)") 
  var middleNode = list.node(at: 1)!
  for _ in 1...4 { 
    middleNode = list.insert(-1, after: middleNode) 
  } 
  print("After inserting: \(list)")
}

执行代码，我们将会在控制台看到如下输出结果：

---Example of inserting at a particular index---
Before inserting: 1 -> 2 -> 3 
After inserting: 1 -> 2 -> -1 -> -1 -> -1 -> -1 -> 3

性能分析

我们已经实现了将值添加到链表的三个操作以及在特定索引处查找节点的方法。

接下来，我们将专注于相反的操作：移除操作。

从链表中删除Value

删除节点主要有以下三种操作：

pop：移除列表最前面的值。
removeLast：删除列表末尾的值。
remove(at:)：删除列表中任意位置的值。

我们接下来将实现这三个并分析它们的性能特征。

pop操作

删除列表前面的值通常称为 pop。这个操作几乎和 push 一样简单，所以直接进入主题。

将以下方法添加到 LinkedList：

@discardableResult 
public mutating func pop() -> Value? { 
  defer { 
    head = head?.next 
    if isEmpty { 
      tail = nil 
    } 
  } 
  return head?.value 
}

pop 返回从列表中删除的值。此值是可选的，因为列表可能为空。

通过将头部向下移动一个节点，我们已经有效地删除了列表的第一个节点。一旦方法完成，ARC 将从内存中删除旧节点，因为不再有引用附加到它。如果列表为空，则将 tail 设置为 nil。回到playground页面并通过在底部添加以下代码来测试它：

example(of: "pop") {
  var list = LinkedList<Int>()
  list.push(3) 
  list.push(2) 
  list.push(1)

  print("Before popping list: \(list)")
  let poppedValue = list.pop() 
  print("After popping list: \(list)") 
  print("Popped value: " + String(describing: poppedValue))
}

我们将会看到如下输出结果：

---Example of pop---
Before popping list: 1 -> 2 -> 3 
After popping list: 2 -> 3 
Popped value: Optional(1)

removeLast 操作

删除列表的最后一个节点有点不方便。尽管我们有对尾节点的引用，但如果没有对它之前的节点的引用，我们就无法将其删除。因此，我们将不得不进行艰苦的遍历。在 pop 下方添加以下代码：

@discardableResult 
public mutating func removeLast() -> Value? { 
  // 1 
  guard let head = head else { 
    return nil 
  } 
  // 2 
  guard head.next != nil else { 
    return pop() 
  } 
  // 3 
  var prev = head 
  var current = head

  while let next = current.next { 
   prev = current 
    current = next 
  } 
  // 4 
  prev.next = nil 
  tail = prev 
  return current.value
}

以下是代码中发生的事情：

如果 head 为 nil，则没有要删除的内容，因此返回 nil。

2.如果列表只包含一个节点，removeLast在功能上等同于pop。由于 pop 将处理更新 head和 tail 引用，因此我们只需将这项工作委托给它。

我们一直在寻找下一个节点，直到 current.next 为 nil。这表示 current 是列表的最后一个节点。
由于 current是最后一个节点，我们只需使用 prev.next 引用断开它。我们还要确保更新尾部引用。

回到playground页面并在底部添加以下内容：

example(of: "removing the last node") {

  var list = LinkedList<Int>()

  list.push(3) 
  list.push(2) 
  list.push(1)
  print("Before removing last node: \(list)") 
  let removedValue = list.removeLast()

  print("After removing last node: \(list)") 
  print("Removed value: " + String(describing: removedValue))
}

在控制台底部，我们会看到如下的输出结果：

---Example of removing the last node---
Before removing last node: 1 -> 2 -> 3 
After removing last node: 1 -> 2 
Removed value: Optional(3)

removeLast要求我们一直遍历列表。这使得 O(n) 操作相对低效。

remove(after:)操作

最后的删除操作是删除列表中特定点的特定节点。这很像 insert(after:);我们将首先找到要删除的节点之前的节点，然后取消链接。

删除中间的节点

回到LinkedList.swift文件，并且在removeLast后面添加如下代码：

@discardableResult 
public mutating func remove(after node: Node<Value>) -> Value? { 
  defer { 
    if node.next === tail { 
      tail = node 
    } 
    node.next = node.next?.next 
  } 
  return node.next?.value 
}

节点的取消链接发生在延迟块中。如果删除的节点是尾节点，则需要特别注意，因为尾引用必须更新。

回到playground添加如下测试代码：

example(of: "removing a node after a particular node") {

  var list = LinkedList<Int>()

  list.push(3) 
  list.push(2) 
  list.push(1)

  print("Before removing at particular index: \(list)") 
  let index = 1 
  let node = list.node(at: index - 1)!
  let removedValue = list.remove(after: node)

 print("After removing at index \(index): \(list)") 
 print("Removed value: " + String(describing: removedValue))
}

我们会在控制台看到如下输出结果：

---Example of removing a node after a particular node---
Before removing at particular index: 1 -> 2 -> 3 
After removing at index 1: 1 -> 3 
Removed value: Optional(2)

尝试添加更多元素并使用 index 的值。与 insert(at:)类似，此操作的时间复杂度为 O(1)，但它需要我们事先对特定节点进行引用。

性能分析

我们已经到达另一个检查站！回顾一下，我们已经实现了从链表中删除值的三个操作：

至此，我们已经为世界上大多数程序员都可以关联的链表定义了一个接口。但是，要修饰 Swift语义还有很多工作要做。后面会有更详细地讲解。

Swift collection 协议

Swift 标准库有一组协议来帮助定义对特定类型的期望。这些协议中的每一个都为特性和性能提供了一定的保证。从这组协议中，我们将专注于四个与集合相关的协议。

以下是每个协议功能的快速摘要：

第 1 层，Sequence：序列类型提供对其元素的顺序访问。它带有一个重要的警告：使用顺序访问可能会破坏性地消耗元素，因此我们无法重新访问它们。
第2 层，Collection：集合类型是提供额外保证的序列类型。集合类型是有限的，允许重复的非破坏性顺序访问。
第 3 层，BidirectionalColllection：集合类型可以是双向集合类型，如果顾名思义，它可以允许在序列中上下双向移动。这对于链表是不可能的，因为我们只能从头到尾，反之则不行。
第 4 层，RandomAccessCollection：双向集合类型可以是随机访问集合类型，如果它可以保证访问特定索引处的元素所花费的时间与访问任何其他索引处的元素所花费的时间一样长。这对于链表来说是不可能的，因为访问靠近链表前面的节点比访问链表后面的节点要快得多。

对于这些，还有更多要说的。当我们为它们编写一致性时，我们将了解更多关于它们的信息。

一个链表可以得到 Swift collection协议中的两个限定条件。首先，由于链表是一个节点链，因此采用 Sequence协议是有意义的。其次，由于节点链是一个有限序列，因此采用 Collection 协议是有意义的。

成为一个 Swift collection

在本节中，我们将研究实现 Collection 协议。Collection 类型是有限序列并提供非破坏性顺序访问。 Swift 集合还允许通过下标进行访问，这是一个花哨的术语，表示索引可以映射到集合中的值。

下面是一个使用 Swift 数组下标的例子：

array[5]

数组的索引是一个 Int 值——本例中的值为 5。下标操作用方括号定义。使用带有索引的下标将从集合中返回一个值。

自定义collection索引

Collection协议方法性能的定义指标是将索引映射到值的速度。与 Swift Array等其他存储选项不同，链表无法使用整数索引实现 O(1) 下标操作。因此，我们的目标是定义一个自定义索引，其中包含对其各自节点的引用。

在LinkedList.swift中，添加以下扩展：

extension LinkedList: Collection {
  public struct Index: Comparable {
    public var node: Node<Value>?
    static public 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 public 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 } 
      }
   }
}

我们将使用此自定义索引来满足 Collection要求。在扩展中写入以下内容以完成它：

// 1 
public var startIndex: Index {
  Index(node: head) 
} 
// 2 
public var endIndex: Index {

 Index(node: tail?.next) 
} 
// 3
public func index(after i: Index) -> Index { 
 Index(node: i.node?.next) 
} 
// 4 
public subscript(position: Index) -> Value {
  position.node!.value 
}

startIndex 由链表的头部合理定义。
Collection 将 endIndex 定义为最后一个可访问值之后的索引，所以你给它 tail?.next。
index(after:)指示如何增加索引。我们只需为其提供下一个节点的索引。

4.下标用于将Index映射到集合中的值。由于我们已经创建了自定义索引，因此我们可以通过引用节点的值轻松地在恒定时间内实现此目的。

以上就是采用Collection的程序。导航回 Playground页面并继续：

example(of: "using collection") {
  var list = LinkedList<Int>()
  for i in 0...9 { 
    list.append(i) 
  }
  print("List: \(list)") 
  print("First element: \(list[list.startIndex])") 
  print("Array containing first 3 elements: \ (Array(list.prefix(3)))") 
  print("Array containing last 3 elements: \ (Array(list.suffix(3)))")

  let sum = list.reduce(0, +) 
  print("Sum of all values: \(sum)")
}

我们会在控制台看到下面的输出：

---Example of using collection---
List: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 
First element: 0 
Array containing first 3 elements: [0, 1, 2] 
Array containing last 3 elements: [7, 8, 9] 
Sum of all values: 45

值语义和写时复制

Swift 集合的另一个重要品质是它具有值语义。这是使用写时复制有效地实现的，在此称为 COW。为了说明值语义的概念，我们将使用数组来探索行为。

在 Playground 页面的底部写下以下内容：

example(of: "array cow") { 
  let array1 = [1, 2] 
  var array2 = array1

  print("array1: \(array1)") 
  print("array2: \(array2)")

  print("---After adding 3 to array 2---") 
  array2.append(3) 
  print("array1: \(array1)") 
  print("array2: \(array2)")
}

我们会看到如下的输出结果：

---Example of array cow---
array1: [1, 2] 
array2: [1, 2]

---After adding 3 to array 2---
array1: [1, 2] 
array2: [1, 2, 3]

修改array2 时，array1 的元素不变。在底层，array2 在调用 append 时会复制底层存储：

现在，检查我们的链表是否具有值语义。在 Playground页面的底部写下以下内容：

example(of: "linked list cow") {
  var list1 = LinkedList<Int>()
  list1.append(1) 
  list1.append(2) 
  var list2 = list1 
  print("List1: \(list1)") 
  print("List2: \(list2)")

  print("After appending 3 to list2") 
  list2.append(3) 
  print("List1: \(list1)") 
  print("List2: \(list2)")
}

我们将会看到如下的输出结果：

---Example of linked list cow---
List1: 1 -> 2 
List2: 1 -> 2 
After appending 3 to list2 
List1: 1 -> 2 -> 3 
List2: 1 -> 2 -> 3

不幸的是，我们的链表没有值语义！这是因为我们的底层存储使用引用类型（节点）。这是一个严重的问题，因为 LinkedList是一个结构并且应该使用值语义。实施 COW 将解决此问题。

使用 COW实现价值语义的策略相当简单。在改变链表的内容之前，我们想要执行底层存储的副本并将所有引用（头和尾）更新到新副本。

在 LinkedList.swift 中，将以下方法添加到 LinkedList：

private mutating func copyNodes() { 
  guard var oldNode = head else { 
    return 
  }

  head = Node(value: oldNode.value) 
  var newNode = head
  
  while let nextOldNode = oldNode.next {
    newNode!.next = Node(value: nextOldNode.value) 
    newNode = newNode!.next
    oldNode = nextOldNode
  }
  tail = newNode
}

此方法将用新分配的具有相同值的节点替换链表的现有节点。

现在找到 LinkedList 中标有 mutating 关键字的所有其他方法，并在每个方法的顶部调用 copyNodes。

总共有六种方法：

push
append
insert(after:)
pop
removeLast
remove(after:)

完成改造后，最后一个示例函数调用应产生以下输出：

---Example of linked list cow---
List1: 1 -> 2 
List2: 1 -> 2 
After appending 3 to list2 
List1: 1 -> 2 
List2: 1 -> 2 -> 3

这就是你想要的！好吧，除了在每个mutating调用中引入 O(n) 开销......

优化COW

每次变异调用的 O(n) 开销是不可接受的。两种策略有助于缓解这个问题。第一个是当节点只有一个所有者时避免复制。

isKnownUniquelyReferenced

在 Swift 标准库中有一个名为 isKnownUniquelyReferenced的函数。此函数可用于确定对象是否只有一个对其的引用。在链表 COW 示例中对此进行测试。

在最后一个示例函数调用中，找到我们编写 var list2 = list1 的行并将其更新为以下内容：

print("List1 uniquely referenced: \ (isKnownUniquelyReferenced(&list1.head))") 
var list2 = list1 
print("List1 uniquely referenced: \ (isKnownUniquelyReferenced(&list1.head))")

结果如下：

List1 uniquely referenced: true 
List1 uniquely referenced: false

使用 isKnownUniquelyReferenced 可以检查底层节点对象是否共享！在 copyNodes 的顶部添加以下条件：

guard !isKnownUniquelyReferenced(&head) else { 
  return 
}

现在可以发现COW 仍然非常有效：

---Example of linked list cow---
List1: 1 -> 2 
List2: 1 -> 2 
After appending 3 to list2 
List1: 1 -> 2 
List2: 1 -> 2 -> 3

通过此更改，我们的链表性能将利用 COW的优势恢复其先前的性能。

一个小困境

在之前的示例代码中添加以下代码：

print("Removing middle node on list2") 
if let node = list2.node(at: 0) { 
  list2.remove(after: node) 
} 
print("List2: \(list2)")

我们会看到如下的输出：

---Example of linked list cow---
List1: 1 -> 2 
List2: 1 -> 2 
After appending 3 to list2 
List1: 1 -> 2 
List2: 1 -> 2 -> 3 
Removing middle node on list2 
List2: 1 -> 2 -> 3

删除操作不再起作用。原因在于我们所做的 CoW 优化。因为每个突变都可以触发节点的副本，所以 remove(after:) 实现是在错误的节点集上进行删除。为了解决这个问题，我们将编写一个专门版本的 copyNodes 方法。返回到 Sources目录中的 LinkedList.swift并在 copyNodes 方法下方编写以下内容：

private mutating func copyNodes(returningCopyOf node: Node<Value>?) -> Node<Value>? {
  guard !isKnownUniquelyReferenced(&head) else { 
    return nil 
  } 
  guard var oldNode = head else {
    return nil 
  }
  head = Node(value: oldNode.value) 
  var newNode = head 
  var nodeCopy: Node<Value>?
  while let nextOldNode = oldNode.next { 
    if oldNode === node { 
      nodeCopy = newNode 
    } 
    newNode!.next = Node(value: nextOldNode.value) 
    newNode = newNode!.next 
    oldNode = nextOldNode  
  }
  return nodeCopy
}

此方法与之前的实现有许多相似之处。主要区别在于它将根据传入的参数返回新复制的节点。将 remove(after:)方法更新为以下内容：

@discardableResult 
public mutating func remove(after node: Node<Value>) -> Value? {
  guard let node = copyNodes(returningCopyOf: node) else { return nil } 
  defer { 
    if node.next === tail { 
      tail = node 
    } 
    node.next = node.next?.next 
  } 
  return node.next?.value 
}

我们现在正在使用刚刚创建的方法并在新复制的节点上执行删除。

共享节点

第二个优化是节点的部分共享。事实证明，在某些情况下我们可以避免复制。对所有场景的全面评估超出了本书的范围，但这会让你对所涉及的内容有所了解。

看下面的例子（这个不用写了）：

var list1 = LinkedList<Int>()
(1...3).forEach { list1.append($0) } 
var list2 = list1

共享节点

现在考虑在禁用cow的情况下对 list2 执行push操作的后果：

list2.push(0)

list1 是否受 list2 上的推送操作影响？在这种情况下不是！如果要打印这两个列表，我们将获得以下输出：

List1: 1 -> 2 -> 3 
List2: 0 -> 1 -> 2 -> 3

在这种情况下，将 100 推送到 list1 的结果也是安全的：

list1.push(100)

如果我们现在要打印这两个列表，将得到以下输出：

List1: 100 -> 1 -> 2 -> 3 
List2: 0 -> 1 -> 2 -> 3

链表的单向性意味着头先插入可以忽略“COW ”！

关键点

链表是线性的和单向的。一旦将引用从一个节点移动到另一个节点，就无法返回。
链表的头部优先插入的时间复杂度为 O(1)。数组对于头先插入具有 O(n) 时间复杂度。
遵循 Swift collection协议（如 Sequence 和 Collection）会自动让我们访问许多有用的方法。
Copy-on-write 行为使我们能够在保持良好性能的同时实现值语义。

上一章	目录	下一章

Swift数据结构和算法04_链表初级

前言

正文

链表

将值添加到列表

push操作

append操作

insert(after:)操作

性能分析

从链表中删除Value

pop操作

removeLast 操作

remove(after:)操作

性能分析

Swift collection 协议

成为一个 Swift collection

自定义collection索引

值语义和写时复制

优化COW

isKnownUniquelyReferenced

一个小困境

共享节点

关键点

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Swift数据结构和算法