Python有链表的概念么？

Python 中有链表的概念，但和传统链表（如 C/C++ 中的链表）的实现方式不同。以下是详细说明：

1. Python 的 list 不是链表

Python 内置的 list 类型虽然名称叫“列表”，但底层实现是动态数组（类似 C++ 的 vector 或 Java 的 ArrayList），而非链表。它的特点是：

• 内存连续分配，支持快速随机访问（时间复杂度 O(1)）。
• 插入/删除元素时（尤其是中间位置），需要移动后续元素，时间复杂度为 O(n)。

2. 如何实现链表？

若需要在 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 __str__(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        return " -> ".join(elements)


# 使用示例
ll = LinkedList()
ll.append(1)
ll.append(2)
print(ll)

输出

1 -> 2

3. Python 的替代方案

如果不想手动实现链表，可以利用以下工具：

• collections.deque：双端队列，底层基于双向链表优化，支持 O(1) 时间复杂度的头尾插入/删除。

from collections import deque
dq = deque()
dq.appendleft(10)  # 头部插入
dq.pop()           # 尾部删除

第三方库：如 lispy 或 pyllist 提供现成的链表实现。

4. 链表 vs 列表的使用场景

| 操作 | Python 列表（动态数组） | 链表 |
| :———— | :————————– | :———————- |
| 随机访问 | O(1) | O(n) |
| 头部插入/删除 | O(n) | O(1)（双向链表为 O(1)） |
| 中间插入/删除 | O(n) | O(1)（需先找到位置） |
| 内存占用 | 更紧凑（连续存储） | 分散（额外指针开销） |

总结

• Python 没有内置的链表结构，但可以通过类手动实现。
• 需要频繁在头部/中间插入时，链表更高效；若需快速随机访问，使用列表或 deque 更合适。
• 在算法题中，链表通常需要手动模拟（如处理 ListNode 类）。