链表和数组的插入删除时间复杂度都是O(n），为什么教材网络上说链表的效率高？

Question

感觉书上纯粹是在囫囵吞枣，至少他没有说清楚，我只能把它视作写的存在问题。
除了insert_first/last(x)，delete_first/last(x)时间复杂度是O(1)，没有其他方面有高效率了吧……而且书上还没有关于修改head/tail提高链表插入修改首尾项的效率的陈述。

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

你的理解基本正确。在数据结构的操作中，插入和删除的时间复杂度并不仅仅取决于数据结构本身，还与具体的操作位置有关。对于数组和链表来说，插入和删除操作的效率确实在某些情况下有所不同。下面我会详细解释一下这个问题。

首先，对于数组来说，由于其元素在内存中是连续存储的，因此在任意位置的插入和删除操作都需要移动元素以填补空位或者腾出空间。所以，无论在数组的哪个位置进行插入或删除操作，时间复杂度都是O(n)。这是因为在最坏的情况下，可能需要移动数组中的所有元素。

然而，对于链表来说，情况有所不同。链表中的元素是通过指针链接在一起的，因此插入和删除操作只需要调整指针的指向，而不需要像数组那样移动元素。这就意味着在链表的某些位置进行插入和删除操作可以具有很高的效率。具体来说：

• 在链表的头部或尾部插入或删除元素的时间复杂度是O(1)。这是因为这些操作只需要调整头指针或尾指针的指向，而不需要遍历整个链表。
• 在链表的中间位置插入或删除元素的时间复杂度是O(n)。这是因为需要找到要插入或删除的位置，这需要遍历链表。然而，即使在时间复杂度为O(n)的情况下，链表的效率仍然可能比数组高，因为调整指针的指向比移动元素要快。

所以，当我们说链表的插入和删除操作效率更高时，通常是指相对于在数组的中间位置进行插入和删除操作的情况而言的。当然，这并不是说链表在所有情况下的效率都比数组高。在某些情况下（例如在数组的头部或尾部进行插入和删除操作），数组的效率可能会更高。因此，在选择数据结构时，需要根据具体的应用场景和需求进行权衡。

至于你提到的教材没有清楚说明这一点的问题，可能是教材在介绍链表时过于强调其优点而忽略了其缺点，或者没有提供足够的背景信息来解释为什么在某些情况下链表会比数组具有更高的效率。这可能是因为教材主要关注数据结构的基本概念，而没有详细讨论每种数据结构的所有细节和特性。如果你对这方面的内容感兴趣，可以查阅更多的资料或者参考一些更深入的教材来进一步了解。