数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。

如果代码中对内存的使用非常苛刻，那数组比较适合，毕竟链表每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针。

如何轻松写出正确的链表代码?

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

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

?示例：

? ?p—>next = q; 表示p节点的后继指针存储了q节点的内存地址。

? ?p—>next = p—>next—>next; 表示p节点的后继指针存储了p节点的下下个节点的内存地址

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

1.插入节点在节点a和节点b之间插入节点x，b是a的下一节点，，p指针指向节点a，则造成指针丢失和内存泄漏的代码：p—>next = x;x—>next = p—>next; 显然这会导致x节点的后继指针指向自身。正确的写法是

2句代码交换顺序，即：x—>next = p—>next; p—>next = x; 2.删除节点在节点a和节点b之间删除节点b，b是a的下一节点，p指针指向节点a：p—>next = p—>next—>next;

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

1.什么是“哨兵”？链表中的“哨兵”节点是解决边界问题的，不参与业务逻辑。如果我们引入“哨兵”节点，则不管链表是否为空，head指针都会指向这个“哨兵”节点。我们把这种有“哨兵”节点的链表称为带头链表，相反，没有“哨兵”节点的链表就称为不带头链表。

2.未引入“哨兵”的情况如果在p节点后插入一个节点，只需2行代码即可搞定： new_node—>next = p—>next; p—>next = new_node; 但，若向空链表中插入一个节点，则代码如下： if(head == null){ head = new_node; } 如果要删除节点p的后继节点，只需1行代码即可搞定： p—>next = p—>next—>next; 但，若是删除链表的最有一个节点（链表中只剩下这个节点），

则代码如下： if(head—>next == null){ head = null; } 从上面的情况可以看出，针对链表的插入、删除操作，需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。这样代码就会显得很繁琐，所以引入“哨兵”节点来解决这个问题。

3.引入“哨兵”的情况 “哨兵”节点不存储数据，无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。这样，插入第一个节点和插入其他节点，删除最后一个节点和删除其他节点都可以统一为相同的代码实现逻辑了。