An array keeps its elements side by side: it reaches any index in O(1), but inserting at the front moves every element. A linked list inserts at the front by changing two links, O(1), but reaches an index by walking from its first node, O(n). Use an array by default, a list when values come and go at the front.
Below, both take the same values twice: put in front, the array moves every value and the list only changes two links; added at the end, the array writes one slot and the list walks every node.
// array vs linked list
Take two values, B and D, in an array of three slots and in a linked list, and put A in front of them. In the array, index 0 is taken; the list has no slot to free, only a head that refers to its first node. Which of the two has to move something?
The moves start from the last value, so that none is overwritten, and their number grows with the array: inserting at the front takes O(n). Deleting from the front moves every value back one slot left.
Inserting at the front takes O(1) in a list of any length. Deleting from the front is O(1) too, and changes a single link: head moves on to the second node.
Note
In C and C++ a link is a pointer; in Java and Python it is a reference.
Now four values, A to D, and E added after the last one. The array keeps count of its values, so it knows where its first free slot is. The list knows only its first node; the last node is the one whose next is null, a link that refers to no node, drawn as an empty box with no arrow.
A dynamic array keeps spare slots so that adding at the end finds one free. When they run out, it copies every value into a larger array, often twice the size. That happens rarely enough that adding at the end takes O(1) amortized, the average per addition over a whole run from an empty array; the array page shows a resize.
In a list of a million nodes, pred passes almost a million of them before E can be linked. A list that also keeps a tail, a link to its last node, skips the walk and adds at the end in O(1). Deleting the last node needs the node before it, though, and only a doubly linked list reaches that one without a walk: singly vs doubly linked list.
The walk in the last player is also how a linked list reaches any index: to read the value at index 3, it follows three links from the head. An array works out where index 3 is: its elements all have the same size and stand side by side, so the element at index i starts i element sizes after the first one. That is one multiplication and one addition whatever the index: O(1). The array page shows it in memory.
The same difference decides searching. A sorted array can be searched by halves, looking at the middle and dropping the half that cannot hold the value, in O(log n). A linked list cannot jump to its middle, so even a sorted list is searched node by node, in O(n).
Memory. An array holds its values and, if it is dynamic, some spare slots: right after it doubles, about half of its slots are empty. A linked list holds a link next to every value, two in a doubly linked list, and each node is a separate piece of memory with some bookkeeping of its own. For small values, the links take more memory than the spare slots do.
The cache. A processor reads memory in blocks of neighboring bytes and keeps them close at hand, in its cache. Walking an array brings the next elements along with each block; a list's nodes can be anywhere, and each one may need a read of its own. That is why an array often wins even where both are O(n): moving the second half of an array to insert in the middle is usually faster than walking a list to the same place.
| Array | Linked list | |
|---|---|---|
| In memory | One block, elements side by side | Separate nodes, each with a link to the next |
| Access by index | O(1) | O(n) |
| Insert or delete at the front | O(n) | O(1) |
| Add at the end | O(1), amortized for a dynamic array | O(n); O(1) with a tail |
| Delete at the end | O(1) | O(n); O(1) in a doubly linked list with a tail |
| Insert or delete in the middle | O(n), to move the values after it | O(n), to walk there; O(1) right after a node you hold |
| Search a sorted sequence | O(log n) | O(n) |
| Extra memory | Spare slots, if dynamic | A link per value, two if doubly linked |
| The values here | Front: 2 values moved. End: 1 write | Front: 2 links changed. End: a walk of 3 steps, then 1 link |
Use an array by default: whenever you read by index, scan from start to end, sort, search by halves or add at the end. Python's list, Java's ArrayList and C++ std::vector are dynamic arrays, and a stack or a heap is usually built on one.
Use a linked list when values are added and removed at the front, or right after nodes you already hold, and never read by index: a queue with a tail, the chains of a hash table, an LRU cache, which keeps its items in order of use, built on a doubly linked list. A list also suits values that must stay where they are in memory while others come and go, since a node stays where it was made. Java's LinkedList and C++ std::list are doubly linked lists; C++ std::forward_list is a singly linked one.
O(1). Only right after a node you already hold. Finding the place, as the second list player does, is a walk: O(n).O(1), and inserting at the front moves every element.An array's elements have one size and stand side by side, so the place of index i is computed from the start of the array in one step. A linked list's nodes can be anywhere in memory, and the only way to the node at index i is to follow i links from the head.
When values are inserted or deleted at the front, which moves every element of an array but changes only one or two links in a list, and when they are inserted or deleted right after a node the program already holds. For access by index, scanning and adding at the end, an array is faster.
ArrayList in most cases: get(i) is O(1), and it keeps the references to its elements side by side in one array, where LinkedList adds a separate node for each element. LinkedList, a doubly linked list that keeps its last node, adds and removes at both ends in O(1), so it works as a queue or a stack, but ArrayDeque, a growable circular array, usually does that faster.
// in the app
In VisiGrab, the array is a 58-slide show and the linked list a 73-slide show, from the first element and the first node to dynamic arrays and the tail, played one step at a time.
One graph shows the worst case, resizes growing as log n and the amortized O(1) line. Then deleting at the end, with and without halving.
A speedometer moves from O(1) for the list's first node to O(n) for any other, and a recap gives the list a winner's cup at the beginning and the array one at the end.
At the beginning, in the middle and at the end of the list, each a chapter of its own, then a tail that makes insertion at the end O(1).
Step through every slide and step back, or jump to any slide from the list. Each show reopens where you left it.
Static arrays in Java and C++, Python's list, Java's ArrayList and C++'s std::vector, a dynamic array built from scratch in Java and C++, and a linked list with six insert and delete methods in all three, explained part by part.
Ten questions on each topic, with an explanation for every option.
// step through both
Download VisiGrab to step through the array and the linked list: dynamic arrays and their resizing, and every insertion and deletion in the list.
The array and the linked list are topics among 30+. See them all