链表

链表

链表: 用指针将一组零散的内存块串联在一起、其中: 把内存块称为链表的节点
为了将节点串联起来、每个链表的节点除了存储数据、还需要记录链上的下一个节点的地址(后继指针)

分为:单链表、双链表和循环链表

其中: 第一个节点称为头节点(用来记录链表的基地址)、最后一个节点称为尾节点、

单链表的尾节点指向一个空地址NULL、
循环链表: 一种特殊的单链表、与单链表的区别是: 尾节点指向链表的头节点
双向链表: 每个节点有一个后继指针next和一个前驱指针prev

存储相同的数据、双向链表要占据两个额外的空间来存储prev和next指针、需要更多的空间、但也带来了双向链表操作的灵活性

一个重要思想:
空间换时间: 在内存充足的时候、若追求代码的执行速度、可以利用空间换时间、选择空间复杂度高、但时间复杂度相对较低的算法
相反: 若内存较少、eg. 代码跑在单片机或者手机上、就需要考虑时间换空间的思路

链表vs数组

1. 链表可有效使用内存、插入和删除效率较高
2. 数组随机访问效率更高、插入删除效率较低
3. 数组的连续存储性、可借助CPU的缓存机制、预读数组中数据、访问效率更高
   链表存储非连续、对CPU缓存支持不够友好
4. 数组大小固定、一旦声明就要占用整块的连续空间、若声明的数组过大、系统无足够连续内存、会导致OOM、链表本身无大小限制、可天然支持动态扩容
5. 若代码对内存要求很高、则数组更合适、且: 对链表频繁的增删会导致频繁的内存申请和释放、容易造成GC

几个写链表代码的技巧

一、理解指针或者引用的含义
   将某个变量赋值给指针、实际上就是将这个变量的地址赋值给指针、即: 指针中存储了这个变量的内存地址、指向了这个变量、通过指针就能找到这个变量

二、警惕指针丢失和内存泄漏
   插入节点时需要注意操作顺序、删除节点时也要手动释放内存

三、利用哨兵简化实现难度
   针对链表的增删操作、需要对头节点和尾节点进行特殊处理

四、留意边界条件
   1. 空链表能否正常工作 ？
   2. 只有一个节点的链表能否正常工作 ？
   3. 只有两个节点能否正常工作 ？
   4. 处理头尾节点时能否正常工作 ？

五、举例画图、辅助思考

六、多写多练