Data Structures · Lecture Notes

Chapter 5: Linked Lists

An array keeps its elements side by side in memory, which makes indexing fast but forces elements to shift whenever something is inserted at the front or in the middle. A linked list stores them differently: each element sits in its own small box, a node, which knows where the next node is. The links, not memory positions, define the order. We start with nodes, then cover traversal, search, insertion, and deletion in a singly linked list, with code and step-by-step traces, followed by classic problems: reversal, the middle element, copying, removing duplicates, merging sorted lists, and sorting. Doubly linked lists, sentinel nodes, and circular lists come next, and the last section weighs arrays against linked lists and collects the costs.

Learning outcomes

Node structure
Explain nodes, links, and references; draw the linked structure that results from a sequence of assignments.
Basic operations
Implement insertion, deletion, search, and traversal in singly, doubly, and circularly linked lists, setting links in the right order.
Kinds of lists
Compare singly, doubly, and circularly linked lists; explain what sentinel nodes and a tail pointer make easier.
Cost analysis
State and justify the time and space cost of linked list operations, and compare it with the cost of the same operation on an array.

5.1Fundamentals

A program rarely knows in advance how many elements it will hold — how many customers will join a queue, how many lines a user will type, how many objects a game will put on screen. Arrays cope poorly: their capacity is fixed, a full array must be copied into a bigger one, and every insertion at the front or in the middle shifts everything behind it. Linked lists remove both problems, at a price spelled out at the end of this section.

5.1.1Linked lists and their kinds

Think of a treasure hunt. The first clue says where the second is hidden, the second says where the third is, and so on. The slips are scattered around the house — in a drawer, inside a book, behind a door — yet the order never gets mixed up, because each one points to the next. To play, you only need to know where the first slip is.

A linked list works the same way. Its elements are not in adjacent cells; each is stored in a separate object, a node, along with the location of the next node. The slip is the node; the address on it is the link.

Definition 5.1

A linked list is a linear data structure that stores its elements in nodes connected by references. The order of the elements is set by the links, not by where the nodes sit in memory. The first node is the head of the list, the last node its tail.

There are three basic kinds, shown side by side in Figure 5.1.

  • Singly linked list: each node points only to its successor. The last node's link is empty, written null in Java. The list can be walked only from front to back.
  • Doubly linked list: each node points to both neighbors, so the list can be walked either way. The first node's previous link and the last node's next link are null.
  • Circularly linked list: the last node points back to the first instead of to null, so the list is a ring with no empty link.
1081null
1081nullnull
1081
Figure 5.1: The three kinds of linked list, each holding 10, 8, 1. Top, singly linked: arrows go only forward, and the last node points to null. Middle, doubly linked: each pair of neighbors has a forward and a backward arrow, with null at both ends. Bottom, circular: the last node's link returns to the first.

All three keep elements in nodes that point to one another; they differ only in how many links a node holds and where the last link points. Those small differences can change costs dramatically: removing the last node means walking the whole singly linked list, but takes constant time in a doubly linked one.

5.1.2The singly linked list

The simplest kind is the singly linked list, where each element holds a one-way link to the next. A reference is a value that tells where an object is in memory; in Java, every variable of a class type is a reference, holding the way to an object rather than the object itself.

The whole list is reached through one variable pointing to the first node, the head, written head in code. Starting there and following the links reaches every node. For an empty list, head is null.

Each node has two parts:

  • Data: the value the node carries — a primitive such as an integer, or an object such as a student record.
  • Pointer: a reference to the next node, null in the last node. In Java “pointer” and “reference” mean the same thing; there is no pointer arithmetic as in C.
10811115nullheaddatanext
Figure 5.2: A singly linked list. The left part of each box holds the node's data (data), the right part the link to the next node (next). head points to the first node (10); the chain runs 10 → 8 → 1 → 11 → 15 and ends in null.

Two things in Figure 5.2 deserve attention. First, head is not a node, just a variable pointing to one. Second, nothing separate marks the end: the list ends at the node whose next field is null, and that field is how a program knows it has reached the last node.

Common mistake

Confusing head with the first element. head holds the way to the node, not the node. Redirect it elsewhere and the only path to the old first node may be lost; if nothing else refers to that node, it and everything after it are cut off from the program.

5.1.3Where nodes live in memory

An array stores its elements contiguously, so finding element i takes one multiplication and one addition. A linked list allows no such computation. Each node is created separately with new, and Java's memory manager puts it wherever there is room; two nodes created in succession may land side by side or far apart.

A linked list is still linear: every element but the last has exactly one successor. A tree node may have several children; a list node has at most one next node. The references in the next fields, not memory positions, set the order.

103F8address 1A085B0address 2C412C4address 3F811nulladdress 5B0memory (address order)head = 1A0
Figure 5.3: Nodes in memory, drawn in address order: 10 at 1A0, 8 at 2C4, 1 at 3F8, 11 at 5B0. Each node's right part holds the address of the next node. Starting at head = 1A0 and following the arrows gives 10 → 1 → 8 → 11, not the address order 10, 8, 1, 11.

Figure 5.3 makes this concrete. The hexadecimal addresses are invented; Java programs never see real ones. The point is that the arrows ignore memory order: 10's node points to 3F8, the node of 1, which points back to 8 at 2C4, which points to 11 at 5B0, whose link is null. In memory 8 precedes 1; in the list it follows.

This has one good consequence and one bad one. Inserting in the middle shifts nothing; only a few links change. But you cannot jump to element i: with no address to compute, you start at the head and follow links one by one. These two facts determine the cost of every linked list operation.

5.1.4The Node class

In Java a node is a small class. Here is one that holds an integer:

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

The class has two fields: data, the integer the node carries, and next, whose type is again Node. A class with a field of its own type is a self-referential structure. The definition looks circular — a node containing a node containing a node — but next holds a reference to a node, not a node. References have a fixed size, so apart from its object header a Node occupies just one integer and one reference.

The constructor stores the value in data and sets next to null. Java initializes reference fields to null anyway; the line just states the intent. A new node is attached to nothing until someone stores its reference in another node's next field or in head.

A generic version stores data of any type:

// Node class
class Node<T> {
    T data;
    Node<T> next;
    Node(T data) {
        this.data = data;
        this.next = null;
    }
}

T is a type parameter: after Node<String> n = new Node<>("Ann");, T is String and the node stores text. For simplicity these notes use the integer version, but every algorithm works unchanged with the generic one, except that objects are compared with equals and compareTo instead of == and <.

Common mistake

Comparing values in a generic node with ==, which asks whether two references point to the same object, not whether the values are equal. Two distinct String objects with the same text can give false. A search in a generic list should test temp.data.equals(target).

5.1.5Building a list by hand

The clearest way to see how a list is built is to create nodes and link them by hand. This code links four nodes in the order 10 → 1 → 8 → 11:

Node first = new Node(10);
Node second = new Node(1);
Node third = new Node(8);
Node fourth = new Node(11);
first.next = second;
second.next = third;
third.next = fourth;

The first four lines create four independent nodes; every next field is null, and each node is reachable only through its own variable (first, second, third, fourth). The last three lines build the links. first.next = second copies the reference in second into the next field of 10's node, which now points to 1's node.

Table 5.1: Trace of the list-building code: each node's next field, and the chain reachable from first, after each line.
Line10.next1.next8.next11.nextChain from first
first = new Node(10)null———10
second = new Node(1)nullnull——10
third = new Node(8)nullnullnull—10
fourth = new Node(11)nullnullnullnull10
first.next = secondnode(1)nullnullnull10 → 1
second.next = thirdnode(1)node(8)nullnull10 → 1 → 8
third.next = fourthnode(1)node(8)node(11)null10 → 1 → 8 → 11
101811nullfirstsecondthirdfourth
101811nullfirstsecondthirdfourth
101811nullfirstsecondthirdfourth
Figure 5.4: Building the list, top to bottom. (a) Four independent nodes with empty next fields (the slash means null). (b) first.next = second: the first link, 10 to 1, is in place (orange arrow). (c) All three links done: 10 → 1 → 8 → 11 → null.

The example shows a fact to keep in mind with linked lists: assignment copies the reference, never the object. After first.next = second, 1's node is reachable both through second and through first.next — one node, two paths. Once all links are set, the helper variables are unnecessary: the whole list is reachable from first, and first.next.next.data is 8.

Real programs call insertion methods instead of linking by hand, but each such method does exactly this inside: create a node and change a few reference fields.

5.1.6Basic operations and their costs

The table summarizes the operations and their costs; each operation's own section justifies them. n is the number of nodes.

Table 5.2: Basic operations on a singly linked list.
OperationHow it worksTime
Insert at frontThe new node points to the old head and becomes the head.O(1)
Insert at endWalk to the last node; with a tail pointer, no walk is needed.O(n) · O(1)
Remove from frontMove the head to the next node.O(1)
Remove from endThe second-to-last node must be found.O(n)
Search, print, lengthWalk from front to back.O(n)
Reverse, mergeOne pass over the lists (merging uses a tail pointer).O(n)

One rule explains Table 5.2: an operation that touches only nodes near the head is constant time; one that must walk into the list is linear. The head is always known, so work there takes the same few steps however long the list is. The last node can be found only by following every link, so operations at the end are O(n) unless something like a tail pointer helps.

Accessing element i is O(n) too. An array reads a[i] in one step; a linked list starts at the head and follows i links — n − 1 of them, in the worst case, for the last node.

Common mistake

Looping over a linked list by index: for (int i = 0; i < n; i++) process(list.get(i));. Each get(i) walks i steps from the head, for a total of 0 + 1 + … + (n − 1) = n(n − 1)/2, or O(n2). The traversal pattern of the next section does the job in one O(n) pass.

5.1.7The list ADT and a Java class

A description of a data structure's operations, independent of their implementation, is an abstract data type (ADT). Goodrich, Tamassia, and Goldwasser define a small ADT for the singly linked list: size, emptiness test, first and last element, insertion at the front and the end, and removal from the front. We use the same names. The class skeleton:

public class SinglyLinkedList {
    private Node head = null, tail = null;
    private int size = 0;    // number of elements
    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }
    public Integer first() {
        return isEmpty() ? null : head.data; }
      // addFirst, addLast, removeFirst …
}

Three fields: head points to the first node, tail to the last, and size counts the elements. All are private, so outside code must go through the methods, and keeping head, tail, and size true to the list's real state is the class's own job.

size() and isEmpty() only read size, so both are O(1). first() returns null for an empty list and the front value otherwise; that is why it returns Integer, which can be null, rather than int, which cannot.

list objectsize = 3tailhead1081null
Figure 5.5: A SinglyLinkedList object. The dashed box is the list object, with fields size = 3, head (pointing to 10), and tail (pointing to 1). The nodes live outside it; the object reaches them only through the two references.
Table 5.3: The textbook's ADT operations and how these notes implement them.
Goodrich–TamassiaIn these notesRoleTime
size(), isEmpty()size(), isEmpty()the size field is updated by every operationO(1)
first(), last()first(), isEmpty() ? null : tail.datareturn null on an empty listO(1)
addFirst, addLastaddFirst, addLastboth constant time with a tail pointer; inserting into an empty list also sets tailO(1)
removeFirst()removeFirst()returns the removed nodeO(1)

