Theory
Request number 101
BookBridge queues issue requests in an array:
String[] queue = new String[100];
Exam week arrives. Request 101 shows up, and the array is full: in Java, an array's size is fixed at birth. Worse, when the first request is served, shifting 99 entries forward is real work, every single time.
What the queue wants is to grow one request at a time and shed served ones instantly. Arrays cannot. This unit builds what can, out of nothing but Java classes.
Theory
A treasure hunt, not a shelf
An array is a shelf with numbered slots: to find slot 47 you jump straight there, but the shelf's length is welded.
A linked structure is a treasure hunt: each clue holds one prize (the data) and directions to the next clue. Add a clue anywhere by rewriting one direction; remove one the same way. No shelf, no welding, just clues that know where the hunt continues. The last clue says: hunt over.
Theory
The self-referential class
The clue, in Java, is a class that refers to its own type:
class Node {
String title; // the data (one request)
Node next; // reference to the NEXT node
}
Read Node next carefully: it is a reference, an address slot, not a Node stuffed inside a Node. That is why this compiles without creating an infinite Russian doll: the object holds directions to another object, not the object itself.
next == null means: hunt over, end of chain.
Practical
Forging the first chain by hand
class Node {
String title;
Node next;
Node(String t) { title = t; } // next starts as null (field default)
}
public class IssueQueue {
public static void main(String[] args) {
Node first = new Node("Let Us C");
Node second = new Node("Java Complete Reference");
first.next = second; // one assignment: the chain forms
// second.next is already null: end of the chain
System.out.println(first.title);
System.out.println(first.next.title); // reached VIA the link
}
}
At a glance
Array vs linked chain
| Aspect | Array | Linked chain |
|---|---|---|
| Size | Fixed at creation | Grows and shrinks one node at a time |
| Insert/delete in front | Shift everything | Re-link 1 or 2 references |
| Reach the i-th item | Instant: queue[i] | Walk the chain from the start |
| Memory | One solid block, possibly half empty | Exactly one node per item, plus link slots |
Think first
The Russian-doll worry
A classmate objects: "class Node contains a Node, which contains a Node... surely one new Node("x") allocates an infinite tower?" Before tapping: what is wrong with that picture?
Show the answer
The field is a reference, not an embedded object. new Node("x") allocates ONE node: its title slot and one address-sized next slot, which starts as null (a field default from Unit 2). Nothing else is built until you explicitly create and link it. In BCA304's C++ this was struct Node { Node* next; }: the asterisk made the indirection visible. Java references are the same indirection with the syntax hidden, and no pointer arithmetic allowed.
Quiz
In a chain of Nodes, how does the program know it has reached the last node?
- Its next reference is null
- Its title field is empty
- Java throws an exception at the last node
- The Node class stores the chain's total length
Show the answer
Its next reference is null
null in the next slot is the agreed full stop: no further clue. That convention drives every loop in the coming lessons: while (cur != null) walks a chain, and cur.next == null finds its tail. Option B confuses data with structure; a request's title says nothing about position. Option C is what happens when you IGNORE the null and call cur.next.title one step too far: NullPointerException. Option D describes bookkeeping a plain node deliberately does not carry.
Watch out
Two ways to hurt a chain
Walking off the end: cur.next.title when cur is already the last node dereferences null: NullPointerException, the chain-builder's signature crash. Check before you step.
Dropping the only reference: in this listing, first is the sole handle to the whole chain. Overwrite it (first = null) and both nodes become unreachable; the garbage collector reclaims them. No delete in Java, but you can still LOSE a structure by letting go of its head.
Theory
One class, many structures
Everything in this unit, and half of every data-structures course after it, is this one idea dressed differently: nodes plus links. String the nodes in a line and you have the singly linked list (next lesson); bend the last link back to the start and it becomes circular (the unit's finale). BCA304's stacks and queues can all be rebuilt on it. Learn the node once, deeply; the rest is arranging clues.
Summary
Key takeaways
- Data structures are built from a self-referential class: data fields plus a next reference of the same type.
- next is a reference (an address), not an embedded object: no infinite nesting, one node per new.
- Chains form by assignment (first.next = second); null in next marks the end.
- Arrays are fixed and shift-heavy; chains grow per node and re-link cheaply, but must be walked to be searched.
- Dereferencing null (one step past the end) throws NullPointerException.
- Losing the head reference loses the whole chain to garbage collection.
- Memory hook: each node is a clue: one prize, one direction to the next.