数组中插入和删除操作的最坏运行时间是O(n(，因为我们可能需要进行n次移位。
链表也是如此，如果我们想插入或删除第i个元素，我们可能需要遍历整个列表，以到达预期插入/删除的位置。所以链表也需要O(n(时间。
那么，为什么链表在执行插入/删除密集型操作时更受欢迎呢。
如果您想在数组中插入/删除第i个元素，由于索引的原因，搜索只需要O(1(。例如，u可以通过array[i]访问数组的第i个元素。但是，在最坏的情况下，插入/删除该元素将花费O(n(时间。例如，如果在位置0插入一个元素，则必须将所有元素向右移动一个位置，这需要遍历整个数组。
如果你想在链表中插入/删除第i个元素，在最坏的情况下搜索将花费O(n(，因为你必须在每次遍历一个元素的列表时保留一个计数和一个指针。一旦到达第i个节点，插入/删除只需要O(1(时间，因为这只是指针的重新排列，而不是移位。
至于为什么当有很多插入/删除时，链表是首选的，我想说的一个原因是，有了链表，你不需要提前知道它有多大。而对于数组，它可能需要经常调整大小，以预期更多/更少的元素。
在两种情况下搜索元素是相同的(O(n)(。不同之处在于当您在指定位置时插入和删除。在这种情况下，插入和删除是链表中的O(1)(因为您应该重置两个指针(，但在数组中需要O(n)(因为您需要O(n)移位(。
另一个区别是从一个位置到另一个位置的遍历。在列表中，此遍历取O(n)，但在数组中为O(1)。
当有一个直接指向节点的额外数据结构时，从链表中删除/插入O(1(的好处就实现了。这样可以避免列表遍历的O(n(开销。
一个很好的例子是有界大小的LRU缓存，其中键值对在映射中表示，该映射还保留指向链表的指针。列表表示访问顺序，LRU在这里利用快速链表访问。从中间取一个元素并把它放在前面就是O(1(。
每个密钥访问(O(1((从列表的中间取消关联节点的链接，并将其移动到列表的开头(在O(1(1(时间内(。当缓存已满时，列表的尾部节点将被删除(它表示最近使用最少的密钥/值(，以及它所表示的密钥-值对