Every operation in Table 5.3 is constant time, provided every method that changes the list keeps head, tail, and size up to date together: insertions increment size, removals decrement it, the first node added to an empty list becomes both head and tail, and emptying a one-node list resets tail to null. Front insertion, end insertion with a tail pointer, and the removal methods do this. Only the walking version of end insertion ignores these fields, since it models the plain list without a tail pointer.

Common mistake

Keeping a size field but not updating it everywhere. If removals do size-- but one insertion method skips size++, the counter drifts; after two insertions and a removal, size() may even return −1, and isEmpty(), which tests size == 0, goes wrong too. Either every modifying method updates the counter, or the length is counted each time.

5.1.8Strengths and weaknesses

Both the strengths and the weaknesses come from nodes holding on to each other by links. The strengths:

  • It is easy to implement. A node class and a head reference are all it takes.
  • Inserting and removing at the front are O(1). On an array both shift every element: O(n).
  • Inserting in the middle shifts nothing. The new node slips in by changing two links.
  • Its size is dynamic. No capacity is reserved; each insertion does one new. The list never fills up, and nothing is resized or copied.

The weaknesses come from the same structure:

  • Search is slow. Membership is decided only by checking nodes one by one: O(n). Even a sorted list rules out binary search, since there is no jumping to the middle node.
  • There is no random access. Reaching element i means walking from the head.
  • It uses extra memory. Each node carries a reference besides its data — proportionally a heavy cost for small data: a single int also needs a reference and an object header.
  • It cannot be walked backward. To find a node's predecessor, you start over from the head.

The O(1) cost of inserting or removing in the middle comes with a condition: the position — more precisely, the node before it — must already be known. Given only an index or a value, you first walk there, in O(n). Claiming linked list insertion is O(1) without counting the walk is misleading.

Common mistake

Concluding that, since middle insertion is O(1) in a linked list and O(n) in an array, the linked list is always faster. Finding the middle is O(n) in a linked list too. The real gain comes from many insertions or removals in a row at one place: the position is found once and each operation after that is constant time, while an array shifts again every time.

5.2Singly linked lists: traversal and insertion

Most linked list operations combine two moves: walking the list from front to back, and changing a few links in the right order. We start with traversal — length and search are small variations of it — and then cover insertion at the front, at the end, and at a given position. Most examples use 10 → 1 → 8 → 11.

5.2.1Traversing and printing

Visiting every node of a list in order is called traversal. Printing is the simplest example: at each node, print its data.

void printList() {
    Node temp = head;
    System.out.print("Linked List: ");
    while (temp != null) {
        System.out.print(temp.data + " -> ");
        temp = temp.next;
    }
    System.out.println("null");
}

The method uses a local variable temp, first pointed at the node head refers to. While temp refers to a node, the loop prints its data and moves on with temp = temp.next. After the last node, temp takes that node's next value, null, and the loop ends; a final null marks the end of the list.

Note that head never changes. Only temp moves, and it vanishes when the method returns, leaving the list as it was.

Table 5.4: Trace of printList() on the list 10 → 1 → 8 → 11.
SteptempCondition temp != nullPrinted in this step
temp = headnode(10)—Linked List:
iteration 1node(10) → node(1)true10 ->
iteration 2node(1) → node(8)true1 ->
iteration 3node(8) → node(11)true8 ->
iteration 4node(11) → nulltrue11 ->
loop endsnullfalsenull

The output is Linked List: 10 -> 1 -> 8 -> 11 -> null. The body runs four times and the condition is tested five times. For n nodes the loop runs n times with constant work each, so the time is O(n) and the extra memory O(1).

101811nullheadtemp
101811nullheadtemp
101811nullheadtemp
Figure 5.6: Three moments in the traversal. (a) temp = head: both point to 10. (b) After the first iteration temp is at 1; head stays put. (c) In the last iteration temp takes 11's next, null, and the loop ends.
Common mistake

Advancing head instead of a local variable: while (head != null) { …; head = head.next; }. Afterward head is null, the only path to the nodes is gone, and the list is effectively deleted; a second print shows only null. Always traverse with a copy, such as Node temp = head;.

5.2.2The same pattern: length and search

The print method's skeleton recurs constantly. Call it the traversal pattern: start with temp = head; while temp != null, process the node; advance with temp = temp.next. Only the loop body changes. To find the length, the body increments a counter:

int listLength() {
    int count = 0;
    Node temp = head;
    while (temp != null) {
        count++;
        temp = temp.next;
    }
    return count;
}

The counter starts at zero and grows by one per node. An empty list skips the loop and returns 0 with no special case. The time is O(n). If the length is needed often, the list keeps a size field, updated on every insertion and removal, and answers in O(1) — at the price that every modifying method must maintain it.

Search uses the same pattern; the body compares the node's data with the target:

int search(int target) {
    Node temp = head;
    int position = 0;
    while (temp != null) {
        if (temp.data == target)
            return position;
        position++;
        temp = temp.next;
    }
    return -1;   // not found
}

The counter position starts at 0 and follows temp node by node. When the target is found, its position is returned at once. If the loop ends without a match, the method returns −1, a safe “not found” because it is never a valid index.

The cost depends on where the target is: at the head, one comparison (best case O(1)); at the end or absent, all n nodes (worst case O(n)); at a random place, about n/2 on average, still O(n).

5.2.3Code trace: search(8)

We search the list 10 → 1 → 8 → 11 for 8, which sits in the third node.

Example 5.1
  1. Start. temp = head, that is, node(10); position = 0.
  2. Iteration 1. temp is not null, so the loop is entered. 10 == 8 is false. position becomes 1 and temp moves to node(1).
  3. Iteration 2. 1 == 8 is false. position becomes 2 and temp moves to node(8).
  4. Iteration 3. 8 == 8 is true. The method executes return position and returns 2.

Three nodes, three comparisons. search(5) on the same list would check all four nodes, end the loop when temp became null, and return −1.

Table 5.5: Trace of search(8). Each row shows the values just before that iteration's comparison.
Iterationtemppositiontemp.data == 8Result
1node(10)0falseadvance
2node(1)1falseadvance
3node(8)2truereturn 2
101811nullheadtemp
101811nullheadtemp
Figure 5.7: The last two moments of search(8). (a) With position at 2, temp moves to node(8). (b) The comparison succeeds; 8 is at position 2.
Common mistake

Putting position++ before the if. The counter is then one ahead at the comparison, and 8 is reported at 3. Increment it after checking the node, on the way to the next one.

5.2.4Inserting at the front

Adding an element at the front is one of the fastest things a linked list can do:

void addFirst(int data) {
    Node newNode = new Node(data);
    newNode.next = head;
    head = newNode;
    if (tail == null) tail = head;
    size++;
}

The first line creates the node, with next set to null. The second copies head into the new node's next, so it points to the current first node. The third points head at the new node; the list now starts there, and the old nodes are reached through it.

The last two lines maintain the other fields. A node added to an empty list is also the last node, and since tail is still null, if (tail == null) tail = head; points it there. Otherwise tail is unaffected. size++ counts the new element.

The order is the essence of the operation: attach the new node to the old list first, then move the head. It works for an empty list too — head is null, so the new node's next gets null and a one-node list results; the only extra step is setting tail.

Table 5.6: Trace of addFirst(11), addFirst(8), addFirst(1) on an empty list.
CallLinenewNodeheadtailsizeList
addFirst(11)new Node(11)11 → nullnullnull0empty
newNode.next = head11 → nullnullnull0empty
head = newNode11node(11)null011 → null
tail = head; size++11node(11)node(11)111 → null
addFirst(8)new Node(8)8 → nullnode(11)node(11)111 → null
newNode.next = head8 → 11node(11)node(11)111 → null
head = newNode8node(8)node(11)18 → 11 → null
tail unchanged; size++8node(8)node(11)28 → 11 → null
addFirst(1)new Node(1)1 → nullnode(8)node(11)28 → 11 → null
newNode.next = head1 → 8node(8)node(11)28 → 11 → null
head = newNode1node(1)node(11)21 → 8 → 11 → null
tail unchanged; size++1node(1)node(11)31 → 8 → 11 → null

Table 5.6 shows something else: the elements went in as 11, 8, 1, but the list reads 1 → 8 → 11. Repeated front insertion reverses the order, just like a stack, where the newest element is in front.

11nullhead, tailnewNode
1181nullheadnewNodetail
1181nullheadnewNodetail
1181nullheadnewNodetail
Figure 5.8: Front insertion in four moments. (a) After addFirst(11) on an empty list, 11 is head and tail. (b) addFirst(1): node 1 is created, attached to nothing; tail is at 11. (c) newNode.next = head: 1 points to the old head, 8. (d) head = newNode: the list is 1 → 8 → 11 → null.

Whatever the length, front insertion is one object creation, two assignments, a comparison, and an increment. No node is visited and nothing shifts: O(1) time and O(1) extra memory. On an array, every element shifts right: O(n).

Common mistake

Reversing the lines: head = newNode;, then newNode.next = head;. By then head is the new node, so the node ends up pointing to itself. The only reference to the old list is lost, and a traversal never ends, returning to the same node forever.

5.2.5Inserting at the end

With only head, appending costs more: the new node must hang off the last node, which we first have to find:

void addLast(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        return;
    }
    Node temp = head;
    while (temp.next != null)
        temp = temp.next;
    temp.next = newNode;
}

An empty list has nothing to walk; the new node becomes the head. Otherwise temp starts at the head and advances while temp.next != null, that is, while it has a successor, so it stops on the last node, and the final line links the new node there.

The two conditions differ in an important way. temp != null carries temp past the last node to null, leaving nothing to link from; temp.next != null stops one step earlier. Whenever the work is at the last node, use the second.

Table 5.7: Trace of addLast(10), addLast(1), addLast(8) on an empty list.
CallBranchNodes visited by tempLink setList
addLast(10)head == null—head = node(10)10 → null
addLast(1)walk10 (next is null, stop)10.next = node(1)10 → 1 → null
addLast(8)walk10 → 1 (next is null, stop)1.next = node(8)10 → 1 → 8 → null
1018nullheadnewNodetemp
1018nullheadnewNodetemp
1018nullheadnewNodetemp
Figure 5.9: addLast(8) in three moments. (a) temp = head: the search for the last node starts at the head. (b) temp is at node(1), whose next is null: the loop ends. (c) temp.next = newNode: the list is 10 → 1 → 8 → null.

The walk costs n − 1 iterations: O(n). Fine for one call, but n appends to an empty list take 0 + 1 + … + (n − 1) = n(n − 1)/2 steps, O(n2) — about 500,000 for 1,000 elements. A tail pointer removes this cost.

5.2.6Inserting at the end with a tail pointer

The fix: keep the last node in a field too, the tail pointer, written tail. No walk is needed:

class SinglyLinkedList {
    Node head, tail;  int size;
    void addLast(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }
}

