Doubly linked, sorted and circular lists

Last week we saw two weak points of the singly linked list: deleting from the end is O(n), and deleting a node requires searching for the one before it. This week there are three variations. The doubly linked list adds a prev reference to each node and can go backward. The ordered list always keeps its elements from smallest to largest. The circular list links the last node back to the start. Exam questions are again tracing and method writing; this time there are more references to update, so there is more room for mistakes.

Golden rules:

1. In a doubly linked list every link is two-sided. If you did a.next = b, you must also do b.prev = a.
2. head and tail are candidates in every operation. Inserting into an empty list and deleting the last element change both.
3. Sorted insertion = find the right place + a normal insertion.
4. There is no null in a circular list. End the loop with “have I come back to the start”.

The doubly linked list

class DNode {
    int data;
    DNode prev, next;
    DNode(int d) { data = d; }
}

class DoublyLinkedList {
    DNode head, tail;
    int size;
}

head                               tail
 |                                  |
 v                                  v
[null|5|*] <-> [*|10|*] <-> [*|20|null]

Each node knows both directions. The cost: one extra reference of memory per node and twice as many reference updates in every operation.

Insertion

void addFirst(int x) {
    DNode n = new DNode(x);
    if (head == null) { head = tail = n; }
    else { n.next = head; head.prev = n; head = n; }
    size++;
}

void addLast(int x) {
    DNode n = new DNode(x);
    if (tail == null) { head = tail = n; }
    else { n.prev = tail; tail.next = n; tail = n; }
    size++;
}

void insertAfter(DNode p, int x) {
    if (p == tail) { addLast(x); return; }
    DNode n = new DNode(x);
    n.prev = p;          // 1
    n.next = p.next;     // 2
    p.next.prev = n;     // 3  (the right neighbour points back to n)
    p.next = n;          // 4  (last: we were still using p.next)
    size++;
}

Four references change when inserting in the middle. The order of 3 and 4 matters: if you do p.next = n first, p.next.prev now becomes the prev of n itself, and the right neighbour is not updated.

Deletion

If you already hold the node to be deleted, you don’t need to search for the one before it. This is the biggest advantage of a doubly linked list.

void removeNode(DNode p) {
    if (p.prev == null) head = p.next; else p.prev.next = p.next;
    if (p.next == null) tail = p.prev; else p.next.prev = p.prev;
    size--;
}

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

removeLast is now O(1). It was O(n) in a singly linked list.

Worked example

d.addLast(10); d.addLast(20); d.addLast(40); d.addFirst(5);
d.insertAfter(d.find(20), 30);
d.printForward(); d.printBackward();
d.removeNode(d.find(20));
System.out.println("removeLast=" + d.removeLast());
d.printForward(); d.printBackward();

5 10 20 30 40 
40 30 20 10 5 
removeLast=40
5 10 30 
30 10 5 

TIP · Print in both directions. The best way to test a doubly linked list method is to print both forward and backward. If it looks right forward but comes out different backward, you forgot a prev. On the exam, check the trace in both directions too.

The ordered linked list

The elements are always kept in ascending order. The user doesn’t say where to insert; the list finds the right place itself.

void insertSorted(int x) {
    Node n = new Node(x);
    if (head == null || x < head.data) {   // empty or the smallest → front
        n.next = head;
        head = n;
        return;
    }
    Node p = head;
    while (p.next != null && p.next.data <= x)
        p = p.next;                         // stop just before the first node greater than x
    n.next = p.next;
    p.next = n;
}

Let’s insert 5, 2, 8, 2, 6 in this order and print after each step:

5 
2 5 
2 5 8 
2 2 5 8 
2 2 5 6 8 

With <= an equal value goes after the existing ones; if you had written < it would go before them. Both give a sorted list, but it makes a difference if the question says “equal values go after”.

Searching in a sorted list

Since the list is sorted, you can stop the moment you pass the value you are looking for:

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

When searching for 7 in the list 2 2 5 6 8, 5 nodes are looked at (it stops at 8), and when searching for 1, a single node is looked at (2 > 1). The average case improves but the worst case is still O(n). You can’t do binary search on a linked list, because you can’t jump to the middle element in O(1).

The circular linked list

The next of the last node points to the first node instead of null. A practical trick: keep only the tail. The first node is always tail.next. That way you have O(1) access to both the front and the end.

          +-----------------------------+
          v                             |
 tail.next=[0] -> [1] -> [2] -> [3]=tail-+

void addFirst(int x) {
    Node n = new Node(x);
    if (tail == null) { tail = n; n.next = n; }   // a single node points to itself
    else { n.next = tail.next; tail.next = n; }
}

void addLast(int x) { addFirst(x); tail = tail.next; }   // add at the front, move the tail

int removeFirst() {
    Node first = tail.next;
    if (first == tail) tail = null;    // there was a single element
    else tail.next = first.next;
    return first.data;
}

void rotate() { if (tail != null) tail = tail.next; }   // the first element moves to the end

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

Note the addLast trick: adding at the front and moving the tail one step forward makes the new node the last. A worked example:

c.addLast(1); c.addLast(2); c.addLast(3); c.addFirst(0);
c.print();
c.rotate(); c.print();
System.out.println("removeFirst=" + c.removeFirst());
c.print();

0 1 2 3 
1 2 3 0 
removeFirst=1
2 3 0 

PITFALL · while (p != null) is an infinite loop in a circular list. No node’s next is null. Use do-while and stop when you come back to the start. If you start with while (p != tail.next) the loop never runs, because p already starts at tail.next.

Typical uses of a circular list: jobs that take turns (a round-robin scheduler), turns in a multiplayer game, and the Josephus problem (eliminating every k-th person in a circle).

Common mistakes

list.addFirst(2);
list.addLast(4);
list.addFirst(1);
list.addLast(6);
list.removeFirst();
list.addFirst(8);

DNode p = head.next;
System.out.println(p.prev.data + p.next.next.data);
System.out.println(tail.prev.prev.data);
p.next.data = p.prev.data * 10;
printForward();

int removeLast() {
    if (tail == null) throw new RuntimeException("empty list");
    int x = tail.data;
    tail = tail.prev;
    if (tail == null)      // there was a single element
        head = null;
    else
        tail.next = null;  // the new last node
    size--;
    return x;
}

void insertSorted(int x) {
    Node n = new Node(x);
    if (head == null || x < head.data) {
        n.next = head;
        head = n;
        return;
    }
    Node p = head;
    while (p.next != null && p.next.data <= x)
        p = p.next;
    n.next = p.next;
    p.next = n;
}

c.addLast(4);
c.addFirst(7);
c.addLast(9);
c.rotate();      // tail = tail.next
c.addFirst(1);
c.removeFirst();
c.rotate();
c.print();       // from tail.next around to tail

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

p.prev.next = p.next;
p.next.prev = p.prev;

if (p.prev == null) head = p.next;
else p.prev.next = p.next;
if (p.next == null) tail = p.prev;
else p.next.prev = p.prev;