链表在检索和动态调整上的优缺点
前面我们说了，数据无序存储的话，链表的检索效率很低。那你可能要问了，有序的链表好像也没法儿提高检索效率啊，这是为什么呢？你可以先停下来自己思考一下，然后再看我下面的讲解。
数组的「连续空间存储」带来了可随机访问的特点。在有序数组应用二分查找时，它以 O(1) 的时间代价就可以直接访问到位于中间的数值，然后以中间的数值为分界线，只选择左边或右边继续查找，从而能快速缩小查询范围。
而链表并不具备「随机访问」的特点。当链表想要访问中间的元素时，我们必须从链表头开始，沿着链一步一步遍历过去，才能访问到期望的数值。如果要访问到中间的节点，我们就需要遍历一半的节点，时间代价已经是 O(n/2) 了。从这个方面来看，由于少了「随机访问位置」的特性，链表的检索能力是偏弱的。
但是，任何事情都有两面性，链表的检索能力偏弱，作为弥补，它在动态调整上会更容易。我们可以以 O(1) 的时间代价完成节点的插入和删除，这是「连续空间」的数组所难以做到的。毕竟如果我们要在有序的数组中插入一个元素，为了保证「数组有序」，我们就需要将数组中排在这个元素后面的元素，全部顺序后移一位，这其实是一个 O(n) 的时间代价了。