In an empty list the new node is both head and tail: head = tail = newNode (Java assigns right to left, tail first). Otherwise tail.next = newNode links it after the old last node and tail = newNode moves the pointer. Either way, size++ follows.

11815nullheadtailold tail
Figure 5.10: A list with head and tail pointers. Appending 5 to 11 → 8 → 1: the old tail (1) points to the new node (highlighted link), and tail is now 5. No node was visited.
Table 5.8: Trace of addLast(10), addLast(1), addLast(8) with tail.
CallLineheadtailsizeList
addLast(10)head = tail = newNodenode(10)node(10)010 → null
size++node(10)node(10)110 → null
addLast(1)tail.next = newNodenode(10)node(10)110 → 1 → null
tail = newNodenode(10)node(1)110 → 1 → null
size++node(10)node(1)210 → 1 → null
addLast(8)tail.next = newNodenode(10)node(1)210 → 1 → 8 → null
tail = newNodenode(10)node(8)210 → 1 → 8 → null
size++node(10)node(8)310 → 1 → 8 → null
1018nullheadtailnewNode
1018nullheadtailnewNode
1018nullheadtailnewNode
Figure 5.11: addLast(8) with tail. (a) The last node, node(1), is already known. (b) tail.next = newNode: the link 1 → 8 is set. (c) tail = newNode: the tail pointer moves to 8.

Each call in Table 5.8 makes at most two link assignments and one increment, regardless of length. Appending is now O(1), and n appends take O(n).

The tail pointer has two costs. First, maintenance: every operation that changes the list must keep tail right — front insertion into an empty list sets it, removing the last node moves it back, emptying the list nulls it. Miss one and tail points to a removed node or to null, so the next append goes astray or throws. Second, it doesn't speed up everything: removing from the end stays O(n), because the link to change belongs to the second-to-last node, and there is no stepping back from tail.

Common mistake

Writing only head = newNode; in the empty-list branch. The first addLast(5) looks fine, but tail stays null, and the second, addLast(7), takes the else branch, where tail.next throws a NullPointerException. The same happens if the first node comes from an addFirst that ignores tail.

5.2.7Inserting at a given position

Positions start at 0: addAt(data, 0) inserts at the front, addAt(data, 2) makes the new element third.

void addAt(int data, int index) {   // index starts at 0
    if (index == 0) { addFirst(data); return; }
    Node temp = head;
    for (int i = 0; i < index - 1 && temp != null; i++)
        temp = temp.next;
    if (temp == null) {          // list shorter than index
        System.out.println("Position not found.");
        return;
    }
    Node newNode = new Node(data);
    newNode.next = temp.next;   // (1)
    temp.next = newNode;           // (2)
    if (temp == tail) tail = newNode;   // inserted at the end
    size++;
}

The method has three parts. The first line delegates index 0 to addFirst, since only front insertion changes head, which the rest of the code never touches.

The second part walks to the node before the target position, at index − 1, since its link is the one that changes. The loop advances temp index − 1 steps; the temp != null test stops it if the list runs out, in which case the method prints a warning and returns, leaving the list untouched.

The third part links. Line (1) points the new node at temp's current successor; line (2) points temp at the new node. The order — (1), then (2) — is critical. Finally, if the node went in at the end (temp == tail), tail moves to it, and size grows.

Example 5.2

On 10 → 1 → 8 → 11, addAt(5, 2) should put 5 third, between 1 and 8.

  1. Special case. The index is not 0, so this is not a front insertion.
  2. Walk. temp = head (node 10); the loop runs index − 1 = 1 time. i = 0: 0 < 1, so temp moves to node(1). i = 1: 1 < 1 fails; the loop ends.
  3. Check. temp is node(1), not null; the position is valid.
  4. New node. new Node(5). 1 still points to 8; the list is unchanged.
  5. (1) newNode.next = temp.next: 5 points to 8. The list is still unchanged, since nothing in it points to 5.
  6. (2) temp.next = newNode: 1 points to 5, and the list is 10 → 1 → 5 → 8 → 11 → null.

Two links changed in all; 8 and 11 never moved in memory.

1018115nullheadtempnewNode
1018115nullheadtempnewNode
1018115nullheadtempnewNode
Figure 5.12: The linking steps of Example 5.2. (a) The new node 5 is created (8 and 11 are drawn shifted right; nothing moves in memory). (b) Line (1): 5 points to 8. (c) Line (2): 1 points to 5.

Reverse the order and (2) makes temp.next equal to 5; then (1) writes 5 into 5's own next. The node points to itself, the only reference to 8 is lost, 8 and 11 drop out, and a traversal loops 10 → 1 → 5 → 5 → … forever.

Walking takes index − 1 steps, O(index), or O(n) near the end; linking is O(1). If the index equals the length, temp stops at the last node and the node is appended; if larger, temp reaches null and “Position not found.” is printed. On 10 → 1 → 8, addAt(99, 3) appends 99, while addAt(99, 5) changes nothing.

Common mistake

Writing the loop as i < index. temp then stops at the insertion point, not before it, and the node lands one place too far: addAt(5, 2) puts 5 after 8. For insertion and deletion, walk to the node before the one you operate on; in a singly linked list only the predecessor's link can change.

5.3Singly linked lists: deletion and other operations

Deletion reverses insertion: a node leaves the chain when the link to it changes. Java needs no explicit freeing; once nothing refers to an object, the garbage collector (GC) reclaims it. So deletion's real job is to make the node unreachable without losing the rest of the list. The second half of the section covers classic problems: reversal, the middle element, copying, removing duplicates, merging, and sorting.

5.3.1Removing from the front

Removing the first node is as cheap as front insertion. The method returns the removed node so the caller can use its value.

Node removeFirst() {
    if (head == null)
        return null;
    Node temp = head;
    head = head.next;  if (head == null) tail = null;
    temp.next = null;  size--;
    return temp;
}

The first test catches the empty list and returns null; without it, head.next would throw a NullPointerException.

Otherwise the doomed node is saved in temp and head = head.next moves the head on; only temp still reaches the old first node. If the list is now empty, tail is nulled too, or it would keep pointing at a removed node. Then the node's next is cleared, size drops, and the node is returned.

temp.next = null isn't needed for correctness; it stops the returned node from pointing into the list, so nobody can reach the list through it by accident.

Table 5.9: Four calls to removeFirst() on the list 10 → 1 → 11.
CalltempNew headtailReturnedList
1stnode(10)node(1)node(11)101 → 11 → null
2ndnode(1)node(11)node(11)111 → null
3rdnode(11)nullnull11empty
4th—nullnullnullempty
10111nullheadtemp
10111nullheadtemp
10111nullheadtemp
Figure 5.13: The first call, step by step. (a) temp = head: the node to be removed (10) is saved so it isn't lost. (b) head = head.next: the head moves to 1; 10 is unreachable from the list. (c) temp.next = null: 10 is fully detached.

Each call makes one comparison and a few assignments, independent of length: O(1). If nobody keeps the returned node, the garbage collector eventually reclaims it.

5.3.2Removing from the end

Removing the last node is expensive here: the link to change is in the second-to-last node, reachable only by walking from the head.

void removeLast() {
    if (head == null) return;
    if (head.next == null) {  // single node
        head = tail = null;  size--;
        return;
    }
    Node temp = head;
    while (temp.next.next != null)
        temp = temp.next;
    temp.next = null;  tail = temp;  size--;
}

Two special cases come first: an empty list needs nothing, and a one-node list (head.next == null), having no second-to-last node, is emptied by nulling head and tail.

In general, the loop tests temp.next.next != null — “is there a node two steps ahead?” When there isn't, temp's successor is the last node, so temp is second to last; temp.next = null drops the last node and tail moves to temp.

Table 5.10: Trace of removeLast() on the list 10 → 1 → 8 → 11.
Steptemptemp.next.nextDecision
startnode(10)node(8)not null, advance
advance 1node(1)node(11)not null, advance
advance 2node(8)nullstop: temp is second to last
unlinktemp.next = null, tail = temp: the list is 10 → 1 → 8 → null, tail = node(8)
101811nullheadtemp
101811nullheadtemp
101811nullheadtemp
Figure 5.14: Removing from the end. (a) temp = head: the goal is the second-to-last node. (b) temp is at node(8); the link two steps ahead is null, so the loop ends. (c) temp.next = null: 11 leaves the list.

The loop runs n − 2 times: O(n). A tail pointer doesn't help: deletion needs the node before tail, and a singly linked list cannot step back. This limitation is the main reason doubly linked lists exist.

Common mistake

Skipping the single-node check. If the list holds only 7, temp.next is null, and temp.next.next reads through it: NullPointerException. In a chain like a.b.c, every intermediate reference must be non-null.

5.3.3Removing a given element

Removing by value means finding the element, then unlinking it through its predecessor. So two pointers walk together: temp on the node being checked, prev one behind.

void remove(int key) {
    if (head == null) return;
    if (head.data == key) {
        head = head.next;  size--;
        if (head == null) tail = null;  return;
    }
    Node prev = head;
    Node temp = head.next;
    while (temp != null) {
        if (temp.data == key) {
            prev.next = temp.next;
            if (temp == tail) tail = prev;  size--;
            return;
        }
        prev = temp;
        temp = temp.next;
    }
    System.out.println("Not found.");
}

The method handles three cases in turn.

  1. Empty list: nothing to remove; return at once.
  2. Target at the head: the head has no predecessor, so it is handled separately. head moves on and size drops; if the list is now empty, tail is nulled too.
  3. General case: start with prev = head, temp = head.next. On a match, prev.next = temp.next skips the node (and tail moves to prev if it was the tail); otherwise both pointers advance. No match prints “Not found.”
1018nullprevtemp
Figure 5.15: Deletion is a bypass: prev.next = temp.next points 10's link straight at 8 (highlighted). The removed node 1, faded, still points to 8, but nothing in the list leads to it.
Example 5.3

remove(8) on the list 10 → 1 → 8 → 11.

  1. Special cases. The list isn't empty and the head, 10, isn't 8; both ifs are passed.
  2. Start. prev = node(10), temp = node(1).
  3. Iteration 1. 1 == 8 is false. prev moves to node(1), temp to node(8).
  4. Iteration 2. 8 == 8 is true. prev.next = temp.next: 1 now points to 11. temp isn't the tail, so tail stays. size drops and the method returns.

The result is 10 → 1 → 11 → null. The removed node 8 still points to 11, but nothing in the list reaches it.

101811nullheadprevtemp
101811nullheadprevtemp
Figure 5.16: The last two steps of Example 5.3. (a) temp has found 8, with prev one behind at 1. (b) prev.next = temp.next: 1 points to 11, and 8 is bypassed.

The cost is the search: up to n nodes, O(n), plus one O(1) assignment to unlink. Only the first match is removed: on 4 → 8 → 4 → 6, remove(4) deletes the leading 4 and leaves the second.

Common mistake

Writing temp = temp.next; on finding the node and believing it removed. That changes only the local variable; no link in the list is touched. The only way to remove a node is to change the link that points to it — the predecessor's next field.

5.3.4Reversing a list

