Learn Java

Lesson 39Phase 4: Collections and algorithms

Linked lists: nodes and references

Building a list out of nodes that point to each other, and how that changes what is fast and what is slow.

By Updated 50 min

  • node
  • head
  • next
  • traversal
  • insertion
  • deletion

An ArrayList keeps its elements side by side in one array. That makes get(1000)instant, and it makes adding at the front slow, because every element has to shift one place to make room. A linked list stores elements another way. Each element sits in its own small object, and each object holds a reference to the next one, so together they form a chain. In this lesson you build that chain with your own code and watch its references change as the program runs. Then you meet Java's LinkedList and find out why ArrayList is still the better choice most of the time.

By the end of this lesson
  • Build a chain of nodes from a Node class with a value and a next reference, and keep a head that refers to the first node.
  • Walk a list with a loop that stops at null, to print it, count it and search it.
  • Add a node at the front, at the end and after a given node, and delete a node, including the first and the last.
  • Change references in an order that never loses part of the list, and handle the empty list without a NullPointerException.
  • Explain what a doubly linked list adds, and use java.util.LinkedList through its List and Deque methods.
  • Compare LinkedList with ArrayList, and say why ArrayList is usually the better default.
From before
From the this keyword and object references you know that an object variable holds a reference to an object, that two variables can refer to the same object, and that null means no object at all, so using the dot on it throws a NullPointerException. ArrayList: a list that can grow showed you the backing array, and why adding at index 0 shifts every element. Stacks, queues and deques used the Deque methods addFirst, pollFirst and the rest, and ended by saying that LinkedList is a Deque too. This lesson builds a linked list from scratch.

A chain instead of a row#

Picture a row of numbered lockers in a school corridor. To open locker 40 you walk straight to it, because the number tells you where it is. An array works the same way: Java works out where slot 40 is and goes there directly. But to fit a new item into locker 0, you would first have to move every item one locker along.

Now picture a treasure hunt. Each clue is a slip of paper that says two things: a message, and where the next clue is hidden. The organisers tell you only where the first clue is. To read the fourth clue you have to find the first three on the way, because nothing else tells you where the fourth one is. Adding a clue at the start is easy, though. You write a new slip that says where the old first clue is, and tell the players to start from the new slip. No other clue moves.

A linked list is that treasure hunt in memory. Each slip is a node: a small object that holds one value and a reference to the next node. The field that holds the reference is usually called next. The last node has nothing after it, so its next is null. A variable called head refers to the first node, and it is the only way into the list. From head you can reach every node by following next references, and without it you can reach none of them.

Key idea

An array finds an element by its position. A linked list finds an element by starting at head and following next references, one node at a time.

Building nodes by hand#

A node needs two fields: one for the value and one for the reference to the next node. This program defines a Node class for a shopping list, makes three nodes, links them into a list and reads the list through head. Press Run, then step through it with the memory view open.

Chain.java
1public class Main {
2 public static void main(String[] args) {
3 Node milk = new Node("milk");
4 Node eggs = new Node("eggs");
5 Node bread = new Node("bread");
6
7 milk.next = eggs;
8 eggs.next = bread;
9
10 Node head = milk;
11 System.out.println(head.value);
12 System.out.println(head.next.value);
13 System.out.println(head.next.next.value);
14 System.out.println(head.next.next.next);
15 }
16}
17
18class Node {
19 String value;
20 Node next;
21
22 Node(String value) {
23 this.value = value;
24 }
25}
Prints
›milk
›eggs
›bread
›null

It prints milk, eggs and bread, then null. Start with the class at the bottom. value holds the item. next has the type Node, so a node refers to another object of its own class. The constructor sets only value. Nothing sets next, which leaves it at the default value of an object field, null, as you saw in creating classes and objects.

The three new Node lines make three separate nodes, each with next still null: three slips that do not yet say where the next clue is. milk.next = eggsstores a reference to the eggs node in milk's next field, and eggs.next = bread does the same for the eggs node. Now the three nodes form a chain.

head.next.next.value reads from left to right. Start at the node head refers to, which is milk. Follow its next to eggs, follow that node's nextto bread, and read bread's value. The last line follows one next too many: bread's next is null, so println prints null.

In the memory view, each Node is a box with a tag in the order it was made: milk's node is Node #1, eggs's is Node #2 and bread's is Node #3. A next field shows an arrow and the tag of the node it refers to, so once the two linking lines have run, Node #1 points at Node #2 and Node #2 points at Node #3. When head is declared, the first box says it is held by both milk and head: two variables, one node.

