本文档涵盖了 TheAlgorithms/Python 存储库中的链表数据结构实现。链表是基本的线性数据结构，由通过指针连接的节点组成，提供动态内存分配以及高效的插入/删除操作。该存储库包含多种链表变体，包括单向、双向和循环实现，以及用于常见操作的专用实用函数。
有关堆栈和队列等其他线性数据结构的信息，请参阅 堆栈、队列和线性结构。有关基于树的链式结构，请参阅 树和基于树的结构。
来源： data_structures/linked_list/singly_linked_list.py8-38 data_structures/linked_list/doubly_linked_list.py6-20 data_structures/linked_list/circular_linked_list.py8-17
主要的单向链表实现通过 LinkedList 类和包含数据和下一个指针的 Node 对象提供了一套完整的操作。
来源： data_structures/linked_list/singly_linked_list.py8-24 data_structures/linked_list/singly_linked_list.py40-48
| 操作 | 方法 | 时间复杂度 | 描述 |
|---|---|---|---|
| 在头部插入 | insert_head(data) | O(1) | 在开头添加节点 |
| 在尾部插入 | insert_tail(data) | O(n) | 在末尾添加节点 |
| 在指定位置插入 | insert_nth(index, data) | O(n) | 在指定索引处插入 |
| 删除头部 | delete_head() | O(1) | 删除第一个节点 |
| 删除尾部 | delete_tail() | O(n) | 删除最后一个节点 |
| 按位置删除 | delete_nth(index) | O(n) | 删除索引处的节点 |
| 反转 | reverse() | O(n) | 反转整个链表 |
| 获取长度 | __len__() | O(n) | 计数节点 |
来源： data_structures/linked_list/singly_linked_list.py176-190 data_structures/linked_list/singly_linked_list.py192-221 data_structures/linked_list/singly_linked_list.py235-287 data_structures/linked_list/singly_linked_list.py337-363
LinkedList 类实现了 Python 的迭代器协议和索引操作。
来源： data_structures/linked_list/singly_linked_list.py50-67 data_structures/linked_list/singly_linked_list.py108-130 data_structures/linked_list/singly_linked_list.py133-158 data_structures/linked_list/singly_linked_list.py69-88 data_structures/linked_list/singly_linked_list.py90-106
双向链表通过包含 next 和 previous 指针的节点提供双向遍历。
来源： data_structures/linked_list/doubly_linked_list.py6-14 data_structures/linked_list/doubly_linked_list.py16-20
DoublyLinkedList 类提供了针对双向访问优化的操作。
| 方法 | 功能性 | 关键实现细节 |
|---|---|---|
insert_at_head(data) | 在开头插入 | 更新旧头节点的 previous 指针 |
insert_at_tail(data) | 在末尾插入 | 更新旧尾节点的 next 指针 |
insert_at_nth(index, data) | 在指定位置插入 | 维护前向和后向链接 |
delete_head() | 删除第一个节点 | 将头节点的 previous 更新为 None |
delete_tail() | 删除最后一个节点 | 将尾节点的 next 更新为 None |
delete_at_nth(index) | 按位置删除 | 重新连接 previous.next 和 next.previous |
来源： data_structures/linked_list/doubly_linked_list.py56-106 data_structures/linked_list/doubly_linked_list.py108-157
循环链表实现将尾节点连接回头节点，形成一个环。
来源： data_structures/linked_list/circular_linked_list.py15-17 data_structures/linked_list/circular_linked_list.py58-87 data_structures/linked_list/circular_linked_list.py107-140 data_structures/linked_list/circular_linked_list.py19-30
循环结构在插入和删除时需要特殊处理，以维护循环属性，其中 tail.next_node 始终指向 head。
来源： data_structures/linked_list/has_loop.py6-8 data_structures/linked_list/has_loop.py25-43 data_structures/linked_list/has_loop.py15-23
swap_nodes 功能根据数据内容在两个节点之间交换数据值
| 步骤 | 实现 | 代码参考 |
|---|---|---|
| 1. 查找 node_1 | 从头部开始遍历，直到 node.data == node_data_1 | data_structures/linked_list/swap_nodes.py122-124 |
| 2. 查找 node_2 | 从头部开始遍历，直到 node.data == node_data_2 | data_structures/linked_list/swap_nodes.py125-127 |
| 3. 验证节点 | 如果任一节点为 None，则提前返回 | data_structures/linked_list/swap_nodes.py128-129 |
| 4. 交换数据 | 交换 node_1.data 和 node_2.data | data_structures/linked_list/swap_nodes.py131 |
来源： data_structures/linked_list/swap_nodes.py67-131
来源： data_structures/linked_list/middle_element_of_linked_list.py20-60 data_structures/linked_list/middle_element_of_linked_list.py51-57
merge_lists 函数将两个 SortedLinkedList 实例合并
来源： data_structures/linked_list/merge_two_lists.py62-75 data_structures/linked_list/merge_two_lists.py20-24
该存储库提供用于从序列创建链表的工厂函数
| 功能 | 模块 | 目的 |
|---|---|---|
make_linked_list(elements_list) | from_sequence.py | 从序列创建基本链表 |
make_linked_list(elements_list) | print_reverse.py | 创建具有扩展功能的 LinkedList |
SortedLinkedList(ints) | merge_two_lists.py | 从整数创建排序链表 |
来源： data_structures/linked_list/from_sequence.py21-36 data_structures/linked_list/print_reverse.py88-107 data_structures/linked_list/merge_two_lists.py20-24
所有链表实现都包含全面的文档测试和测试函数
来源： data_structures/linked_list/singly_linked_list.py366-409 data_structures/linked_list/doubly_linked_list.py191-225 data_structures/linked_list/circular_linked_list.py151-205
链表实现展示了清晰的关注点分离、全面的错误处理，以及与 Python 内置的迭代和索引协议的集成，使其既具有教育意义，又在算法应用中实用。