Reversal is a perennial interview favorite: 10 → 8 → 1 → 11 must become 11 → 1 → 8 → 10. A stack or a new list would work but waste memory; better to create no nodes and just turn the links around.

void reverse() {
    tail = head;                 // the old head becomes the new tail
    Node prev = null;
    Node current = head;
    Node next = null;
    while (current != null) {
        next = current.next;  // 1) save the successor
        current.next = prev;   // 2) reverse the link
        prev = current;           // 3) prev advances
        current = next;          // 4) current advances
    }
    head = prev;
}

We walk the list once and turn each node's next link back toward its predecessor, using three pointers:

  • current: the node whose link is being reversed.
  • prev: where current's new link will point; the head of the already reversed part.
  • next: current's successor, saved before the link changes — afterward the only way to the rest of the list.

Each iteration: (1) save the successor; (2) point current's link back at prev; (3) advance prev; (4) advance current to the saved next. At the end current is null and prev holds the old last node, the new head: head = prev. The first line made the old head the tail.

Input:108111nullOutput:111810null
Figure 5.17: Input and output of reversal. Top, 10 → 8 → 1 → 11 → null; bottom, the same nodes as 11 → 1 → 8 → 10 → null. No node was created; only the links changed direction.
Table 5.11: Trace of reverse() on 10 → 8 → 1 → 11, showing the state at the end of each iteration; “Reversed part” is the chain starting at prev.
IterationnextLink reversedprevcurrentReversed part
startnull—nullnode(10)empty
1node(8)10 → nullnode(10)node(8)10 → null
2node(1)8 → 10node(8)node(1)8 → 10 → null
3node(11)1 → 8node(1)node(11)1 → 8 → 10 → null
4null11 → 1node(11)null11 → 1 → 8 → 10 → null

After each iteration the list has two pieces: the reversed part from prev and the untouched part from current. Each iteration moves the first untouched node to the front of the reversed part — front insertion into a new list, reusing the same nodes.

108111nullhead, currentnullprevnext
108111nullhead, currentnullprevnext
108111nullhead, prevcurrent, next
108111head, prevnullcurrent, next
Figure 5.18: The first iteration's three steps and the result. (a) next = current.next: 8 is saved. (b) current.next = prev: 10's link turns to null; only next still reaches 8. (c) prev and current advance. (d) After four iterations, head = prev: 11 → 1 → 8 → 10 → null.

One pass with four assignments per node: O(n) time; three pointers, no new nodes: O(1) extra memory. An empty list skips the loop, and a one-node list comes out unchanged, with no special checks.

Common mistake

Omitting line (1) or putting it after (2). Once current.next = prev runs, the link to the rest is gone; an unsaved successor is unreachable and reversal stops after one node. Forgetting head = prev leaves head on the old first node, now at the end, so the list looks like a single node.

5.3.5The middle element: slow and fast pointers

The obvious way to find the middle takes two passes: count the length n, then walk n/2 steps. The slow and fast pointers technique needs one. Both start at the head; each iteration the slow one moves one node and the fast one two. When the fast pointer reaches the end, the slow one is halfway.

int findMiddle() {
    if (head == null)
        throw new IllegalStateException("List is empty");
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;          // 1 step
        fast = fast.next.next;  // 2 steps
    }
    return slow.data;
}

Two steps need both fast and its successor, hence fast != null && fast.next != null. With an odd count, fast stops on the last node; with an even count it overshoots to null. Either way slow ends in the middle. An empty list has no middle, so the method throws.

Example 5.4

Find the middle of 10 → 8 → 1 → 11 → 5 (five nodes).

  1. Start. slow and fast are at node(10).
  2. Iteration 1. fast (10) and its successor (8) exist. slow moves to 8, fast two steps to 1.
  3. Iteration 2. fast (1) and its successor (11) exist. slow moves to 1, fast to 5.
  4. End. fast.next is null; the loop ends and the method returns slow.data, 1.

In two iterations slow took 2 steps and fast 4. 1 is the third of five nodes — exactly the middle.

1081115nullhead, slowfast
1081115nullheadslowfast
1081115nullheadslowfast
Figure 5.19: Slow and fast pointers. (a) Both start at the head. (b) After the first iteration slow is at 8 and fast at 1. (c) When fast reaches the last node, slow is at the middle, 1.

An even-length list has two middles; in 10 → 8 → 1 → 11 they are 8 and 1. This code returns the second: after two iterations fast is null and slow is at 1. For the first middle, change the condition to fast.next != null && fast.next.next != null.

About n/2 iterations: O(n) time, O(1) extra memory. The step count matches the two-pass method; the gain is one traversal without knowing the length. The same idea detects cycles (Section 5.5.3).

Common mistake

Writing the condition as just fast.next != null. On an even-length list fast becomes null, and the next test reads null.next: NullPointerException. The fast != null part is needed, and it must come first, because && skips the second operand when the first is false.

5.3.6Copying a list

Copying a list means building a separate list of new nodes with the same values, so that changes to the copy leave the original alone.

SinglyLinkedList copy() {
    SinglyLinkedList newList =
        new SinglyLinkedList();
    Node temp = head;
    while (temp != null) {
        newList.addLast(temp.data);
        temp = temp.next;
    }
    return newList;
}

The method creates an empty list, traverses the original, and appends each value to the copy with addLast. Since addLast does a new Node every time, the copy's nodes are entirely separate from the original's. This is a deep copy.

list:357nullcopy:357nullseparate objects:changing oneother unaffected
Figure 5.20: A deep copy. Top, the original 3 → 5 → 7; bottom, its copy. The values match, but the nodes are different objects, so changing one list doesn't affect the other.

The tempting shortcut newList.head = head creates no nodes, only a second reference to the same ones — a shallow copy; changing a value in one changes the other. A real copy of 10 → 1 → 8 also reads 10 → 1 → 8, but newList.head == head is false.

With a tail pointer each append is O(1) and copying is O(n); with only head, the appends total n(n − 1)/2 steps, O(n2). The n new nodes take O(n) memory.

Common mistake

Copying with addFirst. It is cheap but reverses the order: 10 → 1 → 8 becomes 8 → 1 → 10. Without a tail pointer, to keep the order, hold the copy's last node in a local variable and link each new node directly to it.

5.3.7Removing duplicates

A value may occur more than once. The goal is to keep only the first occurrence of each: 3 → 5 → 3 → 7 → 5 becomes 3 → 5 → 7.

void removeDuplicates() {
    SinglyLinkedList seen =
        new SinglyLinkedList();
    Node prev = null, temp = head;
    while (temp != null) {
        int v = temp.data;
        if (seen.contains(v)) {
            prev.next =
                temp.next;   // skip
            if (temp == tail) tail = prev;  size--;
        } else {
            seen.addFirst(v);
            prev = temp;
        }
        temp = temp.next;
    }
}

Values already met go into a second list, seen, queried with contains(v), which returns search(v) != -1. A seen value marks a duplicate, skipped with prev.next = temp.next; prev stays, because its new successor is still unchecked. A new value goes into seen and prev advances. Either way temp moves on.

prev starts as null, yet prev.next never fails: the first value can't have been seen, so the first node always takes the else branch.

Table 5.12: Trace of removeDuplicates() on 3 → 5 → 3 → 7 → 5.
Nodecontains(v)Actionprev (after)seenList
3 (1st)falseaddFirst(3), prev advancesnode(3)33 → 5 → 3 → 7 → 5
5 (2nd)falseaddFirst(5), prev advancesnode(5)5 → 33 → 5 → 3 → 7 → 5
3 (3rd)true5's link turns to 7; 3 is skippednode(5)5 → 33 → 5 → 7 → 5
7 (4th)falseaddFirst(7), prev advancesnode(7)7 → 5 → 33 → 5 → 7 → 5
5 (5th)true7's link becomes null; the node was the tail, so tail = prevnode(7)7 → 5 → 33 → 5 → 7
35375nullheadprevtemp
35375nullheadprevtemp
Figure 5.21: Two bypasses. (a) The 3 in the third node is a duplicate: 5's link goes straight to 7, and prev stays at 5. (b) The 5 in the last node is a duplicate: 7's link turns to null. The result is 3 → 5 → 7 → null.

The contains calls dominate: one search of up to n values per node, O(n2) in all. A hash set makes each lookup O(1) on average and the total O(n). Extra memory is the number of distinct values, at most O(n).

Using addFirst for seen is deliberate: order doesn't matter there, only membership, and front insertion, at O(1), is the cheapest way in.

Common mistake

Advancing prev after skipping a duplicate, which moves it onto the removed node. With two duplicates in a row, as in 2 → 2 → 2, the second bypass changes the removed node's link and the third 2 stays in the list. When a node is removed, prev stays; only temp moves.

5.3.8Merging two sorted lists

Merging two ascending lists yields one sorted list of all their elements: 1 → 4 → 7 and 2 → 3 → 8 give 1 → 2 → 3 → 4 → 7 → 8. It is also the core step of merge sort.

SinglyLinkedList merge(
        SinglyLinkedList l1,
        SinglyLinkedList l2) {
    SinglyLinkedList result =
        new SinglyLinkedList();
    Node p1 = l1.head, p2 = l2.head;
    while (p1 != null && p2 != null) {
        if (p1.data <= p2.data) {
            result.addLast(p1.data);
            p1 = p1.next;
        } else {
            result.addLast(p2.data);
            p2 = p2.next;
        }
    }
    // append the remaining elements
    while (p1 != null) {
        result.addLast(p1.data);
        p1 = p1.next;
    }
    while (p2 != null) {
        result.addLast(p2.data);
        p2 = p2.next;
    }
    return result;
}

p1 and p2 start at the two heads. While both lists have elements, the smaller current value is appended and only its pointer advances. On a tie, <= takes the first list's element, preserving the order of equal elements.

When one list runs out, the other's leftovers are sorted and no smaller than anything appended, so they go in without comparisons. At most one remainder loop runs.

Table 5.13: Merging 1 → 4 → 7 with 2 → 3 → 8.
Iterationp1p2ComparisonAppendedresult
1121 ≤ 2 true11
2424 ≤ 2 false21 → 2
3434 ≤ 3 false31 → 2 → 3
4484 ≤ 8 true41 → 2 → 3 → 4
5787 ≤ 8 true71 → 2 → 3 → 4 → 7
remaindernull8— (main loop done)81 → 2 → 3 → 4 → 7 → 8
l1l2result147238nullnullp1p2
l1l2result14723812347nullnullnullnullp1p2
l1l2result147238123478nullnullnullnullp1, p2
Figure 5.22: Merging. (a) result is empty; p1 and p2 are at the two heads. (b) After five comparisons p1 reaches null; only 8 remains in the second list. (c) 8 is appended without comparison: 1 → 2 → 3 → 4 → 7 → 8.

Each of the n + m elements is appended once, with at most n + m − 1 comparisons (5 here). With an O(1) addLast the time is O(n + m); appends that walk the result would make it O((n + m)2). The result's new nodes take O(n + m) memory; relinking the original nodes instead needs O(1) but destroys the inputs.

Common mistake

Forgetting the remainder loops. The main loop stops when one list is exhausted, so leftovers like the 8 here never arrive, and the result is 1 → 2 → 3 → 4 → 7.