Walking the list#

Writing head.next.next.value by hand works for three nodes. A real list may hold thousands, and you will not know how many in advance. To visit every node, use a second variable that starts at head and steps along the chain, one next at a time. A common name for it is current.

  1. 1Start at the first node: Node current = head;
  2. 2While current refers to a node, that is while current != null, use current.value.
  3. 3Step on to the next node: current = current.next;
Walk.java
1public class Main {
2 public static void main(String[] args) {
3 Node head = shoppingList();
4
5 Node current = head;
6 while (current != null) {
7 System.out.println(current.value);
8 current = current.next;
9 }
10 System.out.println("End of the list");
11 }
12
13 static Node shoppingList() {
14 Node milk = new Node("milk");
15 Node eggs = new Node("eggs");
16 Node bread = new Node("bread");
17 milk.next = eggs;
18 eggs.next = bread;
19 return milk;
20 }
21}
22
23class Node {
24 String value;
25 Node next;
26
27 Node(String value) {
28 this.value = value;
29 }
30}
Prints
›milk
›eggs
›bread
›End of the list

It prints milk, eggs and bread on three lines, then End of the list. shoppingList() is a static method that builds the same three nodes as before and returns the first one, so main starts with a ready-made list.

Step through it and watch current in the call stack: its arrow moves from Node #1 to Node #2 to Node #3, one node per pass, while head stays on Node #1. After bread, current = current.nextstores bread's next, which is null, so the loop condition is false and the walk ends. The list itself never changes; only current moves. Visiting the nodes one after another like this is called traversal, or walking the list.

The empty list needs no special case here
If head is null, current starts as null, the condition is false straight away, and the body never runs. A walk written this way handles the empty list for free, which is worth checking every time you write one.

The same walk fits in a for loop, with its three parts in the header: start at head, keep going while current is not null, step to current.next. These two methods use that form to count the nodes and to find the position of a value:

Questions.java
1public class Main {
2 public static void main(String[] args) {
3 Node head = shoppingList();
4 System.out.println("size: " + size(head));
5 System.out.println("eggs is at " + indexOf(head, "eggs"));
6 System.out.println("jam is at " + indexOf(head, "jam"));
7 System.out.println("an empty list has size " + size(null));
8 }
9
10 static int size(Node head) {
11 int count = 0;
12 for (Node current = head; current != null; current = current.next) {
13 count++;
14 }
15 return count;
16 }
17
18 static int indexOf(Node head, String target) {
19 int index = 0;
20 for (Node current = head; current != null; current = current.next) {
21 if (current.value.equals(target)) {
22 return index;
23 }
24 index++;
25 }
26 return -1;
27 }
28
29 static Node shoppingList() {
30 Node milk = new Node("milk");
31 Node eggs = new Node("eggs");
32 Node bread = new Node("bread");
33 milk.next = eggs;
34 eggs.next = bread;
35 return milk;
36 }
37}
38
39class Node {
40 String value;
41 Node next;
42
43 Node(String value) {
44 this.value = value;
45 }
46}
Prints
›size: 3
›eggs is at 1
›jam is at -1
›an empty list has size 0

It prints size: 3, eggs is at 1, jam is at -1 and an empty list has size 0. indexOf counts its steps as it walks, and returns -1 when it reaches the end without a match, as the indexOf of an ArrayList does.

Notice what is missing: there is no way to jump to a position. To read position 2, a linked list visits the nodes at positions 0, 1 and 2. In a list of a million nodes, reaching the last one from head means visiting all million. An ArrayList goes straight to any slot, the way you walked straight to locker 40.

Predict the outputStopsEarly.java
1public class Main {
2 public static void main(String[] args) {
3 Node head = new Node("milk");
4 head.next = new Node("eggs");
5 head.next.next = new Node("bread");
6
7 Node current = head;
8 while (current.next != null) {
9 System.out.println(current.value);
10 current = current.next;
11 }
12 }
13}
14
15class Node {
16 String value;
17 Node next;
18
19 Node(String value) {
20 this.value = value;
21 }
22}

This loop tests current.next instead of current. What does it print?

It prints only milk and eggs. When current reaches bread, bread's next is null, so the condition is false before bread is printed. current.next != nullasks “is there a node after this one?”. That is the right question when you want to stop on the last node, as you will when you add a node at the end. To visit every node, ask current != null.

Walking past the end#

The opposite mistake is walking one step too far. This find method returns the node that holds a value. It walks until it sees the value, and nothing stops it at the end of the list:

