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)\)。
二分搜索不适用于链表，因为该算法基于直接跳转到不同的数组元素，而这在链表中是不可能的。
排序算法与数组的时间复杂度相同，这些算法已在本教程前面进行了说明。但请记住，基于直接按索引访问数组元素的排序算法不适用于链表。
