Python 链表：示例教程

链表是一种在数据组织与管理中发挥关键作用的数据结构。它由一系列存储在内存随机位置的节点构成，有助于高效地管理内存。链表中的每个节点包含两个主要部分：数据本身以及指向序列中下一个节点的引用。

如果这个概念乍听有些复杂，别担心！

我们将从基础讲起，解释什么是链表、为何使用链表，以及它所具备的独特优势。

为什么选择链表？

链表的设计初衷是为了解决普通列表和数组在存储数据时的一些缺点，如下所述：

插入与删除更便捷

在列表中，若要在末尾以外的位置插入或删除元素，必须将其后所有元素整体移动到新的位置。此过程的时间复杂度为 O(n)，会显著影响性能，尤其在列表规模变大时。如果您还不熟悉列表的工作原理或其实现方式，可以阅读我们的Python 列表教程。

而链表的运作方式不同。它将元素存放在不连续的内存位置，并通过指针连接到后续节点。这种结构使链表能够仅通过修改链接，在任意位置添加新元素或跳过被删除的元素。

一旦您直接持有插入或删除位置处节点的引用，操作本身就是 O(1)。不过，找到该位置仍需 O(n) 的遍历，所以只有在您已持有相关节点的指针（例如在链表头部操作时）时，O(1) 的优势才成立。

动态大小

Python 列表是动态数组，也就是说它们可以灵活地调整大小。

然而，这一过程涉及一系列复杂操作，包括将数组重新分配到更大的内存块中。由于需要将元素复制到新块，并可能一次性分配超过当下所需的空间，这种重分配并不高效。

相较之下，链表可以在无需重新分配或调整大小的情况下动态增长与收缩。这使其在需要高度灵活性的任务中更具优势。

内存效率

列表会为其全部元素在一块连续的内存中分配空间。如果列表需要超出初始大小，就必须分配一块更大的连续内存，并将所有现有元素复制过去。这个过程既耗时又低效，尤其对大型列表而言。另一方面，如果高估了初始大小，未使用的内存就会被浪费。

而链表为每个元素分别分配内存。由于可在添加新元素时再分配内存，这种结构能更好地利用内存。

何时应使用链表？

尽管链表相较于常规列表和数组在动态大小与内存效率方面有优势，但它也存在局限。由于每个元素都需要存储指向下一个节点的指针，链表的单个元素内存开销更高。此外，这种数据结构不支持直接访问数据。访问某个元素需要从链表开头顺序遍历，因而查找时间复杂度为 O(n)。

在链表与数组之间进行选择，取决于应用的具体需求。链表在以下场景最为有用：

• 需要频繁插入和删除大量元素
• 数据规模不可预期或可能频繁变化
• 不需要对元素进行直接访问
• 数据集包含大型元素或复杂结构

链表的类型

链表有三种类型，各自在不同场景中具有独特优势：

单向链表

单向链表

单向链表是最简单的链表类型，每个节点包含一些数据以及对序列中下一个节点的引用。它只能沿一个方向遍历——从头节点（第一个节点）到尾节点（最后一个节点）。

单向链表中的每个节点通常由两部分组成：

• 数据：节点中存储的实际信息。
• 后继指针：指向下一个节点的引用。最后一个节点的后继指针通常为 null。

由于这种数据结构只能单向遍历，按值或索引访问特定元素需要从头开始，依次经过各节点直至找到目标节点。该操作的时间复杂度为 O(n)，对大型列表来说效率较低。

在单向链表的开头插入或删除节点非常高效，时间复杂度为 O(1)。但在中间或末尾进行插入与删除需要遍历到相应位置，时间复杂度为 O(n)。

单向链表的设计使其在需要在链表开头执行操作时格外实用。

双向链表

双向链表

单向链表的一个缺点是只能单向遍历，若有需要，无法回到前一个节点。这一限制会妨碍我们执行需要双向导航的操作。

双向链表通过在每个节点中加入一个额外指针来解决这个问题，使链表可以双向遍历。双向链表的每个节点包含三个元素：数据、指向下一个节点的指针，以及指向前一个节点的指针。

循环链表

循环链表

