链表理论基础¶
1. 链表的定义
- 一种通过指针串联在一起的线性结构
- 每一个节点由两部分组成,分别是数据域和指针域(存放指向下一个节点的指针)
- 第一个节点称为链表的头结点即 head,最后一个节点的指针域指向空指针
2. 链表的类型
- 单链表
如定义所示。
- 双链表
每一个节点有两个指针域,可分别指向上一个节点和下一个节点。
即说明能做到向前查询和向后查询。
- 循环链表
即链表首尾是相连的。可以用来解决约瑟夫环问题。
3. 链表的存储方式
- 数组是在内存中是连续分布的,但是链表在内存中可不是连续分布的
- 链表是通过指针域的指针链接在内存中各个节点,即链表中的节点在内存中不是连续分布的,而是散乱分布在内存中的某地址上
- 其内存的分配机制取决于操作系统的内存管理
4. 链表的定义
5. 链表的操作
链表操作 | 操作的解释 |
---|---|
删除节点 | ![]() 注意:节点的删除并没有释放被删除节点的内存。 |
添加节点 | ![]() |
6. 性能分析
插入/删除 | 查询 | 适用场景 | |
---|---|---|---|
数组 | \(O(n)\) | \(O(1)\) | 数据量固定,频繁查询,较少增删 |
链表 | \(O(1)\) | \(O(n)\) | 数据量不固定,频繁增删,较少查询 |