Chapter 13: Data Structures
In the 1920s the Polish logician Jan Łukasiewicz was looking for a way to write logical formulae without brackets. His solution was to place every operator in front of the things it acted on, so that the order of the symbols by itself decided the order of the work. It was an elegant idea in logic, and for the next thirty years it stayed in logic.
Then the machines arrived, and with them a very ordinary problem. A computer handed the expression A + B * C has to work out which operation comes first, keep track of brackets, and hold on to half-finished results while it goes looking for the rest. In the late 1950s the Australian philosopher Charles Hamblin proposed reversing Łukasiewicz’s notation — operators written after their operands — and observed that a machine could evaluate such an expression using a very simple kind of memory: one that could be reached at a single end only. In Germany at about the same time, Friedrich Bauer and Klaus Samelson were building expression evaluation on exactly such a store.
Nobody had invented a new kind of memory. They had only restricted how an ordinary block of memory could be used, and the restriction turned out to be the whole idea. Fig. 13.0-1 shows two such restrictions side by side.
Diagram
Fig. 13.0-1 – two panels side by side. Left panel: a vertical container closed at the bottom and open at the top, holding four stacked cells; a curved arrow entering the open top labelled “in” and a curved arrow leaving the same open top labelled “out”; the closed lower end labelled “closed end”; caption under the panel “one end only”. Right panel: a horizontal channel open at both ends, holding four cells in a row; an arrow entering from the right end labelled “in”, an arrow leaving from the left end labelled “out”; caption under the panel “in at one end, out at the other”
This chapter answers all five.
13.1 Data Structures and Abstract Data Types
13.1.1 Why a Program Needs a Data Structure
You already know how to keep many values of the same type together. An array does it: fifty marks in int m[], reached by an index. The array is fast, it is simple, and for a great many problems it is exactly right.
But an array offers you everything at once. Any cell can be read, any cell can be written, at any moment. That freedom is useful when you want it and dangerous when you do not.
Think of a school library counter at the start of a period. Students arrive, join the line, and are served in the order they arrived. Now suppose the counter clerk had an “array” of students and could serve any of them at will. Nothing in the arrangement would stop the last arrival being served first. The fairness of the queue does not come from the students; it comes from the rule about who may be served.
A data structure is that combination: a way of holding data in memory together with a fixed rule about how the data may be put in and taken out.
Storage, and the discipline placed on it
The word “structure” is doing real work in that definition. Two structures can hold identical values in identical memory and still behave completely differently, because they permit different operations.
This chapter deals with structures whose elements sit one after another in a single sequence — a first element, a second, and so on to a last. Such a structure is called a linear data structure. The stack, the queue, the circular queue, the dequeue and the single linked list are all linear. The tree, which arrives at the end of the chapter, is not.
13.1.2 The Abstract Data Type
Ask what a queue is and there are two quite different answers.
The first answer describes behaviour: a queue holds items; you may add an item at the rear; you may remove the item at the front; you may ask whether it is empty. Nothing there says how the items are stored.
The second answer describes machinery: the items sit in an int array of capacity 20, two integers front and rear mark the ends, and removing an item means reading q[front] and moving front forward one place.
The first answer is the abstract data type (ADT). The second is one implementation of it.
Why bother separating them? Because everything that uses the queue depends on the first answer only. A program that adds jobs to a print list and removes them in turn needs to know that removal takes the oldest job. It does not need to know whether the jobs sit in an array or somewhere else entirely. If you later change the storage, that program should not have to change at all.
The syllabus states this plainly: data structures are to be defined as abstract data types with a well-defined interface. Keeping the two apart also keeps a common confusion at bay.
| Feature | Abstract data type | Data structure |
|---|---|---|
| What it states | The operations permitted and what each one does | How the data is actually stored and how each operation is carried out |
| Level | A specification, written for the user of the structure | An implementation, written for the machine |
| Storage mentioned | No | Yes — arrays, fields, links, capacities |
| How many can exist | One ADT | Many different structures can implement the same ADT |
| Expressed in Java as | An interface |
A class that implements the interface |
| Changing it | Forces every program that uses the structure to change | Can be changed silently, provided the operations still behave as promised |
13.1.3 Defining a Data Structure Through a Java Interface
Java gives you a construct that holds a specification and nothing else. An interface lists method headings with no bodies; any class that claims to implement the interface must supply a body for every one of them.
Be careful with the word. In ordinary technical English, “interface” loosely means the set of operations something offers — a class has an interface in that sense whether or not the keyword appears anywhere. In Java, interface is a specific language construct. This section uses the language construct, and it is the construct the syllabus asks for.
Here is a small ADT written that way. It describes a collection of marks that can be added to, counted and averaged.
interface Marks
{
void record(int m);
boolean isEmpty();
int count();
double average();
}Read what this does and does not say. It says a mark can be recorded, that the collection can report emptiness, that it can report how many marks it holds, and that it can report their average. It says nothing about arrays, capacities or loops. Anyone reading only this file knows exactly how to use a Marks, and nothing at all about how one is built.
Methods declared in an interface are automatically public, so a class implementing the interface must declare each of them public too. Leaving the word out is the commonest slip here, and the message the compiler gives is not obvious the first time you meet it.
13.1.4 Multiple Implementations of the Same Interface
The point of writing the specification separately is that more than one class can satisfy it. Fig. 13.1-1 shows the shape of the arrangement: one interface above, two unrelated classes below, each promising to provide everything the interface lists.
Diagram
Fig. 13.1-1 – three boxes. Top box labelled “interface Marks”, listing inside it the four method headings record(int), isEmpty(), count(), average(). Below it, two separate boxes side by side, the left labelled “class MarkList” with the note “stores every mark in an array” and the right labelled “class MarkTally” with the note “stores only a count and a running total”. A dashed arrow rises from each lower box to the top box, each arrow labelled “implements”
The two classes below are not variations of one another. MarkList keeps every mark it is given. MarkTally keeps no marks at all — it adds each one into a running total and forgets it. Both can answer every question the interface asks them to answer, and a program written against Marks cannot tell which it is holding.
The two implementations are not equally good
They agree on every answer here, but they are not interchangeable in every situation, and it is worth being honest about the difference.
MarkTally uses two integers no matter how many marks arrive, and computes its average in a single division. MarkList uses one array cell per mark and adds up the whole array every time an average is asked for — one addition per mark stored. On memory and on speed, the tally wins.
But MarkList still holds the marks. Ask it for the highest mark, or how many students scored above the average, and it can answer; a new method would do it. MarkTally cannot, at any price, because the individual marks are gone. It also has no capacity limit, while MarkList refuses marks once its array is full.
That is the ordinary shape of a design choice in this subject. A structure that stores less is cheaper and answers fewer questions. Choosing between them is not a matter of one being correct — it is a matter of knowing which questions you will be asked.
13.2 The Stack
13.2.1 The Last In First Out Discipline
An examiner marking a bundle of answer scripts puts each finished script face down on a pile. When a colleague asks to see one, the script that comes off is the one that went down last. The pile is not sorted, not indexed and not searched. It has exactly one working surface, and everything enters and leaves through it.
The undo command in a text editor behaves the same way. Every change you make is remembered; pressing undo reverses the most recent one first, then the one before it. Undo cannot reach into the middle of your editing history and reverse a change from ten minutes ago while leaving the later ones intact.
A stack is this arrangement made into a data structure.
The single working end is called the top of the stack. The other end is closed. Because the element that goes in last is the one that comes out first, a stack is said to follow the last in first out (LIFO) principle.
Fig. 13.2-1 shows a stack held inside an array of six cells after three elements have been placed in it.
Diagram
Fig. 13.2-1 – an array of six cells drawn as a vertical column, indices written to the right of each cell from 0 at the bottom to 5 at the top. Cells 0, 1 and 2 contain 15, 28 and 37; cells 3, 4 and 5 are empty. A horizontal arrow on the left points at cell 2, labelled “top”. The bottom of the column is marked “closed end”. Above the column, two curved arrows at the same opening, one pointing down into the column labelled “push” and one pointing up out of it labelled “pop”
Notice what is being given up. The array underneath is an ordinary array and cell 0 is perfectly reachable; the stack simply refuses to reach it. That refusal is not a weakness to be worked around — it is the reason the structure is useful, because it guarantees the order in which things come back out.
| Feature | Array | Stack |
|---|---|---|
| Where an element may be inserted | At any index within the array | At the top only |
| Where an element may be removed | At any index within the array | At the top only |
| How an element is reached | Directly, by its index | Only by removing everything above it |
| What decides the order of removal | The programmer, freely | The order of insertion, reversed |
| What you must remember to use it | The index of every element you care about | One index — the top |
| Typical use | Storing a fixed collection to be examined in any order | Storing work that must be undone or completed in reverse order |
13.2.2 Push and Pop
The two operations of a stack have fixed names. Placing an element on the stack is called a push; removing the topmost element is called a pop.
Both are described most clearly against an array st and an integer top that holds the index of the topmost element. When the stack is empty there is no topmost element, so top is set to −1 — one less than the first valid index. This convention matters, and every method in the class must agree on it: top always names the cell holding the topmost element, never the next free cell.
Work out the method before writing any Java.
Popping reverses the movement, and the order of the two steps is not interchangeable.
Step 2 must come before step 3. Read the value while top still points at it; lower top afterwards.
13.2.3 Overflow, Underflow and Checking Emptiness
A stack built inside an array has a fixed capacity, so two boundary situations arise, and both must be tested for rather than allowed to happen.
If top has reached the last index of the array, there is no free cell above it and a push cannot be carried out. This is called stack overflow. If top is −1 there is no topmost element and a pop cannot be carried out. This is called stack underflow. Fig. 13.2-2 shows both boundary states.
Diagram
Fig. 13.2-2 – two vertical arrays of four cells side by side, indices 0 to 3 marked from bottom to top. Left array: all four cells filled with 15, 28, 37, 46; arrow pointing at cell 3 labelled “top = 3”; caption beneath “full — any push overflows”. Right array: all four cells empty; arrow pointing to the space just below cell 0 labelled “top = -1”; caption beneath “empty — any pop underflows”
Testing for emptiness deserves a method of its own rather than a comparison scattered through the code. A method isEmpty() that returns top == -1 states the intention in one place, and every other method can then be written to read almost like the algorithm it came from.
There is a further question a pop must answer: what should it return when the stack is empty? A method declared to return int has to return some int. The usual practice, and the one the ISC practical papers follow, is to return an agreed impossible value such as −9999 after printing the underflow message.
This is a workable convention and an imperfect one, and it is worth seeing why. If the stack is holding temperatures, or profits and losses, or any quantity that could legitimately be −9999, the caller cannot tell a real value from a failure report. The convention works because the values stored are usually known to lie in a smaller range — not because the design is sound in general.
13.2.4 Implementing a Stack Through a Class
Everything needed is now settled: the specification, the two algorithms and the two boundary tests. Following 13.1, the specification goes into an interface and the machinery into a class that implements it.
The loop in display() runs downwards from top to 0, so the stack is printed top first. Running it upwards would print the same elements in the reverse order and give a misleading picture of which one comes out next.
The last two lines of output are worth a second look. In System.out.println("Popped: " + s.pop()), the call to s.pop() is evaluated before anything is printed, so the underflow message that pop() prints appears on the line above the “Popped:” line, not below it.
| Call | top before |
top after |
Contents of st after (index 0, 1, 2) |
Printed |
|---|---|---|---|---|
push(15) |
−1 | 0 | 15, –, – | — |
push(28) |
0 | 1 | 15, 28, – | — |
push(37) |
1 | 2 | 15, 28, 37 | — |
display() |
2 | 2 | 15, 28, 37 | Top to bottom: 37 28 15 |
push(46) |
2 | 2 | 15, 28, 37 | Stack overflow |
pop() |
2 | 1 | 15, 28, 37 | returns 37 |
Result: after the six calls the stack holds 15 and 28 with top at 1. The trace shows the two things worth noticing about a stack in an array. The refused push changed nothing at all — top is untouched and no value was written. And the successful pop did not erase 37 from cell 2; it only lowered top, which is enough, because a cell above top is not part of the stack and will be overwritten by the next push.
13.2.5 Where Stacks Are Used
The stack turns up wherever work has to be finished, or undone, in the reverse of the order it was started.
The undo history of an editor is the plainest case. So is the back button of a web browser: each page you leave is pushed, and going back pops the most recent one. In both, the discipline matches the problem exactly — you never want to undo a change from the middle of the sequence while keeping the later ones.
A less visible case is the one your own programs already rely on. When a method is called, the point it must return to has to be remembered, and if that method calls another, the second return point must be remembered without losing the first. The returns then happen in reverse order of the calls, which is precisely LIFO. This is why the memory area holding those return points is called the call stack, and why a recursion with no base case eventually exhausts it.
13.3 Infix, Prefix and Postfix Notations
13.3.1 The Three Ways of Writing an Expression
Write A + B and you are following a habit so old that it feels like the only possibility: the operator sits between the two things it acts on. It is not the only possibility, and for a machine it is not the most convenient one.
There are three places an operator can be put relative to its operands, and each gives a complete notation. Throughout this section expressions are shown in a fixed-width form — A + B, AB+ — so that the exact order of the symbols is visible.
Infix notation puts the operator between its two operands: A + B, P * Q, M - N. This is ordinary mathematical writing.
Prefix notation puts the operator before its two operands: +AB, *PQ, -MN. It is also called Polish notation, after the Polish logician whose work introduced it.
Postfix notation puts the operator after its two operands: AB+, PQ*, MN-. Because it is the reverse arrangement of prefix, it is also called reverse Polish notation.
Diagram
Fig. 13.3-1 – three horizontal rows, each showing the same two operand boxes labelled A and B and one small operator box labelled +. Row 1 labelled “prefix”: operator box, then A, then B. Row 2 labelled “infix”: A, then operator box, then B. Row 3 labelled “postfix”: A, then B, then operator box. In each row a brace drawn under the two operand boxes is joined by a line to the operator box, showing which operands the operator acts on
Why the other two notations need no brackets
Now take an expression with two operators: A + B * C. Read it as infix and you have a genuine difficulty. The operand B sits between a + and a *, and nothing in the symbols says which of the two operators gets it. To settle the question you must either bring in an outside rule — that * is performed before + — or add brackets: A + (B * C).
That difficulty is created by the notation itself. An infix operator is separated from one of its operands by whatever else lies in between, so two operators can compete for the same operand.
Now write the same thing in postfix: ABC*+. Reading left to right, A, B and C are operands. The * comes immediately after B and C, so it takes those two. The + then comes after A and after the result of B * C, so it takes those two. There is nothing to decide, and no bracket could change the reading.
| Feature | Infix | Prefix | Postfix |
|---|---|---|---|
| Position of the operator | Between its two operands | Before both operands | After both operands |
| Other name | — | Polish notation | Reverse Polish notation |
A + B * C is written as |
A + B * C |
+A*BC |
ABC*+ |
| Brackets needed | Yes, wherever the intended order differs from the precedence rules | Never | Never |
| Precedence rules needed to read it | Yes | No | No |
| How it is processed | Must be converted before evaluation | Scanned right to left with a stack | Scanned left to right with a stack |
13.3.2 Precedence and Associativity in Conversion
Converting an infix expression means recovering the order the writer intended, and that order comes from two rules.
Precedence decides which operator acts first when two different operators compete for an operand. Associativity decides which acts first when two operators of the same precedence compete.
| Precedence | Operators | Associativity |
|---|---|---|
| Highest | ^ (exponentiation, also written ↑) |
Right to left |
| Middle | * and / |
Left to right |
| Lowest | + and - |
Left to right |
Brackets override both. Anything inside a bracket is settled before the bracket takes part in anything outside it.
Associativity is the rule students most often skip, and it changes answers. In A - B - C, the two subtractions have equal precedence and associate left to right, so the expression means (A - B) - C, not A - (B - C). Try it with 10, 4 and 3: the first reading gives 3, the second gives 9.
Exponentiation is the exception in the table, and it is the exception in mathematics too. A ^ B ^ C means A ^ (B ^ C), because ^ associates right to left.
13.3.3 Converting Infix to Postfix
The bracketing method
The most reliable way to convert by hand is to make the intended order visible before touching the symbols, in three steps.
First, put in every bracket the precedence and associativity rules imply, until each operator has exactly one pair of brackets around itself and its two operands. Second, working from the innermost bracket outwards, move each operator to just after its two operands. Third, remove all the brackets.
Take P + Q * R - S / T. Fully bracketed by the rules of Table 13.5, this is ((P + (Q * R)) - (S / T)). Fig. 13.3-2 shows the order in which the brackets are then resolved.
Diagram
Fig. 13.3-2 – the expression ((P + (Q * R)) - (S / T)) written across the top with each of its three bracket pairs underlined at a different depth. Three numbered stages listed below it: stage 1 “(Q * R) becomes QR” with an arrow to the rewritten expression ((P + QR) - (S / T)); stage 2”(P + QR) becomes PQR+” with an arrow to (PQR+ - (S / T)); stage 3 “(S / T) becomes ST/, then the outer bracket becomes PQR+ST/-” with an arrow to the final answer PQR*+ST/-
Working through the stages: (Q * R) becomes QR*; then (P + QR*) becomes PQR*+; then (S / T) becomes ST/; and finally the outermost bracket, whose two operands are now PQR*+ and ST/ with the operator -, becomes PQR*+ST/-.
Check the answer by reading it forwards. P, Q, R, then * takes Q and R; then + takes P and Q * R; then S, T, then / takes them; then - takes the two results. That is the expression we started with.
The stack method
A machine cannot bracket an expression by eye, so it uses a stack to hold operators whose fate is not yet decided. The idea is the one 13.2 ended on: when an operator arrives, you cannot yet know whether it should act, because a higher-precedence operator may be waiting further right. So you set it aside, and you take it back out when something arrives that settles the matter.
One refinement belongs with step 5. “Equal or higher precedence” is right for the left-associative operators, which is all of them except ^. Because ^ associates right to left, an incoming ^ pops only operators of strictly higher precedence — and since nothing outranks ^, it pops nothing.
| Symbol scanned | Stack, bottom to top | Output so far |
|---|---|---|
| — (start) | ( |
|
( |
( ( |
|
A |
( ( |
A |
+ |
( ( + |
A |
B |
( ( + |
AB |
) |
( |
AB+ |
* |
( * |
AB+ |
C |
( * |
AB+C |
- |
( - |
AB+C* |
D |
( - |
AB+C*D |
^ |
( - ^ |
AB+C*D |
E |
( - ^ |
AB+C*DE |
) |
empty | AB+C*DE^- |
Result: the postfix form is AB+C*DE^-. Two rows repay a second look. At the -, the stack held *, whose precedence is higher, so * was popped into the output before - was pushed. At the ^, the stack held -, whose precedence is lower, so nothing was popped — the - had to keep waiting, and it left the stack only at the final ).
Converting the same expression by the bracketing method gives ((A + B) * C) - (D ^ E), hence AB+, then AB+C*, then DE^, then AB+C*DE^-. The two methods agree, which is the check worth making whenever you are unsure.
13.3.4 Converting Infix to Prefix
The bracketing method converts to prefix just as well. Only the second step changes: instead of moving each operator to just after its two operands, move it to just before them.
Take the same expression, (A + B) * C - D ^ E. Fully bracketed it is (((A + B) * C) - (D ^ E)), and the brackets are resolved from the inside out exactly as before:
(A + B)becomes+AB(+AB * C)becomes*+ABC(D ^ E)becomes^DE- the outermost bracket, with operands
*+ABCand^DEand operator-, becomes-*+ABC^DE
So the prefix form is -*+ABC^DE.
Checking a prefix answer is done by reading right to left, or by unfolding from the left. Unfolding: the leading - needs two operands. The first is *+ABC, which is a * applied to +AB and C, that is (A + B) * C. The second is ^DE, that is D ^ E. So the whole is ((A + B) * C) - (D ^ E), which is where we started.
Two things are worth noticing about the two answers, AB+C*DE^- and -*+ABC^DE.
They are not reverses of one another. Reversing AB+C*DE^- gives -^EDC*+BA, in which the operands appear in the wrong order. It is the arrangement of operator and operands that reverses, not the string; the operands themselves keep their original left-to-right order in all three notations.
And in both answers the operators appear in the order in which they will be performed — in postfix reading left to right, in prefix reading right to left. That is not a coincidence; it is what makes both notations directly executable.
13.3.5 Evaluating a Postfix Expression With a Stack
Converting is only half the point. A postfix expression can be evaluated in a single left-to-right scan, with a stack holding values instead of operators.
Step 3 has a trap in it. The first value popped is the operand that stood on the right of the operator, because it was pushed later. Applying the operator the other way round costs nothing for + and * and is silently wrong for - and /.
| Symbol | Action | Stack after, bottom to top |
|---|---|---|
7 |
operand, push | 7 |
3 |
operand, push | 7, 3 |
2 |
operand, push | 7, 3, 2 |
* |
pop 2, pop 3, push 3 × 2 | 7, 6 |
- |
pop 6, pop 7, push 7 − 6 | 1 |
8 |
operand, push | 1, 8 |
4 |
operand, push | 1, 8, 4 |
/ |
pop 4, pop 8, push 8 ÷ 4 | 1, 2 |
+ |
pop 2, pop 1, push 1 + 2 | 3 |
Result: the final pop returns 3. The infix form of the expression is 7 - 3 * 2 + 8 / 4, which is indeed 7 − 6 + 2 = 3. Notice that the stack never held more than three values even though the expression has five operands — a value is consumed as soon as its operator arrives.
The stack is created with a capacity equal to the length of the expression. That is generous — the trace above never needed more than three cells — but it is guaranteed to be enough, since nothing can be pushed more often than there are symbols to read.
The class is honest only about correct input, and it is worth naming what it does not do. There is no check for underflow, so an ill-formed expression such as 7+ will stop the program with an array index error. There is no check that the final stack holds exactly one value. And the final else treats every unrecognised character as division, so a stray letter would be silently mistaken for a /. A program meant for real use would validate the expression before evaluating it; this one shows the method, not the defences.
One further point about the arithmetic: / on two int values is integer division, so 7 2 / yields 3, not 3.5. Changing the array and the method to double would fix that, and would change nothing else in the logic.
13.4 The Queue
13.4.1 The First In First Out Discipline
Three students send documents to the single printer in the school computer laboratory. The printer cannot print three things at once, so the jobs wait — and the one that arrives first is printed first. Nobody would accept a printer that printed the most recent job first and left the earliest one waiting indefinitely, yet that is exactly what a stack would do.
The lunch counter behaves the same way, and so does a railway reservation window. Arrivals join at the back; service happens at the front. The two ends do different jobs and neither can do the other’s.
A queue is this arrangement made into a data structure.
The end at which elements enter is the rear; the end from which they leave is the front. Because the element that goes in first is the one that comes out first, a queue is said to follow the first in first out (FIFO) principle.
Diagram
Fig. 13.4-1 – an array of six cells drawn as a horizontal row, indices 0 to 5 written beneath the cells. Cells 1, 2 and 3 contain 101, 102 and 103; cells 0, 4 and 5 are empty. An arrow above cell 1 labelled “front”, an arrow above cell 3 labelled “rear”. An arrow entering the row from the right at cell 4 labelled “insertion”, an arrow leaving the row to the left from cell 1 labelled “deletion”
Two position markers are needed rather than one. A stack could get by with top alone, because both operations happened there. A queue has two working ends, so it needs front and rear, and they move independently — and, as 13.4.4 will show, that independence is the source of the structure’s one real weakness.
| Feature | Stack | Queue |
|---|---|---|
| Principle | Last in first out (LIFO) | First in first out (FIFO) |
| Where insertion happens | At the top | At the rear |
| Where deletion happens | At the top | At the front |
| Position markers needed | One, top |
Two, front and rear |
| Which element leaves next | The most recently inserted | The longest present |
| Order in which items come out | The reverse of the order they went in | The same as the order they went in |
| Suits problems where | Work must be undone or completed in reverse | Work must be served in the order it arrived |
13.4.2 Insertion and Deletion
The two operations are called insertion and deletion. They are also called enqueue and dequeue respectively, and that second pair of names needs a warning: the syllabus’s fourth structure, met in 13.6, is itself called a dequeue. To keep the two apart, this chapter says insertion and deletion for the operations, and keeps the word dequeue for the structure.
As with the stack, both markers are set to −1 when the queue is empty, and the queue is empty exactly when front is −1.
Step 3 is the step that gets left out, and leaving it out does not fail immediately.
13.4.3 Implementing a Queue Through a Class
The last three lines of output are the interesting ones, and they are the subject of 13.4.4. The queue held two elements and had two free cells, yet the insertion was refused.
| Call | front before |
rear before |
front after |
rear after |
Contents of q after (0, 1, 2, 3) |
Printed |
|---|---|---|---|---|---|---|
insert(101) |
−1 | −1 | 0 | 0 | 101, –, –, – | — |
insert(102) |
0 | 0 | 0 | 1 | 101, 102, –, – | — |
insert(103) |
0 | 1 | 0 | 2 | 101, 102, 103, – | — |
display() |
0 | 2 | 0 | 2 | 101, 102, 103, – | Front to rear: 101 102 103 |
delete() |
0 | 2 | 1 | 2 | 101, 102, 103, – | returns 101 |
delete() |
1 | 2 | 2 | 2 | 101, 102, 103, – | returns 102 |
Result: the queue now holds one element, 103, with both markers at 2. The trace shows the two markers behaving quite differently from a stack’s single top. Insertion moved only rear; deletion moved only front. Neither deletion erased anything — cells 0 and 1 still hold 101 and 102 — but both cells now lie behind front, and nothing in this class will ever look at them again.
13.4.4 The Limitation of a Simple Queue
Look again at what happened at the end of the demonstration. The queue had capacity 4. It held 103 and 104 in cells 2 and 3, with cells 0 and 1 standing empty. The insertion of 105 was refused.
The refusal is not a mistake in the program. It is exactly what isFull() was written to test: rear == q.length - 1. And that test is the only one available, because insert() can put an element in one place only — the cell just after rear. Once rear has reached the last cell of the array, there is no such cell, whatever is going on at the other end. Fig. 13.4-2 shows the position.
Diagram
Fig. 13.4-2 – an array of four cells drawn as a horizontal row, indices 0 to 3 written beneath. Cells 0 and 1 empty and shaded, cells 2 and 3 containing 103 and 104. An arrow above cell 2 labelled “front”, an arrow above cell 3 labelled “rear”. An arrow arriving from the right beyond cell 3 labelled “105” is drawn crossed out. A caption beneath the two shaded cells reads “free, but unreachable”
The word “full” is therefore a misnomer for a simple queue. isFull() does not report that the queue has no room; it reports that the rear has run out of array. Those were the same thing at the start, and they stop being the same thing the moment the first deletion happens.
The effect worsens with use. Every deletion moves front one place forward and abandons a cell permanently. A simple queue of capacity 100 that has served 100 tokens is finished, no matter how few tokens it is holding at that moment. Its usable capacity is not 100 elements at a time; it is 100 elements in total, ever.
There are two honest ways out. One is to abandon the array and hold the elements in a structure that can grow and shrink at either end without moving anything — that is the linked list of 13.7. The other is to keep the array and stop treating its last cell as the end of the road, by letting rear wrap round to the beginning. That is the circular queue, and it is the subject of 13.5.
13.5 The Circular Queue
13.5.1 Wrapping the Front and Rear Pointers
The waste described in 13.4.4 comes from a single assumption: that the cell after the last cell of the array does not exist. Drop that assumption — decide that the cell after the last one is the first one — and the whole difficulty disappears.
Nothing about the array changes. The array is still a straight run of cells in memory, and cell 3 is still followed in memory by nothing at all. What changes is the arithmetic used to move the markers. Instead of
rear = rear + 1;the class writes
rear = (rear + 1) % q.length;The remainder operator does all the work. For an array of length 4, this gives 1, 2, 3 and then 0 again — the marker walks round the array endlessly instead of falling off the end. A queue whose markers move this way is called a circular queue.
It is helpful to draw the array as a ring, as in Fig. 13.5-1, but this is a picture of the arithmetic and not of the memory.
Diagram
Fig. 13.5-1 – four cells arranged as a ring, drawn as four boxes at the twelve, three, six and nine o’clock positions, labelled with indices 0, 1, 2 and 3 clockwise. Cells 2 and 3 contain 103 and 104; cells 0 and 1 are empty. A curved arrow runs clockwise from cell 3 to cell 0, labelled “(rear + 1) % 4”. An arrow outside the ring points at cell 2 labelled “front”, and another points at cell 3 labelled “rear”
| Feature | Simple queue | Circular queue |
|---|---|---|
How rear advances |
rear + 1 |
(rear + 1) % SIZE |
When rear is at the last cell |
Insertion is refused | Insertion continues at cell 0, if that cell is free |
| Cells freed by deletion | Abandoned permanently | Available again for later insertion |
| Meaning of “full” | The rear has reached the end of the array | Every cell holds an element |
| Test for fullness | rear == SIZE - 1 |
(rear + 1) % SIZE == front |
| Total elements it can ever serve | SIZE, however many are deleted | Unlimited; only the number held at once is limited |
| Cost of insertion and deletion | \(O(1)\) | \(O(1)\) |
13.5.2 Insertion and Deletion in a Circular Queue
Wrapping the markers solves one problem and creates another: telling a full queue from an empty one. In a simple queue, rear == SIZE - 1 said “full” and front == -1 said “empty”, and no confusion was possible. In a ring, front and rear can sit in the same relative position for two entirely different reasons.
The test used here is that the queue is full when the cell the next insertion would use is the cell the next deletion would take — that is, when (rear + 1) % SIZE equals front. Emptiness is still signalled separately, by front being −1, and the two conditions cannot both hold: when front is −1 and rear is −1, (rear + 1) % SIZE is 0, which is not −1.
Keeping a separate signal for emptiness is what allows every cell of the array to be used. Implementations that mark emptiness by front == rear instead have to leave one cell permanently empty to avoid the ambiguity, and can hold only SIZE − 1 elements.
Notice how little has changed. Two occurrences of + 1 became (... + 1) mod SIZE, and one test was rewritten. The discipline of the structure — insert at the rear, delete from the front — is exactly as it was.
13.5.3 Implementing a Circular Queue Through a Class
isFull() is safe to call on an empty queue even though it does not test emptiness first. When the queue is empty both markers are −1, so (rear + 1) % q.length is 0 while front is −1, and the test correctly returns false.
display() cannot use a simple for loop from front to rear, because in a wrapped queue front may be greater than rear — in the fourth line of output, front is 2 and rear is 1. The while loop instead walks round the ring from front, stopping when it reaches rear, and the last element is printed after the loop. The loop is written this way, rather than as “walk while i is not past rear”, because front == rear is a legitimate state meaning one element, not zero.
The reuse is not free. Everything about a circular queue is harder to read than the simple version — the arithmetic, the fullness test and the display loop — and every one of those places is somewhere a fault can hide. What you buy with that complication is an array whose cells can be used indefinitely rather than once each.
13.6 The Dequeue
13.6.1 A Queue Open at Both Ends
A stack has one working end. A queue has two, but each is allowed to do one job only — arrivals at the rear, departures at the front. The next question almost asks itself. What if both ends were allowed to do both jobs?
Consider the “recently opened files” list that most editors keep. Open a file and it goes to the top of the list. Open enough files and the oldest entry falls off the bottom to keep the list at a fixed length. Additions happen at one end; removals happen at both — deliberately at the top when a file is reopened and moves up, and automatically at the bottom when the list is full. Neither a stack nor a queue can do that.
Or take an ordinary school office counter. Students are normally served from the front. But a student who reaches the counter and finds a form missing steps aside and is put back at the front of the line once the form is fetched, rather than sent to the back. That is an insertion at the front of a queue, which a queue forbids.
A structure that permits insertion and deletion at both ends is called a dequeue, short for double ended queue. It is written deque in many books; the syllabus spells it dequeue, and this chapter follows the syllabus.
Diagram
Fig. 13.6-1 – an array of five cells drawn as a horizontal row, indices 0 to 4 written beneath. Cells 1, 2 and 3 contain 20, 30 and 40; cells 0 and 4 are empty. An arrow above cell 1 labelled “front” and an arrow above cell 3 labelled “rear”. At the left-hand end, two curved arrows: one pointing into the row labelled “insert at front”, one pointing out of the row labelled “delete from front”. At the right-hand end, two matching curved arrows labelled “insert at rear” and “delete from rear”
A dequeue therefore has four operations where a queue has two: insertion at the front, insertion at the rear, deletion from the front and deletion from the rear.
| Feature | Queue | Dequeue |
|---|---|---|
| Insertion permitted at | The rear only | Either end |
| Deletion permitted at | The front only | Either end |
| Number of operations | Two | Four |
| Order in which elements leave | Fixed by the order they arrived | Chosen by the caller, one end at a time |
| What the structure guarantees | Strict first in first out service | Only that elements are taken from an end, never from the middle |
| Can imitate | Nothing else | Both a stack and a queue |
That last row is worth expanding, because it cuts both ways.
Use a dequeue’s insertFront and deleteFront only, and it behaves exactly as a stack: everything enters and leaves at one end. Use insertRear and deleteFront only, and it behaves exactly as a queue. A dequeue can therefore stand in for either.
But that flexibility is bought by giving up a guarantee. A queue cannot serve out of order, and in a program that must be fair — print jobs, tokens at a counter — being unable to do the wrong thing is the whole value of the structure. A dequeue makes no such promise; nothing in it prevents a caller from removing the newest element every time. Choosing a dequeue where a queue would do is not a free upgrade. It removes a safeguard.
13.6.2 Insertion and Deletion at Either End
Half the work is already done. Inserting at the rear and deleting from the front are precisely the two operations of 13.5 — the algorithms, the tests and the wrap-round arithmetic are unchanged. What is new is the pair that works at the opposite end.
The dequeue built here is circular, for the reason 13.5 gave: without wrapping, the waste is not merely repeated but doubled, since front would run out of array at index 0 while rear ran out at the last index. Both markers therefore move by the remainder arithmetic, and both must be able to move in either direction.
Moving front backwards is the one genuinely new piece of arithmetic. From cell 0 the previous cell is the last one, and Fig. 13.6-2 shows the step.
Diagram
Fig. 13.6-2 – an array of five cells drawn as a horizontal row, indices 0 to 4 beneath. An arrow above cell 0 labelled “front, before”, a dashed curved arrow leaving the left edge of the row, passing under it, and re-entering at the right edge to point at cell 4, labelled “(front - 1 + 5) % 5”. An arrow above cell 4 labelled “front, after”
The addition of SIZE before taking the remainder is not decoration.
13.6.3 Implementing a Dequeue Through a Class
The output repays a careful reading against the array. After the third call the elements 10, 20 and 30 are held in cells 4, 0 and 1 — insertFront pushed the front marker from 0 backwards to 4. The printed order is still 10, 20, 30, because display() walks the ring from front rather than the array from index 0. The order elements are stored in and the order they are served in have parted company completely, and only the markers know the difference.
The overflow at the end comes with every one of the five cells occupied, which is the point of the circular arithmetic. Many textbooks show a dequeue built on a plain, non-wrapping array; in that version insertFront must refuse as soon as front reaches 0, so a dequeue of capacity 5 that has had one element inserted can accept nothing at all at the front.
13.7 The Single Linked List
13.7.1 The Node, the Data Field and the Link Field
Every structure so far has been built inside an array, and every one has inherited the array’s two inconveniences.
The first is fixed size. An array’s length is settled when it is created. A stack of capacity 20 cannot become a stack of capacity 21, however much room the machine has, and a program that guesses the capacity too high wastes memory while one that guesses too low fails.
The second is the cost of moving things. Suppose an array holds 41, 52, 63 in that order and 57 must be placed between 52 and 63. Cell 2 already holds 63, so 63 must move to cell 3 first — and if there were fifty elements after 52, all fifty would have to move. The elements are neighbours in memory, so making room for one means shifting all the others.
Both inconveniences come from the same source: the elements are held next to each other. Give that up, and both go away.
The idea is to store each element wherever there happens to be free memory, and to store alongside it the address of where the next element is. Such a package — one data value together with the address of the next package — is called a node.
The first part is the data field; the second is the link field. In Java, “the address of the next node” is written as a reference to a Node object, and the special value meaning “there is no next node” is null.
class Node
{
int data;
Node link;
Node(int d)
{
data = d;
link = null;
}
}A class whose field is of its own type looks alarming the first time you meet it, so it is worth being precise about what it does and does not mean. Node link does not put a Node inside a Node. A reference variable does not hold an object; it holds the address of one. So link is a small field holding an address, and the node it names sits somewhere else entirely.
Chain these together and you have a single linked list.
That last clause matters more than it looks. Nothing points to the first node from inside the list, so a separate reference — traditionally called start or head — must hold its address. Fig. 13.7-1 shows the arrangement.
Diagram
Fig. 13.7-1 – top half: a single node drawn as one rectangle divided into two boxes, the left box labelled “data” containing 41, the right box labelled “link”; caption “one node”. Bottom half: four such nodes drawn in a row, containing 41, 52, 63 and 74; an arrow from the link box of each node to the left edge of the next node; the link box of the last node marked with the electrical earth symbol and labelled “null”. A small box to the left of the first node labelled “start” with an arrow to the left edge of the first node. The four nodes are drawn at uneven heights and uneven distances apart, with a caption beneath reading “the nodes need not be next to each other in memory”
Lose start and you lose the entire list — not one node but all of them, because there is no other way in.
13.7.2 Creating and Traversing a Single Linked List
The rest of this section builds one class, SingleList, a method at a time. Each method is shown as it is explained; the complete, runnable class is collected at the end of 13.7.7.
The class holds one field, and it is the only thing it needs to hold.
class SingleList
{
private Node start;
SingleList()
{
start = null;
}
}A new list has no nodes, so start is null. Note that there is no capacity, no size and no array. The list grows one node at a time, and how far it can grow is decided by the memory available when it grows, not by a number chosen in advance.
To do anything with the list, a program must be able to walk along it. Walking a linked list from the first node to the last, doing something at each one, is called traversal.
PTR must be a separate variable. Walking with start itself would move start along and leave it pointing at the last node, losing every node before it.
void display()
{
if (isEmpty())
{
System.out.println("List is empty");
}
else
{
Node ptr = start;
System.out.print("List:");
while (ptr != null)
{
System.out.print(" " + ptr.data);
ptr = ptr.link;
}
System.out.println();
}
}Creating a list means making nodes and linking them, which is just repeated insertion. Rather than write a separate creation method, this class builds a list by calling its insertion methods, which 13.7.4 develops.
13.7.3 Checking Emptiness
Of all the operations the syllabus names for a linked list, this is the shortest, and it is worth a method of its own for the same reason a stack’s isEmpty() was.
boolean isEmpty()
{
return start == null;
}A list is empty exactly when start holds null. There is no separate counter to keep correct, no marker to reset, and no way for the test to disagree with the facts — which is one quiet advantage of this structure over the array-based ones, where emptiness had to be signalled by a convention that every method was obliged to maintain.
Note the comparison operator. start == null compares a reference with null; writing start.equals(null) would attempt to call a method on a reference that may hold no object at all.
13.7.4 Insertion into a Single Linked List
Insertion always follows the same three movements: make the new node, point it at whatever should follow it, and make whatever should precede it point at the new node. The three cases differ only in what “precede” and “follow” mean.
13.7.4.1 Insertion at the Beginning
void insertBeginning(int v)
{
Node temp = new Node(v);
temp.link = start;
start = temp;
}13.7.4.2 Insertion at the End
Adding at the other end is not symmetrical, and the reason is the one 13.7.1 gave: nothing in the list names the last node, so it has to be found.
void insertEnd(int v)
{
Node temp = new Node(v);
if (isEmpty())
{
start = temp;
}
else
{
Node ptr = start;
while (ptr.link != null)
{
ptr = ptr.link;
}
ptr.link = temp;
}
}Diagram
Fig. 13.7-2 – two panels, one above the other. Upper panel labelled “insertion at the beginning”: three existing nodes containing 41, 52, 63 linked left to right with null in the last link; a new node containing 30 drawn below and to the left; an arrow numbered 1 from the link box of node 30 to node 41; the “start” box drawn with its old arrow to node 41 crossed out and a new arrow numbered 2 to node 30. Lower panel labelled “insertion at the end”: the same three nodes; a new node containing 74 drawn below and to the right; the link box of node 63 shown with its null crossed out and an arrow numbered 1 to node 74; the link box of node 74 marked null; a marker labelled “ptr” above node 63 with a caption “found by walking from start”
13.7.4.3 Insertion in the Middle
To place a node after the n-th node, that node must be found by counting along from start. Once found, the two link changes are the same two as before, and their order is the thing to get right.
Diagram
Fig. 13.7-3 – four nodes in a row containing 30, 41, 52 and 63, linked left to right, null in the last link, with the “start” box and its arrow to node 30. A marker labelled “ptr” above node 52 with the caption “the 3rd node”. A new node containing 57 drawn below, between nodes 52 and 63. An arrow numbered 1 from the link box of node 57 to node 63, labelled “temp.link = ptr.link”. The existing arrow from the link box of node 52 to node 63 is crossed out, and an arrow numbered 2 runs from the link box of node 52 to node 57, labelled “ptr.link = temp”
13.7.5 Deletion from a Single Linked List
Deleting the n-th node means making the node before it point past it. That is the difficulty: from the n-th node there is no way back to the (n−1)-th, so the walk must carry a second reference one step behind.
Diagram
Fig. 13.7-4 – four nodes in a row containing 30, 41, 52 and 63, with the “start” box and its arrow to node 30 and null in the last link. A marker labelled “prev” above node 41 and a marker labelled “ptr” above node 52. The existing arrow from the link box of node 41 to node 52 is crossed out; a curved arrow numbered 1 runs from the link box of node 41 over node 52 to node 63, labelled “prev.link = ptr.link”. The arrow from the link box of node 52 to node 63 is crossed out and its link box marked null, numbered 2. Node 52 is drawn in outline with the caption “no longer reachable”
Step 7 is not strictly necessary — the node has already left the list at step 6 — but it is good practice, because it leaves no stray link into a list the node is no longer part of.
Nothing else is needed. In Java, an object that no reference names any longer is reclaimed automatically by the memory manager, so there is no instruction to free the deleted node and none is written. Books written for languages without automatic reclamation include such a step; in Java it would not compile.
13.7.6 Extracting an Element or a Sublist
Extracting a single element is traversal that stops early. Walk from start, counting, and when the count reaches the wanted position, return that node’s data field. The list is not changed.
int elementAt(int n)
{
if (n < 1)
{
System.out.println("No such position");
return -9999;
}
Node ptr = start;
int count = 1;
while (ptr != null && count < n)
{
ptr = ptr.link;
count = count + 1;
}
if (ptr == null)
{
System.out.println("No such position");
return -9999;
}
return ptr.data;
}Extracting a sublist means producing a list of the elements lying between two given positions. There is a decision to make first, and it is a design decision rather than a coding one: should the extracted portion be cut out of the original list, or copied from it?
Cutting it out is quicker — two link changes and no new nodes — but it destroys the original. Copying leaves the original intact and costs one new node per element extracted. This class copies, because a method that silently damages the list it was asked to read is a poor neighbour.
SingleList sublist(int from, int to)
{
SingleList out = new SingleList();
if (from < 1 || to < from)
{
return out;
}
Node ptr = start;
int count = 1;
while (ptr != null && count < from)
{
ptr = ptr.link;
count = count + 1;
}
while (ptr != null && count <= to)
{
out.insertEnd(ptr.data);
ptr = ptr.link;
count = count + 1;
}
return out;
}13.7.7 Reversing a Single Linked List
Reversal is the operation that shows what a linked list really is. Reversing an array means moving values about. Reversing a linked list means moving no values at all: every node stays exactly where it is in memory, and only the direction of the arrows changes.
The method walks the list once, and at each node turns that node’s link field round to point at the node behind instead of the node ahead. Doing so destroys the only record of what came ahead — so before turning a link round, the address it holds must be saved. Three references are therefore in play at once.
Diagram
Fig. 13.7-5 – four nodes containing 41, 52, 57 and 63 drawn in a row, showing one pass of the loop. The links of nodes 41 and 52 already point leftwards, with node 41’s link box marked null. Markers above the nodes: “prev” above node 52, “ptr” above node 57, “next” above node 63. The arrow from node 57 to node 63 is crossed out, and a new arrow from the link box of node 57 points left to node 52, labelled “ptr.link = prev”. Two small captions: to the left of node 52, “already reversed”; to the right of node 63, “not yet touched”
void reverse()
{
Node prev = null;
Node ptr = start;
while (ptr != null)
{
Node next = ptr.link;
ptr.link = prev;
prev = ptr;
ptr = next;
}
start = prev;
}| Pass | ptr at top of pass |
next saved |
Link of ptr set to |
prev at end of pass |
ptr at end of pass |
|---|---|---|---|---|---|
| 1 | node 41 | node 52 | null | node 41 | node 52 |
| 2 | node 52 | node 57 | node 41 | node 52 | node 57 |
| 3 | node 57 | node 63 | node 52 | node 57 | node 63 |
| 4 | node 63 | null | node 57 | node 63 | null |
Result: the loop ends with ptr null and prev naming node 63, so start is set to node 63 and the list reads 63, 57, 52, 41. The trace shows why next cannot be dropped: on pass 3, the address of node 63 exists in exactly one place before the link is turned — in ptr.link — and the very next statement overwrites it. Saving it into next first is the only thing standing between this method and a list that ends after two nodes.
The complete class
Every method that takes a position walks from start with a counter, and every one of them tests ptr != null before count < n. The order of those two tests is not decoration. Java evaluates && from left to right and stops as soon as the answer is settled, so if ptr is null the second test is never attempted. Reversing the two would attempt to read a field of a reference holding no object.
There is no size() method and no node count anywhere in the class. Adding one would mean adjusting it correctly in five different methods, and the class has no need of it. When a structure can answer a question by walking, storing the answer as well is one more thing that can drift out of step with the truth.
13.7.8 The Linked List Compared With an Array
Both hold a sequence of elements. Everything else about them differs, and the differences all follow from one fact: an array’s elements are neighbours in memory and a linked list’s are not.
| Feature | Array | Single linked list |
|---|---|---|
| Where the elements sit | In consecutive memory locations | Anywhere; each node records where the next one is |
| Size | Fixed when the array is created | Grows and shrinks one node at a time as the program runs |
| Memory per element | The element only | The element plus a link field |
| Reaching the k-th element | One step, by computing its position from the index | k − 1 steps, by following links from start |
| Inserting or deleting in the middle | Every later element must be shifted, \(O(n)\) | Two link fields change once the place is found, \(O(1)\) |
| Inserting at the beginning | Every element must be shifted, \(O(n)\) | \(O(1)\) |
| Direction of movement | Either, freely | Forward only |
| Wasted space | Unused cells of an over-large array | None from unused cells; one link field per element instead |
Read the table as a trade and not as a scoreboard. The linked list wins on inserting and deleting; the array wins on reaching an element by position; and neither advantage is small.
Which matters depends entirely on the problem. A structure that is built once and then read many times at arbitrary positions — a table of bus fares looked up by route number — belongs in an array, where the linked list’s walking would be pure loss. A structure that is constantly added to and removed from in the middle, and always read from one end anyway, belongs in a linked list.
It is also worth noticing which structures of this chapter each one suits. A stack and a queue only ever touch their ends, so they never pay the linked list’s access cost, and building them from nodes removes the fixed capacity that forced the circular queue into existence. The array was never the natural home for those structures; it was the convenient one.
13.8 Binary Trees
13.8.1 From Linear Structures to a Hierarchy
Every structure in this chapter so far has been linear. Each element has one element before it and one after it, and the whole thing can be laid out along a line. That shape is exactly right for a waiting list or a pile of scripts, and exactly wrong for a great many other things.
Open the file manager on any computer and look at a folder. It contains files, and it contains other folders, and those contain files and folders in turn. There is no sense in which one item “follows” another. What the arrangement records is containment: a downward branching from a single top-level folder, with no way back up except the way you came.
A tree is a structure of that shape.
Its parts have their own names. Each item is a node, and the line joining a node to one directly below it is an edge. Every node except the topmost one hangs from exactly one node above it, and the topmost node hangs from nothing.
Because a node may have several nodes below it, a tree is a non-linear data structure: there is no single “next” element, and no single line along which the whole structure can be laid out.
This chapter deals with the case in which the branching is limited to two, which gives the binary tree.
The words “left” and “right” are part of the structure, not part of the drawing. A node whose only child is a left child is a different tree from a node whose only child is a right child, even though both drawings show one node with one node below it. This distinction has no counterpart in any linear structure, and it is what the traversals of 13.8.4 depend on.
One tree serves as the example for the whole of this section. Fig. 13.8-1 shows it, and every term defined from here on is illustrated against it.
Diagram
Fig. 13.8-1 – nine nodes drawn as circles, arranged in four rows and joined by straight edges. Row 1, centred: P. Row 2: Q to the left and R to the right, each joined to P — Q is the left child of P and R is the right child of P. Row 3: S and T beneath Q, S being its left child and T its right child; U beneath R and drawn to the right of it, U being the right child of R, with R having no left child. Row 4: V beneath S and drawn to its left, V being the left child of S, with S having no right child; W beneath T and drawn to its right, W being the right child of T, with T having no left child; X beneath U and drawn to its left, X being the left child of U, with U having no right child. The node P carries a label “root” with a short arrow, and one edge, between P and Q, carries the label “edge”
13.8.2 The Vocabulary of a Binary Tree
Most questions about a tree are answered by naming its parts correctly, so the vocabulary is worth learning precisely rather than approximately.
13.8.2.1 Root, Parent, Child and Siblings
The root is the single node at the top of the tree, the one that hangs from nothing. In Fig. 13.8-1 the root is P. A tree has exactly one root, and every other node can be reached from it by following edges downward.
A node joined directly above another is its parent node; the node below is a child node. P is the parent of Q and of R; S and T are the children of Q. Every node except the root has exactly one parent — which is what makes a tree a tree, rather than a tangle.
Two nodes with the same parent are siblings. In the example, Q and R are siblings, and so are S and T. V, W, X and U each have no sibling, because each is the only child of its parent.
The terms are relative, and a node holds several of them at once. Q is a child of P, the parent of S and T, and a sibling of R, all at the same time. Asking “is Q a parent?” without saying parent of what is asking an incomplete question.
13.8.2.2 Internal Nodes, External Nodes and Sub Trees
A node with no children at all is an external node, also called a leaf. A node with at least one child is an internal node.
In Fig. 13.8-1 the external nodes are V, W and X. Every other node — P, Q, R, S, T and U — is internal. Every node of a tree is one or the other and never both, so the two counts always add up to the number of nodes.
Notice that leaves need not all lie at the bottom row. In this tree they happen to, but a node higher up with no children would be a leaf too.
The most useful idea in the whole vocabulary is the sub tree. Take any node, together with every node reachable from it by going downwards, and what you have is itself a tree, with that node as its root.
The sub tree rooted at Q consists of Q, S, T, V and W. The sub tree rooted at R consists of R, U and X. The sub tree rooted at V consists of V alone — a single leaf is a perfectly good tree of one node.
This is why trees are so often described in terms of themselves. Every node of a binary tree has a left sub tree and a right sub tree, either of which may be empty; the left sub tree of P is the tree rooted at Q, and the left sub tree of R is empty. Almost every statement about a binary tree can be made by saying what is true of the root and then saying that the same thing is true of both sub trees.
13.8.2.3 Height, Depth, Level, Size and Degree
These five are the terms most often mixed up, and four of them are counts of the same thing measured from different places.
The level of a node is the number of edges on the path from the root down to it, with the root itself at level 0. In Fig. 13.8-1, P is at level 0; Q and R at level 1; S, T and U at level 2; V, W and X at level 3.
The depth of a node is the same count: the number of edges from the root to that node. Depth and level are two words for one measurement, taken downwards from the root.
The height of a node is measured the other way — the number of edges on the longest path from that node down to a leaf. A leaf has height 0, since there is no path below it.
Height and depth agree for the tree as a whole and disagree for almost every individual node. Take Q: its depth is 1, because it is one edge below P; its height is 2, because the longest path below it is Q → S → V. Take V: its depth is 3 and its height is 0.
For the whole tree, the height is the height of the root, that is 3, since the longest root-to-leaf path is P → Q → S → V and it has three edges. The depth of the tree is the depth of its deepest node, also 3. The level of the tree is the level of its lowest row, again 3.
The size of a tree is simply the number of nodes it contains. The tree in Fig. 13.8-1 has size 9.
The degree of a node is the number of children it has. The degree of a tree is the largest degree of any of its nodes. In a binary tree no node may have more than two children, so the degree of a binary tree is never more than 2.
Table 13.12 sets out every one of these measurements for every node of the example tree at once, which is the quickest way to see how they behave.
| Node | Children | Degree | Sibling | Depth (= level) | Height | Internal or external |
|---|---|---|---|---|---|---|
| P | Q, R | 2 | none | 0 | 3 | internal |
| Q | S, T | 2 | R | 1 | 2 | internal |
| R | U | 1 | Q | 1 | 2 | internal |
| S | V | 1 | T | 2 | 1 | internal |
| T | W | 1 | S | 2 | 1 | internal |
| U | X | 1 | none | 2 | 1 | internal |
| V | none | 0 | none | 3 | 0 | external |
| W | none | 0 | none | 3 | 0 | external |
| X | none | 0 | none | 3 | 0 | external |
Reading down the two count columns shows the pattern at a glance: depth rises as you go down the tree and height falls, and the two meet only where a longest path passes through.
Diagram
Fig. 13.8-2 – the same nine-node tree as Fig. 13.8-1, with four dashed horizontal lines drawn across it, one through each row of nodes, labelled at the left-hand margin “level 0”, “level 1”, “level 2” and “level 3”. Beside node Q, a bracket with two labels: an arrow upward to P labelled “depth 1” and an arrow downward along the path Q to S to V labelled “height 2”. At the right-hand margin, a vertical brace spanning all four rows labelled “height of the tree = 3”
One convention needs stating because questions depend on it: here the root is at level 0. Some books number the root as level 1, which raises every level and every depth by one while leaving every height unchanged. Whenever a level or a depth is quoted, the convention has to be quoted with it.
13.8.3 Completeness and Balancing
Two trees can hold the same nodes and be shaped quite differently, and shape here is not a matter of appearance. Two named properties describe how well a binary tree is filled out, and both come down to the same question: how deep does the tree have to reach?
Completeness describes a tree filled in without gaps, level by level from the top down and from the left across.
Diagram
Fig. 13.8-3 – two small binary trees side by side, drawn as circles joined by edges. Left tree, captioned “complete”: a root with two children; the left child has two children of its own; the right child has a left child only, its absent right position drawn as a short stub ending in a small hollow circle — so the deepest level holds three nodes occupying the leftmost positions. Right tree, captioned “not complete”: a root with two children; the left child has a right child only, its absent left position drawn as a stub ending in a hollow circle; the right child has two children. A note beneath the right tree reads “the gap lies to the left of nodes that exist”
The tree of Fig. 13.8-1 is not complete. Level 2 holds three nodes where it could hold four, and level 3 has nodes on it all the same — a level was left unfilled while a deeper one was begun, which is exactly what completeness forbids.
Completeness is worth naming for a practical reason. Because a complete binary tree has no gaps, it can be held in a plain array with no link fields at all, the children of the node at index \(i\) sitting at indices \(2i + 1\) and \(2i + 2\). A tree with gaps can use that arrangement only by leaving cells empty.
Balancing is about the two sides of each node rather than about gaps.
Test the tree of Fig. 13.8-1 node by node. At P and at Q the two sub trees are of equal height, a difference of 0; at S, at T and at U the difference is 1, which is allowed. At R it is not: the left sub tree is empty, of height −1, while the right sub tree rooted at U has height 1, a difference of 2. One node is enough, so the tree is unbalanced.
A tree whose two sides differ widely is unbalanced, and the extreme case — every node having at most one child, so that the whole tree runs down in a single line — is called skewed.
Why this matters is best seen by asking what a tree is for. The point of a hierarchy is that the number of nodes can grow far faster than the height. A binary tree of height 3 with every level completely filled holds 15 nodes; of height 10 it holds 1023. Reaching any node from the root costs at most as many steps as the height, so a well-shaped tree of a thousand nodes is ten steps deep, not a thousand.
A skewed tree throws all of that away. Fig. 13.8-4 shows the two extremes with the same number of nodes.
Diagram
Fig. 13.8-4 – two trees of seven nodes side by side. Left tree, captioned “balanced — height 2”: a root with two children, each of which has two children, drawn as a perfect tree of three levels; a note beneath reads “at most 2 edges from the root to any node”. Right tree, captioned “skewed — height 6”: seven nodes in a single descending diagonal line, each node having only a right child; a note beneath reads “up to 6 edges from the root to the last node”
The skewed tree on the right is a linked list wearing a tree’s vocabulary. Every node has one child, every search from the root walks the whole chain, and none of the advantage of branching survives. This is why balancing is a property worth naming and worth maintaining, and why a structure that keeps its tree balanced as nodes are added is worth the extra work it costs.
13.8.4 Tree Traversals
Visiting every node of a structure exactly once is called traversal, and for the linear structures of this chapter there was nothing to decide: you start at one end and follow the only route there is.
A tree offers no such route. Standing at the root, there are two ways down, and whichever is taken first, the other must be taken later. The order in which the nodes come out therefore depends on a choice, and three choices are standard.
All three are described in the same way, in terms of three jobs to be done at every node: visit the node itself, deal with its entire left sub tree, and deal with its entire right sub tree. What separates the three traversals is only the order in which those jobs are done, and the same order is then used at every node of the tree without exception.
Diagram
Fig. 13.8-5 – a single circle labelled “node” near the top, with two triangles below it, the left one labelled “left sub tree” and the right one labelled “right sub tree”, each joined to the circle by an edge. A dashed curve is drawn around the whole figure, starting above and to the left of the circle, running down the outside of the left triangle, up between the two triangles, down the outside of the right triangle and back up to the top. Three small marks on the curve: one to the left of the circle labelled “pre-order records the node here”, one directly beneath the circle between the two triangles labelled “in-order records the node here”, one to the right of the circle labelled “post-order records the node here”
That figure also gives a reliable way to work a traversal out by hand. Draw a curve that starts at the root and hugs the outside of the whole tree, going down the left of everything, round the bottom and back up the right. The curve passes every node three times — once on its left, once underneath, once on its right. Record each node on its first pass and you have the pre-order; on the second pass, the in-order; on the third, the post-order.
13.8.4.1 Pre-order Traversal
In pre-order traversal the node is recorded first, then its left sub tree is traversed, then its right sub tree. The order is root, left, right.
Applied to the tree of Fig. 13.8-1, start at P and record it. Then traverse P’s left sub tree, the one rooted at Q: record Q, traverse Q’s left sub tree rooted at S — record S, traverse S’s left sub tree, giving V, and S’s right sub tree, which is empty. That finishes S’s sub tree as S, V. Then Q’s right sub tree rooted at T gives T followed by W. So P’s left sub tree yields Q, S, V, T, W. Finally P’s right sub tree, rooted at R: record R, its left sub tree is empty, its right sub tree rooted at U gives U then X.
The pre-order traversal is P, Q, S, V, T, W, R, U, X.
Notice the first node. In a pre-order traversal the root always comes out first, which makes pre-order the natural way to copy a tree — the root is available before anything needs to be hung beneath it.
13.8.4.2 In-order Traversal
In in-order traversal the left sub tree is traversed first, then the node is recorded, then the right sub tree is traversed. The order is left, root, right.
Working through the same tree: P cannot be recorded until the whole of its left sub tree has been dealt with. That sub tree is rooted at Q, and Q cannot be recorded until its left sub tree, rooted at S, is done; S cannot be recorded until V is, and V has no left sub tree, so V is the first node out. Then S, then S’s empty right sub tree. Q follows, then Q’s right sub tree rooted at T: T’s left sub tree is empty, so T is recorded, then W. That completes P’s left sub tree as V, S, Q, T, W. Now P is recorded. Then P’s right sub tree: R’s left sub tree is empty, so R is recorded, then its right sub tree rooted at U, which gives X before U.
The in-order traversal is V, S, Q, T, W, P, R, X, U.
The root of a tree always appears in the middle of its in-order traversal, with everything from its left sub tree before it and everything from its right sub tree after it. That property is what makes in-order the traversal used whenever a tree is arranged so that “smaller” values are placed to the left.
13.8.4.3 Post-order Traversal
In post-order traversal both sub trees are traversed first and the node is recorded last. The order is left, right, root.
For the same tree: nothing can be recorded until the deepest left-hand node is reached, so V comes first, then S, since S’s right sub tree is empty. Then Q’s right sub tree: T’s left sub tree is empty and its right sub tree gives W, so W then T. Only now is Q recorded. P’s left sub tree therefore yields V, S, W, T, Q. On the right, R’s left sub tree is empty and its right sub tree rooted at U gives X then U, after which R is recorded. P comes last of all.
The post-order traversal is V, S, W, T, Q, X, U, R, P.
The root always comes out last, and every node appears after both of its children. That is what makes post-order the traversal used when something must be done to the parts before it can be done to the whole — clearing a tree away, or working out a total that depends on the totals of both sub trees.
| Feature | Pre-order | In-order | Post-order |
|---|---|---|---|
| Order of the three jobs | root, left, right | left, root, right | left, right, root |
| Where the root appears | First | Between the two sub trees | Last |
| Sequence for the example tree | P, Q, S, V, T, W, R, U, X | V, S, Q, T, W, P, R, X, U | V, S, W, T, Q, X, U, R, P |
| Which node comes out first | The root | The leftmost node reachable by going left | The leftmost node reachable by going left |
| Suited to | Copying or listing a tree from the top down | Reading the nodes in left-to-right order | Working on the parts before the whole |
Two rows of that table repay attention.
The first nodes of the in-order and post-order traversals are the same, V, and they are the same for every tree. Both traversals go as far left as they can before recording anything, so both begin at the same node — but they diverge immediately afterwards.
And all three sequences contain the same nine letters. A traversal never adds or omits a node; it only chooses an order. If a traversal you have written down has eight entries or ten, it is wrong before anything else is checked.
13.9 Summary
Data structures and abstract data types
A data structure is an arrangement of data in memory together with the operations permitted on it. Two structures can hold identical values in identical memory and behave completely differently, because the permitted operations, and no others, decide how data enters and leaves.
A linear data structure holds its elements in a single sequence. The stack, the queue, the circular queue, the dequeue and the single linked list are linear; the binary tree is not.
An abstract data type describes a structure entirely in terms of its operations and what each one does, saying nothing about storage. A data structure is one implementation of it. The same abstract data type can have many different implementations.
In Java the specification is written as an interface, which lists method headings with no bodies, and the implementation as a class that implements it. Methods declared in an interface are automatically public, so every method implementing one must be declared public.
Two classes implementing the same interface may store entirely different things and still answer every question the interface asks. Choosing between them is a trade: a structure that stores less is cheaper and can answer fewer questions later.
The stack
A stack permits insertion and deletion at one end only, called the top. The element removed is always the one most recently inserted and not yet removed, so a stack follows the last in first out (LIFO) principle.
Inserting is called a push and removing is called a pop. Held in an array, a stack needs one marker, the index of the topmost element, set to −1 when the stack is empty.
That marker must mean the same thing in every method. A push raises it and then stores; a pop reads and then lowers it. Reversing either order breaks the class.
Attempting to push onto a stack whose array is full is a stack overflow; attempting to pop from an empty one is a stack underflow. Both are normal conditions to be tested for and reported, not errors to be allowed to happen.
Push and pop are \(O(1)\) in the best, average and worst case, where \(n\) counts the elements currently held; neither operation looks at any element other than the topmost.
Stacks are used wherever work must be undone or completed in the reverse of the order it was begun — editor undo, browser history, the return points of nested method calls, and the evaluation of arithmetic expressions.
Infix, prefix and postfix notations
A binary operator can be written between its operands (infix), before both of them (prefix, also called Polish notation), or after both of them (postfix, also called reverse Polish notation). The operands keep their relative order in all three.
Infix needs precedence rules and brackets because an operand can lie between two operators and belong to either. In prefix and postfix each operator stands alongside the two things it acts on, so the positions of the symbols alone fix the reading and brackets have nothing to do.
Precedence, highest first, is exponentiation, then multiplication and division, then addition and subtraction. Associativity is left to right for multiplication, division, addition and subtraction, and right to left for exponentiation. Brackets override both.
The bracketing method converts by hand: put in every bracket the rules imply, then, working from the innermost bracket outwards, move each operator after its two operands for postfix or before them for prefix, then remove the brackets.
The stack method converts an infix expression to postfix in one left-to-right scan. Operands go straight to the output; an operator is held on the stack until an operator of equal or lower precedence, or a closing bracket, proves it can wait no longer. The cost is \(O(n)\), where \(n\) counts the symbols in the expression.
Prefix is not the reverse of the postfix string. Reversing a postfix expression produces the operands in the wrong order and is not a valid expression at all.
A postfix expression is evaluated in one left-to-right scan with a stack of values: push each operand, and on each operator pop two values, apply it and push the result. The first value popped is the right-hand operand, because it was pushed later. Getting that order wrong is invisible for addition and multiplication and silently wrong for subtraction and division. The cost is \(O(n)\), where \(n\) counts the symbols.
The queue
A queue permits insertion at one end, the rear, and deletion at the other, the front. The element removed is always the one present longest, so a queue follows the first in first out (FIFO) principle.
Two markers are needed rather than one, and they move independently — insertion moves only the rear, deletion only the front. Both are set to −1 when the queue is empty.
When the element deleted is the last one present, both markers must be reset to −1. Omitting this leaves a queue that holds nothing but does not report itself empty.
Insertion and deletion are both \(O(1)\), where \(n\) counts the elements currently held.
A simple queue held in an array has a permanent flaw. Insertion can only use the cell after the rear, and every deletion abandons a cell at the front, so once the rear reaches the last cell no further insertion is possible however many cells stand empty. Such a queue can serve only as many elements in total as its array has cells.
The circular queue
A circular queue removes that waste by treating the array positions as a ring: the position after the last cell is the first cell. The rear advances by taking the remainder of one more than its value on division by the capacity.
Fullness becomes a relationship between the two markers rather than a property of one: the queue is full when the cell the next insertion would use is the cell holding the front element. Emptiness is still signalled separately, by the front marker being −1, and keeping that separate signal is what allows every cell of the array to be used.
Insertion and deletion remain \(O(1)\), where \(n\) counts the elements held. What is bought is unlimited reuse of the cells; what is paid is arithmetic and tests that are harder to read and easier to get wrong.
The dequeue
A dequeue, or double ended queue, permits both insertion and deletion at either end, so it has four operations where a queue has two.
Inserting at the rear and deleting from the front are the queue operations unchanged. Inserting at the front and deleting from the rear are their mirror images, moving a marker backwards round the ring by adding the capacity before taking the remainder — a step needed because in Java the remainder of a negative number is negative.
All four operations are \(O(1)\), where \(n\) counts the elements held.
Restricted to one end, a dequeue behaves exactly as a stack; restricted to insertion at the rear and deletion at the front, exactly as a queue. That flexibility costs a guarantee: a queue cannot serve out of order, and a dequeue makes no such promise.
The single linked list
An array holds its elements next to one another, which fixes its size and makes insertion in the middle cost a shift of every later element. A linked list gives up that adjacency and both difficulties go with it.
A node holds two parts: a data field storing one element, and a link field storing the address of the next node, or
nullin the last node. A reference variable outside the list holds the address of the first node; lose it and the whole list is lost.A node’s link field is a reference, not a node inside a node. The nodes may lie anywhere in memory and need not be near one another.
A single linked list can be walked forwards only. A node records the address of the node after it and nothing about the node before it, so the address needed to move back was never written down.
Traversal walks from the first node to the last with a separate reference, following link fields until
null. It costs \(O(n)\), where \(n\) counts the nodes. A list is empty exactly when the start reference holdsnull, which needs no counter and no convention to maintain.Insertion at the beginning changes two links and never examines a node, so it is \(O(1)\). Insertion at the end must first find the last node by following \(n-1\) links, so it is \(O(n)\). The two ends of the structure are not equally cheap.
Insertion after a stated node is two link changes once the node is found, and finding it costs a walk. The two changes must be made in the right order: attach the new node to the rest of the list before letting the preceding node point at it. The general rule is that the last thing you may overwrite is the only remaining copy of an address.
Deletion of a node requires the node before it, which cannot be reached from the node itself, so the walk carries a second reference one step behind. Deleting the first node is a separate case, because the reference that must change is the one holding the start of the list. No node is explicitly freed; a node no reference names is reclaimed automatically.
Extracting an element is a traversal that stops at the wanted position and leaves the list unchanged. Extracting a sublist may either cut the portion out or copy it; copying costs one new node per element and leaves the original intact.
Reversal moves no data at all. Every node stays where it is and only the direction of the links changes, one node at a time, with three references in play — the reversed portion behind, the node being turned, and the address about to be overwritten, which must be saved before the link is changed. Reversal is \(O(n)\), where \(n\) counts the nodes.
Against an array, a linked list wins on inserting and deleting and loses on reaching an element by position: an array reaches its k-th element in one step, a linked list in \(k-1\). Neither advantage is small, and which matters depends on whether the structure is mostly rebuilt or mostly read.
Binary trees
A tree is a non-linear structure: each node may have several nodes below it, so there is no single “next” element. Nodes are joined by edges, and every node except the topmost hangs from exactly one node above it.
A binary tree is a tree in which every node has at most two children, distinguished as the left child and the right child. That distinction is part of the structure, not of the drawing.
The root is the single node at the top. A node directly above another is its parent and the one below is its child; two nodes with the same parent are siblings. A node with no children is an external node or leaf, and a node with at least one child is an internal node.
Any node together with everything reachable below it forms a sub tree, itself a tree with that node as its root. Every node of a binary tree has a left sub tree and a right sub tree, either of which may be empty.
The level of a node, and equally its depth, is the number of edges from the root down to it, with the root at level 0. The height of a node is the number of edges on the longest path from that node down to a leaf, so a leaf has height 0. For the tree as a whole, height and depth are the same number; for an individual node they generally differ.
The size of a tree is its number of nodes. The degree of a node is its number of children, and the degree of a tree is the largest degree of any node — never more than 2 in a binary tree.
A binary tree is complete when every level except possibly the deepest holds as many nodes as that level can hold, and the nodes of the deepest level occupy the leftmost positions with no gaps between them. Because a complete tree has no gaps, it can be held in a plain array with no link fields at all.
A tree is balanced when, at every node, the heights of its left and right sub trees differ by at most one, an empty sub tree counting as height −1. A tree in which every node has at most one child is skewed. Shape decides cost: reaching a node means walking down from the root, so the worst case is the height of the tree — about \(\log_2 n\) for a balanced tree, giving \(O(\log n)\), but \(n - 1\) for a skewed tree, giving \(O(n)\), where \(n\) counts the nodes. A skewed tree is a linked list in a tree’s vocabulary, and throws the advantage of branching away.
Traversal visits every node exactly once. A tree offers no single route, so an order must be chosen, and the choice is made once and applied at every node: pre-order records the node, then the left sub tree, then the right; in-order takes the left sub tree, then the node, then the right; post-order takes both sub trees and records the node last.
The root comes out first in pre-order, between the two sub trees in in-order, and last in post-order. In-order and post-order both begin at the same node, the leftmost one reachable by going left. All three sequences contain exactly the same nodes; a traversal chooses an order and never adds or omits anything.
13.10 Key Terms
abstract data type (ADT) — a description of a data structure given entirely in terms of the operations it permits and what each one does, saying nothing about how the data is stored.
ADT — abstract data type; see the entry above.
associativity — the rule deciding which of two operators of equal precedence acts first; left to right for
*,/,+and-, right to left for exponentiation.balancing — the property of a binary tree in which, at every node, the heights of the left and right sub trees differ by at most one.
binary tree — a tree in which every node has at most two children, the two being distinguished as the left child and the right child.
child node — a node joined directly below another node.
circular queue — a queue held in an array whose positions are treated as a ring, so that the position after the last cell is the first cell and freed cells can be reused.
completeness — the property of a binary tree in which every level except possibly the deepest is filled to capacity, and the deepest level is filled from the left with no gaps.
data field — the part of a node that holds the element being stored.
data structure — an arrangement of data in memory together with a fixed rule about which operations are permitted on it.
degree — of a node, its number of children; of a tree, the largest degree found among its nodes.
deletion — the removal of an element from a queue, which takes place at the front.
depth — of a node, the number of edges from the root down to it; of a tree, the number of edges on the longest root-to-leaf path.
dequeue — a double ended queue; a linear structure permitting both insertion and deletion at either end.
double ended queue — the full name of the dequeue.
edge — the line joining a node to one directly below it in a tree.
external node — a node of a tree with no children; also called a leaf.
FIFO — first in first out; see the entry below.
first in first out (FIFO) — the rule followed by a queue, under which the element removed is always the one that has been present longest.
front — the end of a queue from which elements are deleted.
height — of a node, the number of edges on the longest path from it down to a leaf; of a tree, the height of its root.
infix notation — the way of writing an expression in which a binary operator stands between its two operands.
in-order — the traversal that deals with the left sub tree, then the node, then the right sub tree.
insertion — the addition of an element to a queue, which takes place at the rear.
internal node — a node of a tree with at least one child, the root included.
last in first out (LIFO) — the rule followed by a stack, under which the element removed is always the most recently inserted one still present.
leaf — another name for an external node of a tree.
level — the number of edges from the root down to a node, the root itself being at level 0.
LIFO — last in first out; see the entry above.
linear data structure — a structure whose elements form a single sequence, each with at most one element before it and one after it.
link field — the part of a node that holds the address of the next node, or
nullin the last node.node — an object holding one element of a list together with the address of the next node; also, an item of a tree.
non-linear data structure — a structure in which an element may have several elements below it, so that there is no single “next” element; the tree is the example in this chapter.
parent node — the node joined directly above another node.
Polish notation — another name for prefix notation.
pop — the operation that removes the topmost element of a stack.
postfix notation — the way of writing an expression in which a binary operator stands after both of its operands.
post-order — the traversal that deals with the left sub tree, then the right sub tree, and takes the node last.
precedence — the rule deciding which of two different operators acts first when both compete for the same operand.
prefix notation — the way of writing an expression in which a binary operator stands before both of its operands.
pre-order — the traversal that takes the node first, then deals with the left sub tree, then the right.
push — the operation that places an element on the top of a stack.
queue — a linear structure permitting insertion at the rear only and deletion from the front only.
rear — the end of a queue at which elements are inserted.
reverse Polish notation — another name for postfix notation.
root — the single node at the top of a tree, the one node having no parent.
siblings — two nodes of a tree having the same parent.
single linked list — a structure whose elements are held in separate nodes, each carrying one link to the next, with an external reference to the first node and
nullin the link of the last.size — the number of nodes in a tree.
skewed — describing a tree in which every node has at most one child, so that the whole tree runs down in a single line.
stack — a linear structure permitting insertion and deletion at one end only, called the top.
stack overflow — the condition reached when a push is attempted on a stack whose array has no free cell.
stack underflow — the condition reached when a pop is attempted on an empty stack.
sub tree — any node of a tree together with every node below it, which is itself a tree.
top — the single working end of a stack, at which both insertion and deletion take place.
traversal — visiting every element of a structure exactly once in a fixed order; along the links in a linked list, and in one of three standard orders in a binary tree.
tree — a non-linear structure of nodes joined by edges, in which one node is the root and every other node has exactly one parent.
13.11 Points to Ponder
A dequeue can do everything a stack can do and everything a queue can do. Yet 13.6 argued that a class offering only
pushandpopis sometimes the better choice precisely because it can do less. When is the ability to do less a property worth paying for — and who is being protected by it, the program or the programmer?Two classes in 13.1 implemented the same interface, returned the same answers to every question asked of them, and differed in that one had thrown the data away and the other had not. If a program using them through the interface cannot tell them apart, in what sense are they the same structure, and in what sense are they clearly not? What kind of question would force the difference into the open?
A pop from an empty stack returns −9999 by agreement, and the agreement holds only as long as −9999 is not a value anyone would legitimately store. What else could a method return to report that it has nothing to give — and whatever you propose, what work does it move onto the caller?
Postfix notation needs no brackets, needs no precedence rules, and can be evaluated in a single left-to-right scan by a machine. Infix needs all three. Why, then, does almost everybody still write, read and think in infix — and is that a fact about notation or a fact about people?
A single linked list of \(n\) integers stores \(n\) links as well as \(n\) values, and so can occupy more memory than an array holding the same values. Under what circumstances does a structure that uses more memory per element nevertheless leave a program using less memory overall?
Given only the pre-order traversal of a binary tree, several different trees could have produced it, so the traversal alone is not enough to rebuild the tree. What would have to be added to make the reconstruction certain, and why does one extra traversal help where a longer one would not?
13.12 Objective Questions
- The principle followed by a queue is: [1 mark]
- LIFO
- FIFO
- LILO
- FILO
- In a circular queue of capacity SIZE with markers
frontandrear, insertion must be refused when: [1 mark]
rear == SIZE - 1front == rear(rear + 1) % SIZE == frontfront == -1
- The notation in which an operator is written after both of its operands is called: [1 mark]
- infix notation
- prefix notation
- Polish notation
- reverse Polish notation
- A stack is held in an array with
topnaming the index of the topmost element. The value oftopfor an empty stack is: [1 mark]
- 0
- −1
- the capacity of the array
- one less than the capacity of the array
- In a single linked list, deleting the first node requires a change to: [1 mark]
- the link field of the last node
- the link field of the second node
- the reference
start - the data field of the first node
- The degree of an external node of a binary tree is: [1 mark]
- 0
- 1
- 2
- equal to its level
- A binary tree has 11 nodes and its root is at level 0. Its size is: [1 mark]
- 10
- 11
- 12
- cannot be determined without the height
- Assertion (A): In a stack, the element inserted last is the first to be removed. Reason (R): A stack permits insertion and deletion at one end only. Choose the correct option: [1 mark]
- Both A and R are true and R is the correct explanation of A.
- Both A and R are true but R is not the correct explanation of A.
- A is true but R is false.
- A is false but R is true.
- Assertion (A): A single linked list can be traversed from its last node back to its first. Reason (R): Each node of a single linked list stores the address of the node that follows it. Choose the correct option: [1 mark]
- Both A and R are true and R is the correct explanation of A.
- Both A and R are true but R is not the correct explanation of A.
- A is true but R is false.
- A is false but R is true.
- Match each structure in Column A with the property in Column B that describes it. [1 mark]
| Column A | Column B |
|---|---|
| a. Stack | i. insertion at the rear, deletion from the front |
| b. Queue | ii. at most two children per node |
| c. Dequeue | iii. insertion and deletion at one end only |
| d. Binary tree | iv. insertion and deletion at both ends |
Fill in the blank: the traversal of a binary tree in which the root of every sub tree is taken last is called ____________ traversal. [1 mark]
Fill in the blank: in a dequeue held in an array of capacity SIZE, the front marker is stepped backwards by the expression ____________ . [1 mark]
State whether each of the following is true or false. [1 mark]
- The link field of the last node of a single linked list holds the address of the first node.
- Every leaf of a binary tree is an external node.
- Give the full form of each of the following: LIFO, FIFO, ADT. [1 mark]
13.13 Check Your Concepts
Define an abstract data type, and state one thing an abstract data type does not tell you about a structure. [2 marks]
What is meant by stack underflow? State the condition, in terms of
top, under which it occurs. [2 marks]State what the link field of the last node of a single linked list contains, and explain why it must contain that value. [2 marks]
Define the height of a binary tree and the depth of a node of a binary tree, making clear how the two are measured differently. [2 marks]
Differentiate between a stack and a queue, giving three points of difference. [3 marks]
Convert the infix expression
A + B * (C - D) / Einto its postfix form, showing the intermediate steps of your working. [3 marks]Convert the infix expression
(P - Q) * R + S / Tinto its prefix form, showing the intermediate steps of your working. [3 marks]Give reasons why a simple queue held in an array may refuse an insertion while several of its cells stand empty, and state how a circular queue removes the fault. [3 marks]
Study the binary tree in Fig. 13.13-1 and answer the questions that follow. [4 marks]
Diagram
Fig. 13.13-1 – a binary tree drawn with circular nodes joined by straight edges. Root A at the top with a left child B and a right child C. B has a left child D and a right child E. C has no left child and a right child F; draw the absent left position as a short stub ending in a small hollow circle. E has a left child G and no right child, again with a stub for the absent position. F has no left child and a right child H, with a stub for the absent position
- Write the pre-order traversal of the tree.
- Name the external nodes of the tree.
- State the height of the tree when the root is at level 0.
- Name the siblings of node D.
Write the algorithm to insert an element at the rear of a circular queue held in an array of capacity SIZE, with
frontandrearboth holding −1 when the queue is empty. State the cost of your algorithm in big O notation, saying what \(n\) counts. [4 marks]When a node is inserted at the beginning of a single linked list, two link assignments are made. Explain, with an example, why performing them in the wrong order destroys the list. [4 marks]
A programmer must choose between an array and a single linked list to hold a collection of examination marks. Compare the two structures under the headings of storage, cost of reaching the \(k\)th element, cost of inserting at the beginning, and memory used per element. Conclude by stating one situation in which each of the two is the better choice, with your reason. [6 marks]
Explain in full the method by which a stack converts an infix expression into postfix form, stating what is done for an operand, for an operator, for a left bracket and for a right bracket. Apply your method to the expression
(A + B) / C * (D - E), showing the contents of the stack and of the output expression after each symbol is scanned. [6 marks]
13.14 Output & Debugging
- Study the following program and state exactly what it prints. [2 marks]
class Pile
{
public static void main(String args[])
{
int st[] = new int[5];
int top = -1;
for (int i = 1; i <= 4; i++)
{
top = top + 1;
st[top] = i * i;
}
System.out.print(st[top] + " ");
top = top - 1;
System.out.print(st[top] + " ");
top = top - 1;
System.out.println(st[top]);
}
}- State what the following program prints, and say in one sentence what the variable
rrepresents. [2 marks]
class Ring
{
public static void main(String args[])
{
int size = 5;
int r = 3;
for (int k = 1; k <= 4; k++)
{
r = (r + 1) % size;
System.out.print(r + " ");
}
System.out.println();
}
}- The following program is intended to store 10, 20, 30 and 40 in an array whose positions wrap round, moving the marker backwards each time. It does not run. Identify the single error, state what happens when the program is run, and correct the line at fault. [3 marks]
class Backward
{
public static void main(String args[])
{
int dq[] = new int[4];
int f = 0;
dq[f] = 10;
for (int k = 1; k <= 3; k++)
{
f = (f - 1) % dq.length;
dq[f] = 10 * (k + 1);
}
System.out.println(dq[0] + " " + dq[1]);
}
}- State the output of the following program. The total of the three values stored is 31, so explain why the program does not print that, and correct the fault. [3 marks]
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
class AddUp
{
public static void main(String args[])
{
Node start = new Node(7);
start.next = new Node(11);
start.next.next = new Node(13);
int total = 0;
Node ptr = start;
while (ptr.next != null)
{
total = total + ptr.data;
ptr = ptr.next;
}
System.out.println("Total = " + total);
}
}- State what the following program prints, and write the infix expression that the string
exprepresents. [3 marks]
class Evaluate
{
public static void main(String args[])
{
int st[] = new int[10];
int top = -1;
String exp = "852-/";
for (int i = 0; i < exp.length(); i++)
{
char c = exp.charAt(i);
if (c >= '0' && c <= '9')
{
top = top + 1;
st[top] = c - '0';
}
else
{
int b = st[top];
top = top - 1;
int a = st[top];
top = top - 1;
if (c == '-')
{
top = top + 1;
st[top] = a - b;
}
else
{
top = top + 1;
st[top] = a / b;
}
}
}
System.out.println(st[top]);
}
}- The following program inserts one element into a queue and then deletes it, leaving the queue holding nothing. State what it prints, explain why the last line printed is misleading, and give the correction needed. [3 marks]
class Counter
{
public static void main(String args[])
{
int q[] = new int[5];
int front = -1;
int rear = -1;
front = 0;
rear = 0;
q[0] = 21;
int v = q[front];
front = front + 1;
System.out.println("Deleted " + v);
System.out.println("front = " + front + ", rear = " + rear);
System.out.println("Empty? " + (front == -1));
}
}13.15 Programming Practice
- A library issue counter records the accession numbers of books as they are placed on a returns trolley. A book can be added to the trolley or taken from it at the top only.
Define a class Trolley with the following details:
| Item | Detail |
|---|---|
| Class name | Trolley |
bk[ ] |
array to hold the accession numbers |
cap |
maximum capacity of the array |
top |
index of the topmost element |
Trolley(int m) |
constructor to initialise cap = m and top = -1, and to create the array |
void addBook(int n) |
adds an accession number at the top if possible, otherwise prints “Trolley is full” |
int takeBook( ) |
removes and returns the topmost accession number if any, otherwise prints “Trolley is empty” and returns −9999 |
void display( ) |
prints the accession numbers held, topmost first |
Specify the class Trolley, giving the details of the constructor and of the three member functions. The main( ) function and the algorithm need not be written. Name the data structure the class implements and state the principle it follows. [6 marks]
- Define a class
TokenRingthat holds token numbers in a circular queue.
| Item | Detail |
|---|---|
| Class name | TokenRing |
tk[ ] |
array to hold the token numbers |
lim |
maximum capacity of the array |
front |
index of the front end |
rear |
index of the rear end |
TokenRing(int m) |
constructor to initialise lim = m and front = rear = -1, and to create the array |
void addToken(int n) |
adds a token number at the rear end if possible, otherwise prints “Ring is full” |
int callToken( ) |
removes and returns the token number at the front end if any, otherwise prints “Ring is empty” and returns −9999 |
Specify the class TokenRing, giving the details of the constructor and of void addToken(int) and int callToken( ). Assume the display method has already been defined. The main( ) function and the algorithm need not be written. State also how the class would differ if the queue were not circular. [6 marks]
- Write a complete program that reads an infix expression from the keyboard as a single string, containing single-letter operands, the operators
+,-,*and/, and round brackets, with no spaces. Using a stack, convert the expression into its postfix form and print the result.
Submit the algorithm, the class, and a variable description table. Show the output for the sample input (A+B)*C-D and test your program also on the unseen input A*(B+C/D). [6 marks]
- A single linked list is formed from the objects of the class below.
class Node
{
int mark;
Node next;
}Write an algorithm OR a method to count the nodes of an existing linked list whose mark field holds a value greater than a stated limit, and to return that count. The method declaration is:
int countAbove(Node start, int limit)State also, in big O notation, the cost of your method, saying what \(n\) counts. [5 marks]
- A word is a palindrome if it reads the same forwards and backwards. Write a complete program that reads one word from the keyboard, inserts each of its letters at the rear of a dequeue, and then decides whether the word is a palindrome by repeatedly removing one letter from the front and one from the rear and comparing them, stopping when fewer than two letters remain.
Submit the class, including the dequeue operations it uses, and a variable description table. Print Palindrome or Not a palindrome. Show the output for the sample input MALAYALAM and test your program also on the unseen input LEVELS. [5 marks]