循环链表是一种特殊形式的链表，其最后一个节点会指回第一个节点，形成环状结构。这意味着与前面提到的单向和双向链表不同，循环链表没有终点，而是循环往复。

循环链表的循环特性使其非常适用于需要不断轮转的场景，例如从最后一位玩家回到第一位玩家的棋盘游戏，或计算机中的轮转调度（round-robin）等算法。

时间复杂度概览

快速对比链表与 Python 列表的表现：

关键信息：链表在头部的插入与删除可达 O(1)，但在其他方面处于劣势。如果您并不经常在数据结构的开头添加或移除元素，那么常规的 Python 列表往往是更好的选择。

如何在 Python 中创建链表

现在我们已经了解了链表是什么、为什么使用它以及它的不同变体，接下来将在 Python 中实现这些数据结构。本文配套的笔记本也可在这个 DataLab 工作簿中获取；如果您创建一份副本，便可编辑并运行代码。如果您本地运行代码遇到问题，这是一个很好的选择！

初始化节点

正如我们之前所学，节点是链表中的元素，用于存储数据以及指向序列中下一个节点的引用。以下是在 Python 中定义节点的方法：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

    def __repr__(self):
        return f"Node({self.data})"

上述代码通过两项主要操作来初始化一个节点：“data”属性被赋予表示节点所包含实际信息的值；“next”属性代表下一个节点的地址。当前它被设置为 None，表示尚未链接到链表中的任何其他节点。随着我们不断向链表添加新节点，该属性会更新为指向后继节点。

创建链表类

接下来，我们需要创建链表类。它将封装管理节点的所有操作，例如插入与删除。我们先从初始化链表开始：

class LinkedList:
    def __init__(self):
        self.head = None  # Initialize head as None

将 self.head 设为 None，表示链表最初为空，尚无可指向的节点。接下来我们将通过插入新节点来填充该链表。

在链表开头插入新节点

在 LinkedList 类中，我们将添加一个方法来创建新节点并将其放在链表的起始位置：

    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)  # Create a new node 
        new_node.next = self.head  # Next for new node becomes the   current head
        self.head = new_node  # Head now points to the new node

每次调用上述方法，都会创建一个包含您指定数据的新节点。该新节点的后继指针会被设置为当前链表的头节点，从而将其置于现有节点之前。最后，将新创建的节点设为链表的头节点。

现在我们将用一系列单词来填充该链表，以更好地理解插入操作的工作方式。为此，先创建一个用于遍历并打印链表内容的方法：

    def printList(self):
        temp = self.head # Start from the head of the list
        while temp:
            print(temp.data,end=' ') # Print the data in the current node
            temp = temp.next # Move to the next node
        print()  # Ensures the output is followed by a new line

上述方法会打印我们链表的内容。接下来使用已定义的方法，将一系列单词插入到链表中：“the quick brown fox”。

if __name__ == '__main__':
    # Create a new LinkedList instance
    llist = LinkedList()

    # Insert each letter at the beginning using the method we created
    llist.insertAtBeginning('fox') 
    llist.insertAtBeginning('brown') 
    llist.insertAtBeginning('quick')  
    llist.insertAtBeginning('the')  

    # Now 'the' is the head of the list, followed by 'quick', then 'brown' and 'fox'

    # Print the list
    llist.printList()

上述代码将产生如下输出：

"the quick brown fox"

在链表末尾插入新节点

我们接下来在 LinkedList 类中创建一个名为 insertAtEnd 的方法，在链表末尾创建新节点。若链表为空，新节点将成为头节点；否则，它会被追加到当前最后一个节点之后。看看实际实现：

    def insertAtEnd(self, new_data):
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

该方法首先创建一个新节点。随后检查链表是否为空，若为空，则将新节点设为头节点。否则，遍历链表找到最后一个节点，并将其后继指针指向新节点。

现在将此方法加入 LinkedList 类，并用它在链表末尾添加一个单词。为此，请将主函数修改如下：

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list
    llist.printList()

请注意，我们只需调用 insertAtEnd 方法，便可在链表末尾插入单词“jumps”。上述代码应输出：

"the quick brown fox jumps"

从链表开头删除节点

删除链表的第一个节点很简单，只需将头指针指向第二个节点即可。这样，第一个节点就不再属于该链表。为此，请在 LinkedList 类中加入以下方法：

