相比于数组的优势：
数组的存储需要连续的的内存空间，如果我们申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。
链表则是通过"指针"将一组零散的内存块串联起来使用，，所以如果我们申请的是 100MB 大小的链表，根本不会有问题。
链表常见的三种结构分别为:单链表、双向链表、循坏链表
单链表:
链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next。
image
单链表
其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
单链表的插入、删除、访问的时间复杂度与数组刚好相反，单链表的插入、删除的时间复杂度为o(1),访问的时间复杂度为o(n).
image
插入、删除操作
循环链表:
循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中，你应该可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表。
image
循环链表
双向链表：
一个结点指向两个方向，一个前驱指针指向前面的结点，一个后驱指针指向后面的结点。
这个双向链表在开发中，更常用到，因为在单链表的插入和删除中，(首尾不算)还要先遍历一遍插入和删除中结点的前一个结点，让其指针在重新指向，时间复杂度为o(n)，而由于双向链表，有指向前一结点的指针，就可以在o(1)的复杂度中，找到前一个结点从而进行指针指向操作。
image
双向链表示意图
双向链表有种用“空间换时间”的操作，因为每个结点有两个指针，所以同样的数据需要更多的内存空间，但是在效率上却更好。
最后一个是双向循环链表，根据自己的数据特性选择使用
image
双向循环链表
链表和数组的比较
从数据量来讲:
由于数组的内存地址是连续分配的，而且申请的大小是固定，所以数组适合一些小的数据量。数组也有动态扩容的ArrayList，但是每当要扩容的话就要寻找另一个地址，然后把之前的数据全部转移到新的分配地址，所以数据量越大，这转移的时间成本就越大。
对于链表来说，由于它的内存地址是可以不连续通过指针来合成，但是由于每个结点有指针的存在，会让存储成倍上升。而且链表的插入、删除会使内存的也频繁的创建和删除，在java中会导致GC(垃圾回收)
从内存的预读来讲:
数组的内存是连续分配的，所以预读效果好，链表的内存地址不是连续分配的，所以预读效果不好。
从随机访问、插入、删除的时间复杂度讲：
image
复杂度对比
练习:
单链表反转
链表中环的检测
两个有序的链表合并
删除链表倒数第 n 个结点
求链表的中间结点
网友评论