这是我参与11月更文应战的第11天，活动详情检查：2021终究一次更文应战

导言

数据结构是用于在计算机中安排和存储数据的容器，以便我们可以有效地履行操作。它们是编程最底子的组成部分。最闻名和最常用的数据结构，除了 数组、 栈 和 队伍等，还有一个非常有用的数据结构–链表。不过，Swift 没有供给内置的链表结构，所以，今天我们就来一步步的完成一个。

什么是单链表

Swift 中的链表

链表是链接节点的列表。节点是一个单独的元素，它包括一个泛型值和一个指向下一个节点的指针。链表有以下几种类型:

  • 单链表 每个节点只需一个指向下一个节点的指针。操作只能向一个方向传递
  • 双向链表 每个节点有两个指针，一个指向下一个节点，另一个指向前一个节点。操作可以向前和向后两个方向进行
  • 循环链表 终究一个节点的下一个指针指向第一个节点，第一个节点的上一个指针指向终究一个节点

今天我们来完成 Swift 中的单链表。

Node

Node 有必要定义为 Class。因为规划到引证，所以它需求是引证类型，Node 类有两个特色：

  • value 存储节点实践值的泛型数据类型
  • next 指向下一个节点的指针
class Node<T> {
    var value: T
    var next: Node<T>?
    init(value: T, next: Node<T>? = nil) {
        self.value = value
        self.next = next
    }
}

链表

与 Node 不同，链表是一种值类型，定义为 Struct。默许情况下，链表有三个底子特色:

  • head链表的第一个节点
  • tail链表的终究一个节点
  • isEmpty链表是否为空

当然，你可以依据需求增加其他特色，例如:

  • count链表的节点个数
  • description链表的描绘文本
struct LinkedList<T> {
 var head: Node<T>?
 var tail: Node<T>?
 var isEmpty: Bool { head == nil }
 init() {}
}

与栈和队伍不同，链表不包括可以直接调用和使用的数据集结。列表中的一切节点都有必要链接到下一个可用的节点(假设有的话)。

Push

把数据增加到链表头部，这意味着当时的 head 将被替换为新节点，新节点将成为链表的 head。

struct LinkedList<T> {
    ...
    mutating func push(_ value: T) {
        head = Node(value: value, next: head)
        if tail == nil {
            tail = head
        }
    }
}

通过调用 push(_ value: T) ，我们用该值创立一个新节点，并使新节点指向原本的 head。然后我们用新节点替换 head，这样原本的 head 就成为链表的第二个节点。

Swift 中的链表

Append

与 push 相似，我们将数据增加到链表的末尾。这意味着当时的尾部将被替换为新节点，新节点将成为新的尾部。

struct LinkedList<T> {
    ...
    mutating func append(_ value: T) {
        let node = Node(value: value)
        tail?.next = node
        tail = node
    }
}

通过调用 append(_ value: T) ，我们创立了一个新节点，并将原本的尾部指向新节点。终究，我们将原本的 tail 替换为新的节点，因此原本的 tail 成为列表的倒数第二个节点。新的节点将成为新的尾部

Swift 中的链表

Node At

链表不能通过下标索引取值，因此我们不能像数组 array[0] 那样读取数据集结。

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

为了获取某个索引对应的 Node，需求遍历。

Insert

正如我之前所说，链表不能通过索引下标取值。链表只知道哪个节点链接到哪个节点。为了告诉链表在特定方位插入一个节点，我们需求找到链接到该方位的节点。v需求用到上面的函数：node(at index: Int) -> Node<T>?

struct LinkedList<T> {
    ...
    func insert(_ value: T, after index: Int) {
        guard let node = node(at: index) else { return }
        node.next = Node(value: value, next: node.next)
    }
}

首要，我们有必要找到坐落给定方位的节点。我们接下来让它指向新节点，新节点指向原本的下一个节点。

Swift 中的链表

Pop

我们将 head 从列表中删去，这样第二个节点将成为 head:

struct LinkedList<T> {
    ...
    mutating func pop() -> T? {
        defer {
            head = head?.next
            if isEmpty {
                tail = nil
            }
        }
        return head?.value
    }
}

回来原本的 head 的值，并用原本的下个节点替换原本的 head，这样原本的下个节点就成为了 head。

Swift 中的链表

Remove Last

与 pop() 相似，这是删去链表的尾部，因此倒数第二个节点将成为尾部。

struct LinkedList<T> {
    ...
    mutating func removeLast() -> T? {
        guard let head = head else { return nil }
        guard let _ = head.next else { return pop() }
        var previousNode = head
        var currentNode = head
        while let next = currentNode.next {
            previousNode = currentNode
            currentNode = next
        }
        previousNode.next = nil
        tail = previousNode
        return currentNode.value
    }
}

但与 pop() 不同的是，去掉尾部节点有点杂乱，因为尾部不知道前一个节点是谁。我们需求遍历链表以找到尾部之前的节点，并将其设置为尾部。

  • 假设头部是nil，意味着该列表是空的，我们没有什么要删去，然后回来nil
  • 假设head.next是nil，这意味着只需一个节点在链表中，然后删去头
  • 循环遍历列表，找到尾部之前的节点，并将其设置为尾部

Remove After

与 insert(_ value: T, after index: Int) 相似，我们需求先找到待删去方位的节点。

struct LinkedList<T> {
    ...
    mutating func remove(after index: Int) -> T? {
        guard let node = node(at: index) else { return nil }
            defer {
                if node.next === tail {
                tail = node
            }
            node.next = node.next?.next
        }
        return node.next?.value
    }
}

移除指定索引处的节点有点扎手，因此我们底子上只是越过一个节点，然后指向那个节点之后的节点。

Swift 中的链表

总结

这些是单链表通常具有的底子特色和函数。当然，你也可以在这些基础上增加其他特色和函数。