04.链表

1.定义

链表不需要连续的内存结构，它通过指针将一系列零碎的内存块串联起来。

image.png

2.分类

单链表

由结点(data)+后继指针(next)组成。

image.png

头结点：记录链表的基地址，有了它就可以遍历整个链表；
尾结点：指向的是一个空结点；
时间复杂度：
插入和删除：O(1)
查找，由于不支持随机访问O(n)

循环链表

尾结点指向的是头结点

image.png

双向循环链表

每一个结点，不仅有一个后继指针(Next)还有一个前驱指针(Prev)

image.png
双向链表由于储存了两个指针，所以占用的存储空间比较大，优势是支持双向遍历。
从结构上来看，双向链表支持O(1)复杂度的情况找到前驱结点，这样使双向链表在某些情况下比单链表的插入和删除更加高效。

删除操作简析

删除无非有两个：

• 给定某个值删除
  这时候对于单向还是双向，都需要先遍历O(n)，然后删除O(1),所以整体的时间复杂度还是O(n)
• 删除给定指针指向的结点。
  这时候双向链表，由于知道前面的结点的位置，所以删除比较方便，时间复杂度为(1),但是单向链表由于不知道前面结点的位置，还需要遍历，故时间复杂度是O(n)
  对于插入也是上述两种情况，所以在特定的情况下，双向链表的时间复杂度更低，这就是“空间换时间”的思想。

3.与数组的性能比较

• 数组数据在一块连续的内存上面，支持CPU数据预读，支持随机访问。
• 链表在零碎的内存空间上面，不支持CPU数据预读，访问性能不高；
• 数组的缺点是大小固定，一经声明就要占用整块连续内存空间。同时内存满了以后还要扩容，操作比较麻烦。
• 如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC

4.技巧小结

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

指针或者引用指向的是下一个节点的内存地址；
将某个变量赋值给指针，实际上就是将这个变量的内存地址给这个指针；反过来，指针储存了这个变量的内存地址，那么，就能通过这个指针找到这个变量；

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

//注意二者的顺序
x.next=a.next;
a.next=x;

技巧三

利用哨兵简化思考难度，特别是对头尾节点的特殊考虑；

技巧四

重点留意边界条件处理
问几个几个问题？

• 如果是空链表会怎么样？
• 如果只有一个节点会怎么样？
• 如果只有两个节点会怎么样？
• 如果处理头节点和尾结点，能否正常工作？

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