什么是链表？
链表是物理存储单元上非连续的、非顺序的存储结构，它是由一个个结点，通过指针来联系起来的，其中每个结点包括数据和指针。
链表示意图
链表在内存中的表示
链表的优缺点是什么
缺点：
每个结点都分配在非连续的位置，结点与结点之间通过指针连在了一起，所以如果我们要找比如值为 3 的结点时，只能通过结点 1 从头到尾遍历寻找，如果元素少还好，如果元素太多（比如超过一万个），每个元素的查找都要从头开始查找，时间复杂度是O(n)比起数组的 O(1)，差距不小。
我们知道 CPU 运行速度是非常快的，如果 CPU 每次运算都要到内存里去取数据无疑是很耗时的，所以在 CPU 与内存之间往往集成了挺多层级的缓存，这些缓存越接近CPU，速度越快，所以如果能提前把内存中的数据加载到如下图中的 L1, L2, L3 缓存中，那么下一次 CPU 取数的话直接从这些缓存里取即可，能让CPU执行速度加快，那什么情况下内存中的数据会被提前加载到 L1,L2,L3 缓存中呢，答案是当某个元素被用到的时候，那么这个元素地址附近的的元素会被提前加载到缓存中
内存与缓存的关系图
由于链表的每个结点在内存里都是随机分布的，只是通过指针联系在一起，所以这些结点的地址并不相邻，自然无法利用程序局部性原理 来提前加载到 L1,L2,L3 缓存中来提升程序性能。
链表的优点：
1.插入删除操作很方便，只要更改指针。不用像数组一样，移动其他元素的位置。
2.可利用非连续的空间，空间利用率高。