def deleteFromBeginning(self):
    if self.head is None:
        return "The list is empty" # If the list is empty, return this string
    self.head = self.head.next  # Otherwise, remove the head by making the next node the new head

从链表末尾删除节点

要删除链表的最后一个节点，需要遍历链表找到倒数第二个节点，并将其后继指针设为 None。这样，最后一个节点就不再属于该链表。将以下方法复制粘贴到 LinkedList 类中：

def deleteFromEnd(self):
    if self.head is None:
        return "The list is empty" 
    if self.head.next is None:
        self.head = None  # If there's only one node, remove the head by making it None
        return
    temp = self.head
    while temp.next.next:  # Otherwise, go to the second-last node
        temp = temp.next
    temp.next = None  # Remove the last node by setting the next pointer of the second-last node to None

该方法首先检查链表是否为空，若为空则向用户返回提示信息。否则，若链表仅包含一个节点，则将其删除。对于包含多个节点的链表，该方法会定位到倒数第二个节点，并将其后继引用更新为 None。

现在更新主函数，以从链表的开头和末尾删除元素：

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from the beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()

上述代码会在删除前后打印链表，展示链表中的插入与删除操作如何工作。运行后应看到如下输出：

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox

在链表中查找特定值

本章的最后一个操作是检索链表中的特定值。实现方式是从链表头开始，逐个遍历节点，检查节点数据是否与目标值匹配。以下是该操作的一个实用实现：

def search(self, value):
    current = self.head  # Start with the head of the list
    position = 0  # Counter to keep track of the position
    while current: # Traverse the list
        if current.data == value: # Compare the list's data to the search value
            return f"Value '{value}' found at position {position}" # Print the value if a match is found
        current = current.next
        position += 1
    return f"Value '{value}' not found in the list" 

要在我们创建的链表中查找特定值，请将主函数更新为包含刚刚创建的查找方法：

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

   # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()
    
        # Search for 'quick' and 'lazy' in the list
    print(llist.search('quick'))  # Expected to find
    print(llist.search('lazy'))   # Expected not to find

上述代码将产生以下输出：

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox 
Value 'quick' found at position 0
Value 'lazy' not found in the list

单词“quick”成功在链表中被定位，因为它位于链表的第一个位置。而“lazy”并不在链表中，因此未能找到。

结语

能读到这里，恭喜您！您已经扎实掌握了链表的基本原理，包括其结构、类型、如何添加与删除元素，以及如何遍历。

但这并不是终点。链表只是数据结构与算法世界的起点。以下是一些潜在的下一步，帮助您更深入地理解这一主题：

动手做一个项目

将链表应用到实际的编程或数据科学项目中。链表可用于开发文件系统、构建哈希表，甚至用于创建 GPS 导航系统和棋盘游戏。要开始您的项目，可以查看我们免费的引导式数据科学项目，学习如何用 Python、R 和 SQL 解决真实世界的问题。

学习数据结构与算法

在理解链表之后，进一步学习其他数据结构（如树、栈与队列）是自然的进阶。这些结构建立在链表原理之上，能帮助您更高效地解决更广泛的计算问题。例如，树与二叉搜索树将链表的概念扩展为层级结构，使每个节点可以连接到数据结构中的多个元素。

如果这些概念对您来说还比较陌生，也不用担心！Datacamp 提供了完整的 Python 数据结构与算法课程，带您更深入地学习。您将首先学习栈、树、哈希表、队列与图等数据结构。随着课程推进，您还将掌握查找与排序算法，帮助您成为更高效的程序员与问题解决者。

探索更高级的链表概念

本教程实现了单向链表，涵盖了插入、删除与遍历等操作。

您可以进一步学习双向链表与循环链表的实现。跳表（Skip list）是链表的另一种扩展，它通过更快速地访问元素，实现更高效的查找。

学习这些高级数据结构将显著提升您的技术能力，帮助您在数据科学、软件开发与机器学习工程等领域应对更复杂的挑战。

如果您希望在挑战这些高级主题之前，先进行更友好的入门学习，不妨探索我们的Python 编程技能路径。它包含一系列课程，带您系统掌握该语言的基础。