Find.java
1public class Main {
2 public static void main(String[] args) {
3 Node head = shoppingList();
4 System.out.println(find(head, "eggs").value);
5 System.out.println(find(head, "jam").value);
6 }
7
8 static Node find(Node head, String target) {
9 Node current = head;
10 while (!current.value.equals(target)) {
11 current = current.next;
12 }
13 return current;
14 }
15
16 static Node shoppingList() {
17 Node milk = new Node("milk");
18 Node eggs = new Node("eggs");
19 Node bread = new Node("bread");
20 milk.next = eggs;
21 eggs.next = bread;
22 return milk;
23 }
24}
25
26class Node {
27 String value;
28 Node next;
29
30 Node(String value) {
31 this.value = value;
32 }
33}
Prints
›eggs
!Exception in thread "main" java.lang.NullPointerException: Cannot read field "value" because "current" is null
! at Main.find(Main.java:10)
! at Main.main(Main.java:5)
Stops on line 10

NullPointerException: Cannot read field "value" because "current" is null

A variable held null, so there was no object to use.

The first search prints eggs. The second never finds jam. currentmoves from milk to eggs to bread, then to bread's next, which is null, and the next check of the condition reads current.value. The program stops on line 10 with a NullPointerException and this message: Cannot read field "value" because "current" is null. It names the field Java tried to read and the variable that held null. (Built with plain javac, the message says "<local2>" instead of "current"; reading errors and debugging explains why.)

The fix is to stop when current becomes null as well as when the value matches. The order of the two checks matters:

FindFixed.java
1public class Main {
2 public static void main(String[] args) {
3 Node head = shoppingList();
4 System.out.println(find(head, "eggs").value);
5 System.out.println(find(head, "jam"));
6 System.out.println(find(null, "jam"));
7 }
8
9 static Node find(Node head, String target) {
10 Node current = head;
11 while (current != null && !current.value.equals(target)) {
12 current = current.next;
13 }
14 return current;
15 }
16
17 static Node shoppingList() {
18 Node milk = new Node("milk");
19 Node eggs = new Node("eggs");
20 Node bread = new Node("bread");
21 milk.next = eggs;
22 eggs.next = bread;
23 return milk;
24 }
25}
26
27class Node {
28 String value;
29 Node next;
30
31 Node(String value) {
32 this.value = value;
33 }
34}
Prints
›eggs
›null
›null

It prints eggs, then null twice: find now returns null for a value that is not in the list, and for an empty list. && looks at its right side only when its left side is true, the short-circuit rule from operators, so current.value is read only after current != null has passed. The caller still has to check the result before using it, which is why the last two lines print what find returns instead of its value.

Quick check
A teammate writes the condition the other way round: while (!current.value.equals(target) && current != null). What happens when the target is not in the list?
ExerciseGetByPosition.java
Finish get so it returns the value at a position, counting from 0, or null when the list has no node at that position. It must not throw for a position past the end, or for an empty list.
A list inside a list
A list is either empty or a node followed by a shorter list. That description mentions a list inside itself, and the next lesson, recursion, uses it to walk a list with a method that calls itself on next.

Changing the links#

Adding a node to a list is called insertion, and taking one out is called deletion. In an array both mean shifting elements along. In a linked list no node ever moves: an insertion creates a node and links it in by changing one or two references, and a deletion changes one reference so that walks skip a node. The care goes into changing them in the right order.

Adding at the front#

Adding at the front takes two lines. Point the new node at the current first node, then move head to the new node:

AddFirst.java
1public class Main {
2 public static void main(String[] args) {
3 Node head = shoppingList();
4 print(head);
5
6 Node jam = new Node("jam");
7 jam.next = head;
8 head = jam;
9 print(head);
10 }
11
12 static Node shoppingList() {
13 Node milk = new Node("milk");
14 Node eggs = new Node("eggs");
15 Node bread = new Node("bread");
16 milk.next = eggs;
17 eggs.next = bread;
18 return milk;
19 }
20
21 static void print(Node head) {
22 for (Node current = head; current != null; current = current.next) {
23 System.out.print(current.value + " -> ");
24 }
25 System.out.println("null");
26 }
27}
28
29class Node {
30 String value;
31 Node next;
32
33 Node(String value) {
34 this.value = value;
35 }
36}
Prints
›milk -> eggs -> bread -> null
›jam -> milk -> eggs -> bread -> null

