Big O of Common Array and Hash Operations

Because a Python list is a contiguous block of memory with a pointer to each element. Appending writes into the free space at the end and bumps a length counter, which is a fixed amount of work. Inserting at the front has no free space at the front, so every existing element must shift one slot to the right to make room. That is n moves, so the operation is O(n).

from collections import deque

stack = [1, 2, 3, 4, 5]
stack.insert(0, 0)
print(stack)

queue = deque([1, 2, 3, 4, 5])
queue.appendleft(0)
print(list(queue))

Both lines print the same sequence, zero followed by one through five, but the work behind them is completely different. The list version physically relocated five elements. The deque version stores elements in small blocks with links between them and keeps an index of where the front begins, so adding to the front is a matter of writing one cell and moving that index along.

The trade-off to state is that a list gives you cheap random access, since element i sits at a computable offset, while a deque gives you cheap insertion and removal at both ends. Pick the container for the operation you perform most often. If a workload appends and pops from the front in a loop, using a list costs quadratic time across the run, and switching to a deque turns that into linear.

Two practical notes round this off. The deque indexing by position is O(n), so if you need random access, convert to a list first. And the shift cost of insert is not always paid: Python lists keep a small amount of spare capacity, so appending amortised over many operations is constant, even though any single append can occasionally trigger a full reallocation and copy.

Scanning a list for a value is O(n), because the only way to know an element is present is to compare against entries until you find it or run out. Looking the same value up in a dict is O(1) on average, because the key is hashed to a bucket and you compare against at most the handful of entries that landed there.

The mechanism is the hash function. Given a key, it produces an integer; the dict uses that integer to jump straight to a region of its internal table, so the search never touches unrelated entries. That is the entire reason the cost does not depend on how many keys the dict already holds. A list has no such index, so it must walk from the front.

Two caveats keep the answer honest. First, the dict guarantee is average, not worst case. If every key collides into the same bucket, lookups degrade to O(n) as well. Python randomises the string hash by default, which makes such collisions impractical for well-behaved keys but is worth naming. Second, a dict lookup is not free in constant terms: computing the hash of a long string takes time proportional to the string length, so lookup is only constant time with respect to the number of entries, not the size of the keys.

The practical rule: reach for a dict when you need to look things up by a key, and reach for a list when you need order, duplicates, or cheap index access. Membership testing on a list is a common interview trap precisely because a set or dict gives the same answer in constant time instead of linear time.