Linked Structures and Pointers

Suppose you need to keep an ordered collection of items in a program: a playlist, a queue of print jobs, or a row of records loaded from a file. Java provides more than one class that can hold such a sequence. Two of the most common are java.util.ArrayList and java.util.LinkedList. Both implement the same List interface, so they share the same set of operations, and a program can often call the same methods on either one.

Yet the two classes behave very differently in speed, and that difference is the reason both exist. The underlying question is this: if the operations are identical, why not build one list class? The answer is that no single internal design makes every operation fast. Each design makes some operations cheap and others expensive. So the practical skill is not memorizing which class is better. It is recognizing which operations your program will repeat most often, and then picking the design that makes those operations cheap.

An ArrayList keeps its items in one contiguous block of storage, behaving like a row of numbered slots. Slot 0 holds the first item, slot 1 holds the second, and so on. The row can grow: when it fills up, the list obtains a larger row and copies the items across. From the programmer's point of view you simply keep adding items and the list takes care of the growing. Internally, though, the items sit side by side, and that arrangement is what makes positions so easy to compute.

The important feature is adjacency. Slot 2 sits directly after slot 1 in the same block, so the list does not need to examine slots 0 and 1 to know where slot 2 is. Keep this picture in mind, because the rest of the comparison follows from it.

A LinkedList takes a completely different approach. Instead of one block of adjacent cells, it stores each item in its own small container called a node. Every node holds an item and also a pointer, meaning a reference, to the next node in the sequence. The list itself only needs to remember where the first node is. Everything after that is reached by following the pointers from one node to the next.

Because the nodes are not required to sit next to each other, they can be scattered anywhere. What holds the sequence together is the chain of pointers. Picture a node holding value A whose pointer leads to a node holding B, whose pointer leads to a node holding C, and so on. The end of the chain is the last node, which has no next node to point to.

This arrangement is the key to the LinkedList's strengths and weaknesses. Changing where one node points is a local change that does not disturb the rest of the chain. Finding a node, on the other hand, requires walking the chain one link at a time.

Random access means getting or changing the item at a specified position k. Whenever a program asks for the item in slot 7, or wants to overwrite the item at position 12, it is doing random access. This is where the two structures diverge most sharply.

For an ArrayList, random access is essentially immediate. The list knows exactly where slot k lives because the cells are contiguous, so the time needed does not depend on how many items the list holds. This is written Theta(1), a constant amount of work. Slot 7 costs about the same as slot 0.

For a LinkedList there is no shortcut. To reach position k, the program must start at the first node and follow pointers forward k times. Picture a LinkedList holding A, B, C, D, E, F, G, H. To reach H at position 7, the walk goes: start at the first node (A), follow to B, follow to C, follow to D, follow to E, follow to F, follow to G, and follow once more to H. That is seven pointer follows. A position near the front is reached quickly, while a position near the back takes a long walk. The work grows with k, which is written Theta(k).

Changing the middle of a list is where the LinkedList earns its place. Consider what it takes to insert a new item between two existing items. In an ArrayList, the new item needs a free slot at the correct position, so every item from that point onward must move one position to make room. The cost depends on how many items sit after the insertion point. Inserting at the beginning forces the most movement, because every item shifts. Writing this cost as Theta(n) means the time grows in step with the number of items n.

In a LinkedList, the same insertion is a matter of re-pointing a few links. The new node is created, its pointer is set to the node that should follow it, and the pointer of the node before it is changed to point to the new node. Inserting X between A and B means setting X's pointer to B and changing A's pointer to X. Nothing else moves. A handful of pointer updates is enough regardless of how long the list is. That is why these changes take Theta(1) time once the program is already standing at the spot where the change belongs.

Read this table against your own program. If the work is dominated by reading items by position, such as looking up slot 7 many times, the ArrayList's constant-time access is the decisive advantage. If the work is dominated by inserting or removing in the middle of the sequence, the LinkedList's cheap relinking is the advantage. If the work is mostly appending and sorting, both classes perform well, and other design choices will probably matter more than this one.