Lists

A list is an interface, not a layout

A list is an abstract data type: an ordered, resizable sequence of items you reach one after another from a head toward a tail. What defines it is the set of operations it promises, not how those operations are stored in memory. The standard list interface offers get(i) and set(i, x) to read or overwrite the item at position i, add(i, x) to insert a new item at position i (shifting later items down), remove(i) to delete the item at position i, and a search to find where a value lives. 'Ordered' here means the items have positions 0, 1, 2, ... — first, second, third — not that they are sorted. Because a list is just this contract, two structures with completely different performance can both honor it. The rest of this lesson is about those two structures and why the same operation can be cheap on one and expensive on the other.

Implementation 1: the dynamic array

A dynamic array stores the items in one contiguous block of memory, exactly like a plain array, but keeps some spare capacity at the end and quietly allocates a bigger block when it fills up. Because storage is contiguous, the item at index i sits at a computable offset, so get(i) and set(i, x) are O(1) — direct random access, no scanning. (The base-plus-offset addressing math itself belongs to the arrays topic; here we only borrow the result that indexing is constant time.) Appending at the end is O(1) most of the time; occasionally the block is full and the structure allocates a larger one and copies every element over, which costs O(n) for that single append. Averaged over many appends this evens out to O(1) each — the amortized cost. The weakness is insertion and deletion away from the end: add(i, x) and remove(i) must shift every element after position i, which is O(n - i), and up to O(n) at the front. This is precisely what Python's built-in list is. In CPython, indexing and append are O(1), insert and delete are O(n), and 'x in mylist' is an O(n) linear search. The Python docs put it plainly: appends and pops at the end are fast, but inserts and pops at the beginning are slow because every other element must shift by one.

Implementation 2: the linked list

A linked list stores each item in its own small object called a node, and every node holds the value plus a pointer (a link) to the next node. The list keeps a head pointer to the first node; a singly-linked list links only forward, while a doubly-linked list also links backward and usually keeps a tail pointer to the last node. Nodes can sit anywhere in memory, so there is no offset arithmetic and therefore no O(1) indexing: to reach the i-th item you must start at the head and follow i links, which is O(n). Searching for a value is likewise O(n). The payoff is splicing. If you already hold a reference to a node, inserting a new node next to it or deleting it just rewires a couple of pointers — O(1), with nothing shifted. A doubly-linked list makes get, set, add, and remove run in O(1 + min{i, n-i}) time: the O(1) is the actual pointer work, and the min{i, n-i} is the cost of walking from the nearer end to find the node. Once you have the node, the edit is constant time. Appending is O(1) when a tail pointer is kept; without one, a singly-linked list must walk to the end first, which is O(n).

Comparing the two implementations

The two implementations are near mirror images. Reach for a dynamic array when you index or append a lot and rarely splice in the middle; reach for a linked list when you constantly insert and delete at positions you already have handles on and seldom jump to an arbitrary index. Here are the standard complexities:

The deep reason the columns disagree is the memory model: contiguous storage buys O(1) indexing but makes middle edits expensive because of shifting; scattered nodes buy O(1) splicing but make indexing expensive because you must traverse. There is no free lunch — you trade indexing speed for splicing speed and back.

Terminology across languages

The word 'list' is overloaded, so name the implementation you mean. A Python 'list' and a Java 'ArrayList' are dynamic arrays, not linked lists — despite the name, indexing them is O(1) and front-insertion is O(n). Java also ships an actual 'LinkedList' (a doubly-linked list) with the opposite trade-offs. C and Java 'array' means the fixed-size, contiguous primitive that cannot grow — the resizable list is built on top of it. Lists are also the substrate for other structures you will meet soon: a stack (last-in, first-out) and a queue (first-in, first-out) are lists restricted to adding and removing at particular ends, and both can be backed by either a dynamic array or a linked list. When someone says 'use a list,' the useful follow-up question is always: array-backed or linked?