A linked list stores a collection as a chain of small objects instead of one block of memory. This article covers what that chain is, how it compares with an array, and a minimal implementation you can run.
Key takeaways
- A linked list is a linear chain of nodes, and each node holds data plus a pointer to the next node.
- Reading position k costs O(k) because you walk from the head, while an array reaches any index in O(1).
- Growth is the trade: a linked list can add nodes one at a time, while an array's length is fixed when you declare it.
- Every node carries an extra pointer, so the memory per element is higher than in an array.
What a Linked List Is
A linked list is a linear chain of nodes. Each node holds two things: its data and a pointer to the next node.
The structure is called linear because each node refers to exactly one other node. If you draw it, it looks like a snake: one body segment follows another, with no branches.
To read anything in the list, you need a starting point. That point is the head node. Nothing points to it, and it points to the next node.
The opposite end is the tail. Other nodes point to it, but it points to nothing.
There are three common kinds: singly, doubly, and circular linked lists. We'll cover them in later articles.
Why Not Just Use an Array?
Arrays and linked lists do the same job, which is storing a collection of values. They differ in how they lay that collection out in memory.
An array is contiguous. The elements sit next to each other, so you can reach any element by its index in O(1). The catch is that an array's length is fixed when you declare it.
A linked list is scattered. Its nodes can live anywhere in memory, and the pointers chain them together. That lets the list grow node by node. The catch is that reaching position k means walking k nodes from the head, which is O(k).
A linked list also costs more memory per element. Every node stores a pointer in addition to its data.
| Aspect | Linked list | Array |
|---|---|---|
| Size | Can grow node by node | Fixed at declaration |
| Access time | O(k), walk k nodes to reach position k | O(1) by index |
| Layout in memory | Scattered, chained by pointers | Contiguous, ordered by index |
Neither one wins in general. The right choice depends on what your program does most.
Nodes and a Minimal Implementation
The node is the main building block, so it gets its own class. It has a field for data and a field for next, the pointer to the following node. In Java, that pointer is an ordinary object reference.
For a simple list, you also keep a reference to head. It is your entry point to every other node. Keeping a reference to tail is optional, though it is often stored to make adding data at the end easier.
This program builds the list 1, 2, 3, 4. It then prints the values by starting at head and following next until it reaches null:
public class SimpleLinkedList {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
public static void main(String[] args) {
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
for (Node current = head; current != null; current = current.next) {
System.out.println(current.data);
}
}
}I compiled and ran this with javac 21. The output:
1
2
3
4The loop never uses an index. It only follows pointers, which is the O(k) walk from the previous section.
What Comes Next
In the next article, we'll build a singly linked list properly. You'll create the node, a wrapper class around it, and the methods that work on the list.
Happy coding 👋