关于ArrayList与LinkedList时间复杂度的三个技术疑问

Great questions—these get into some nuanced details about list implementations that are easy to mix up! Let’s break each down clearly:

1. Why might ArrayList's remove(i) be listed as O(1) instead of O(n)? #

First, let’s set the record straight: in standard implementations like Java’s ArrayList, remove(int i) isn’t always O(1). Its time complexity depends entirely on which index you’re targeting:

• If you’re removing the last element (where i == size() - 1), the operation is O(1). All we need to do is decrement the list’s size counter—no elements need to be shifted or copied around.
• For any other index, every element after i has to be shifted left by one to fill the gap left by the removed element. In the worst case (removing the first element), this means shifting every element in the list, which is O(n).

It’s almost certain your textbook was referring to the best-case scenario (removing the last element) when it stated O(1). Some texts simplify complexity explanations by focusing on specific cases, so context here is key.

2. Why is LinkedList's add(i,e) listed as O(n) instead of O(min(i, n-i))? #

This boils down to how big O notation works—we typically use it to describe the worst-case upper bound of an algorithm’s runtime.

• You’re totally right that for a doubly linked list, we can optimize traversal by starting from whichever end (head or tail) is closer to index i. That gives us a more precise complexity of O(min(i, n-i)).
• But in the worst case—say, when i is exactly the middle of the list (i = n/2)—min(i, n-i) equals n/2, which still falls under O(n) (since constants are ignored in big O).

Many textbooks stick to O(n) for simplicity because it’s a valid upper bound that covers all possible cases, even if it’s not the most granular description.

3. Is O(min(i, n-i)) for linked list operations due to doubly linked list traversal optimization? #

Yep, that’s exactly the reason! Doubly linked lists keep track of both the head and tail of the list, and each node has pointers to both its previous and next node. When we need to access the element at index i, we can:

• Check if i is closer to the head (i < n/2): traverse forward from the head i steps.
• If i is closer to the tail (i >= n/2): traverse backward from the tail n-i steps.

This cuts the traversal time in half for many cases, which is why we can use the more precise O(min(i, n-i)) complexity for index-based operations on doubly linked lists.

内容的提问来源于stack exchange，提问作者Melanie A