链表 (Linked List)

定义与概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指针域。节点在内存中非连续存储，通过指针连接形成链式结构。

核心特点

• 动态大小：无需预先分配固定空间
• 高效插入删除：在已知位置操作时间复杂度为 O(1)
• 顺序访问：只能从头开始顺序访问，不支持随机访问
• 内存灵活：节点可以分散在内存各处

主要类型

• 单链表：每个节点指向下一个节点
• 双链表：节点包含前后两个指针
• 循环链表：尾节点指向头节点形成环

基本操作复杂度

操作	时间复杂度	空间复杂度
访问	O(n)	O(1)
搜索	O(n)	O(1)
插入	O(1)	O(1)
删除	O(1)	O(1)

应用场景

• 实现栈、队列等数据结构
• 内存管理系统
• 浏览器历史记录
• 多项式运算