基础概念
定义：一种非线性数据结构，由一系列节点组成，每个节点包含数据元素和指向下一个节点的指针
例子： 想象一个长长的链条，每个链环都包含一个数据元素和一个指向下一个链环的指针
特点：
- 非线性结构: 链表中的元素之间不是连续存储的，而是通过指针连接
- 动态大小: 链表可以动态地增长或缩小，无需预先分配固定大小的内存
- 插入和删除操作高效: 在链表中插入或删除元素只需要修改指针，时间复杂度为 O(1)
基本操作
- 插入 (Insert): 在链表中插入元素只需要修改指针，时间复杂度为 O(1)
- 删除 (Delete): 从链表中删除元素只需要修改指针，时间复杂度为 O(1)
- 访问 (Access): 访问链表中的元素需要从头开始遍历，时间复杂度为 O(n)
应用场景
- 实现栈和队列: 链表可以用来实现栈和队列数据结构
- 存储动态数据: 链表可以用来存储动态变化的数据，例如购物清单、待办事项列表等
- 分配内存: 链表可以用来管理内存块，提高内存利用率