[AlgoGo]线性存储结构-链表

与数组的对比

链表插入、删除操作不需要移动内存，时间复杂度低，但是无法实现“随机读取”，需要遍历找到对应节点。

链表类型

1. 单链表
   只有后继节点，尾节点指向NULL。
2. 双向链表
   有前驱节点和后继节点，尾节点指向NULL。
3. 循环链表
   只有后继节点，尾节点指向头节点。
4. 双向循环链表
   有前驱和后继节点，尾节点的后继指向头节点，头节点的前驱指向尾节点。

双向链表相比单向列表的优势

• 针对链表常用的插入、删除操作，删除某个指定节点时需要获取它的前驱节点，如果是单链表需要遍历找到p->next == q，时间复杂度O(n)，而双向链表只要q->pre即可得到。
• 对于有序的链表，双向链表的插入操作也更有优势，因为可以记录上次查找到的p的位置，根据这次数据的大小确定是往前查还是往后查。

代价就是双向列表存储了前驱和后继节点，空间消耗上大于单向链表。

链表的典型应用

LRU缓存淘汰算法

1. 有新的节点加入时，判断是否存在于链表中
2. 若存在则将其删除，插入链表头部
3. 若不存在则判断链表长度是否达到最大
4. 若达到最大则删除链表尾部节点，将新节点加入头部
5. 若未达到最大则直接将新节点加入头部

写链表代码的技巧

1. 理解指针或引用的含义
   指针和引用的本质都是表示内存地址，时刻搞清楚当前指针指向的地址
2. 警惕指针丢失和内存泄漏
   链表操作过程中某些指针在改动时需要缓存下来，若直接覆盖将找不到原内存地址，导致指针丢失和内存泄漏，具体情况需要在写代码时小心分析。
3. 巧用哨兵
   例如单链表的头节点，添加了头节点可以保证链表有无节点时的操作一致，简化了逻辑。
4. 格外关注边界条件的处理
   链表为空时？只有一个节点时？只有两个节点时？处理头节点和尾节点时？
   测试用例覆盖。
5. 举例画图，辅助思考
   好记性不如烂笔头，画图减少了大脑记忆工作量，思维可以聚焦于核心逻辑上。
6. 多写多练，没有捷径

几个常见链表操作训练

• 单链表反转

  Need 3 temporary variables : cur prev next

  1. Save next node
  2. Reverse cur node
  3. Move pre and cur node ahead

• 链表中环的检测
• 两个有序链表的合并
• 删除链表倒数第N个节点
• 求链表的中间节点
• 判断链表是否回文

  1. find midnode in list
  2. reverse list after midnode
  3. compare left half and reversed right half list
  4. recover right half to origin