Arrays, Dynamic Arrays and Linked Lists

Where elements live determines the cost

An array stores elements contiguously, so indexing a[i] is O(1): the address is computed directly. Inserting or deleting in the middle is O(n), because later elements must shift. A dynamic array (Python list, Java ArrayList, C++ vector) appends at the end in amortised O(1) time: occasionally it must allocate a larger block and copy everything, but by growing geometrically (for example doubling) the copying averages out to a constant per append. Inserting or removing at the front is O(n). A linked list stores nodes connected by pointers: inserting or deleting at a known node is O(1), but finding the i-th element or a value is O(n), and its poor memory locality makes it slower in practice than arrays for most workloads. A deque (double-ended queue, such as Python's collections.deque) supports O(1) appends and pops at both ends, making it the right choice for queues.

Contiguous versus linked storage

Arrays sit in one block of memory; linked lists scatter nodes connected by pointers.

Costs of common sequence operations (typical implementations)

Big-O for Python list, deque and a singly linked list.

operation                     Python list   collections.deque   singly linked list
----------------------------  ------------  ------------------  ------------------
index a[i]                    O(1)          O(n)*               O(n)
append at end                 O(1) amort.   O(1)                O(1) with tail ptr
pop from end                  O(1)          O(1)                O(n) (need prev)
insert / pop at front         O(n)          O(1)                O(1)
insert in middle (by index)   O(n)          O(n)                O(n) to find + O(1)
search by value (x in s)      O(n)          O(n)                O(n)

* deque indexing is O(1) near the ends and O(n) towards the middle

list.pop(0) in a loop is quadratic

Using a Python list as a queue with pop(0) shifts every remaining element each time, so processing n items costs O(n²). Use collections.deque and popleft() for O(n) total.

Quick check: What is the amortised cost of appending to a dynamic array that doubles its capacity when full?

• O(n)
• O(log n)
• O(1)
• O(n²)