数据结构学习笔记 - 链表

痛定思痛。 2022-12-03 12:53 95阅读 0赞

## 链表 ##

比数组稍微复杂一点的数据结构

### 简介 ###

不需要连续的内存空间, 通过指针将一组零散的内存块串联起来使用.  
链表结构五花八门, 三种最常见的链表结构, **单链表**, **双向链表**, **循环链表**.

### 单链表 ###

被串联的内存块称为结点, 每个结点存有**数据**和记录**下一个结点的地址**, 叫做后继指针next  
第一个结点叫头结点, 最后一个结点叫尾结点, 尾结点指向一个空地址null.

链表也支持数据的查找, 插入和删除操作  
链表的插入和删除操作只需要考虑相邻接点的指针改变, 所以时间复杂度为O(1).  
但想要随机访问第k个元素, 就需要一个一个结点遍历, 需要O(n)的时间复杂度.

### 循环链表和双向链表 ###

循环链表是一种特殊的单链表, **尾结点指向链表的头结点**.  
优点是从链尾到链头比较方便, 当要处理的数据有环形结构时, 就适合采用循环链表, 比如约瑟夫问题(todo)

双向链表支持两个方向, 每个结点不只有一个**后继指针next**, 还有一个**前驱指针prev**.  
双向链表需要额外的空间存储后继结点和前驱结点地址, 如果存储同样多的数据, 双向链表比单链表占用更多的内存空间.  
双向链表可以O(1)的时间复杂度找到前驱结点, 因此某些情况下, 双向链表的插入删除等操作比单链表更简单高效.

常见的删除操作有两种:

1.  删除结点中值等于给定值的结点
2.  删除给顶指针指向的结点  
    对于第一种, 单链表和双向链表的时间复杂度都是O(n), 但对于第二种, 双向链表的时间复杂度为O(1),  
    同理, 在链表的某个指定结点前插入一个结点时, 双向链表的时间复杂度也是O(1).  
    另外, 对于有序链表, 双向链表的按值查询效率也高一些.

**双向链表尽管比较费内存, 但比单链表应用更广泛, 比如java中的LinkedHashMap容器, 就用到了双向链表, 即空间换时间策略.**

### 和数组的比较 ###

插入, 删除, 随机访问的时间复杂度正好相反.  
数组简单易用, 可借助cpu缓存机制预读数组中的数据, 访问效率更高, 缺点是大小固定, 不能动态扩容.

### 写链表代码技巧 ###

1.  理解指针或引用含义  
    将某个变量赋值给指针, 实际上是将这个变量的地址赋值给指针.
2.  警惕指针丢失和内存泄漏  
    插入节点时, 一定要注意操作顺序.
3.  利用哨兵简化实现难度  
    针对链表的插入删除操作, 需要对插入头结点和删除尾结点特殊处理, 所以可插入一个不带数据的哨兵结点, 这种链表被称为带头链表.
4.  重点留意边界条件处理  
    比如链表为空, 只有一个结点, 有两个结点, 处理头结点和尾结点时.
5.  举例画图, 辅助思考  
    画图法和举例法, 帮助理清思路
6.  多写多练  
    [单链表反转][Link 1]  
    链表中环的检测 (todo)  
    两个有序的链表合并 (todo)  
    删除链表倒数第n个结点 (todo)  
    求链表的中间结点 (todo)  
    [基于链表实现LRU缓存淘汰算法][LRU]  
    单链表字符串, 判断是一个回文串 (todo)

[Link 1]: https://github.com/WangDanpeng/Vamos/blob/main/src/main/scala/wdp/struct/link/ReverseSingleLink.scala
[LRU]: https://github.com/WangDanpeng/Vamos/blob/main/src/main/scala/wdp/struct/link/LRU.scala