数据结构与算法 / 系统课时
单链表的节点结构
单链表的节点结构
单链表不依赖连续下标,而是让每个节点保存数据和后继引用。本课将建立节点、头引用、尾节点与空链表的准确概念,并用一个完整程序完成链表构建和顺序遍历。
学习目标
- 认识节点的数据域与后继引用
- 区分
head、首元节点、尾节点和空链表 - 掌握单链表遍历及其复杂度
节点与链表边界
单链表节点通常包含 value 和 next 两部分。value 保存当前数据,next 指向后继节点;尾节点没有后继,因此其 next 为 None。
本课中的 head 是链表入口引用,直接指向第一个有效数据节点。head is None 表示空链表。需要特别注意,head 是变量,不是额外节点;虚拟头节点则是人为创建的辅助节点,二者不能混淆。

遍历与访问特点
遍历必须从 head 开始,沿 next 逐个移动。应使用临时变量 current,这样遍历结束后仍能保留原链表入口。
数组可根据下标直接定位元素,随机访问通常是 O(1)。单链表节点不要求连续存储,访问第 k 个节点必须经过前面的节点,因此成本是 O(k),最坏为 O(n)。
链表插入和删除只有在已经持有目标附近节点引用时,修改连接本身才是 O(1);若先按下标查找位置,整体操作仍是 O(n)。
主示例
下面的程序构建一条单链表,并将其遍历结果转换为普通列表。构建过程中同时维护 head 和 tail,避免每次追加都重新遍历。
python
from dataclasses import dataclass
from typing import Iterable, Optional
@dataclass
class ListNode:
value: int
next: Optional["ListNode"] = None
def build_linked_list(values: Iterable[int]) -> Optional[ListNode]:
head: Optional[ListNode] = None
tail: Optional[ListNode] = None
for value in values:
node = ListNode(value)
if head is None:
head = node
tail = node
else:
# tail 始终指向当前最后一个节点
assert tail is not None
tail.next = node
tail = node
return head
def to_list(head: Optional[ListNode]) -> list[int]:
result: list[int] = []
current = head
while current is not None:
result.append(current.value)
current = current.next
return result
def main() -> None:
head = build_linked_list([10, 20, 30, 40])
print(to_list(head))
print(head.value if head is not None else None)
if __name__ == "__main__":
main()预期输出:
text
[10, 20, 30, 40]
10输出说明遍历没有改变 head,第二次访问仍能得到首元节点的值。
边界与常见错误
遍历条件应是 current is not None,访问 current.value 前必须确认引用有效。若尾节点错误地指向前面的节点,链表会形成环,普通遍历将无法自然结束。
不要直接用 head = head.next 完成只读遍历,否则循环结束后入口变量会变成 None。调试未知链表时可限制最大访问节点数,避免错误环造成无限输出。
按自己的节奏,确认真正理解。