5.3.9Sorting a list

A list can also be sorted without moving nodes, by swapping the values in their data fields. A simple exchange sort:

void sort() {
    Node current = head;
    while (current != null) {
        Node other = current.next;
        while (other != null) {
            if (current.data > other.data) {
                int temp = current.data;
                current.data = other.data;
                other.data = temp;
            }
            other = other.next;
        }
        current = current.next;
    }
}

The outer loop walks current along the list; the inner loop visits every later node with other, swapping values through the local temp whenever current's is larger. After each inner loop, current holds the smallest value from there on, and the outer loop moves on.

Table 5.14: Trace of sort() on 4 → 1 → 3 → 2. Positions are numbered 1 to 4; the nodes stay in place and only the values change.
currentotherComparisonSwapList
node 1node 24 > 1yes1 → 4 → 3 → 2
node 1node 31 > 3no1 → 4 → 3 → 2
node 1node 41 > 2no1 → 4 → 3 → 2
node 2node 34 > 3yes1 → 3 → 4 → 2
node 2node 43 > 2yes1 → 2 → 4 → 3
node 3node 44 > 3yes1 → 2 → 3 → 4
node 4null——1 → 2 → 3 → 4
4132nullhead, current
1432nullhead, currentother
1234nullheadcurrent
Figure 5.23: Sorting by swapping values. (a) Start: 4 → 1 → 3 → 2. (b) First comparison, 4 > 1: the values are swapped, giving 1 → 4 → 3 → 2. (c) Result: 1 → 2 → 3 → 4. No node moved and no link changed.

Table 5.14 has 3 + 2 + 1 = 6 comparisons. In general node k costs n − k, for n(n − 1)/2 in total whatever the initial order, sorted or not. Swaps depend on the input (4 here). Time O(n2), extra memory O(1).

Merge sort suits linked lists better: split with slow and fast pointers, sort the halves, merge — O(n log n), and relinking needs no extra array. Index-hungry methods such as quicksort and heapsort fit lists poorly.

Common mistake

Trying to swap nodes by swapping two local variables: Node t = current; current = other; other = t;. No link changes; the pointers just trade names and the loops break. Real node swaps update both nodes' links and their predecessors'. Swapping values is far simpler.

5.4Doubly linked lists

A singly linked list cannot step back from a node. That is why removing from the end costs O(n), why removing an element needs two pointers, and why backward printing is impossible. A doubly linked list gives each node one more link.

5.4.1Definition, node, and structure

Definition 5.2

A doubly linked list is a linked list in which every node holds references to both the previous and the next node. The first node's previous link and the last node's next link are null. The list is usually kept with both a head (head) and a tail (tail) reference and can be traversed in either direction.

prevdatanextprevious nodenext nodeNode
Figure 5.24: A doubly linked node has three fields: prev, pointing to the previous node; data, holding the value; and next, pointing to the next node.

The node class gains one field:

class Node {
    int data;
    Node prev;
    Node next;
    Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

The list class keeps Node head, tail;. The gain: backward traversal, and O(1) removal of a known node and of the last node. The price: a second reference per node, a noticeable memory increase for a list of integers, and links in both directions to update on every change — roughly twice as many.

1101525nullnullheadtail
Figure 5.25: The doubly linked list 1 ⇄ 10 ⇄ 15 ⇄ 25. head points to 1, tail to 25. Each pair of neighbors has a forward and a backward link; the empty links at the two ends point to null.

Every operation follows these rules:

  • Elements are reachable both forward and backward.
  • Inserting a node updates pointers in both directions: the new node's two links and each neighbor's link toward it.
  • Removing a node updates the pointers of both its predecessor and its successor.
  • Search can go either way; for a target known to be near the end, start from the tail.

Correctness is one invariant: for every node d, if d.next is not null then d.next.prev == d, and if d.prev is not null then d.prev.next == d. Every forward link is matched by a backward one, and an operation is correct only if it preserves this.

5.4.2Inserting at the front and the end

Front insertion adds one assignment to the singly linked version's two:

public void addFirst(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        tail = newNode;
    } else {
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }
}

An empty list gets the node as head and tail. Otherwise: the new node's next points to the old head (forward link); the old head's prev, so far null, points back to it; head moves to it. Its own prev stays null, as the first node's must.

Table 5.15: Trace of addFirst(1) on 10 ⇄ 15 ⇄ 25.
Line1.prev1.next10.prevhead
new Node(1)nullnullnullnode(10)
newNode.next = headnullnode(10)nullnode(10)
head.prev = newNodenullnode(10)node(1)node(10)
head = newNodenullnode(10)node(1)node(1)
1015251nullnullheadtailnewNode
1015251nullnullheadtailnewNode
1015251nullnullhead, newNodetail
Figure 5.26: addFirst(1) on a doubly linked list. (a) newNode.next = head: forward link 1 → 10. (b) head.prev = newNode: backward link 10 → 1, replacing 10's null. (c) head = newNode: the list is 1 ⇄ 10 ⇄ 15 ⇄ 25.

Insertion at the end mirrors it:

public void addLast(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        tail = newNode;
    } else {
        newNode.prev = tail;
        tail.next = newNode;
        tail = newNode;
    }
}

The new node's prev points to the old tail, the old tail's next to it, and tail moves to it — no traversal. addLast(30) on 1 ⇄ 10 ⇄ 15 ⇄ 25 gives 1 ⇄ 10 ⇄ 15 ⇄ 25 ⇄ 30, which reads 30, 25, 15, 10, 1 backward.

110152530nullnullheadtailnewNode
110152530nullnullheadtailnewNode
110152530nullnullheadtailnewNode
Figure 5.27: addLast(30) on a doubly linked list. (a) newNode.prev = tail: backward link 30 → 25. (b) tail.next = newNode: forward link 25 → 30. (c) tail = newNode: the tail pointer moves to 30.

Both are O(1), at one assignment more than the singly linked versions — the price of cheap backward traversal and removal at the end.

Common mistake

Setting only the forward links. Without head.prev = newNode, forward printing looks right and hides the bug, but backward printing stops at 10, missing 1, and removals working back from 10 update the wrong node. Printing both ways after each change catches this early.

5.4.3Inserting at a position

Again we walk to the node before the insertion point, but linking changes four links instead of two.

void addAt(int data, int index) {   // index starts at 0
    if (index == 0) { addFirst(data); return; }
    Node temp = head;
    for (int i = 0; i < index - 1 && temp != null; i++)
        temp = temp.next;
    if (temp == null) { System.out.println("Invalid position."); return; }
    if (temp == tail) { addLast(data); return; }   // also updates tail
    Node newNode = new Node(data);
    newNode.next = temp.next;     // (1)
    newNode.prev = temp;              // (2)
    temp.next.prev = newNode;      // (3)
    temp.next = newNode;             // (4)
}

The opening matches the singly linked version: index 0 goes to addFirst, temp walks to node index − 1, an invalid position prints a warning. New: if temp is the last node, addLast takes over, because line (3), temp.next.prev, would read through the last node's null; addLast also updates tail.

The four links are set in this order — the new node's own two first, leaving the list untouched, then the neighbors' links toward it:

  1. newNode.next = temp.next: the new node points to its right neighbor.
  2. newNode.prev = temp: the new node points to its left neighbor.
  3. temp.next.prev = newNode: the right neighbor's backward link turns to the new node.
  4. temp.next = newNode: the left neighbor's forward link turns to the new node.
101512(1)(2)(3)(4)temp
Figure 5.28: Inserting 12 between 10 and 15. The numbers are code lines: (1) 12 → 15, (2) 12 → 10, (3) 15's backward link to 12, (4) 10's forward link to 12. The dashed line is the direct link between 10 and 15 before the insertion.
Example 5.5

addAt(12, 2) on 1 ⇄ 10 ⇄ 15 ⇄ 25.

  1. Walk. temp advances index − 1 = 1 step to node(10), which is not the last node.
  2. (1) 12.next = 15. No node in the list points to 12 yet.
  3. (2) 12.prev = 10.
  4. (3) temp.next is still 15; 15.prev becomes 12.
  5. (4) 10.next becomes 12.

Forward the list reads 1, 10, 12, 15, 25; backward, 25, 15, 12, 10, 1. Four links changed.

110152512nullnullheadtailtempnewNode
110152512nullnullheadtailtempnewNode
110152512nullnullheadtailtempnewNode
Figure 5.29: The last steps of Example 5.5. (a) (3): 15's backward link points to 12. (b) (4): 10's forward link points to 12. (c) The result, redrawn: 1 ⇄ 10 ⇄ 12 ⇄ 15 ⇄ 25.

Why must (3) precede (4)? Line (3) reaches 15 through temp.next. Run (4) first and temp.next is 12, so (3) sets 12.prev = 12, while 15 still points back to 10. Forward reading (1, 10, 12, 15, 25) hides the bug; backward reading (25, 15, 10, 1) skips 12. Rule: when you reach a node through a link, finish with that node before changing the link.

Linking is O(1); the walk is O(index), O(n) at worst. For an index in the second half, walking back from the tail takes at most n/2 steps — still O(n).

5.4.4Removing from the front and the end

In a doubly linked list, removal at either end is constant time:

void removeFirst() {
    if (head == null) return;  // empty
    if (head == tail) {  // single node
        head = tail = null;
    } else {
        head = head.next;
        head.prev = null;
    }
}
void removeLast() {
    if (tail == null) return;  // empty
    if (head == tail) {  // single node
        head = tail = null;
    } else {
        tail = tail.prev;
        tail.next = null;
    }
}

One skeleton serves both. An empty list needs nothing; a one-node list (head == tail) is emptied by nulling both fields. Otherwise the front version moves head on and nulls its prev; the end version moves tail back and nulls its next.

The speed comes from tail = tail.prev: one step to the second-to-last node, which a singly linked list finds only by walking the whole list.

Table 5.16: Trace of removal at both ends of a doubly linked list.
OperationLineEffectList
removeFirst(), 1 ⇄ 10 ⇄ 15head = head.nexthead moves to 10(10 still points back to 1)
head.prev = null10's backward link is cleared10 ⇄ 15
removeLast(), 1 ⇄ 10 ⇄ 15 ⇄ 25tail = tail.prevtail moves to 15(15 still points forward to 25)
tail.next = null15's forward link is cleared1 ⇄ 10 ⇄ 15
11015nullnullheadtail
11015nullnullheadtail
1101525nullnullheadtail
1101525nullnullheadtail
Figure 5.30: Removal at both ends. (a) head = head.next: the head moves to 10. (b) head.prev = null: 10's backward link is cleared too. (c) tail = tail.prev: one step reaches the second-to-last node. (d) tail.next = null: 25 leaves the list, giving 1 ⇄ 10 ⇄ 15.

Each method is O(1). In the one-node case, head and tail must be nulled together; otherwise the list looks empty from one end and nonempty from the other, and the next insertion takes the wrong branch.

Common mistake

Skipping head.prev = null. Forward traversal still works, but the new head points back to the removed node, so backward printing prints the removed 1 too — and the lingering reference keeps the garbage collector from reclaiming it.