The first line of output is milk -> eggs -> bread -> null. print walks the list with the for loop from before and draws an arrow after each value. The second line is jam -> milk -> eggs -> bread -> null. Step to head = jamand look at the arrows: jam's next names milk, and milk, eggs and bread are untouched. It takes the same two lines whether the list holds three nodes or three million.

Predict the outputWrongOrder.java
1public class Main {
2 public static void main(String[] args) {
3 Node head = new Node("milk");
4 head.next = new Node("eggs");
5
6 Node jam = new Node("jam");
7 head = jam;
8 jam.next = head;
9
10 System.out.println(head.value);
11 System.out.println(head.next.value);
12 System.out.println(head.next.next.value);
13 }
14}
15
16class Node {
17 String value;
18 Node next;
19
20 Node(String value) {
21 this.value = value;
22 }
23}

Here the same two lines run in the other order: head moves first. What does the program print?

It prints jam three times. After head = jam, no variable and no next field refers to the milk node any more, so milk and eggs are cut off from the program. Then jam.next = head copies head, which by now is jam itself, into jam's next: the node points at itself. Following next from jam leads back to jam every time, so a walk over this list would never end.

Key idea

Before you move a reference away from a node, make sure something else still refers to that node. When you add, link the new node to the rest of the list first, then change the reference that leads into it.

Removing the first node#

To remove the first node, move head on to the second one:

RemoveFirst.java
1public class Main {
2 public static void main(String[] args) {
3 Node head = shoppingList();
4 print(head);
5
6 head = head.next;
7 print(head);
8 }
9
10 static Node shoppingList() {
11 Node milk = new Node("milk");
12 Node eggs = new Node("eggs");
13 Node bread = new Node("bread");
14 milk.next = eggs;
15 eggs.next = bread;
16 return milk;
17 }
18
19 static void print(Node head) {
20 for (Node current = head; current != null; current = current.next) {
21 System.out.print(current.value + " -> ");
22 }
23 System.out.println("null");
24 }
25}
26
27class Node {
28 String value;
29 Node next;
30
31 Node(String value) {
32 this.value = value;
33 }
34}
Prints
›milk -> eggs -> bread -> null
›eggs -> bread -> null

It prints milk -> eggs -> bread -> null, then eggs -> bread -> null. Watch the memory view at head = head.next. The arrow from head moves to the eggs node, and the milk node is left with no variable holding it. No variable refers to it, and no nextfield points at it. Milk's own next still points at eggs, but that does not help milk: a reference leads from one node to the next, never back, and nothing leads to milk.

The program can never reach that node again. Java notices objects like this and frees their memory, as it did with the old backing array in the ArrayList lesson. The part of Java that does this is the garbage collector, and it runs on its own, at times it chooses. Your code never deletes a node directly: it stops referring to the node, and the garbage collector does the rest.

The memory view keeps lost nodes
The visualizer has no garbage collector, so the milk box stays on screen to the end of the run. That lets you check that nothing refers to it. A real JVM would free that memory at some point after head moved on.
Quick check
After head = head.next, what happens to the node that used to be first?

Inserting after a node#

To insert a node in the middle you need a reference to the node it goes after. Here jam goes after eggs. The order matters again: the new node takes over the eggs node's next first, and only then does eggs point at the new node.

Insert.java
1public class Main {
2 public static void main(String[] args) {
3 Node head = shoppingList();
4 Node eggs = head.next;
5
6 Node jam = new Node("jam");
7 jam.next = eggs.next;
8 eggs.next = jam;
9 print(head);
10 }
11
12 static Node shoppingList() {
13 Node milk = new Node("milk");
14 Node eggs = new Node("eggs");
15 Node bread = new Node("bread");
16 milk.next = eggs;
17 eggs.next = bread;
18 return milk;
19 }
20
21 static void print(Node head) {
22 for (Node current = head; current != null; current = current.next) {
23 System.out.print(current.value + " -> ");
24 }
25 System.out.println("null");
26 }
27}
28
29class Node {
30 String value;
31 Node next;
32
33 Node(String value) {
34 this.value = value;
35 }
36}
Prints
›milk -> eggs -> jam -> bread -> null

It prints milk -> eggs -> jam -> bread -> null. jam.next = eggs.next copies the reference to bread into jam, so for a moment two nodes point at bread. Then eggs.next = jam moves the eggs node's arrow over to jam. Step through it and compare the arrows before and after those two lines: eggs now points at jam, and jam points at bread. No other reference changed, and no node moved.

Put the lines in orderBetween.java
Put the lines in order so the program builds a list of milk and bread, slides eggs in between them, and prints milk eggs bread. One wrong order of two lines prints milk eggs eggs; work out why before you check.

