第七节-链表下

这节课主要讲了如何轻松正确地写出正确地链表代码

技巧一：理解指针或引用的含义

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向这个变量，通过指针就能找到这个变量。

技巧二：警惕指针丢失和内存泄漏

写链表时，一定要注意指针指向哪了，对于脑子转不过来的情况，可以在纸上画图辅助思考。
对于自己管理内存的语言，如 C 语言，如果没有手动释放节点对应的内存空间，就会产生内存泄漏。不过，对于 Java 这种虚拟机自动管理内存的编程语言来说，就不需要考虑那么多了。

技巧三：利用哨兵简化实现难度

有时代码写不出来，也是因为代码的小逻辑多而乱，如果能够实现分析代码，简化逻辑，那么写起代码来就会更容易轻松了。
比如，当在单链表插入一个新节点时，需要两个小逻辑：1. 链表是空的的情况 2. 链表不是空的情况 写起来的代码就会像这样复杂
而如果我们有一个哨兵节点，那么就只需“无脑”往这个节点后面插入新节点而不用进行一次判空特殊处理了。

拓展：在很多算法中都有用到哨兵做简化，比如插入排序、归并排序、动态规划等。
下面这个例子就是用了哨兵提升性能：

inf find(char* a, int n, int key) {
  if (a[n-1] == key) {
    return n-1;
  }
  char tmp = a[n-1];
  a[n-1] = key;
  int i = 0;
  while (a[i] != key) {
    ++i;
  }
  a[n-1] = tmp;
  if (i == n-1) return -1;
  return i;
}

技巧四：重点留意边界条件处理

软件开发中，我们往往是从“通常情况入手，设计代码”，这种情况下，如果不注意特殊情况（边界情况）时，就容易产生 BUG。一定要在写完代码后，检查边界条件是否考虑齐全。
常用来检查链表代码是否正确的边界条件有这样几个：

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

技巧五：画图举例，辅助思考

感觉这也是软件设计图的细节版。写出来，整理一下，就明白了。

技巧六：多写多练，没有捷径

水滴石穿，时刻铭记。