Java singly linked lists

Before you start

Java classes and references.

Build a list of nodes by hand, insert at the front and the back, and reverse it.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

A singly linked list stores each item in a node that holds a value and a reference to the next node. The list keeps a reference to the first node, called the head. Inserting at the front is O(1): create a node whose next is the old head and make it the new head. Appending at the end is O(n) unless the list also keeps a tail reference.

Reversing the list walks through it once and flips each next reference. Three references are needed: the previous node, the current node, and the next node, saved before the link is changed. Lists give constant-time insertion at a known position and no shifting, but they have no fast indexing and use extra memory per element.

Code example

Java

class Main {
  static class Node {
    int value;
    Node next;

    Node(int value, Node next) {
      this.value = value;
      this.next = next;
    }
  }

  static Node head = null;

  static void addFirst(int value) {
    head = new Node(value, head);
  }

  static void addLast(int value) {
    Node node = new Node(value, null);
    if (head == null) {
      head = node;
      return;
    }
    Node current = head;
    while (current.next != null) {
      current = current.next;
    }
    current.next = node;
  }

  static void reverse() {
    Node previous = null;
    Node current = head;
    while (current != null) {
      Node next = current.next;
      current.next = previous;
      previous = current;
      current = next;
    }
    head = previous;
  }

  static String show() {
    StringBuilder sb = new StringBuilder();
    for (Node n = head; n != null; n = n.next) {
      sb.append(n.value).append(n.next == null ? "" : " -> ");
    }
    return sb.toString();
  }

  public static void main(String[] args) {
    addFirst(2);
    addFirst(1);
    addLast(3);
    addLast(4);
    System.out.println(show());
    reverse();
    System.out.println(show());
  }
}

Output

1 -> 2 -> 3 -> 4
4 -> 3 -> 2 -> 1

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1class Main {

2 static class Node {

3 int value;

4 Node next;

6 Node(int value, Node next) {

7 this.value = value;

8 this.next = next;

9 }

10 }

12 static Node head = null;

14 static void addFirst(int value) {

15 head = new Node(value, head);

16 }

18 static void addLast(int value) {

19 Node node = new Node(value, null);

20 if (head == null) {

21 head = node;

22 return;

23 }

24 Node current = head;

25 while (current.next != null) {

26 current = current.next;

27 }

28 current.next = node;

29 }

31 static void reverse() {

32 Node previous = null;

33 Node current = head;

34 while (current != null) {

35 Node next = current.next;

36 current.next = previous;

37 previous = current;

38 current = next;

39 }

40 head = previous;

41 }

43 static String show() {

44 StringBuilder sb = new StringBuilder();

45 for (Node n = head; n != null; n = n.next) {

46 sb.append(n.value).append(n.next == null ? "" : " -> ");

47 }

48 return sb.toString();

49 }

51 public static void main(String[] args) {

52 addFirst(2);

53 addFirst(1);

54 addLast(3);

55 addLast(4);

56 System.out.println(show());

57 reverse();

58 System.out.println(show());

59 }

60}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
The new node points to the old head and becomes the head: O(1).	`—`	—
To append, walk to the last node: O(n).	`—`	—
Reversal flips the link of the current node to point backwards.	`—`	—
After addFirst(2), addFirst(1), addLast(3), addLast(4) the list is 1, 2, 3, 4.	`—`	1 -> 2 -> 3 -> 4
When the loop ends, previous is the old last node, which is the new head.	`—`	1 -> 2 -> 3 -> 4
The same nodes now appear in the reverse order.	`—`	1 -> 2 -> 3 -> 4 4 -> 3 -> 2 -> 1

Behind the scenes

How Java processes this code

The Java compiler produces bytecode. The JVM loads the class and invokes its main method.

Cost and common mistakes

addFirst O(1), addLast O(n), reverse O(n) time and O(1) extra space.

Always save current.next before overwriting it, or the rest of the list is lost.
Forgetting to handle the empty list (head == null) causes a NullPointerException.
In practice use java.util.LinkedList or ArrayList. Writing a list by hand is for learning how they work.

Try it yourself

How would you add a tail reference to make addLast O(1)?

Reveal answer and reasoning

Keep a Node tail field; addLast sets tail.next = node and tail = node, with a special case for an empty list.