链表理论知识

链表（Linked List）是一种通过指针连接节点的线性数据结构，具有动态内存管理和高效插入/删除操作的特点‌。 它由一系列节点组成，每个节点包含数据域和指针域，主要类型包括 单向链表、双向链表和循环链表 。相较于数组，链表在内存利用和操作效率上具有优势，但牺牲了随机访问性能。‌‌ ‌

核心特性与分类‌

‌基本结构‌

‌节点组成‌： 链表节点包含数据域（存储数据）和指针域（指向下一个节点）。例如，单向链表的指针域仅指向下一个节点，而双向链表包含前驱和后继指针。‌‌

‌内存分配‌： 节点在内存中非连续存储，通过指针关联，支持动态扩展。‌‌

‌类型对比‌

类型	特点
单向链表	仅含指向下一节点的指针，遍历方向单一
双向链表	含前驱和后继指针，支持双向遍历，操作更灵活
循环链表	尾节点指向头节点形成闭环，适用于环形数据处理场景

性能与应用场景‌

时间复杂度‌

插入/删除： O(1)（已知位置时）

查询：O(n)（需从头节点遍历）

优缺点分析‌

‌优势‌：无需预分配内存、动态调整容量、插入删除高效。

‌局限‌：无法随机访问、存储指针增加内存开销。‌‌

典型应用‌

实现栈、队列、哈希表等数据结构

文件系统目录管理、内存动态分配

处理稀疏数据（如稀疏矩阵）

与数组的对比‌

维度	数组	链表
内存连续性	连续存储	非连续存储
访问方式	随机访问（O(1)）	顺序访问（O(n)）
插入/删除	需移动元素（O(n)	修改指针（O(1)）
内存预分配	需预先确定大小	动态扩展