链表就先以单向链表为例，简单讲解下，为何有时用链表，有时却觉得数组(列表）。
首先必须初始化数组，然后把新节点的指针指向next，这个地方指针容易出错，须注意下。
初始化节点cur
cur指向next
prev指向cur
删除操作，先找上节点，将其指针，直接指向next。这时，你会说，咦，cur.next指针没有清空啊，emmm,那你也可以清空。指向null。
delete节点
双向列表实现，只要给next,加上pre属性，让它指向前面cur,就行。
双向链表
循环链表
循环列表实现时，将头节点的next属性指向其本身，然一次添加元素即可。
现在看看，链表的优势和劣势。
链表通过‘指针’将一组零散的内存串联起来，就可以充分利用内存；而数组内存需连续的，足够大的空间。
但是呢，链表也得支持增改删查，每次遍历最优时间复杂度O(1),最差时间复杂度O(n),而数组只要用下表就可以访问到，时间复杂度O(1),如果随机查找，时间复杂度则是，O(n).
在开发中，一般用双向列表或者循环列表，这样就能大大降低，所需的时间复杂度。其实仔细想想，这就是用时间换空间的思路。
简单介绍下，CPU缓存：cpu从内存中读取数据时，会把每次取到的数据加载到CPU的缓存中。而CPU每次从内存中读取数据并不是只读取那个特定要访问的地址，而是读取一个数据块，并保存到CPU缓存中，然后下次访问内存数据的时候就会从CPU缓存中开始查找，如果没找到，就从内存中取。这样就实现了比内存访问更快的机制。
对于数组而言，存储空间是连续的，所以在加载某个下标元素时，可以把以后的几个下标元素在也加载到CPU缓存这样，执行起来速度更快(比访问内存)，比存储空间不连续的链表存储也快。
如果，我们能利用缓存链表，那么又能降低操作链表的时间复杂度了。也可采用2-8策略，用过的元素放到链表最前面，少用的自然就在后面了，这个实现，可用哈希表来记录数据的位置；缓存呢，注意一下，是否达到上限就行。
reference:极客时间 《数据结构与算法之美》
《数据结构与算法javascript描述》
部分源码：https://github.com/Jiangjao/python_learn_demo/new/master
部分图片来源：leetcode 链表介绍
详细细节，有时间再慢慢添加。
网友评论