Tap a line, then tap where it should go. Or use the arrows.

Deleting a node further along#

To delete any node except the first, you change the node before it. That node skips over the one you delete: its next takes the deleted node's next. In this program head refers to milk, the node before eggs, and the same line runs twice:

Delete.java
1public class Main {
2 public static void main(String[] args) {
3 Node head = shoppingList();
4 print(head);
5
6 head.next = head.next.next;
7 print(head);
8
9 head.next = head.next.next;
10 print(head);
11 }
12
13 static Node shoppingList() {
14 Node milk = new Node("milk");
15 Node eggs = new Node("eggs");
16 Node bread = new Node("bread");
17 milk.next = eggs;
18 eggs.next = bread;
19 return milk;
20 }
21
22 static void print(Node head) {
23 for (Node current = head; current != null; current = current.next) {
24 System.out.print(current.value + " -> ");
25 }
26 System.out.println("null");
27 }
28}
29
30class Node {
31 String value;
32 Node next;
33
34 Node(String value) {
35 this.value = value;
36 }
37}
Prints
›milk -> eggs -> bread -> null
›milk -> bread -> null
›milk -> null

It prints milk -> eggs -> bread -> null, then milk -> bread -> null, then milk -> null. The first head.next = head.next.next reads milk's next (eggs), then that node's next (bread), and stores bread in milk's next, so the walk jumps from milk straight to bread. The second time, milk's nextis bread and bread's next is null, so the same line stores null. Deleting the last node needs no code of its own.

At the end, the memory view shows nothing pointing at eggs. The bread box still has one arrow coming in, from eggs, but eggs cannot be reached itself, so that arrow leads nowhere useful. What counts is whether a walk that starts from one of the program's variables can get to a node, and the garbage collector works by the same rule.

You need the node before
Deleting a node means changing the next of the node before it. A reference to the node you want to delete is not enough, because that node does not know which node points at it. That is why the delete code later on this page walks with current.next: it keeps current one node behind the node it is checking.

A list class of your own#

So far head has been a local variable in main, and every change was written out by hand. Real code keeps head inside a class, with a method for each operation, so the rest of the program never touches a node. This is the start of such a class:

ShoppingList.java
1public class Main {
2 public static void main(String[] args) {
3 ShoppingList list = new ShoppingList();
4 list.addLast("eggs");
5 list.addLast("bread");
6 list.addFirst("milk");
7 list.addLast("jam");
8 list.print();
9 }
10}
11
12class ShoppingList {
13 Node head;
14
15 void addFirst(String value) {
16 Node node = new Node(value);
17 node.next = head;
18 head = node;
19 }
20
21 void addLast(String value) {
22 Node node = new Node(value);
23 if (head == null) {
24 head = node;
25 return;
26 }
27 Node current = head;
28 while (current.next != null) {
29 current = current.next;
30 }
31 current.next = node;
32 }
33
34 void print() {
35 for (Node current = head; current != null; current = current.next) {
36 System.out.print(current.value + " -> ");
37 }
38 System.out.println("null");
39 }
40}
41
42class Node {
43 String value;
44 Node next;
45
46 Node(String value) {
47 this.value = value;
48 }
49}
Prints
›milk -> eggs -> bread -> jam -> null

It prints milk -> eggs -> bread -> jam -> null. addFirst is the two lines from before, now working on the head field. addLast has more to do, because a new node goes after the last node, and finding the last node takes a walk. current starts at head and moves on while current.next != null, the loop from the Predict that stops on the last node instead of going past it. Then current.next = node hooks the new node on.

