Singly linked list

An array is a nice structure, but it has two troubles: its size is fixed in advance, and to insert an element in the middle you have to shift the others. A linked list solves both troubles. Each element sits in its own little box (node) and carries the address of the next box. The exam has two types of question: writing the final state of the list after a series of operations, and writing a method such as addLast, remove or countNodes from scratch.

Golden rules:

1. List = the head reference. If you lose the head, you lose the list.
2. Always traverse with p = p.next. The stopping condition is p != null (visit every node) or p.next != null (stop at the last node).
3. When inserting, first link the new node, then redirect the old one.
4. To delete, find the previous node. You can’t go backward in a singly linked list.
5. The empty list, the single-element list and the head are always special cases.

The Node class

A node carries two things: data and a reference to the next node (next). The next of the last node is null.

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; }   // next is automatically null
}

class SinglyLinkedList {
    Node head;   // first node; null in an empty list
    int size;
}

In memory the list 10 → 20 → 30 looks like this:

head
 |
 v
[10 | *]--->[20 | *]--->[30 | null]

Each box can sit in a different place in memory. This is the difference from an array: a[2] is computed directly, but to reach the third element of a list you have to start from the head and follow next twice. That is why access by index is O(n).

PITFALL · Node p = head; does not create a new node. It just creates a second arrow pointing to the existing node. If you do p.data = 99, the head’s data also becomes 99, because it is the same box.

Traversal

Printing the list, summing it, searching for an element: all the same pattern.

void print() {
    Node p = head;
    while (p != null) {
        System.out.print(p.data + " ");
        p = p.next;
    }
    System.out.println();
}

boolean contains(int x) {
    for (Node p = head; p != null; p = p.next)
        if (p.data == x) return true;
    return false;
}

Don’t advance head itself (head = head.next). After printing, the list would look empty. Always use a helper p.

Insertion

Inserting at the front (addFirst)

void addFirst(int x) {
    Node n = new Node(x);
    n.next = head;   // the new node points to the old first node
    head = n;        // head becomes the new node
    size++;
}

Two lines, no loop: O(1). It works on an empty list too (if head is null, n.next = null).

Inserting at the end (addLast)

If you have only head, you have to walk to the last node.

void addLast(int x) {
    Node n = new Node(x);
    if (head == null) { head = n; size++; return; }
    Node p = head;
    while (p.next != null) p = p.next;   // p is now the last node
    p.next = n;
    size++;
}

Time O(n). If you add a tail reference to the class it becomes O(1) with tail.next = n; tail = n;, but then you also have to update the tail on every deletion.

Inserting in the middle (insertAt)

To insert at position index, go to the node at position index - 1.

void insertAt(int index, int x) {   // 0 = front
    if (index == 0) { addFirst(x); return; }
    Node p = head;
    for (int i = 0; i < index - 1; i++) p = p.next;
    Node n = new Node(x);
    n.next = p.next;   // 1) the new node points to p's old next
    p.next = n;        // 2) p points to the new node
    size++;
}

Before: p=[20] ---> [30]
1)      [25] ---> [30]   (n.next = p.next)
2)      [20] ---> [25] ---> [30]   (p.next = n)

PITFALL · The order of the lines. If you write p.next = n; first, the old value of p.next (30) is lost. Then n.next = p.next; actually becomes n.next = n. The node points to itself, and the list enters an infinite loop.

Deletion

Deleting from the front

int removeFirst() {
    if (head == null) throw new RuntimeException("empty list");
    int x = head.data;
    head = head.next;
    size--;
    return x;
}

Nobody points to the old first node any more, and Java’s garbage collector cleans it up. O(1).

Deleting from the end

To delete the last node you must set the next of the node before the last to null.

int removeLast() {
    if (head == null) throw new RuntimeException("empty list");
    if (head.next == null) {            // single element
        int x = head.data; head = null; size--; return x;
    }
    Node p = head;
    while (p.next.next != null) p = p.next;   // p = the node before the last
    int x = p.next.data;
    p.next = null;
    size--;
    return x;
}

Even with a tail reference this is O(n). The tail gives you the last node but not the one before it.

Deleting by value

boolean remove(int x) {
    if (head == null) return false;
    if (head.data == x) { head = head.next; size--; return true; }
    Node p = head;
    while (p.next != null && p.next.data != x) p = p.next;
    if (p.next == null) return false;
    p.next = p.next.next;   // skip the target
    size--;
    return true;
}

The order of the loop condition matters: p.next != null is checked first, so p.next.data is not called on null (&& short-circuits).

Worked example: an operation trace

Start with an empty list and write the list at each step:

list.addFirst(20);
list.addFirst(10);
list.addLast(30);
list.addLast(40);
list.print();
list.insertAt(2, 25);
list.print();
System.out.println("removeFirst=" + list.removeFirst());
System.out.println("removeLast=" + list.removeLast());
list.print();
System.out.println(list.remove(25) + " " + list.remove(99));
list.print();

10 20 30 40 
10 20 25 30 40 
removeFirst=10
removeLast=40
20 25 30 
true false
20 30 

addFirst(20)   [20]
addFirst(10)   [10, 20]
addLast(30)    [10, 20, 30]
addLast(40)    [10, 20, 30, 40]
insertAt(2,25) [10, 20, 25, 30, 40]   (after the 20 at index 1)
removeFirst    [20, 25, 30, 40]   returns 10
removeLast     [20, 25, 30]       returns 40
remove(25)     [20, 30]           true
remove(99)     [20, 30]           false, unchanged

On the exam, draw this table yourself. Writing the whole list at each row prevents mistakes.

Complexity summary

Common mistakes

list.addFirst(3);
list.addFirst(7);
list.addLast(5);
list.addFirst(1);
list.print();

list.addLast(4);
list.addLast(8);
list.addFirst(2);
list.addLast(6);
list.removeFirst();
list.addFirst(9);
list.removeLast();
list.print();

Node a = new Node(1);
a.next = new Node(2);
a.next.next = new Node(3);
a.next.next.next = new Node(4);
a.next = a.next.next;
for (Node p = a; p != null; p = p.next)
    System.out.print(p.data + " ");

Node h = new Node(5);
h.next = new Node(10);
h.next.next = new Node(15);
Node t = h.next;
t.next.data = t.data + h.data;
h.data = t.next.data * 2;
for (Node p = h; p != null; p = p.next)
    System.out.print(p.data + " ");

list.insertAt(1, 9);
list.insertAt(4, 7);
list.insertAt(0, 5);
list.print();
list.remove(2);
list.remove(5);
list.print();

int countNodes() {
    int c = 0;
    Node p = head;
    while (p != null) {
        c++;
        p = p.next;
    }
    return c;
}

void addLast(int x) {
    Node n = new Node(x);
    if (head == null) {
        head = n;
        return;
    }
    Node p = head;
    while (p.next != null)
        p = p.next;
    p.next = n;
}

boolean remove(int x) {
    if (head == null) return false;
    if (head.data == x) {
        head = head.next;
        return true;
    }
    Node p = head;
    while (p.next != null && p.next.data != x)
        p = p.next;
    if (p.next == null) return false;   // not found
    p.next = p.next.next;               // skip it
    return true;
}

p.next = n;
n.next = p.next;

for (Node p = head; p != null; p = p.next.next)
    System.out.print(p.data + " ");

int mx = head.data, cnt = 0;
for (Node r = head; r != null; r = r.next) {
    if (r.data > mx) mx = r.data;
    if (r.data % 2 == 1) cnt++;
}
System.out.println(mx + " " + cnt);