iOS中的链表 - 单向链表
什么是链表
链表是一种线性数据结构，它由一系列节点（Node）组成。每个节点包含数据以及指向下一个节点的引用。链表的第一个节点称为“头节点”（Head），最后一个节点则不指向任何节点，称为“尾结点”（Tail）。与数组不同，链表中的元素并不是连续存储的，而是通过节点间的引用进行连接。
链表与数组的区别
链表与数组的区别，我们可以四个方面来分析一下：
存储方式：
- 数组时一块连续的内存空间，所有元素按顺序存储在内存中。
- 链表的节点在内存中可以分散存放，通过节点中的指针（引用）进行连接。
大小的灵活性：
- 数组在初始化时需要定义大小，虽然在Swift中有动态数组，但扩容时可能会涉及到整个数组的重新分配和复制。
- 链表是动态的，大小不固定，添加或删除节点不会涉及到内存的重新分配，因此扩展性更好。
插入和删除效率：
在数组中，插入或删除元素可能需要移动多个元素，特别是在数组的中间位置操作时，时间复杂度为O(n)。
在链表中，插入和删除操作进需要调整相邻节点的引用，操作的时间复杂度为O(1)（在已知位置的情况下），尤其是在头部或尾部操作时更加高效。
访问效率：
- 数组支持通过索引直接访问任意元素，访问时间复杂度为O(1)。
- 链表需要从头节点逐个遍历来找到目标节点，因此访问时间复杂度为O(n)。
单向链表
节点
为了在Swift中实现链表，我们首先需要定义一个链表节点。每个节点既保存数据，也会包含指向下一个节点的引用。这可以通过下面的ListNode类来实现：
class ListNode {
/// 当前数据
var val: Int
/// 下一个节点
var next: ListNode?
/// 初始化节点，赋值数据，并将下一个节点设置为 nil
init(_ val: Int) {
self.val = val
self.next = nil
}
}在这个定义中：
- val存储当前节点的数据。
- next是对下一个节点的引用，next设置为可选类型（ListNode?）因为最后一个节点的next应该为nil。
- init(_val: Int)是节点的初始化方法，用来创建新的链表节点。
每个ListNode实例代表链表中的一个节点，链表通过这些节点的next属性串联起来。
链表
我们通过LinkedList类来管理链表。这个类包含头节点、尾节点以及链表的长度。以下是一个简单的链表类：
/// 链表
class LinkedList {
/// 头节点
var head: ListNode?
/// 尾节点
var tail: ListNode?
/// 链表长度
var length: Int = 0
/// 初始化链表为空
init() {
self.head = nil
self.tail = nil
self.length = 0
}
/// 向链表的尾部添加节点
func append(_ val: Int) {
let newNode = ListNode(val)
if let tailNode = tail {
tailNode.next = newNode
} else {
head = newNode
}
tail = newNode
length += 1
}
/// 打印链表中的所有节点
func printAllNodes() {
var currentNode = head
while let node = currentNode {
print(node.val)
currentNode = node.next
}
}
}
主要功能说明：
- head：链表的头节点，指向链表的第一个元素。如果链表为空，head为nil。
- tail：链表的尾节点，指向链表的最后一个元素。插入新节点时，tail方便我们快速找到链表末端。
- length：记录链表节点数量，方便进行长度的操作和判断。
该链表中一共定义了三个操作：
- 初始化链表：init()初始化一个空链表，head和tail都为nil，并将长度设置为0。
- 添加节点：append(_val: Int)方法可以向链表的末尾添加一个新的节点。首先，创建一个新节点newNode，然后检查当前链表是否为空。如果链表为空，直接设置head和tail都指向newNode；否则，将tail的next指向新节点，最后更新tail和length。
- 打印所有节点：printAllNodes()方法遍历链表，从head开始，逐个打印节点的值，直到链表结束（即当前节点的next为nil）。
使用示例：
let list = LinkedList()
list.append(1)
list.append(2)
list.append(3)
list.printAllNodes()
// 输出:
// 1
// 2
// 3
上述的添加节点方法为尾插法，将新的节点添加到链表的最末端。与之相对应的还有头插法。
添加节点
头插法的思想是将新节点插入到链表的开头，即让新节点成为链表的头节点，并且它的next指向之前的头节点。这样新节点会成为链表的第一个元素。
具体代码如下：
/// 向链表的头部添加节点（头插法）
func prepend(_ val: Int) {
let newNode = ListNode(val)
if let headNode = head {
newNode.next = headNode
} else {
tail = newNode
}
head = newNode
length += 1
}头插法的解释：
- 创建一个新的节点newNode，它保存要插入的值。
- 如果链表有头节点（即链表不为空），将新节点的next指向当前的head节点，从而把新节点插入链表的开头。
- 如果链表为空（即head == nil），说明这是链表的第一个节点，因此同时更新tail指向该节点。
- 最后更新head指向新节点，并且增加链表长度length。
删除链表中的节点同样也是链表操作的关键部分之一。我们需要针对不同的场景实现删除节点的方法，删除头节点、删除尾结点，和删除指定的节点。
删除节点
删除头节点
删除头节点是最简单的操作，只需要将head指向当前头节点的next，并更新链表长度。如果删除后的链表为空，还需要将tail设置为nil。
/// 删除头节点
func removeHead() {
if let headNode = head {
head = headNode.next
length -= 1
// 如果删除后链表为空，需要更新 tail
if head == nil {
tail = nil
}
}
}
删除尾节点
删除尾节点比较复杂，因为链表是单向的（没有前向指针），因此需要遍历找到为尾节点的前一个节点，然后将其next设为nil，并更新tail和链表长度。
/// 删除尾节点
func removeTail() {
// 链表为空或只有一个节点时特殊处理
if head == nil {
return
} else if head?.next == nil {
head = nil
tail = nil
length = 0
return
}
// 遍历找到倒数第二个节点
var currentNode = head
while currentNode?.next?.next != nil {
currentNode = currentNode?.next
}
// 移除尾节点并更新 tail
currentNode?.next = nil
tail = currentNode
length -= 1
}
删除特定值的节点
如果想要删除链表中某个特定值的节点，需要遍历链表，找到该节点并移除它。这个操作又包含三种情况：节点在头部，节点在中间，节点在尾部。
/// 删除包含特定值的节点
func remove(value: Int) {
// 如果链表为空，直接返回
if head == nil {
return
}
// 如果要删除的是头节点
if head?.val == value {
removeHead()
return
}
// 遍历链表找到要删除的节点
var currentNode = head
while currentNode?.next != nil && currentNode?.next?.val != value {
currentNode = currentNode?.next
}
// 如果找到了要删除的节点
if currentNode?.next != nil {
// 如果要删除的是尾节点
if currentNode?.next === tail {
removeTail()
} else {
// 删除中间节点，跳过要删除的节点
currentNode?.next = currentNode?.next?.next
length -= 1
}
}
}
单向链表的应用
现在有这样一个场景，给出了一个链表和一个x值，要求将链表中所有小于x的值放到左边，所有大于或等于x的值放到右边，并且原链表的节点顺序不能变。
例如：1,5,3,2,4,2，给定x=3,则需要返回 1,2,2,5,3,4。
对于这种情况，我们需要先处理左边，然后处理右边，最后将左右两边连接起来。
把题目抽象一下就是要实现这样一个函数：
func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
...
}
那我们只需要采用尾插法，遍历链表，将小于x的值接入一个新的链表，然后将大于或等于x的值接入一个新的链表，最后将两个链表进行连接即可。
func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
let smallDummy = ListNode(0) // 小于x的虚拟头节点
let largeDummy = ListNode(0) // 大于等于x的虚拟头节点
var smallList = smallDummy
var largeList = largeDummy
var current = head
// 遍历原链表
while let node = current {
if node.val < x {
smallList.next = node
smallList = node
} else {
largeList.next = node
largeList = node
}
current = current?.next
}
// 结束大于等于x的链表部分，避免形成环
largeList.next = nil
// 连接小于x的部分和大于等于x的部分
smallList.next = largeDummy.next
return smallDummy.next
}
代码中引用了dummy节点，它的作用就是作为一个虚拟的头节点。这里引入它的原因就是我们不知道要返回的新链表的头节点是那一个，它有可能是原链表的第一个节点，可呢个是在原链表的中间，也可能在最后，甚至可能不存在。而dummy节点的引入可以巧妙地涵盖以上的所有情况，可以用dummy.next方便地返回最终需要的头节点。
结语
通过文本的介绍，我们链接了单向链表的基本结构和核心操作，包括头插法、尾插法和节点删除操作。链表作为一种灵活的动态数据结构，适合用于需要频繁插入和删除的场景，尤其在处理大数据量时比数组更高效。尽管链表的实现相对复杂，但其独特的优势在某些应用场景中不可替代。