DSA 链表操作
链表操作
我们可以对链表进行的基本操作包括
- 遍历
- 删除节点
- 插入节点
- 排序
为了简单起见，下面将使用单链表来解释这些操作。
链表遍历
遍历链表意味着按照从一个节点到下一个节点的链接顺序遍历整个链表。
遍历链表通常用于搜索特定节点，读取或修改节点的内容，删除节点或在该节点之前或之后插入节点。
为了遍历单链表，我们从链表中的第一个节点（头节点）开始，沿着该节点的下一个链接，以及下一个节点的下一个链接，依此类推，直到下一个地址为 null，就像下面的动画一样。
下面的代码按照与上面动画相同的方式打印出节点值，因为它遍历链表。
示例
Python 中的单链表遍历
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverseAndPrint(head):
currentNode = head
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
traverseAndPrint(node1)查找链表中的最小值
让我们通过遍历单链表并检查每个值来找到单链表中的最小值。
在链表中找到最小值与我们在数组中找到最小值的方式非常类似，只是我们需要沿着下一个链接才能到达下一个节点。
这是在原则上查找链表中最小值的工作方式
最小值:
为了找到最小值，我们需要像在前面的代码中那样遍历列表。但是，除了遍历列表之外，我们还必须在找到具有较低值的节点时更新当前最小值。
在下面的代码中，查找最小值的算法被移到名为 findLowestValue 的函数中。
示例
Python 中的单链表查找最小值
class Node:
def __init__(self, data):
self.data = data
self.next = None
def findLowestValue(head):
minValue = head.data
currentNode = head.next
while currentNode:
if currentNode.data < minValue:
minValue = currentNode.data
currentNode = currentNode.next
return minValue
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
print("The lowest value in the linked list is:", findLowestValue(node1))上面标记的行是算法的核心。初始最小值被设置为第一个节点的值。然后，如果找到更小的值，则最小值变量被更新。
运行示例 »删除链表中的节点
在这种情况下，我们拥有要删除的节点的链接（或指针或地址）。
重要的是在删除节点之前连接节点两侧的节点，以便链表不会断开。
因此，在删除节点之前，我们需要从前面的节点获取下一个指针，并将前面的节点连接到新的下一个节点，然后再删除中间的节点。
在单链表中，就像我们这里的情况一样，为了从前面的节点获取下一个指针，我们实际上需要从头开始遍历链表，因为没有办法从要删除的节点向后移动。
下面的模拟显示了我们要删除的节点，以及如何在删除节点之前先遍历链表以正确连接链表，而不会破坏链表。
此外，在删除节点之前，将下一个指针连接到要删除节点后的节点是一个好主意。这样做是为了避免“悬挂”指针，即指向空值的指针，即使只是短暂的时刻。
在下面的代码中，删除节点的算法被移到名为 deleteSpecificNode 的函数中。
示例
Python 中的单链表删除特定节点
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverseAndPrint(head):
currentNode = head
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
def deleteSpecificNode(head, nodeToDelete):
if head == nodeToDelete:
return head.next
currentNode = head
while currentNode.next and currentNode.next != nodeToDelete:
currentNode = currentNode.next
if currentNode.next is None:
return head
currentNode.next = currentNode.next.next
return head
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
print("Before deletion:")
traverseAndPrint(node1)
# Delete node4
node1 = deleteSpecificNode(node1, node4)
print("\nAfter deletion:")
traverseAndPrint(node1)在上面的 deleteSpecificNode 函数中，返回值是链表的新头节点。例如，如果要删除的节点是第一个节点，则返回的新头节点将是下一个节点。
插入链表中的节点
在链表中插入节点与删除节点非常类似，因为在这两种情况下，我们都需要处理下一个指针以确保我们不会破坏链表。
为了在链表中插入节点，我们首先需要创建节点，然后在我们插入的位置调整指针，以便前面的节点指向新节点，而新节点指向正确的下一个节点。
下面的模拟显示了在插入新节点时如何调整链接。
- 创建新节点
- 节点 1 连接到新节点
- 新节点连接到下一个节点
示例
Python 中的单链表插入节点
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverseAndPrint(head):
currentNode = head
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
def insertNodeAtPosition(head, newNode, position):
if position == 1:
newNode.next = head
return newNode
currentNode = head
for _ in range(position - 2):
if currentNode is None:
break
currentNode = currentNode.next
newNode.next = currentNode.next
currentNode.next = newNode
return head
node1 = Node(7)
node2 = Node(3)
node3 = Node(2)
node4 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
print("Original list:")
traverseAndPrint(node1)
# Insert a new node with value 97 at position 2
newNode = Node(97)
node1 = insertNodeAtPosition(node1, newNode, 2)
print("\nAfter insertion:")
traverseAndPrint(node1)在上面的 insertNodeAtPosition 函数中，返回值是链表的新头节点。例如，如果节点插入在链表的开头，则返回的新头节点将是新节点。
其他链表操作
我们上面只介绍了三种基本的链表操作：遍历（或搜索）、节点删除和节点插入。
还有很多其他操作可以对链表进行，例如排序。
之前在教程中，我们已经介绍了许多排序算法，我们也可以在链表上执行这些排序算法中的许多。例如，以选择排序为例。在选择排序中，我们找到最小值，将其删除，然后将其插入开头。我们也可以对链表执行同样的操作，对吧？我们已经看到了如何遍历链表、如何删除节点以及如何插入节点。
注意：我们不能使用计数排序、基数排序或快速排序等排序算法对链表进行排序，因为它们使用索引直接根据元素的位置修改数组元素。
链表与数组
这些是与数组相比的一些关键链表属性。
- 链表不像数组那样被分配到内存中的固定大小空间，因此当固定内存空间被填满时，链表不需要像数组那样将整个列表移动到更大的内存空间中。
- 链表节点不会像数组元素那样在内存中连续排列，因此在插入或删除节点时，链表节点不需要在内存中向上或向下移动。
- 链表节点需要更多的内存来存储一个或多个指向其他节点的链接。数组元素不需要那么多的内存，因为数组元素不包含指向其他元素的链接。
- 链表操作通常比类似的数组操作更难编程，并且需要更多行代码，因为编程语言对数组有更好的内置支持。
- 我们必须遍历链表才能找到特定位置的节点，但对于数组，我们可以通过编写 myArray[5] 来直接访问元素。
注意: 在使用 Java 或 Python 等编程语言中的数组时，即使我们不需要编写代码来处理数组填满其内存空间的情况，也不需要在删除或插入元素时在内存中向上或向下移动元素，这些操作仍然在后台发生，并且可能会在时间敏感的应用程序中造成问题。
链表操作的时间复杂度
这里我们将讨论链表操作的时间复杂度，并将它们与我们之前在本教程中讨论过的数组算法的时间复杂度进行比较。
请记住，时间复杂度只说明了算法根据大量数据 \(n\) 所需的大致操作次数，并不告诉我们算法的特定实现所花费的确切时间。
这意味着，即使线性搜索被认为对数组和链表具有相同的时间复杂度：\(O(n)\)，但这并不意味着它们花费相同的时间。算法运行的确切时间取决于编程语言、计算机硬件、数组和链表操作所需时间的差异，以及许多其他因素。
线性搜索 对于链表和数组的工作方式相同。从头节点遍历一个无序值列表，直到找到具有特定值的节点。时间复杂度为 \(O(n)\)。
二分搜索 不适用于链表，因为该算法基于直接跳转到不同的数组元素，而链表是不允许的。
排序算法与数组的相同时间复杂度，这些在本章前面已作了解释。但请记住，基于直接访问索引处的数组元素的排序算法不适用于链表。
