Python 中的链表

顾名思义，链表是一种节点相互链接的列表。每个节点包含数据和一个指针。它们链接的方式是，每个节点指向下一个节点在内存中的位置。

链表

链表由包含某种数据的节点以及指向下一个节点的指针（或链接）组成。

链表与数组的比较

理解链表最简单的方法或许是将链表与数组进行比较。

链表由节点组成，是一种我们自行构建的线性数据结构，而数组则是编程语言中已存在的数据结构，我们可以直接使用。

链表中的节点存储指向其他节点的链接，但数组元素不需要存储指向其他元素的链接。

注意：链表和数组在内存中的存储方式在“内存中的链表”页面中有详细说明。

下表通过比较链表和数组，帮助更好地理解链表。

以下是链表与数组相比的一些关键特性：

• 链表不像数组那样在内存中分配固定大小，因此当固定内存空间填满时，链表不需要像数组那样将整个列表移动到更大的内存空间。
• 链表节点在内存中并非连续排列，因此插入或删除节点时，链表节点不需要在内存中上下移动。
• 链表节点需要更多内存来存储指向其他节点的一个或多个链接。数组元素不需要那么多内存，因为数组元素不包含指向其他元素的链接。
• 链表操作通常比类似的数组操作更难编程，且需要更多代码行，因为编程语言对数组有更好的内置支持。
• 我们必须遍历链表才能找到特定位置的节点，但对于数组，我们可以通过编写 myArray[5] 直接访问元素。

链表的类型

链表有三种基本形式：

• 单向链表
• 双向链表
• 循环链表

单向链表是最简单的链表类型。它在内存中占用的空间更少，因为每个节点只有一个指向下一个节点的地址，如下图所示。

双向链表的节点同时包含指向前一个节点和后一个节点的地址，如下图所示，因此占用的内存更多。但双向链表的好处是，你可以在列表中双向移动。

循环链表类似于单向或双向链表，但第一个节点（“头”）和最后一个节点（“尾”）是相连的。

在单向或双向链表中，我们只需检查链接是否为 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)

# 删除 node4
node1 = deleteSpecificNode(node1, node4)

print("\nAfter deletion:")
traverseAndPrint(node1)

亲自试一试

在上面的 deleteSpecificNode 函数中，返回值是链表的新头节点。例如，如果要删除的节点是第一个节点，则返回的新头节点将是下一个节点。

在链表中插入节点

在链表中插入节点与删除节点非常相似，因为在两种情况下，我们都需要处理下一个指针，以确保不破坏链表。

要在链表中插入节点，我们首先需要创建节点，然后在插入的位置，我们需要调整指针，使前一个节点指向新节点，新节点指向正确的下一个节点。

下面的模拟演示了插入新节点时链接是如何调整的。

1. 新节点被创建
2. 节点 1 链接到新节点
3. 新节点链接到下一个节点

实例

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)

# 在位置 2 插入一个值为 97 的新节点
newNode = Node(97)
node1 = insertNodeAtPosition(node1, newNode, 2)

print("\nAfter insertion:")
traverseAndPrint(node1)

亲自试一试

在上面的 insertNodeAtPosition 函数中，返回值是链表的新头节点。例如，如果节点被插入到链表的开头，则返回的新头节点将是新节点。

链表操作的时间复杂度

下面我们讨论链表操作的时间复杂度，并将其与本教程前面讨论过的数组算法的时间复杂度进行比较。

请记住，时间复杂度只是根据大量数据 (n) 来说明算法所需的大致操作次数，并不告诉我们算法特定实现所需的确切时间。

这意味着，即使线性搜索对于数组和链表的时间复杂度相同：O(n)，也并不意味着它们所需的时间相同。算法运行的确切时间取决于编程语言、计算机硬件、数组和链表操作所需时间的差异以及其他许多因素。

链表的线性搜索与数组的线性搜索工作方式相同。从头节点开始遍历未排序的列表，直到找到具有特定值的节点。时间复杂度为 O(n)。

链表无法进行二分搜索，因为该算法基于直接跳转到不同的数组元素，这在链表中是不可能的。

排序算法的时间复杂度与数组相同，这些在本教程前面已经解释过。但请记住，基于直接通过索引访问数组元素的排序算法不适用于链表。