数据结构学习笔记 - 链表

链表

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

简介

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

单链表

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

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

循环链表和双向链表

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

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

常见的删除操作有两种:

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

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

和数组的比较

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

写链表代码技巧

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