数组和链表的增删操作的快慢

Question

        老师好，在java面试题中有这么一道题：数组和链表的区别！ 我看标准答案是这样说的：数组的查改操作快于链表，链表的增删操作快于数组。
        数组在第index个位置添加一个元素，数组的第index+1到最未的元素都要往后挪一位；删除第index个元素，那么数组的第index+1到最尾的元素都向前挪一个位置，时间复杂度是O(n)。
        链表由于没有索引，增删第index个节点都会从链表头遍历到index-1的位置，时间复杂度也是O(n)。
        那为什么说链表的增删快呢？

Answer 1

liuyubobobo 2018-07-21 09:19:22

这个说法稍微有点儿约定俗成的味道，背后基于了一个具体应用上的假设。那就是对于线性数据结构，我们通常都只会在首位或者尾位进行元素的增删操作。

如果可能在线性结构的任意位置进行元素的增删操作，如你所说，链表和数组都是O(n)级别的操作，此时，链表唯一的劣势是需要进行自动扩容和缩容，而链表是完全动态的。但是在均摊分析下，二者的复杂度相同。甚至在实践中，n很大的情况，链表有劣势，因为需要不停的进行内存空间的开辟和释放。

但是，如果首尾位都可能添加和删除元素则不同了。链表在首尾不管是添加还是删除，都是O(1)级别的操作。但是对于数组，在首位添加或者删除，是O(n)级别的，而在尾位，才是O(1)。当然了，你其实可以使用课程中的循环数组的方案，创建一个在首位添加删除元素也是O(1)复杂度的基于数组的结构，但我估计这不是这个问题里“数组”的含义：）可是你要告诉我数组也能做到首位增删O(1)，并且给出正确的思路，我给你120分：）

btw，在首尾都能进行添加和删除元素的数据结构，称为deque，是double queue的简写。有兴趣，可以基于链表和数组，分别实现一个属于自己的Deque类：）

无论是笔试还是面试，对于这个问题，都这么叙述。在我看来，这么叙述才是正确的（注意，上面的叙述，我只说了添加个删除，没有说访问操作。）。抛开应用场景，说谁优谁劣，是不严谨的。

识货的考官，看到你这么叙述，一定是120分；但如果你遇到了一个考官，说你的回答和标准答案不一样，所以不对，嗯。。。这个公司不值得去。

加油！