数据结构与算法之美-03链表

链表类型

• 单链表
  
• 循环链表
  
• 双向链表
  
• 双向循环链表
  
  注：这里暂时先只介绍常用的链表类型

链表与数组的对比

• 内存分布
  
  由上图可知：数组需要一块连续的内存来存储
  链表需要一组零散的内存块来存储
  如果我们申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。但是申请链表就不会有问题！！！
• 时间复杂度对比
  
• 优缺点对比

数组：
缺点：大小固定
优点：简单实用，访问效率更高（可借助CPU缓存机制）

链表：
缺点：内存不连续，访问效率不高。对内存使用苛刻，当链表发生频繁插入、删除操作时，会导致频繁的内存申请和释放。
优点：链表本身没有大小的限制，天然地支持动态扩容

空间换时间思想

• 当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。
• 相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。
• 双向链表 比 单向链表更加高效的删除操作

1、在删除给定指针指向的结点时，我们已经找到了要删除的结点，但是删除某个节点q需要知道其前驱结点，而单向链表并不支持直接获取前驱结点。
2、所以，为了找到前驱结点，我们还是要从头开始遍历结点。针对双向链表来说，上述情况就比较有优势了。
3、虽说双向链表比单向链表实现起来空间复杂度更高，但是其删除节点时的简便性确凸显出来。
4、实际工程开发中，要具体考量时间换空间，还是空间换时间的方法！

快速写出链表代码小技巧

• 理解指针或引用的含义
  将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量
• 警惕指针丢失和内存泄漏

插入结点时，注意操作的顺序
删除链表结点时，也一定记得手动释放内存空间

• 利用哨兵简化实现难度

针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。
可通过插入哨兵结点，统一所有操作。

• 重点留意边界条件处理

如果链表为空时，代码是否能正常工作？
如果链表只包含一个结点时，代码是否能正常工作？
如果链表只包含两个结点时，代码是否能正常工作？
代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

• 举例画图，辅助思考
• 多写多练，没有捷径

单链表反转
链表中环的检测
两个有序的链表合并
删除链表倒数第 n 个结点
求链表的中间结点