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.
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
nullin 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.
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,
nullin the last node. In Java “pointer” and “reference” mean the same thing; there is no pointer arithmetic as in C.
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.
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.
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 <.
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.
| Line | 10.next | 1.next | 8.next | 11.next | Chain from first |
|---|---|---|---|---|---|
first = new Node(10) | null | — | — | — | 10 |
second = new Node(1) | null | null | — | — | 10 |
third = new Node(8) | null | null | null | — | 10 |
fourth = new Node(11) | null | null | null | null | 10 |
first.next = second | node(1) | null | null | null | 10 → 1 |
second.next = third | node(1) | node(8) | null | null | 10 → 1 → 8 |
third.next = fourth | node(1) | node(8) | node(11) | null | 10 → 1 → 8 → 11 |
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.
| Operation | How it works | Time |
|---|---|---|
| Insert at front | The new node points to the old head and becomes the head. | O(1) |
| Insert at end | Walk to the last node; with a tail pointer, no walk is needed. | O(n) · O(1) |
| Remove from front | Move the head to the next node. | O(1) |
| Remove from end | The second-to-last node must be found. | O(n) |
| Search, print, length | Walk from front to back. | O(n) |
| Reverse, merge | One 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.
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.
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.| Goodrich–Tamassia | In these notes | Role | Time |
|---|---|---|---|
size(), isEmpty() | size(), isEmpty() | the size field is updated by every operation | O(1) |
first(), last() | first(), isEmpty() ? null : tail.data | return null on an empty list | O(1) |
addFirst, addLast | addFirst, addLast | both constant time with a tail pointer; inserting into an empty list also sets tail | O(1) |
removeFirst() | removeFirst() | returns the removed node | O(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.
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
intalso 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.
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.
| Step | temp | Condition temp != null | Printed in this step |
|---|---|---|---|
temp = head | node(10) | — | Linked List: |
| iteration 1 | node(10) → node(1) | true | 10 -> |
| iteration 2 | node(1) → node(8) | true | 1 -> |
| iteration 3 | node(8) → node(11) | true | 8 -> |
| iteration 4 | node(11) → null | true | 11 -> |
| loop ends | null | false | null |
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).
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.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.
- Start.
temp = head, that is, node(10);position = 0. - Iteration 1.
tempis notnull, so the loop is entered.10 == 8is false.positionbecomes 1 andtempmoves to node(1). - Iteration 2.
1 == 8is false.positionbecomes 2 andtempmoves to node(8). - Iteration 3.
8 == 8is true. The method executesreturn positionand 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.
| Iteration | temp | position | temp.data == 8 | Result |
|---|---|---|---|---|
| 1 | node(10) | 0 | false | advance |
| 2 | node(1) | 1 | false | advance |
| 3 | node(8) | 2 | true | return 2 |
search(8). (a) With position at 2, temp moves to node(8). (b) The comparison succeeds; 8 is at position 2.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.
| Call | Line | newNode | head | tail | size | List |
|---|---|---|---|---|---|---|
addFirst(11) | new Node(11) | 11 → null | null | null | 0 | empty |
newNode.next = head | 11 → null | null | null | 0 | empty | |
head = newNode | 11 | node(11) | null | 0 | 11 → null | |
tail = head; size++ | 11 | node(11) | node(11) | 1 | 11 → null | |
addFirst(8) | new Node(8) | 8 → null | node(11) | node(11) | 1 | 11 → null |
newNode.next = head | 8 → 11 | node(11) | node(11) | 1 | 11 → null | |
head = newNode | 8 | node(8) | node(11) | 1 | 8 → 11 → null | |
tail unchanged; size++ | 8 | node(8) | node(11) | 2 | 8 → 11 → null | |
addFirst(1) | new Node(1) | 1 → null | node(8) | node(11) | 2 | 8 → 11 → null |
newNode.next = head | 1 → 8 | node(8) | node(11) | 2 | 8 → 11 → null | |
head = newNode | 1 | node(1) | node(11) | 2 | 1 → 8 → 11 → null | |
tail unchanged; size++ | 1 | node(1) | node(11) | 3 | 1 → 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.
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).
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.
| Call | Branch | Nodes visited by temp | Link set | List |
|---|---|---|---|---|
addLast(10) | head == null | — | head = node(10) | 10 → null |
addLast(1) | walk | 10 (next is null, stop) | 10.next = node(1) | 10 → 1 → null |
addLast(8) | walk | 10 → 1 (next is null, stop) | 1.next = node(8) | 10 → 1 → 8 → null |
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.
tail is now 5. No node was visited.| Call | Line | head | tail | size | List |
|---|---|---|---|---|---|
addLast(10) | head = tail = newNode | node(10) | node(10) | 0 | 10 → null |
size++ | node(10) | node(10) | 1 | 10 → null | |
addLast(1) | tail.next = newNode | node(10) | node(10) | 1 | 10 → 1 → null |
tail = newNode | node(10) | node(1) | 1 | 10 → 1 → null | |
size++ | node(10) | node(1) | 2 | 10 → 1 → null | |
addLast(8) | tail.next = newNode | node(10) | node(1) | 2 | 10 → 1 → 8 → null |
tail = newNode | node(10) | node(8) | 2 | 10 → 1 → 8 → null | |
size++ | node(10) | node(8) | 3 | 10 → 1 → 8 → null |
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.
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.
On 10 → 1 → 8 → 11, addAt(5, 2) should put 5 third, between 1 and 8.
- Special case. The index is not 0, so this is not a front insertion.
- Walk.
temp = head(node 10); the loop runs index − 1 = 1 time.i = 0:0 < 1, sotempmoves to node(1).i = 1:1 < 1fails; the loop ends. - Check.
tempis node(1), notnull; the position is valid. - New node.
new Node(5). 1 still points to 8; the list is unchanged. - (1)
newNode.next = temp.next: 5 points to 8. The list is still unchanged, since nothing in it points to 5. - (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.
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.
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.
| Call | temp | New head | tail | Returned | List |
|---|---|---|---|---|---|
| 1st | node(10) | node(1) | node(11) | 10 | 1 → 11 → null |
| 2nd | node(1) | node(11) | node(11) | 1 | 11 → null |
| 3rd | node(11) | null | null | 11 | empty |
| 4th | — | null | null | null | empty |
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.
| Step | temp | temp.next.next | Decision |
|---|---|---|---|
| start | node(10) | node(8) | not null, advance |
| advance 1 | node(1) | node(11) | not null, advance |
| advance 2 | node(8) | null | stop: temp is second to last |
| unlink | temp.next = null, tail = temp: the list is 10 → 1 → 8 → null, tail = node(8) | ||
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.
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.
- Empty list: nothing to remove; return at once.
- Target at the head: the head has no predecessor, so it is handled separately.
headmoves on andsizedrops; if the list is now empty,tailis nulled too. - General case: start with
prev = head,temp = head.next. On a match,prev.next = temp.nextskips the node (andtailmoves toprevif it was the tail); otherwise both pointers advance. No match prints “Not found.”
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.remove(8) on the list 10 → 1 → 8 → 11.
- Special cases. The list isn't empty and the head, 10, isn't 8; both
ifs are passed. - Start.
prev= node(10),temp= node(1). - Iteration 1.
1 == 8is false.prevmoves to node(1),tempto node(8). - Iteration 2.
8 == 8is true.prev.next = temp.next: 1 now points to 11.tempisn't the tail, sotailstays.sizedrops 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.
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.
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: wherecurrent'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.
| Iteration | next | Link reversed | prev | current | Reversed part |
|---|---|---|---|---|---|
| start | null | — | null | node(10) | empty |
| 1 | node(8) | 10 → null | node(10) | node(8) | 10 → null |
| 2 | node(1) | 8 → 10 | node(8) | node(1) | 8 → 10 → null |
| 3 | node(11) | 1 → 8 | node(1) | node(11) | 1 → 8 → 10 → null |
| 4 | null | 11 → 1 | node(11) | null | 11 → 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.
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.
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.
Find the middle of 10 → 8 → 1 → 11 → 5 (five nodes).
- Start.
slowandfastare at node(10). - Iteration 1.
fast(10) and its successor (8) exist.slowmoves to 8,fasttwo steps to 1. - Iteration 2.
fast(1) and its successor (11) exist.slowmoves to 1,fastto 5. - End.
fast.nextisnull; the loop ends and the method returnsslow.data, 1.
In two iterations slow took 2 steps and fast 4. 1 is the third of five nodes — exactly the middle.
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).
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.
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.
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.
| Node | contains(v) | Action | prev (after) | seen | List |
|---|---|---|---|---|---|
| 3 (1st) | false | addFirst(3), prev advances | node(3) | 3 | 3 → 5 → 3 → 7 → 5 |
| 5 (2nd) | false | addFirst(5), prev advances | node(5) | 5 → 3 | 3 → 5 → 3 → 7 → 5 |
| 3 (3rd) | true | 5's link turns to 7; 3 is skipped | node(5) | 5 → 3 | 3 → 5 → 7 → 5 |
| 7 (4th) | false | addFirst(7), prev advances | node(7) | 7 → 5 → 3 | 3 → 5 → 7 → 5 |
| 5 (5th) | true | 7's link becomes null; the node was the tail, so tail = prev | node(7) | 7 → 5 → 3 | 3 → 5 → 7 |
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.
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.
| Iteration | p1 | p2 | Comparison | Appended | result |
|---|---|---|---|---|---|
| 1 | 1 | 2 | 1 ≤ 2 true | 1 | 1 |
| 2 | 4 | 2 | 4 ≤ 2 false | 2 | 1 → 2 |
| 3 | 4 | 3 | 4 ≤ 3 false | 3 | 1 → 2 → 3 |
| 4 | 4 | 8 | 4 ≤ 8 true | 4 | 1 → 2 → 3 → 4 |
| 5 | 7 | 8 | 7 ≤ 8 true | 7 | 1 → 2 → 3 → 4 → 7 |
| remainder | null | 8 | — (main loop done) | 8 | 1 → 2 → 3 → 4 → 7 → 8 |
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.
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.
current | other | Comparison | Swap | List |
|---|---|---|---|---|
| node 1 | node 2 | 4 > 1 | yes | 1 → 4 → 3 → 2 |
| node 1 | node 3 | 1 > 3 | no | 1 → 4 → 3 → 2 |
| node 1 | node 4 | 1 > 2 | no | 1 → 4 → 3 → 2 |
| node 2 | node 3 | 4 > 3 | yes | 1 → 3 → 4 → 2 |
| node 2 | node 4 | 3 > 2 | yes | 1 → 2 → 4 → 3 |
| node 3 | node 4 | 4 > 3 | yes | 1 → 2 → 3 → 4 |
| node 4 | null | — | — | 1 → 2 → 3 → 4 |
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.
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
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.
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.
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.
| Line | 1.prev | 1.next | 10.prev | head |
|---|---|---|---|---|
new Node(1) | null | null | null | node(10) |
newNode.next = head | null | node(10) | null | node(10) |
head.prev = newNode | null | node(10) | node(1) | node(10) |
head = newNode | null | node(10) | node(1) | node(1) |
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.
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.
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:
newNode.next = temp.next: the new node points to its right neighbor.newNode.prev = temp: the new node points to its left neighbor.temp.next.prev = newNode: the right neighbor's backward link turns to the new node.temp.next = newNode: the left neighbor's forward link turns to the new node.
addAt(12, 2) on 1 ⇄ 10 ⇄ 15 ⇄ 25.
- Walk.
tempadvances index − 1 = 1 step to node(10), which is not the last node. - (1) 12.next = 15. No node in the list points to 12 yet.
- (2) 12.prev = 10.
- (3)
temp.nextis still 15; 15.prev becomes 12. - (4) 10.next becomes 12.
Forward the list reads 1, 10, 12, 15, 25; backward, 25, 15, 12, 10, 1. Four links changed.
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.
| Operation | Line | Effect | List |
|---|---|---|---|
removeFirst(), 1 ⇄ 10 ⇄ 15 | head = head.next | head moves to 10 | (10 still points back to 1) |
head.prev = null | 10's backward link is cleared | 10 ⇄ 15 | |
removeLast(), 1 ⇄ 10 ⇄ 15 ⇄ 25 | tail = tail.prev | tail moves to 15 | (15 still points forward to 25) |
tail.next = null | 15's forward link is cleared | 1 ⇄ 10 ⇄ 15 |
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.
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.
| Step | temp | Check | Action |
|---|---|---|---|
| search | node(1) | 1 ≠ 15 | advance |
| search | node(10) | 10 ≠ 15 | advance |
| search | node(15) | 15 == 15 | loop ends |
| left | node(15) | temp.prev = 10, not null | 10.next = 25 |
| right | node(15) | temp.next = 25, not null | 25.prev = 10 |
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.
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.
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.
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.
On an empty list with sentinels we call addFirst(10) and addFirst(5), then remove 10's node with remove.
- Start.
header.next = trailer,trailer.prev = header,size = 0. addFirst(10). This callsaddBetween(10, header, trailer), since in the empty listheader.nextis the trailer. Four assignments: 10.prev = header, 10.next = trailer, header.next = 10, trailer.prev = 10.size = 1.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.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.
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.
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).
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.
| (i, j) | New node | right | down |
|---|---|---|---|
| (1, 2) | 6 | none (last column) | none (last row) |
| (1, 1) | 5 | 6 | none (last row) |
| (1, 0) | 4 | 5 | none (last row) |
| (0, 2) | 3 | none (last column) | 6 |
| (0, 1) | 2 | 3 | 5 |
| (0, 0) | 1 | 2 | 4 |
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.
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
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.
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.
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.
| Step | current | current != tail | Printed |
|---|---|---|---|
| start | node(1) | — | — |
| iteration 1 | node(1) | true | 1 |
| iteration 2 | node(8) | true | 8 |
| iteration 3 | node(10) | true | 10 |
| loop ends | node(16) | false | — |
| last line | node(16) | — | 16 |
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 returnsfalse. - 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 == fastand the method returnstrue.
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. □
The list is 1 → 2 → 3 → 4 → 5 → 6, and 6 points back to 3.
- Iteration 1.
slowreaches 2,fast3. 2 ≠ 3. - Iteration 2.
slowreaches 3,fast5. 3 ≠ 5. - Iteration 3.
slowreaches 4;fastgoes 5 → 6 and, via the cycle link, to 3. 4 ≠ 3. The fast pointer has lapped the cycle and trails by one node. - Iteration 4.
slowreaches 5;fastgoes from 3 to 4 to 5. 5 == 5: the method returnstrue.
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.
| Iteration | slow | fast | slow == fast |
|---|---|---|---|
| start | 1 | 1 | (not tested) |
| 1 | 2 | 3 | no |
| 2 | 3 | 5 | no |
| 3 | 4 | 3 | no |
| 4 | 5 | 5 | yes → true |
At most n/2 iterations without a cycle and n with one: O(n) time. Only two pointers: O(1) extra memory.
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.
| Call | Assignments | tail | Ring | size |
|---|---|---|---|---|
addLast(1) | tail = temp; tail.next = tail | node(1) | 1 → (1) | 1 |
addLast(8) | 8 → 1; 1 → 8; tail = 8 | node(8) | 1 → 8 → (1) | 2 |
addLast(10) | 10 → 1; 8 → 10; tail = 10 | node(10) | 1 → 8 → 10 → (1) | 3 |
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.
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).
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.
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).| Step | temp | temp.next == tail | Decision |
|---|---|---|---|
| start | node(1) | no (8) | advance |
| advance 1 | node(8) | no (10) | advance |
| advance 2 | node(10) | yes (16) | stop |
| relink | 10.next = 1; tail = 10; size 3: ring 1 → 8 → 10 → (1) | ||
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.
| Turn | Served (tail.next) | tail after rotate() | New head |
|---|---|---|---|
| 1 | 1 | 1 | 8 |
| 2 | 8 | 8 | 10 |
| 3 | 10 | 10 | 1 |
| 4 | 1 | 1 | 8 |
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).
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.
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.
| Criterion | Array | Linked list |
|---|---|---|
| Access to element i | O(1): address computed | O(n): walk from head |
| Insert / remove at front | O(n): shifting | O(1) |
| Insert after a known position | O(n) | O(1): two links |
| Size | fixed; growing is an O(n) copy | dynamic, one new per insertion |
| Overhead and cache | unused capacity; cache-friendly | a 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.
| Operation | Singly (head only) | Singly (head + tail) | Doubly (head + tail) | Circular (tail only) |
|---|---|---|---|---|
| Insert at front | O(1) | O(1) | O(1) | O(1) |
| Insert at end | O(n) | O(1) | O(1) | O(1) |
| Remove from front | O(1) | O(1) | O(1) | O(1) |
| Remove from end | O(n) | O(n) | O(1) | O(n) |
| Search / element i | O(n) | O(n) | O(n) | O(n) |
| Remove a known node | O(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.
| Bug | What happens | Fix |
|---|---|---|
| No empty-list check | head.data or head.next while head is null: NullPointerException. | if (head == null) return; |
| Setting links in the wrong order | If 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 traversing | The list is unreachable after printing. | Traverse with Node temp = head;. |
Forgetting tail | After 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 list | If 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 list | A ring has no null: infinite loop. | while (p != tail) … |
Not updating size in some methods | size() 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 throughhead. 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; whiletemp != null, work;temp = temp.next. Printing, length, and search are variations;temp.next != nullstops 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(andsize). - 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 = headis 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
nullchecks andhead/tailupdates. - A linked structure from a matrix gives each node
rightanddownlinks. 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
tailis kept, and the head istail.next. Appending, front insertion and removal, and rotation are O(1); removal from the end is O(n). Traversal stops attail, notnull. 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.
- linked list
- node
- head
- tail
- pointer
- reference
- null
- singly linked list
- doubly linked list
- circularly linked list
- traversal
- sentinel
- cycle detection
- abstract data type (ADT)
- generic
- deep copy
- shallow copy
- swap
- merge sort
- hash table
- matrix
- round robin
- time complexity
- space complexity
5.10Test Yourself
On an empty
SinglyLinkedList(keepingheadandtail) we calladdLast(4),addFirst(2),addLast(9),addAt(7, 1), andremoveFirst(). 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 withtailstill 9.What do
search(6)andsearch(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.reverse()runs on 5 → 2 → 7. At the end of the second iteration, what areprev,current, and the reversed part? What are the final list andtail?Answer
Iteration 1 turns 5's link to
null(prev5,current2); iteration 2 turns 2's link to 5 (prev2,current7). The reversed part is 2 → 5 → null; 7's link is stillnull. After iteration 3,head = prevgives 7 → 2 → 5. The first line settailto the old head, 5.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.nextis thennull, and 4 is returned. Second list: (8, 7), (7, null), returning 7, the second middle. For the first middle (8), usefast.next != null && fast.next.next != null; one iteration runs andslowstays at 8.removeDuplicates()runs on 2 → 2 → 5 → 2 → 5 → 9. What is the result, how many nodes are skipped, how many times iscontainscalled, and what doesseenhold at the end?Answer
The result is 2 → 5 → 9. The second, fourth, and fifth nodes (2, 2, 5) are skipped: 3 nodes.
containsruns once per node, 6 times.seengrows at the front, so it holds 9 → 5 → 2. When the second node goes,prevstays on the first, so the fourth node's 2 is also skipped correctly after 5.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.
On the doubly linked list 3 ⇄ 6 ⇄ 9 we call
remove(3),removeLast(), andaddFirst(1). Which branch ofremoveand ofremoveLastruns in each call? What do forward and backward reading give at the end?Answer
remove(3): 3 is the head (temp.previsnull), soelse head = temp.nextruns; the right neighbor 6 exists, so 6.prev becomes null: 6 ⇄ 9.removeLast():head != tail, general branch;tailmoves to 6, 6.next = null.addFirst(1): 1 ⇄ 6. Forward: 1 6; backward: 6 1.In 1 → 2 → 3 → 4 → 5 → 6 → 7, node 7 points back to 5. In which iteration, and at which node, does
hasCyclereturntrue? On the cycle-free list 1 → 2 → 3 → 4 → 5, after how many iterations does it returnfalse?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.nextisnulland the method returnsfalse.On the circular list 4 → 7 → 2 → (4) (
tail= 2) we callremoveLast()and thenaddFirst(9). How many times does the loop inremoveLastadvance? What doesprint()output at the end, and which node istail?Answer
tempstarts at 4; its successor 7 isn'ttail, so it advances once, and 7's successor istail. 7 is linked to 4 and becomestail: 4 → 7 → (4).addFirst(9): 9 points to 4, 7 to 9,tailunchanged.print()outputs9 4 7;tailis 7.A 3×3 matrix is turned into a linked structure with
build. How many nodes are created, and how manyrightanddownlinks are non-null? How many nodes does a recursive version create that callsbuild(i, j+1)andbuild(i+1, j)directly, without the tabled?Answer
buildcreates 9 nodes, with 3 · 2 = 6rightand 2 · 3 = 6downlinks. 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
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009.
- M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6th ed., Wiley, 2014.
- D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed., Addison-Wesley, 1997.
- R. Lafore, Data Structures and Algorithms in Java, 2nd ed., Sams, 2002.
- R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.
Related pages: Chapter 5 slides · Study questions · Glossary · © Sercan Külcü. All rights reserved.