在说链表之前，有必要先聊聊数组，只有理解了数组的缺点，才能明白链表的好处。
数组是一种非常基础且常用的数据结构，它的形式表现与物理表现完全一致。
在C语言中，「 int a[5] 」就是申请一块连续内存，这块内存有5个单元，每个单元占据int类型的大小，一般为4字节。
而通过a[1]这样的下标形式来映射到实际内存完成对元素的访问(这里所说的实际内存其实是操作系统提供的虚拟内存机制，最终通过MMU才映射为实际物理内存)。
这种映射很简单，即内存地址 = 首地址 + 偏移量 * 单元大小。
这里数组的首地址也就是1000，偏移量就是下标，单元大小就是数组类型的大小，int类型占据4字节。
所以这个例子中，a[1]这样下标形式访问就映射为「1000 + 1 * 4」这个内存地址。
可以发现，这样数组访问每个元素的复杂度都是O(1)的，性能非常好。
既然如此，为什么还需要链表？
链表出现的背景
链表的出现就是为了解决数组的一些弊端的，尽管数组支持O(1)的随机访问，但数组有两个核心缺陷：
1.内存不连续
数组的申请需要一块连续的内存，假设要申请1MB大小的数组，内存明明还剩余2MB，完全够，但却到不到一块连续的1MB内存，这2MB剩余内存是「离散」的。
此时申请1MB大小的数组则会失败：
而用链表可以解决这个问题，链表结构核心有两个部分：一个部分存放数据，另一个部分存放下一个元素的地址。
因为数组通过下标访问映射到实际内存，所以实际内存的申请必然是连续的，否则这个映射公式会很复杂。
而链表在内存不连续时依然可以分配，只要总内存大小够用就行。
2.解决动态扩容
内存的每次申请都需要指定一个大小，在程序较小时这个数值可以依靠经验提供。当程序越来越庞大，发展为工程时，这个初始分配的大小就很难做到「准确」。
太小了后续不够用，太大了浪费内存。因此急需一个解决数组不能动态扩容的数据结构，链表就能胜任这个需求。
当需要扩容时，申请一个结点，将新结点放在链表后面即可。
你可能说，这数组也能做到啊，但数组的扩容效率实在太低了。数组的扩容需要申请一个比原先大的新数组，再把旧数组的元素一个一个拷贝到新数组。
那你又说，为什么不在数组后面追加申请呢，别忘了，数据申请需要连续的内存空间，谁知道数组尾部后面的内存有没有被其他程序占用呢。
链表的种类
理解了数组的缺陷后，链表就此诞生。随着解决问题和提升效率的需要，链表又发展为多个类型，每种类型都有各自的应用场景。
-
单链表
链表里面有两个结点比较特殊，一个是头结点，另一个是尾结点。头结点即链表第一个结点，知道了它地址，就可以顺序访问整个链表了。
而尾结点的next的指向空，表示链表结束，通常循环遍历链表可以把尾结点判空来停止循环。
数组的插入和删除元素都需要移动大量元素，时间复杂度为O(n)。而链表却可以做到O(1)复杂度的插入和删除。
插入操作：
删除操作：
-
循环链表
实际上跟单链表差不多，只不过尾结点指向头结点，形成了「环」。
在解决一些算法问题时会用到，例如「约瑟夫问题」，实际开发中很少用到这个结构。
-
双向链表
就是在单链表的基础上，增加一个指针，指向前置结点。
这种结构有很多好处，例如不经可以从头结点遍历，也可以从尾结点遍历。
还有在进行插入和删除结点时，可以轻松知道前置结点，不需要再去遍历获取被删除或插入结点的前置结点了。
双向链表无论是算法领域还是软件开发，都用的比较多，Java里「LinkedHashMap」底层就用到了双向链表。
-
双向循环链表
听名字显然就是循环链表和双向链表的融合：
END
总的来说，虽然数组支持O(1)性能的随机访问，但「需要连续空间」和「不能动态扩容」这两大缺点催生了链表的诞生。
链表不仅解决了这两大问题，还支持O(1)的插入和删除操作，在很多场景下提高了性能。
而为了解决问题的需要和进一步提升效率，链表衍生出了很多改进版本。
评论区