1回答

liuyubobobo

2018-07-21

已采纳

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

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

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

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

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

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

加油！

12

0