The first call, list.addLast("eggs"), runs on an empty list. head is null, there is no last node, and the if at the top of addLast handles that: the new node becomes the whole list. Step through the first call and watch it take that branch. Then watch the last call, list.addLast("jam"), walk from milk past eggs to bread before it hooks jam on. Every node gets the next tag as it is made (Node #1, Node #2 and so on), so you can follow each box as the arrows change, wherever the node was created.

Quick check
You delete the if block from addLast, so the method goes straight from Node current = head; into the loop. What happens when a program calls addLast on a new, empty ShoppingList?

Inserting after a value puts together the fixed find loop and the two linking lines:

InsertAfter.java
1public class Main {
2 public static void main(String[] args) {
3 ShoppingList list = new ShoppingList();
4 list.addFirst("bread");
5 list.addFirst("eggs");
6 list.addFirst("milk");
7
8 System.out.println(list.insertAfter("eggs", "jam"));
9 System.out.println(list.insertAfter("cake", "tea"));
10 list.print();
11 }
12}
13
14class ShoppingList {
15 Node head;
16
17 void addFirst(String value) {
18 Node node = new Node(value);
19 node.next = head;
20 head = node;
21 }
22
23 boolean insertAfter(String existing, String value) {
24 Node current = head;
25 while (current != null && !current.value.equals(existing)) {
26 current = current.next;
27 }
28 if (current == null) {
29 return false;
30 }
31 Node node = new Node(value);
32 node.next = current.next;
33 current.next = node;
34 return true;
35 }
36
37 void print() {
38 for (Node current = head; current != null; current = current.next) {
39 System.out.print(current.value + " -> ");
40 }
41 System.out.println("null");
42 }
43}
44
45class Node {
46 String value;
47 Node next;
48
49 Node(String value) {
50 this.value = value;
51 }
52}
Prints
›true
›false
›milk -> eggs -> jam -> bread -> null

It prints true, false, then milk -> eggs -> jam -> bread -> null. Because main adds bread, eggs and milk with addFirst, the one added last comes first. insertAfter walks until current is null or holds the value it is looking for. If current is null, the value is not in the list and the method returns false, as it did for cake. Otherwise current is the node to insert after, and the two lines from before do the rest, in the same order.

The lab below draws a list as boxes and arrows and runs these methods one reference change at a time, along with find and a remove method that the class does not have yet. Pick a node, then insert after it, delete it or find it. Delete the first node and the last one, search for a value that is not there, empty the list and fill it again, and tick the box to see the two linking lines run in the wrong order.

Linked list lab3 nodes · next value "jam"
Pick a node:
headmilkeggsbread

head → milk

milk, eggs and bread, linked by their next references. Pick an operation, and pick a node first for insert, delete and find.

Each box is a node: its value on the left, its next on the right. An arrow shows where next refers, and a slash means next is null. A faded, dashed box is lost: no walk from head can reach it.

The delete you just watched is the last method the class needs, and you have every piece of it: the case where the first node goes, the walk that stays one node behind, and the line that skips a node.

ExerciseRemove.java
Write remove so it deletes the first node that holds value and returns true, or returns false when no node holds it. The calls in main remove a node from the middle, the first node, the last node and a value that is not there; then the only node left, and finally from an empty list.

Doubly linked lists#

Every list so far has been singly linked: each node knows only the node after it. That makes some jobs awkward. A music player's previous button needs the song before the current one, and a singly linked node has no idea which node that is. Removing the last node has the same problem. The node before it has to become the new last node, and the only way to find it is to walk from head.

A doubly linked list gives every node a second reference, prev, to the node before it. The list keeps a second reference as well, tail, which refers to the last node the way head refers to the first. From either end you can start a walk, and from any node you can step either way.

Playlist.java
1public class Main {
2 public static void main(String[] args) {
3 Playlist songs = new Playlist();
4 songs.addLast("Intro");
5 songs.addLast("Waves");
6 songs.addLast("Echo");
7 songs.printBackwards();
8
9 System.out.println("Removed " + songs.removeLast());
10 System.out.println("Removed " + songs.removeLast());
11 songs.printBackwards();
12 }
13}
14
15class Playlist {
16 Node head;
17 Node tail;
18
19 void addLast(String value) {
20 Node node = new Node(value);
21 if (tail == null) {
22 head = node;
23 } else {
24 tail.next = node;
25 node.prev = tail;
26 }
27 tail = node;
28 }
29
30 String removeLast() {
31 if (tail == null) {
32 return null;
33 }
34 String value = tail.value;
35 tail = tail.prev;
36 if (tail == null) {
37 head = null;
38 } else {
39 tail.next = null;
40 }
41 return value;
42 }
43
44 void printBackwards() {
45 for (Node current = tail; current != null; current = current.prev) {
46 System.out.print(current.value + " ");
47 }
48 System.out.println();
49 }
50}
51
52class Node {
53 String value;
54 Node prev;
55 Node next;
56
57 Node(String value) {
58 this.value = value;
59 }
60}
Prints
›Echo Waves Intro
›Removed Echo
›Removed Waves
›Intro

It prints Echo Waves Intro, the list walked backwards from tail through the prev references. Then Removed Echo, Removed Waves and finally Intro, the one song left. addLast never walks: it hooks the new node onto tailin both directions, old tail's next to the new node and the new node's prev back to the old tail, then moves tail on. On an empty playlist there is no old tail, so the new node becomes head as well.

removeLast never walks either. tail.prev is the node before the last, so tail moves back to it, and setting its next to null cuts off the old last node. When that node was the only one, tail becomes null, and head is set to null too, so the playlist is empty. On an empty playlist the method returns null straight away instead of reaching through a null tail.

Removing from the front stays as quick as it was before: head moves on to head.next, and the new first node's prev is set to null. Both ends now take the same few steps, however long the playlist is.

The extra reference has a price. Each node holds one more field, and every change has more references to keep straight. Inserting a node in the middle of a doubly linked list changes four of them: the new node's prev and next, the next of the node before it and the prev of the node after it.

Singly linked
Doubly linked
Each node holds value and next.
Each node holds value, prev and next.
Walks forwards from head only.
Walks forwards from head or backwards from tail.
Removing the last node means walking to the node before it, even with a tail reference.
Removing the last node uses tail.prev, with no walk.
Deleting a node needs a reference to the node before it.
A node can be unlinked on its own, because its prev and next lead to both neighbours.
Two references change for an insert in the middle.
Four references change for an insert in the middle.

Java's LinkedList#

java.util.LinkedList is a doubly linked list. It has been in Java since version 1.2. Inside, it keeps a reference to its first node, a reference to its last node and a count of its nodes, and each node holds an element with prev and next references, like the Playlist above. It implements List, so it has positions like an ArrayList, and Deque, so it has the two-ended methods from stacks and queues.

Songs.java
1import java.util.LinkedList;
2
3public class Main {
4 public static void main(String[] args) {
5 LinkedList<String> songs = new LinkedList<>();
6 songs.add("Waves");
7 songs.addFirst("Intro");
8 songs.addLast("Echo");
9 songs.add(2, "Tides");
10 System.out.println(songs);
11
12 System.out.println(songs.get(2) + " is at index " + songs.indexOf("Tides"));
13 System.out.println("first " + songs.getFirst() + ", last " + songs.getLast());
14
15 songs.removeFirst();
16 songs.removeLast();
17 System.out.println(songs + ", size " + songs.size());
18
19 songs.push("Rain");
20 System.out.println(songs.peek() + " " + songs.pollLast() + " " + songs);
21 }
22}
Prints
›[Intro, Waves, Tides, Echo]
›Tides is at index 2
›first Intro, last Echo
›[Waves, Tides], size 2
›Rain Tides [Rain, Waves]

The first line is [Intro, Waves, Tides, Echo], built by add, addFirst, addLast and add(2, "Tides"). get(2) and indexOf("Tides") agree that Tides is at index 2, and getFirst and getLast read the two ends. After removeFirst and removeLast the list is [Waves, Tides], size 2. push and peek are the stack methods, working at the front, and pollLast takes from the back, so the last line is Rain Tides [Rain, Waves].

MethodsWhat they doWhat a LinkedList does inside
addFirst, addLast, add(x), push, offerAdd at an endChanges the references at that end.
removeFirst, removeLast, pollFirst, pollLast, pop, pollRemove at an endChanges the references at that end.
getFirst, getLast, peekFirst, peekLast, peekRead an endFollows its reference to the first or last node.
get(i), set(i, x)Read or replace position iWalks from whichever end is nearer to i.
add(i, x), remove(i)Insert or remove at position iWalks to position i, then changes the references there.
contains(x), indexOf(x), remove(x)Search by valueWalks from the first node, checking each one.
Based on the LinkedList description in the Java SE 25 API documentation and the OpenJDK source code.

Java's documentation says that operations which use an index walk the list from the beginning or the end, whichever is closer. So on a list of 1,000 elements, get(900) starts at the last node and steps back 99 times. That is still a walk, and a loop such as for (int i = 0; i < songs.size(); i++) with songs.get(i) inside starts a new walk on every pass. A for-each loop steps from each node to the next instead, so it is the way to visit every element of a LinkedList.

Declare the interface you use
Write List<String> songs = new LinkedList<>(); when the program uses positions, and Deque<String> songs = new LinkedList<>(); when it uses the two ends. Switching to ArrayList or ArrayDeque later then changes one word, as in the Collections Framework.

LinkedList or ArrayList?#

The two List classes make opposite trade-offs. This table puts them side by side:

JobArrayListLinkedList
Read or replace position i: get, setGoes straight to slot i.Walks from the nearer end.
Add or remove at the endUses the next free slot, and now and then copies everything into a bigger array.Changes the references at the last node.
Add or remove at the frontShifts every element one place.Changes the references at the first node.
Add or remove in the middleShifts every element after that position.Walks to the position, then changes a few references.
Visit every element in orderReads one array from start to end.Follows a reference to each node, wherever it sits in memory.
Memory for each elementOne slot in the backing array, plus spare slots.A whole node object, with its own bookkeeping and three references.
Based on the ArrayList and LinkedList descriptions in the Java SE 25 API documentation and the comparison of the two on dev.java.

Going by the table, LinkedList should win whenever a program adds or removes at the front or in the middle. In practice it rarely does, for two reasons.

The first is memory. Every node is a separate object, and each object carries some bookkeeping of its own besides its fields. In the measurements published on dev.java, a LinkedList node takes 24 bytes, while an ArrayList spends between 4 and 6 bytes per element on its backing array, spare slots included. A list of 1,000 elements came to a little more than 24 KB as a LinkedList and a little less than 5 KB as an ArrayList, not counting the elements themselves.

The second is the way processors read memory. Fetching from main memory is slow compared with the processor's own speed. To make fewer trips, the processor fetches a small block of neighbouring bytes at once and keeps recently used blocks in a small, fast memory called the cache. An ArrayList's references sit side by side in one array, and a walk through it finds most of them already in the cache. A linked list's nodes can be anywhere in memory, and each step to the next node may have to wait for main memory. Following references from object to object like this is called pointer chasing, and dev.java's benchmarks found that it makes walking a LinkedList much slower than walking an ArrayList.

Even an insert in the middle usually goes faster in an ArrayList. The LinkedList must walk to the position first, chasing a pointer at every step, while the ArrayListmoves the later elements with one fast copy of a block of memory. In dev.java's measurements, ArrayList won every kind of insert except at the very front. The same two reasons help explain why the ArrayDeque documentation says ArrayDeque is likely to be faster than LinkedList when used as a queue: an ArrayDeque keeps its elements in an array too.

Key idea

Use ArrayList for a list, and ArrayDeque for a stack, a queue or a deque. LinkedList is rarely the fastest choice for either job, even though its inserts look cheaper on paper.

LinkedList still has its uses. It is the one class here that is a List and a Deque at the same time, it accepts null elements where ArrayDeque refuses them, and its iterator can insert and remove nodes during a walk without shifting anything. When you do pick it, work at its two ends or walk it with a for-each loop or an iterator, and keep get(i) out of loops.

Quick check
A to-do app keeps tasks in order, lets the user jump straight to task number 40, and now and then adds a task at the end. Which class should hold the tasks?
Big-O gives these costs names
“Goes straight there” and “changes the references at that end” share the short name O(1), and “walks node by node” is O(n). How fast is it? Big-O in plain wordsexplains them, with a table of what each collection's operations cost, two lessons from now.

Try it

Answer each one in your head or on paper first, then open the answer.

1
The list is milk, eggs, bread. What do head.next.value and head.next.next.next print?
Open in playground
2
Why can an array jump straight to element 500, while a linked list cannot?
3
A new node is held in a variable tea. Write the two lines that add it to the front of the list that head refers to. What goes wrong if you swap them?
4
current refers to a node in a singly linked list. Which one line deletes the node after current? Why does the same line work when that node is the last one, and when does it throw?
5
In the Playlist, which references does removeLast change when the playlist holds three songs? What else changes when it holds one?
6
A LinkedList holds 1,000 elements. Where does get(900) start, and how many steps does it take? What about get(100)?

Practice

Work through these on your own. Each one builds on this page.

1
Give ShoppingList a size() method twice. First, walk the list and count. Then keep an int size field and update it in every method that adds or removes a node, as java.util.LinkedList does. Which version would you rather call inside a loop, and what goes wrong if one method forgets to update the field?
2
Write reverse() for ShoppingList. It turns milk -> eggs -> bread into bread -> eggs -> milk by changing the next references, without making any new node. Draw the three nodes on paper first and decide the order of the changes.
3
Add a tail field to ShoppingList so that addLast no longer walks. Update addFirst, addLast and remove so that tail always refers to the last node, including for an empty list and a list of one node. Then write removeLast, and explain why it still has to walk.
4
Find the middle node of a list in a single walk. Use two variables that start at head: one moves one node per pass and the other moves two. Where is the slow one when the fast one reaches the end? Test your method on lists of 1, 2, 3, 4 and 5 nodes, and on an empty list.

Further reading#

Spotted a mistake, or a part that did not make sense? Report it by email