3.2 Insertion and Removal | Code Scholars Tutoring

How it works

Once positioned, inserting or removing costs constant time because only a couple of references change. Getting positioned is the expensive part.

Write reassignments in an order that attaches the new node before detaching the old link.

Common error

Overwriting the reference you still need, which silently drops the tail of the list.

Worked example

Java snippets run inside a main method. Add import java.util.*; when collection types are used.

Java

class Node {
    int value; Node next;
    Node(int v, Node n) { value = v; next = n; }
}
Node head = new Node(2, new Node(5, null));
head = new Node(1, head);
head.next = head.next.next;
System.out.println(head.value + ":" + head.next.value);

Output

1:5

Prepending changes the head reference. The later reassignment bypasses the old node containing 2. Reference changes must preserve access to the rest of the chain.

Exercises

3.2.1 · Explain

If p refers to the predecessor of a node to remove, what reassignment bypasses that node in a singly linked list?

Show solution

When p and p.next are non-null, use p.next = p.next.next. Removing the head instead requires updating head.

3.2.2 · Write code

Build the singly linked chain 2 -> 5 -> 8, remove its head, and print the remaining values.

Show solution

Removing the head requires assigning the head reference to its successor.

One valid solution

class Node {
    int value; Node next;
    Node(int v, Node n) { value = v; next = n; }
}
Node head = new Node(2, new Node(5, new Node(8, null)));
head = head.next;
for (Node p = head; p != null; p = p.next)
    System.out.print(p.value + " ");

Expected output

5 8

Open Java compiler