Python如何实现链表？数据结构入门教程-Python教程-PHP中文网

Python如何实现链表？数据结构入门教程

星夢妙者

发布： 2025-08-19 18:41:01

原创

562人浏览过

python中实现链表的核心在于定义节点类和链表类，1.节点类包含数据和指向下一个节点的引用；2.链表类管理节点，维护头部引用；3.通过append、prepend、delete_node等方法实现链表操作；4.链表适合频繁中间增删场景，而python列表适合随机访问；5.遍历链表通常使用迭代方法，维护current指针从头部开始；6.实现时需注意空链表、头尾节点处理及查找删除逻辑。

Python如何实现链表？数据结构入门教程

Python中实现链表的核心在于定义一个节点（Node）类，它包含数据和指向下一个节点的引用，然后通过一个链表（LinkedList）类来管理这些节点，通常只维护一个指向链表头部的引用。这种结构允许我们动态地添加或删除元素，而无需像数组那样预设大小或进行大量的数据移动。

解决方案

要用Python构建一个链表，我们首先需要一个表示单个元素的“节点”：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None # 初始时，下一个节点为空

class LinkedList:
    def __init__(self):
        self.head = None # 链表的头部，初始为空

    def append(self, data):
        """在链表末尾添加一个新节点。"""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def prepend(self, data):
        """在链表头部添加一个新节点。"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def delete_node(self, key):
        """删除链表中第一个匹配给定键值的节点。"""
        current = self.head
        if current and current.data == key:
            self.head = current.next
            current = None
            return

        prev = None
        while current and current.data != key:
            prev = current
            current = current.next

        if not current: # 键值不存在
            print(f"Warning: Node with data '{key}' not found.")
            return

        prev.next = current.next
        current = None

    def display(self):
        """打印链表中的所有数据。"""
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        print(" -> ".join(map(str, elements)))

    def search(self, key):
        """查找链表中是否存在某个键值。"""
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

    def get_length(self):
        """获取链表的长度。"""
        count = 0
        current = self.head
        while current:
            count += 1
            current = current.next
        return count

# 简单使用示例
# my_list = LinkedList()
# my_list.append(10)
# my_list.append(20)
# my_list.prepend(5)
# my_list.display() # 输出: 5 -> 10 -> 20
# my_list.delete_node(10)
# my_list.display() # 输出: 5 -> 20
# print(f"Length: {my_list.get_length()}") # 输出: Length: 2
# print(f"Is 20 in list? {my_list.search(20)}") # 输出: Is 20 in list? True

登录后复制

为什么选择链表而不是Python内置列表？

这真是一个经典的问题，初学者常常会困惑，毕竟Python的

list

登录后复制

用起来太方便了。但实际上，链表和Python内置列表（底层是动态数组）在某些场景下表现截然不同。我个人认为，理解这种差异是深入数据结构的关键一步。

立即学习“Python免费学习笔记（深入）”；

Python列表在内存中是连续存储的。这意味着随机访问（通过索引直接获取元素）非常快，因为CPU可以直接计算出目标元素的内存地址。比如你想获取

my_list[5]

登录后复制

，它就是瞬间的事。但是，当你在列表的中间插入或删除一个元素时，问题就来了。为了保持内存的连续性，Python列表可能需要将插入点之后的所有元素向后或向前移动。想象一下，一个有几百万个元素的列表，你在它的开头插入一个新元素，那将是一场“数据大搬家”，效率会非常低，时间复杂度是O(n)。

链表则不同，它的元素（节点）在内存中可以是不连续的。每个节点只知道下一个节点在哪里，通过一个指针（引用）连接起来。这使得在链表的任意位置进行插入或删除操作变得非常高效，只需要修改少数几个指针即可，时间复杂度是O(1)。当然，前提是你已经找到了那个位置。如果需要从头开始遍历才能找到目标位置，那总体的查找时间复杂度仍然是O(n)。

所以，什么时候用链表？当你的应用场景频繁涉及在数据集合的中间进行插入和删除，并且对随机访问的需求不高时，链表可能是一个更好的选择。比如，实现一个简单的消息队列，或者一个需要快速增删的播放列表。当然，如果只是做一些简单的增删改查，Python列表的综合性能和易用性通常还是首选。

如何遍历链表以访问每个节点？

遍历链表是其最基本的操作之一，也是理解链表工作原理的核心。我的习惯是，只要涉及到链表操作，脑子里首先浮现的就是遍历。

最常见的遍历方式是迭代（iterative）方法。它需要一个“当前”指针（通常命名为

current

登录后复制

或

temp

登录后复制

），从链表的头部（

head

登录后复制

）开始。然后，在一个循环中，我们不断地访问

current

登录后复制

指向的节点的数据，并将

current

登录后复制

指针移动到它的下一个节点，直到

current

登录后复制

变成

None

登录后复制

（表示已经到达链表末尾）。

就像这样：

PHP5 和 MySQL 圣经

本书是全面讲述PHP与MySQL的经典之作，书中不但全面介绍了两种技术的核心特性，还讲解了如何高效地结合这两种技术构建健壮的数据驱动的应用程序。本书涵盖了两种技术新版本中出现的最新特性，书中大量实际的示例和深入的分析均来自于作者在这方面多年的专业经验，可用于解决开发者在实际中所面临的各种挑战。

466

查看详情

    def traverse_and_print(self):
        """遍历链表并打印每个节点的数据。"""
        current = self.head
        if not current:
            print("链表是空的。")
            return

        print("链表元素:")
        while current:
            print(current.data, end=" -> " if current.next else "")
            current = current.next
        print() # 换行

登录后复制

这种方法直观且高效。你也可以用递归来实现遍历，但通常不推荐，因为它可能会在链表很长时导致栈溢出（Python默认递归深度有限制），而且代码可读性有时不如迭代版。迭代遍历是链表操作的基石，无论是查找、删除还是修改，几乎所有操作都离不开它。

实现链表时常见的技术挑战和注意事项？

在实现链表，尤其是单向链表时，确实有一些陷阱和边缘情况需要特别注意，这往往是新手容易出错的地方。我记得自己刚学的时候，光是处理空链表、删除头部节点、或者删除尾部节点就花了不少时间。

空链表操作： 这是最常见的一个。当链表为空（
```
self.head is None
```
登录后复制
）时，很多操作（如删除、查找）都需要特殊处理。比如，尝试删除一个不存在的节点，或者在空链表中查找元素，代码应该能够优雅地处理这些情况，而不是直接报错。在我的
```
append
```
登录后复制
和
```
delete_node
```
登录后复制
方法里，都包含了对
```
if not self.head
```
登录后复制
的判断，这就是为了处理空链表的场景。
头部节点的处理： 插入到头部（
```
prepend
```
登录后复制
）相对简单，但删除头部节点则需要小心。如果直接将
```
self.head
```
登录后复制
指向
```
self.head.next
```
登录后复制
，那么原来的头部节点就会被垃圾回收，但在此之前，要确保如果链表只有一个节点，删除后
```
self.head
```
登录后复制
能正确地变为
```
None
```
登录后复制
。
尾部节点的处理： 在链表末尾添加（
```
append
```
登录后复制
）需要遍历到倒数第二个节点，然后将其
```
next
```
登录后复制
指针指向新节点。删除尾部节点则更复杂，你需要找到倒数第二个节点，并将其
```
next
```
登录后复制
指针设为
```
None
```
登录后复制
。这通常意味着你需要维护一个“前一个节点”的引用，或者在遍历时提前一步。
查找与删除： 当删除一个特定值的节点时，需要找到它的前一个节点，然后修改前一个节点的
```
next
```
登录后复制
指针，跳过要删除的节点。如果找不到要删除的节点，或者要删除的是头部节点，都需要单独考虑。我的
```
delete_node
```
登录后复制
方法就包含了
```
prev
```
登录后复制
指针来处理这种情况。
循环引用和内存泄漏（Python中较少见）： 在一些低级语言中，如果链表节点之间形成循环，而没有正确断开引用，可能会导致内存泄漏。Python有垃圾回收机制，通常能处理这种情况，但理解指针（引用）的正确管理仍然很重要，尤其是在进行复杂操作时。
双向链表与单向链表： 上面实现的都是单向链表，每个节点只知道“下一个”是谁。如果需要频繁地向前或向后遍历，或者需要更高效地删除任意节点（无需查找前一个节点），那么双向链表（每个节点除了
```
next
```
登录后复制
还有一个
```
prev
```
登录后复制
指针）会是更好的选择，但它会增加内存开销和维护复杂性。