How to write linked list code?

1. 理解指针或引用的含义：将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量 p.Next = q 的含义是 p 结点的 Next 指针存储了 q 结点的内存地址

2. 警惕指针丢失和内存泄漏

   

   我们希望在结点 a 和相邻的结点 b 之间插入结点 x，假设当前指针 p 指向结点 a。如果我们将代码实现变成下面这个样子，就会发生指针丢失和内存泄露。p.Next 指针在完成第一步操作之后，已经不再指向结点 b 了，而是指向结点 x。第 2 行代码相当于将 x 赋值给 x.Next，自己指向自己

   p.Next = x
   x.Next = p.Next
   

   插入结点时，一定要注意操作顺序，指针指向应该同方向不能交叉，要先将结点 x 的 next 指针指向结点 b，再把结点 a 的 next 指针指向结点 x，这样才不会丢失指针，导致内存泄漏。所以，对于刚刚的插入代码，我们只需要把第 1 行和第 2 行代码的顺序颠倒一下就可以了。

   x.Next = p.Next
   p.Next = x
   

3. 利用哨兵简化实现难度（虚拟头结点

   

   哨兵结点是不存储数据的。因为哨兵结点一直存在，所以插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点，都可以统一为相同的代码实现逻辑了。

4. 重点留意边界条件处理

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

5. 举例画图，辅助思考