5.4.5Removing a given element

The singly linked version needed prev and temp in step. Here one pointer suffices, since the predecessor is temp.prev.

void remove(int data) {
    Node temp = head;
    while (temp != null && temp.data != data)
        temp = temp.next;
    if (temp == null) return;  // not found
    if (temp.prev != null)
        temp.prev.next = temp.next;
    else head = temp.next;   // removing the head
    if (temp.next != null)
        temp.next.prev = temp.prev;
    else tail = temp.prev;    // removing the tail
}

The loop advances while temp is non-null and holds another value, ending on the target or at null, meaning the value is absent.

Two links bypass the node: the left neighbor's forward link goes to the right neighbor, and the right neighbor's backward link to the left one. At the ends, head (no left neighbor) or tail (no right neighbor) is updated instead; in a one-node list both become null.

11015temp
Figure 5.31: Removing from the middle. To remove 10, 1's forward link goes to 15 and 15's backward link to 1 (highlighted). The removed node is faded.
Table 5.17: Trace of remove(15) on 1 ⇄ 10 ⇄ 15 ⇄ 25.
SteptempCheckAction
searchnode(1)1 ≠ 15advance
searchnode(10)10 ≠ 15advance
searchnode(15)15 == 15loop ends
leftnode(15)temp.prev = 10, not null10.next = 25
rightnode(15)temp.next = 25, not null25.prev = 10
1101525nullnullheadtailtemp
1101525nullnullheadtailtemp
Figure 5.32: The linking steps of remove(15). (a) temp.prev.next = temp.next: forward link 10 → 25; 15 is bypassed going forward. (b) temp.next.prev = temp.prev: backward link 25 → 10. The result is 1 ⇄ 10 ⇄ 25.

Search is O(n), unlinking O(1). The real gain comes when the node is already in hand: a program that keeps node references removes one in O(1) through its prev and next. A singly linked list still has to walk from the head to find the predecessor.

5.4.6Printing backward

Backward printing mirrors forward printing: start at tail and follow the prev links.

void printBackward() {
    Node temp = tail;
    System.out.print("Backward: ");
    while (temp != null) {
        System.out.print(temp.data + " <-> ");
        temp = temp.prev;
    }
    System.out.println("null");
}

No walk is needed to reach the last node. Each iteration prints temp's data and steps back with temp = temp.prev, ending past the first node, whose prev is null. For 1 ⇄ 10 ⇄ 15 ⇄ 25 the output is Backward: 25 <-> 15 <-> 10 <-> 1 <-> null.

1101525nullnullheadtail, temp
1101525nullnullheadtailtemp
Figure 5.33: Printing backward. (a) temp = tail: the traversal starts at the last node. (b) After 1 is printed, temp takes 1's prev, null, and the loop ends.

Both directions are O(n). A singly linked list can print backward by recursion or with a stack, but either costs O(n) extra memory (for recursion, the call stack); the doubly linked list needs O(1).

5.4.7Sentinel nodes

The same special cases recur in every doubly linked method: empty list? head? tail? They lengthen the code and breed bugs — miss one and you get a NullPointerException or a wrong head/tail. There is an elegant way to eliminate them.

Definition 5.3

