抽空找资料温习了下数组和链表的内容，刚巧在极客时间上看到一篇比较过瘾，看完后，用自己的理解来整理下对数据和链表的理解。

数组和链表是常用的数据结构。

定义：

数组是一块具有连续内存的可以随机存取的数据结构， 而链表是不连续内存的无法随机存取的数据结构，但是链表可以很容易地进行插入/删除节点。

数组特征：

内存连续随机存取插入/删除某个元素时需要挪动数组中元素，时间复杂度为O(n)

链表特征：

内存不连续不能随机存取可以在O(1)时间复杂度内插入/删除元素

根据数组和链表的特性，如果要从一组数列中寻找一个指定的元素，在数组中，可以先对数组进行一个排序，然后利用二分查找（折半查找）的方式来进行元素的寻找，时间复杂度可以达到O(lg n), 然而利用链表是无法做折半查找的，因为链表不是连续存储，即使是一个有序的链表，也不具备随机访问的能力，只能从头开始寻找，所以时间复杂度时O(n)，但是在链表中插入/删除一个元素的时候，只需要改变前后两个元素的指向即可，时间复杂度是O（1）。

下面开始思考对数组或者链表进行变形，核心思想就是利用折半查找的思路，在搜索的时候，可以不断减半式地缩小搜索空间，达到高效的搜索，而可以做到不断减半搜索空间的前提是可以快速（以O(1)时间复杂度为例）定位到中间部分的元素，所以最初我的思路是将链表和数组两种数据结构进行合并，合并成一种新的数据结构C，使C具有数组的随机存取特性，又具有链表的快速插入/删除元素的特性。

基于这种链表和数组合并的思想，选择有2种：

链表的快速插入/删除元素的特性合并到数组中；数组的随机存储特性合并到链表中；

首先尝试方案1:

首先开始尝试数组中嵌套链表结构，让数组具备链表的快速插入/删除元素的特性，因为数组每个元素就是一个元素值，如果可以在每个元素中增加一个属性：后续元素的索引，那么这时候就类似于链表的那根指针。

当增加一个元素的时候，就可以直接插入元素到尾部，只要调整这个元素到前驱和后继的索引位置即可，但是每次把元素插入尾部，就失去了数组随机存取的特性了，难以做折半查找。暂时还没想到其他方案？？

再来尝试方案2:

在链表中嵌套数组结构，让链表具备随机存储的特性, 我尝试在链表中加入一个类似于数组一样的索引，试图能够做到随机查找元素，然后当我往链表中插入一个节点后，发现需要去更新这个索引，更新索引是O（n）的时间复杂度，所以失去了O（1）时间内插入/删除节点的特性了；暂时还没想到其他方案？？

总结了下上面两种失败的改造导致的后果是让数组和链表都失去了自己原本最重要的特性，反而得不偿失，于是在学习课程的时候，听到课程中老师提到的另一种改造思路是，在链表的的每个节点内，加入部分的有序数组，类似于下面这样：

这样就能对链表中的每个节点做部分的二分查找，假设当查询4是否存在于这个链表中，还是顺序访问每个节点，再对每个节点中的数组做二分查找，当插入4这个元素时，会对部分的元素进行移动（减少了移动的次数），那么问题来了：一个节点中的数组长度是多少比较合适？

这个问题就取决于是查找和插入的访问次数，抽象下来，查找对应的就是读，插入对应的是写，也就是问题抽象为两种场景，分别是读多写少和读少写多 ？

针对读多写少的场景，可以尽量增加一个节点内数组的长度，这样长度越大，越能利用数组二分查找的特性，查找速度越快，但是这种场景下，插入节点的效率会变低，因为数组长度越长，插入元素后，需要调整位置的数也越多，慢慢就会退化成数组的插入。

针对读少写多的场景，可以尽量减少一个节点内数组的长度，这样长度越小，插入元素时需要调整位置的数也越少，但是这种场景下，查找的效率会变低，因为每个节点的数组长度越小，那么所有数就会分布越多的节点，查找就慢慢退化成链表的查找。

如果采用这种数据结构，具体一个链表节点中的数组的长度则需要根据具体的业务去做一下benchmark，通过benchmark 以及业务的SLA等各种数据来决定链表中数组的长度到底是多少才合适。

其实写到这里，也确实能够感受到数据如何存储、数据结构如何设计是工程上方案设计的一个至关重要的因素，也能隐约理解现如今为什么有那么多的数据库存储方案，比如nosql、couchbase、mysql，elasticsearch、oracle等等，业务功能无论如何花哨，最终回到对于业务数据的处理，对于业务数据的处理就回到数据的读写上来，如何高性能读？如何高性能写？读写是否同时高性能？读写需要如何权衡等一系列问题就抛出来了。

从数据结构来思索各种数据解决的方案显得比较累，也不全面，如果再正向去思考，目前市面上比较流行的数据库解决方案有哪些，分别是怎么做的，为什么要这么做，底层用的数据结构和算法是什么，那样就能理解的更加清楚了，抽象地看问题，往往就能把很多表象结合一起，原理很多都是同宗的。

