04.链表

2020-05-17 本文已影响0人学海一乌鸦

1.定义

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

image.png

由结点(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)
对于插入也是上述两种情况，所以在特定的情况下，双向链表的时间复杂度更低，这就是“空间换时间”的思想。

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

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

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

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

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