A sentinel node is a fixed node placed at one end of a list that carries no real element. A doubly linked list with sentinels has two: a header and a trailer (Goodrich and Tamassia's terms). The real nodes always lie between them.

empty list——headertrailer2 items—510—headertrailer
Figure 5.34: A doubly linked list with sentinels. Top, the empty list: just the two sentinels, pointing to each other. Bottom, a two-element list: 5 and 10 sit between header and trailer. The sentinels' data fields are shown as “—”.

With sentinels, every real node always has a predecessor and a successor, so null checks and head/tail updates vanish. Even the empty list is ordinary: two sentinels pointing to each other, linked once at construction and never separated. Two small helpers do all insertions and removals:

void addBetween(int v, Node pred, Node succ) {
    Node newest = new Node(v);
    newest.prev = pred;
    newest.next = succ;
    pred.next = newest;
    succ.prev = newest;  size++;
}
void addFirst(int v) {
    addBetween(v, header, header.next); }
void remove(Node d) {
    d.prev.next = d.next;
    d.next.prev = d.prev;
    size--; }

addBetween(v, pred, succ) inserts between two neighbors with four assignments. addFirst calls it with the header and the first real node; appending uses addBetween(v, trailer.prev, trailer). remove(d) links d's neighbors to each other. No method contains an if.

Example 5.6

On an empty list with sentinels we call addFirst(10) and addFirst(5), then remove 10's node with remove.

  1. Start. header.next = trailer, trailer.prev = header, size = 0.
  2. addFirst(10). This calls addBetween(10, header, trailer), since in the empty list header.next is the trailer. Four assignments: 10.prev = header, 10.next = trailer, header.next = 10, trailer.prev = 10. size = 1.
  3. addFirst(5). addBetween(5, header, node(10)); the same four assignments put 5 between the header and 10. List: header ⇄ 5 ⇄ 10 ⇄ trailer; size = 2.
  4. remove(d), d = node(10). d.prev.next = d.next: 5 points straight to the trailer. d.next.prev = d.prev: the trailer points back to 5. size = 1.

10 was the last real node. Without sentinels, removing it would have required updating tail; here nothing special happened.

——nullnullheadertrailer
——10nullnullheadertrailerpredsuccnewest
——105nullnullheadertrailerpredsuccnewest
——105nullnullheadertrailerd
Figure 5.35: Four moments of Example 5.6. (a) The empty list: the two sentinels point to each other. (b) After addFirst(10). (c) After addFirst(5): 5 is between the header and 10. (d) remove has bypassed 10 in both directions.

Every insertion and removal is O(1), and shorter code means fewer branches and fewer bugs. The price is two extra nodes, and traversal runs from header.next while temp != trailer, not temp != null. Java's java.util.LinkedList is also doubly linked, and many textbook implementations use sentinels.

Common mistake

Starting a traversal at header prints its meaningless data; running to null prints the trailer too. Sentinels are not data: start at the first real node and stop at the trailer.

5.4.8Links in more directions: a linked structure from a matrix

Links can run in whatever directions a structure needs. A nice example turns a two-dimensional matrix into a linked structure whose nodes hold right (the cell to the right) and down (the cell below): class Node { int data; Node right, down; }, with constructor Node(int data).

123null456null789nullright → down ↓
Figure 5.36: The linked structure of a 3×3 matrix. Each node points to the one on its right and the one below. The right field is null in the last column, and down is null in the last row. The whole structure is reached from the top-left node.

Two nested traversals from the top-left node print it row by row:

void display(Node start) {
    Node down = start;
    while (down != null) {       // rows
        Node right = down;
        while (right != null) {     // columns
            System.out.print(right.data + " ");
            right = right.right;
        }
        System.out.println();
        down = down.down;
    }
}

The outer loop follows down links from row to row, the inner loop right links along a row. For Figure 5.36 the output is 1 2 3, 4 5 6, 7 8 9 on three lines. Each node is visited once: O(rows · columns).

Building it is more interesting. Setting a node's right and down requires those neighbors to exist already, so creation starts at the bottom-right corner and runs backward:

Node build(int[][] m) {
    int r = m.length, c = m[0].length;
    Node[][] d = new Node[r][c];
    for (int i = r - 1; i >= 0; i--)
        for (int j = c - 1; j >= 0; j--) {
            Node n = new Node(m[i][j]);
            if (j + 1 < c) n.right = d[i][j+1];
            if (i + 1 < r) n.down = d[i+1][j];
            d[i][j] = n;
        }
    return d[0][0];
}

Nodes are stored in a helper array d at their matrix positions. Because i and j count down, d[i][j+1] and d[i+1][j] exist when cell (i, j) is built; in the last column and last row the corresponding link stays null. The top-left node is returned.

Table 5.18: Trace of build(m) for the 2×3 matrix {{1, 2, 3}, {4, 5, 6}}.
(i, j)New noderightdown
(1, 2)6none (last column)none (last row)
(1, 1)56none (last row)
(1, 0)45none (last row)
(0, 2)3none (last column)6
(0, 1)235
(0, 0)124
m =1 2 34 5 6d[0][0]d[0][1]d[0][2]d[1][0]d[1][1]d[1][2]
m =1 2 34 5 6d[0][0]d[0][1]3456right: nullright: null
m =1 2 34 5 6123456right: nullright: nullreturned ►
Figure 5.37: Three moments of build(m). (a) The array d is empty. (b) The bottom row's three nodes and 3 have been created; 3's down link points to 6. (c) Six nodes for six cells; d[0][0] (1) is returned.

One node per cell: O(rows · columns) time and the same memory for d. An r-by-c matrix gets r(c − 1) right and (r − 1)c down links — 6 and 6 for 3×3.

Why the table d? The obvious recursion creates node (i, j) and calls build(i, j+1) for right and build(i+1, j) for down, reaching each cell by many routes and creating a node each time: (1, 1) is reached from (0, 1) and from (1, 0), yielding two nodes. Each cell gets one node per right-down path from the corner — 19 instead of 9 for 3×3, and exponentially worse as the matrix grows. Since the paths never meet at a shared node, the result isn't even a grid. The table creates each node once.

Common mistake

Running the loops from the top left: for (int i = 0; i < r; i++). d[i][j+1] and d[i+1][j] are still null when node (i, j) is created, so all links stay null and nine disconnected nodes result. Create a node before linking to it.

5.5Circularly linked lists

Some work goes round in turns. In a board game the turn passes from player to player, back to the first after the last. An operating system hands waiting programs short time slices in turn. A music player on “repeat” follows the last song with the first. Such lists have no end; the end is tied to the beginning.

5.5.1Definition and class

Definition 5.4

A circularly linked list is a linked list whose last node points to the first node instead of to null. The nodes form a ring; each still points to its successor, and no link in the list is null.

101811tailhead = tail.next
Figure 5.38: The circular list 10 → 1 → 8 → 11. The last node (11) points back to the first (10). The list is kept through tail alone; the head is tail.next.

Keeping only tail suffices, since the head is always tail.next: one reference reaches both ends in O(1). A separate head field would need updating everywhere — needless work and another source of bugs.

public class CircularLinkedList {
    class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    private Node tail;  // head = tail.next
    private int size;
}

The class nests its node class and keeps tail and size. Two special cases: an empty list has tail == null, and a lone node points to itself, tail.next == tail — odd-looking but consistent, since that node is both first and last.

Common mistake

Traversing a circular list with while (p != null). A ring has no null, so the loop never ends. Stop on returning to the start node or reaching tail.

5.5.2Printing a circular list

void print() {
    if (tail == null) return;
    Node current = tail.next;
    while (current != tail) {
        System.out.print(current.data + " ");
        current = current.next;
    }
    System.out.print(current.data + " ");
}

An empty list prints nothing. Otherwise the traversal starts at the head, tail.next, printing and advancing while current != tail. The loop stops on the last node before printing it, so the line after the loop prints it.

Table 5.19: Trace of print() on the ring 1 → 8 → 10 → 16 → (1) (tail = node 16).
Stepcurrentcurrent != tailPrinted
startnode(1)——
iteration 1node(1)true1
iteration 2node(8)true8
iteration 3node(10)true10
loop endsnode(16)false—
last linenode(16)—16
181016tailcurrent
181016tail, current
Figure 5.39: Printing a circular list. (a) current = tail.next: the traversal starts at the head, 1. (b) When current reaches the last node (16), the loop ends; null is never reached.

The output is 1 8 10 16, in O(n) time. With one node, current equals tail at once, the loop is skipped, and the last line prints the node exactly once.

A do-while loop also works — print, advance, stop on returning to the head — and since it runs the body before testing, needs no separate last line.

5.5.3Cycle detection: Floyd's algorithm

A circular list's ring is deliberate, but a bug can create an unwanted cycle in a singly linked list: some next points to an earlier node, and printing or measuring the list never ends. So detecting cycles is a practical question.

Watching for a return to the head isn't enough, since the cycle may loop back to a middle node: if 6 points back to 3 in 1 → 2 → 3 → 4 → 5 → 6, the traversal circles 3, 4, 5, 6 forever without revisiting 1. A set of visited nodes works but costs O(n) memory.

Floyd's cycle detection algorithm needs O(1) extra memory. It reuses the slow and fast pointers, hence its nickname, “tortoise and hare.”

boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null &&
           fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

Each iteration the slow pointer moves one node and the fast pointer two. Two outcomes are possible:

  • No cycle: the fast pointer reaches the end — it or its successor becomes null — the loop condition fails, and the method returns false.
  • A cycle: both pointers end up circling inside it, and the fast one gains one node per iteration. The gap shrinks by exactly one, so it cannot jump over the slow pointer and must land on it; then slow == fast and the method returns true.
Theorem 5.1 (Correctness of Floyd's algorithm)

If a singly linked list has a cycle, the slow and fast pointers meet at the same node within n iterations; if not, the fast pointer reaches the end within n/2 iterations. Here n is the number of distinct nodes in the list.

Without a cycle, the fast pointer covers two nodes per iteration and exhausts the path within n/2 iterations. With one, let μ be the length of the part before the cycle and λ the cycle length (μ + λ = n). The slow pointer enters after μ iterations, with the fast one already inside. Let d be the number of nodes by which the fast pointer then trails the slow one, counting forward around the cycle; 0 ≤ d < λ. Each iteration shrinks the gap by exactly one, so they meet after d more, μ + d < μ + λ = n in total. The exception is μ = 0, a cycle back to the head: then d = 0 at the start, but equality isn't tested before the first move, and the pointers coincide again after λ = n iterations, still within n. □

Example 5.7

The list is 1 → 2 → 3 → 4 → 5 → 6, and 6 points back to 3.

  1. Iteration 1. slow reaches 2, fast 3. 2 ≠ 3.
  2. Iteration 2. slow reaches 3, fast 5. 3 ≠ 5.
  3. Iteration 3. slow reaches 4; fast goes 5 → 6 and, via the cycle link, to 3. 4 ≠ 3. The fast pointer has lapped the cycle and trails by one node.
  4. Iteration 4. slow reaches 5; fast goes from 3 to 4 to 5. 5 == 5: the method returns true.

Here μ = 2 (1 and 2) and λ = 4 (3, 4, 5, 6). The slow pointer enters in iteration 2, with the fast one at 5, two nodes behind it; they meet two iterations later.

Table 5.20: Trace of hasCycle (1 → … → 6, 6 → 3).
Iterationslowfastslow == fast
start11(not tested)
123no
235no
343no
455yes → true
123456head, slow, fast
123456headslowfast
123456headslow, fast
Figure 5.40: Floyd's algorithm. (a) Both pointers start at the head; the link from 6 back to 3 forms the cycle. (b) At the end of iteration 3, the fast pointer has lapped the cycle to 3; the slow one is at 4. (c) In iteration 4 they meet at 5.

At most n/2 iterations without a cycle and n with one: O(n) time. Only two pointers: O(1) extra memory.

Common mistake

Comparing before the pointers move. Both start at head, so the first test succeeds and every list, cyclic or not, gets true. Test after advancing.

5.5.4Inserting at the end

Appending puts the new node between the last node and the head:

Node temp = new Node(value);
if (tail == null) {
    tail = temp;
    tail.next = tail;
} else {
    temp.next = tail.next;
    tail.next = temp;
    tail = temp;
}
size++;

An empty list's new node becomes the tail and points to itself (tail.next = tail), closing the ring. Otherwise: the new node points to the head (temp.next = tail.next), the old tail to the new node (tail.next = temp), and tail moves. size grows either way.

Table 5.21: Trace of addLast(1), addLast(8), addLast(10) on an empty circular list.
CallAssignmentstailRingsize
addLast(1)tail = temp; tail.next = tailnode(1)1 → (1)1
addLast(8)8 → 1; 1 → 8; tail = 8node(8)1 → 8 → (1)2
addLast(10)10 → 1; 8 → 10; tail = 10node(10)1 → 8 → 10 → (1)3
1tail, temp
18tailtemp
18tailtemp
18tail, temp
Figure 5.41: Inserting into a circular list. (a) addLast(1): the single node points to itself. (b) addLast(8), first assignment: the new node points to the head (1). (c) Second assignment: the old tail (1) points to the new node. (d) tail moves to 8.

At most three assignments, no traversal: O(1). Order matters: doing tail.next = temp first erases the only link to the head, so temp.next = tail.next links the node to itself and the old nodes fall out of the ring.

5.5.5Inserting and removing at the front

Front and end insertion are nearly identical here: the new node enters the ring at the same spot, between the last node and the head. Only the choice of tail differs:

void addFirst(int value) {
    Node temp = new Node(value);
    if (tail == null) {
        tail = temp;
        tail.next = tail;
    } else {
        temp.next = tail.next;
        tail.next = temp;
    }   // tail is unchanged
    size++;
}

This is end insertion minus tail = temp: with tail unmoved, the new node follows the last node, at the front. addFirst(5) on 1 → 8 → 10 → (1) (tail = 10) points 5 at the old head, then 10 at 5: 5 → 1 → 8 → 10 → (5), tail still 10.

18105tailtemp
18105tailtemp
Figure 5.42: addFirst(5) on a circular list. (a) temp.next = tail.next: 5 points to the old head (1). (b) tail.next = temp: 10 now points to 5, the new head; tail doesn't change.

Removing from the front is constant time as well:

void removeFirst() {
    if (tail == null) return;
    Node head = tail.next;
    if (head == tail)   // single node
        tail = null;
    else
        tail.next = head.next;
    size--;
}

The head is tail.next. A single node (head == tail) empties the list. Otherwise tail.next = head.next routes the ring past the head, whose successor becomes the new head: 1 → 8 → 10 → (1) becomes 8 → 10 → (8).

1810tailhead
Figure 5.43: Removing from the front of a circular list. tail.next = head.next: 10 now points to 8, and 1 has left the ring.

Both are O(1). The local head is not a field, just a temporary reference to the front node.

5.5.6Removing from the end

With only tail, removing from the end of a singly linked ring is still O(n): the predecessor's link must change, and reaching it means walking the ring:

void removeLast() {
    if (tail == null) return;
    if (tail.next == tail) tail = null;   // single node
    else {
        Node temp = tail.next;
        while (temp.next != tail)     // second to last
            temp = temp.next;
        temp.next = tail.next;     // link to the head
        tail = temp;
    }
    size--;
}

A single node (tail.next == tail) empties the list. Otherwise temp walks from the head until its successor is tail; temp.next = tail.next then links it to the head, dropping the old tail, and tail moves to temp.

181016temp, tail
Figure 5.44: Removing from the end of the ring 1 → 8 → 10 → 16. temp and the new tail are at 10; 10's link is redirected to the head (1) (highlighted link), and 16 leaves the ring (faded).
Table 5.22: Trace of removeLast() on the ring 1 → 8 → 10 → 16 → (1) (tail = node 16).
Steptemptemp.next == tailDecision
startnode(1)no (8)advance
advance 1node(8)no (10)advance
advance 2node(10)yes (16)stop
relink10.next = 1; tail = 10; size 3: ring 1 → 8 → 10 → (1)
181016tailtemp
181016tailtemp
181016tail, temp
Figure 5.45: The last steps of removeLast(). (a) 10's successor is tail: temp is on the second-to-last node. (b) temp.next = tail.next: 10 points to the head, and 16 leaves the ring. (c) tail = temp: the tail is now 10.

The loop runs n − 2 times: O(n). A doubly linked ring reaches the second-to-last node as tail.prev and removes in O(1), which is why many implementations, Java's LinkedList among them, link both ways.

5.5.7Rotation and taking turns

Rotation is the circular list's most elegant operation: moving the front element to the back changes no link; tail just advances one node:

void rotate() {              // Goodrich: rotate()
    if (tail != null)
        tail = tail.next;   // the old head moves to the back
}
// round-robin: serve the front element each turn
for (int round = 1; round <= 4; round++) {
    System.out.print(tail.next.data + " ");
    list.rotate();
}

After tail = tail.next, the old head is the tail and its successor, tail.next, the new head. The ring is unchanged; only our viewpoint moves. Goodrich and Tamassia call this rotate(); it is one assignment, O(1).

Rotation models round robin scheduling directly: jobs sharing the processor sit in a ring, the front job gets a short slice, the list rotates, and the next job's turn comes. The code's second part runs four turns.

Table 5.23: Four turns of round robin on the ring 1 → 8 → 10 → (1) (initially tail = 10).
TurnServed (tail.next)tail after rotate()New head
1118
28810
310101
4118
1810tail
1810tail
1810tail
Figure 5.46: Rotation. (a) Start: tail = 10, head 1. (b) First rotate(): tail moves to 1, and the head becomes 8. (c) Second rotate(): tail moves to 8, and the head becomes 10. No link changed.

The output is 1 8 10 1: fair turns. A plain list could remove from the front and append instead, building new links and updating the tail; the ring needs one assignment. Finished jobs leave with removeFirst() and new ones join with addLast, both O(1).

Common mistake

Rotating by detaching and re-appending nodes. It works, but changes links needlessly and risks a wrong tail. A ring's starting point is just where tail points; advancing it is all rotation takes.

5.6Array or linked list?

Arrays and linked lists answer the same question — how to store a sequence — and the better choice depends on what the program does. Figure 5.47 shows both in memory.

array (contiguous)1010008100411008111012linked list (scattered)108111
Figure 5.47: Left, an array: four elements in consecutive cells at addresses 1000, 1004, 1008, and 1012. Right, a linked list: the same four elements in scattered nodes, ordered by arrows.

An array finds element i at its start address plus i element sizes: with 4-byte integers, index 2 is at 1000 + 2 · 4 = 1008, in one step regardless of length. A linked list must follow links.

Table 5.24: Arrays compared with singly linked lists.
CriterionArrayLinked list
Access to element iO(1): address computedO(n): walk from head
Insert / remove at frontO(n): shiftingO(1)
Insert after a known positionO(n)O(1): two links
Sizefixed; growing is an O(n) copydynamic, one new per insertion
Overhead and cacheunused capacity; cache-friendlya reference per node; scattered access

The last row of Table 5.24 shows what big-O misses. The processor reads memory in consecutive blocks and keeps them in a fast store, the cache. Reading one block of an array brings the next few elements along; scattered list nodes may each need a separate read. So a traversal that is O(n) for both is often markedly faster on an array.

Both waste memory. An array may leave capacity unused — up to the element count in a doubling dynamic array. A list leaves none but spends a reference and object header per element, more than the data for small elements like integers.

A rough rule of thumb:

  • Array: when random access is frequent, the element count is roughly known, and elements are mostly appended.
  • Linked list: when changes cluster at the ends or at known positions, the size is unpredictable, and indexing is rare. Stacks and queues, which work only at the ends, are natural fits.

Which kind of linked list to use also depends on the operations; Table 5.25 compares four common forms.

Table 5.25: Operation costs for the kinds of linked list.
OperationSingly (head only)Singly (head + tail)Doubly (head + tail)Circular (tail only)
Insert at frontO(1)O(1)O(1)O(1)
Insert at endO(n)O(1)O(1)O(1)
Remove from frontO(1)O(1)O(1)O(1)
Remove from endO(n)O(n)O(1)O(n)
Search / element iO(n)O(n)O(n)O(n)
Remove a known nodeO(n)*O(n)*O(1)O(n)*

Starred costs come from walking to the predecessor. Inserting after a known node is O(1) in all four, since only that node's link changes. So if you often remove nodes at the end or in the middle, choose a doubly linked list.

5.7Common mistakes

Most linked list bugs fall into a few types. The per-operation mistakes are collected here as a review checklist.

Table 5.26: Common bugs in linked list code.
BugWhat happensFix
No empty-list checkhead.data or head.next while head is null: NullPointerException.if (head == null) return;
Setting links in the wrong orderIf head or the predecessor's link changes first, the rest of the list is lost; a node may point to itself.Attach the new node to the rest first: newNode.next = head; head = newNode;
Advancing head while traversingThe list is unreachable after printing.Traverse with Node temp = head;.
Forgetting tailAfter removing the only node, tail still points to it; after inserting into an empty list, tail stays null.if (head == null) tail = null;; on insertion into an empty list, head = tail = newNode;
Updating one direction in a doubly linked listIf prev isn't updated, backward traversal breaks; forward printing hides the bug.Four links per insertion, two per removal: next.prev = newNode;
!= null in a circular listA ring has no null: infinite loop.while (p != tail) …
Not updating size in some methodssize() and isEmpty() answer wrongly; the counter may go negative.Every method that changes the list updates the counter.

Two questions lie behind all of these. First: “Which node is unreachable after this assignment?” Overwriting a link erases a path to its old target; if the target is still needed, save it in a local first, as next does in reversal and temp in front removal. Second: “Is this right for an empty list, a one-node list, and the first and last nodes?” Most bugs surface in these four cases, and tracing a method through them on paper catches most of them. Sentinels are valuable precisely because they remove these cases structurally.

5.8Summary

  • A linked list keeps elements in nodes connected by references; links, not memory positions, define the order. The node class has a field of its own type (self-referential structure).
  • In a singly linked list each node points to the next, the last to null, and the list is reached through head. Front insertion and removal are O(1); search, indexing, appending (without a tail pointer), and removal from the end are O(n).
  • The traversal pattern: temp = head; while temp != null, work; temp = temp.next. Printing, length, and search are variations; temp.next != null stops at the last node.
  • The order of links is critical: attach the new node to the rest first, then change the predecessor's link or head. Walk to the node before the one you operate on.
  • A tail pointer makes appending O(1) but not removal from the end; every operation must maintain tail (and size).
  • Reversal uses three pointers and no new nodes: O(n) time, O(1) extra memory. Slow and fast pointers find the middle in one pass, returning the second middle for even lengths.
  • A deep copy creates new nodes; newList.head = head is only a second reference. Removing duplicates is O(n2) with a seen-list, O(n) with a hash set. Merging sorted lists is O(n + m) with a tail pointer. Value-swap sorting makes n(n − 1)/2 comparisons; O(n log n) merge sort suits lists better.
  • In a doubly linked list nodes point both ways. Insertion and removal at either end and removal of a known node are O(1), and backward traversal works, at the cost of a second reference per node and two-way updates. Middle insertion changes four links in a fixed order.
  • Sentinel nodes (header and trailer) give every real node a predecessor and a successor, eliminating null checks and head/tail updates.
  • A linked structure from a matrix gives each node right and down links. Built from the bottom right with the nodes stored in a table, it takes O(rows · columns).
  • In a circularly linked list the last node points to the head; only tail is kept, and the head is tail.next. Appending, front insertion and removal, and rotation are O(1); removal from the end is O(n). Traversal stops at tail, not null. Rotation models round robin scheduling.
  • Floyd's algorithm uses slow and fast pointers to detect a cycle in O(n) time and O(1) extra memory.
  • Arrays win at random access and cache use; linked lists win at insertion and removal at the ends and at unpredictable sizes.

5.9Key terms

Each term links to the course glossary, which defines it in a sentence and names the chapter that explains it.

5.10Test Yourself

  1. On an empty SinglyLinkedList (keeping head and tail) we call addLast(4), addFirst(2), addLast(9), addAt(7, 1), and removeFirst(). Which value does the node returned by the last call hold, and what is the final list?

    Answer

    The list goes 4; 2 → 4; 2 → 4 → 9; 2 → 7 → 4 → 9. In addAt(7, 1) the loop runs index − 1 = 0 times, so 7 goes in after the leading 2. removeFirst() returns 2's node, leaving 7 → 4 → 9 with tail still 9.

  2. What do search(6) and search(5) return on 6 → 3 → 6 → 1? How many nodes' data does each compare?

    Answer

    search(6) matches the first node and returns 0 after one comparison, never reaching the second 6. search(5) checks all four nodes and returns −1. These are the best (O(1)) and worst (O(n)) cases.

  3. reverse() runs on 5 → 2 → 7. At the end of the second iteration, what are prev, current, and the reversed part? What are the final list and tail?

    Answer

    Iteration 1 turns 5's link to null (prev 5, current 2); iteration 2 turns 2's link to 5 (prev 2, current 7). The reversed part is 2 → 5 → null; 7's link is still null. After iteration 3, head = prev gives 7 → 2 → 5. The first line set tail to the old head, 5.

  4. What does findMiddle() return for 3 → 1 → 4 → 1 → 5 and for 9 → 8 → 7 → 6? What must change to get the first middle of the second list?

    Answer

    First list, (slow, fast) per iteration: (1, 4), (4, 5); fast.next is then null, and 4 is returned. Second list: (8, 7), (7, null), returning 7, the second middle. For the first middle (8), use fast.next != null && fast.next.next != null; one iteration runs and slow stays at 8.

  5. removeDuplicates() runs on 2 → 2 → 5 → 2 → 5 → 9. What is the result, how many nodes are skipped, how many times is contains called, and what does seen hold at the end?

    Answer

    The result is 2 → 5 → 9. The second, fourth, and fifth nodes (2, 2, 5) are skipped: 3 nodes. contains runs once per node, 6 times. seen grows at the front, so it holds 9 → 5 → 2. When the second node goes, prev stays on the first, so the fourth node's 2 is also skipped correctly after 5.

  6. 1 → 5 → 6 and 2 → 3 → 7 → 8 are combined with merge. How many comparisons does the main loop make, and which elements are appended without comparison?

    Answer

    Comparisons: 1 ≤ 2 (1 appended), 5 ≤ 2 false (2), 5 ≤ 3 false (3), 5 ≤ 7 (5), 6 ≤ 7 (6). The first list is exhausted: 5 comparisons. 7 and 8 are appended without comparison, giving 1 → 2 → 3 → 5 → 6 → 7 → 8.

  7. On the doubly linked list 3 ⇄ 6 ⇄ 9 we call remove(3), removeLast(), and addFirst(1). Which branch of remove and of removeLast runs in each call? What do forward and backward reading give at the end?

    Answer

    remove(3): 3 is the head (temp.prev is null), so else head = temp.next runs; the right neighbor 6 exists, so 6.prev becomes null: 6 ⇄ 9. removeLast(): head != tail, general branch; tail moves to 6, 6.next = null. addFirst(1): 1 ⇄ 6. Forward: 1 6; backward: 6 1.

  8. In 1 → 2 → 3 → 4 → 5 → 6 → 7, node 7 points back to 5. In which iteration, and at which node, does hasCycle return true? On the cycle-free list 1 → 2 → 3 → 4 → 5, after how many iterations does it return false?

    Answer

    (slow, fast) per iteration: (2, 3), (3, 5), (4, 7), (5, 6), (6, 5), (7, 7) — they meet at 7 in iteration 6. Here μ = 4, λ = 3: when the slow pointer enters in iteration 4, the fast one is at 6, two behind, and they meet two iterations later. Without a cycle the fast pointer goes 1 → 3 → 5; after iteration 2, fast.next is null and the method returns false.

  9. On the circular list 4 → 7 → 2 → (4) (tail = 2) we call removeLast() and then addFirst(9). How many times does the loop in removeLast advance? What does print() output at the end, and which node is tail?

    Answer

    temp starts at 4; its successor 7 isn't tail, so it advances once, and 7's successor is tail. 7 is linked to 4 and becomes tail: 4 → 7 → (4). addFirst(9): 9 points to 4, 7 to 9, tail unchanged. print() outputs 9 4 7; tail is 7.

  10. A 3×3 matrix is turned into a linked structure with build. How many nodes are created, and how many right and down links are non-null? How many nodes does a recursive version create that calls build(i, j+1) and build(i+1, j) directly, without the table d?

    Answer

    build creates 9 nodes, with 3 · 2 = 6 right and 2 · 3 = 6 down links. The recursive version creates a cell once per right-down path from the top left: row by row 1, 1, 1 / 1, 2, 3 / 1, 3, 6, or 19 nodes.

5.11Further reading

  • M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Data Structures and Algorithms in Java (6th ed., 2014), Chapter 3: singly linked, circular, and doubly linked lists with sentinels, in Java code very close to the ADT in these notes; rotate() and list copying are covered there too.
  • R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Section 1.3: linked lists as the basis for stack, queue, and bag implementations, with short, tidy code.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (3rd ed., 2009), Section 10.2: doubly linked lists and circular lists with a single sentinel, in pseudocode and more formal language.
  • D. E. Knuth, The Art of Computer Programming, Vol. 2 (3rd ed., 1997), Section 3.1, Exercise 6: among the first written sources to credit Floyd with cycle detection by slow and fast pointers.

5.12References

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009.
  2. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6th ed., Wiley, 2014.
  3. D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed., Addison-Wesley, 1997.
  4. R. Lafore, Data Structures and Algorithms in Java, 2nd ed., Sams, 2002.
  5. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.

Related pages: Chapter 5 slides · Study questions · Glossary · © Sercan Külcü. All rights reserved.