继续来记录链表和数组的衍生，上面选择了一种折中的方案将数据和链表结合在一起来使用，试图去提高效率，那么有没有一种数据结构是更加优胜的？

由于数组在内存组织上的连续性，所以对于有序数组，能够用二分查找在O（lgn）时间复杂度内查找到指定元素，但是在频繁插入数据的场景下，数组需要为了保持其有序性，需要不断重建排序（包括移动大量数据），而链表则能很好地应对频繁插入数据的情况，因为内存不连续，所以如果能够找到一种可以链表上实行二分查找算法的数据结构，就能应对快速查找的场景。通过将链表进行升维，从而达到一个二维的二叉树结构：

总体思想还是利用二分查找不断减半搜索空间的做法，减半式地减少搜索空间比一个个元素减少搜索空间的效率要高不少，假设在链表上采用二分查找，意味着可以先找到中间的元素M，然后通过判断指定元素和元素M的大小，来决定是往左寻找还是往右寻找：

如果是往左，也还是采取相应的策略，找出中间那个节点的元素L，往右也是一样，反复采取这种策略，最后衍化成的是一种二叉树的结构，每一棵子树上的根节点都是我们要查询的中间节点，也正是因为这个中间节点，才能不断把搜索空间减半：

而且会发现这种结构的左子树的节点值<中间节点<右子树的节点值，这就是一个标准的二叉排序树，从链表到二叉排序树到演化过程就是对于折半优化搜索空间的思想的实现过程，我觉得这种思想比演化的结果更加关键，因为也许可以用在某个场景或者其他的数据结构上，搜索的核心应该也就是不断地在一个有限子集中查询指定的值，有限子集空间越大，搜索越慢，所以要减少目标搜索空间，减少的速度越快，搜索到目标用到的时常越短，从上面的推理过程中，可以发现，在满足某些数据规律的情况下（如数据有序），就可以采用一种合理的数据分布存储方式或者数据结构来规划数据，比如这里的二叉排序树就是一种合理的数据分布结构，因为这种数据结构，配上二分查找算法，就能够做到O（lgn）时间复杂度之内去搜索到某个指定的数或者插入位置，然后以O（1）的时间复杂度来做插入或者删除，这里也再次映证了一个道理：正确的算法配合正确的数据结构才能事半功倍，就如这里，如果是无序的数据，二分查找算法是没有意义的，跟顺序遍历是一个效果，所以一个经典的数据结构背后一定是有一套优化的算法，反过来说，一个优化的算法一定要有一个与之匹配的数据结构。

一个数据结构的优化过程是艰辛的，因为实际生活中，诸多的实际场景容易让一个数据结构夭折，比如这里的二叉排序树，看起来已经是非常优化的数据结构，但是由于数据分布的不均匀，可能会导致下面这种情况

这种情况就是只有右子树，没有左子树的情况，那么这时候去查找某个节点的时候，其实就是退化成了一维线性结构的链表，时间复杂度退化成了O(n), 因此就要对二叉排序树做优化，才会有了现在的二叉平衡树和红黑树，这两种树的结构不是无端端产生的，他们要解决的问题就是动态保持树的平衡性，能够让搜索指定数字的时候会有一个相对平衡稳定的搜索空间，这样才能发挥出折半查找的优势。在删除或者插入树中某个节点的时候，会动态调整树的平衡度，不至于退化成单链表的形式。

除了上面这种二叉排序树来解决链表快速访问中间节点的方案之外，还有一种就是跳表，闻名遐迩的Redis这种数据存储方案，就是利用了跳表的特性，来对数据进行增删改查，这种方案是比二叉排序树更加容易理解的一种基于链表的演进，因为链表不具备随机快速访问某个节点的特性，链表的某个节点只有一个指针指向后续节点，所以如果可以在每个节点中加入多级指针，使得每个节点不单能访问后续节点，还能跳节点式地访问，那就等于具备了跳跃式地搜索能力，可以快速减少搜索空间

类似这张图，如果是这样的一种多级指针的链表结构，那么链表也就具备了直接访问中间节点的能力，每次最先访问指向最远的那个节点，相当于将搜索范围降低了一半，跳表唯一带来的缺陷是空间上的开销，以及链表中加入/删除节点时，指针的调整带来的损失，指针越多，搜索效率肯定越高，但是调整时的复杂度肯定也是越高的，所以可以根据实际情况，去调整自己的多级指针列表，或者采取多级指针随机的方案，不用保持每个节点的指针层数时一样的，可以用一个随机函数来生成多级指针的层数即可。比如插入一个结点k后，可以就调整k和k前面的节点即可，k的层数可以根据随机来定，尽量地可以减少指针调整带来的时间损耗

这里也只是一个参考方案，具体的优化还是需要根据业务场景，SLA、Benchmark等指标来进行测试优化。

以上主要从搜索的场景角度来记录链表和数组的区别，以及如何基于数组和链表其自身的特性来做层层优化、以及优化思想的由来，涉及到的数据结构包括数组、链表、二叉排序树、二叉平衡树、红黑树、跳表等，涉及到的算法是二分查找算法。