Data Structures Notes | B.Sc. (Computer Science) Semester 3 | Mumbai University | munotes

The definition, said properly

A data structure is a way of organising data in a computer's memory so that a particular set of operations on it is efficient.

Two halves of that sentence do work, and students usually keep only the first.

A way of organising data in memory. Contiguous cells, or scattered cells joined by addresses, or a branching arrangement. This is the part that is easy to draw.

So that a particular set of operations is efficient. No structure is fast at everything. Every structure in this paper is a bargain: it makes some operations cheap by making others expensive. The array indexes instantly and inserts slowly. The linked list inserts instantly and searches slowly. The hash table finds instantly and cannot tell you what comes next in order.

So the honest question is never "which data structure is best". It is "which operations does my problem do most often, and which structure is cheap at exactly those". A student who leaves this paper with that question in their head has got the value out of it.

A second experiment, so the first is not a fluke

Membership is one operation. Here is a different one, and this time the list wins.

import time

N = 40000

start = time.perf_counter()
row = []
for i in range(N):
    row.append(i)
append_seconds = time.perf_counter() - start

start = time.perf_counter()
front = []
for i in range(N):
    front.insert(0, i)
insert_seconds = time.perf_counter() - start

print("items added              :", N)
print("both hold the same       :", len(row) == len(front))
print("front at least 20x slower:", append_seconds * 20 < insert_seconds)

items added              : 40000
both hold the same       : True
front at least 20x slower: True

Same structure, same number of items, same machine. Adding at the end is cheap; adding at the front is not, because every existing item has to shuffle up one place to make room.

That is the second lesson, and it is sharper than the first: the cost belongs to the pair, the structure and the operation, never to the structure alone. "Lists are fast" is not a statement that means anything. "Adding at the end of a Python list is cheap, and adding at the front is not" is.

What you are going to build

This paper sets eight structures. Here they are in one sentence each, so you know where the road goes.

Every one of them is built from scratch in this book, run, and measured.

How to read the timings in this book

A timing in seconds is a fact about a machine, not a fact about a structure. This book therefore never says "a linked list takes 0.4 seconds". It says what happens to the time when the data gets bigger, because that is the part that belongs to the structure and travels to your machine.

The three shapes you will meet, over and over:

• Constant. Double the data, the work stays the same. Written O(1).
• Linear. Double the data, double the work. Written O(n).
• Logarithmic. Double the data, add one step. Written O(log n).

The last one is the one worth feeling rather than memorising. Going from a thousand items to a million items multiplies the data by a thousand and adds about ten steps. That is what a tree buys you, and it is why half this paper is trees.

Machine used for every measurement in this book: the timings were produced by the program printed beside them, and the numbers you get will differ. What must not differ is the shape.

Quick revision

• A data structure is an arrangement of data in memory together with the operations that arrangement

makes efficient.

• No structure is good at everything. Every one is a bargain: cheap at some operations, expensive at

others.

• Cost belongs to the pair, structure and operation, never to the structure by itself.
• The right question is which operations the problem does most, not which structure is best.
• Timings in seconds belong to a machine. What belongs to the structure is how the time grows when the

data grows: constant, linear or logarithmic.

• Searching a row of 40,000 numbers one by one against computing where the number lives is the

difference this whole paper is about.

Test yourself

1. Define a data structure in one sentence, including both halves of the definition. A way of organising data in memory together with the operations that arrangement makes efficient. The second half is the half students drop, and it is the half that matters.

2. Is a linked list faster than an array? The question has no answer as asked. A linked list is cheaper at inserting and removing; an array is cheaper at reaching the nth item. Cost belongs to the pair of structure and operation.

3. In the first experiment both programs printed the same answer. What, then, was wrong with the slow one? Nothing was wrong with its correctness. It was wrong in its choice of arrangement for the operation it did most: it searched by walking when it could have searched by computing.

4. Why does this book refuse to say "a linked list search takes 0.4 seconds"? Because that is a fact about one machine on one day. The fact that belongs to the structure is that doubling the data doubles the work.

5. Going from 1,000 items to 1,000,000 items, how much extra work does an O(log n) operation do? About ten more steps. The data multiplied by a thousand; a logarithmic cost adds about ten.

6. Give one operation that an array is cheap at and a linked list is expensive at, and one the other way round. Reaching the nth item: the array computes the address, the linked list walks to it. Inserting at the front: the linked list moves one link, the array shuffles every element up.

But it is the boundary of this paper, and the University drew it: four things the practical sets are taught in this book because a student is examined on them and no theory label names them. They are evaluating a postfix expression (chapter 38), the array-backed stack and peek (chapter 32), the comparison of the array against the linked list (chapter 22), and chaining and linear probing by name (chapters 104 and 105).

How this book is built

Every program in it was run. Not checked by reading, run. The output printed under a program is what the interpreter printed, on three versions of Python, and if the three disagreed the book says so. A gate refuses to build this book if any printed output is not what the program produced.

Every trace was produced by the machine. Where you see a tree after each of six insertions, or an array after each swap of a heapify, the program printed it. Nobody typed it out and hoped.

Every cost claim was measured, at growing sizes, and what is printed is either a counted operation or a claim with room to spare. You will not find "this takes 0.4 seconds" anywhere in this book, because that is a fact about somebody else's laptop.

Every chapter has the same shape: what it is in one line, the substance, a Quick revision at five mark length, and Test yourself with the answers written out.

How to use it in the last week

• Read the Quick revision of every chapter in a module. That is the module in about an hour.
• Work the Test yourself questions with the answers covered.
• Then read chapter 110 twice. It is the Q.3 chapter, it is a third of the paper, and it is the part

most students walk in without.

Quick revision

• Data Structures is a Major, Type Theory, 2 credits, 30 hours, 50 marks.
• External: 1 hour, 30 marks. Q.1 Module 1, Q.2 Module 2, Q.3 both, each any 2 of 4 for 10.
• Every sub-question is 5 marks and about ten minutes.
• Internal 20: two class tests averaged to 10, two assignments totalling 10.
• Pass 40% in each component, internal and external separately.
• Q.3 spans both modules and is a third of the paper; chapter 110 is written for it.
• Computer Science Practical 3 is a separate paper with its own marks and its own journal.

Test yourself

1. How long is the written paper and how many marks is it? One hour, 30 marks, out of a total of 50 for the subject.

2. How many sub-questions are printed, how many do you answer, and what is each worth? Twelve printed, six answered, five marks each.

3. Which question is set on both modules together? Q.3. It is 10 of the 30 external marks.

4. Can you skip Module 2 and still pass the written paper? No. Q.2 is set on Module 2 alone and Q.3 draws on both, so 20 of the 30 marks need it.

5. What is the internal 20 made of? Two class tests, one per module, averaged to 10; and two assignments, one per module, totalling 10.

6. Is the practical examined in this paper? No. Computer Science Practical 3 is a separate paper with its own examination and its own compulsory journal, though four things it sets are taught here because they are examinable and the theory labels do not name them.

int 0          28 bytes
int 255        28 bytes
int 10^30      40 bytes
float          24 bytes
empty str      41 bytes
str 'A'        42 bytes
bool           28 bytes
empty list     56 bytes
list of 3      88 bytes

Those numbers are this Python's, on this machine. Another build gives different ones and the book is not asking you to memorise them. What they show is the point: a value has a size, the size depends on the type, and an empty list is not free.

Notice that int 0 and int 255 are the same size, but 10**30 is bigger. Python's integers grow to fit the number, which is unusual and generous. In C or Java an int is a fixed number of bytes and a number too big for it wraps around silently. That difference is exactly why the next chapter exists.

Static and dynamic typing, in one paragraph

In C and Java you declare the type and it is fixed: int n; and n holds integers for ever. That is static typing, checked before the program runs. In Python the value carries the type and a name can point at anything, which is dynamic typing, checked as it runs.

This paper's structures are built in Python, so the types are dynamic. But every structure here is a structure in any language, and where a language's typing changes the design, this book says so.

Why a type is not a data structure

A type says what one value is. A data structure says how many values are arranged.

Put the other way: int is a type. "Ten thousand integers, in a row, in order" is a data structure. The paper is about the second, and it starts with the first because a structure is made of typed values and you cannot reason about the cost of the arrangement without knowing the cost of one item.

Quick revision

• Memory is bytes; the bits do not say what they mean. A type is what says.
• A type settles three things: the allowed values, the allowed operations, and the representation.
• The same operator means different things on different types: + adds integers and joins strings.
• Every value has a size, the size depends on the type, and an empty container is not free.
• Python integers grow to fit; C and Java integers are fixed width and can overflow.
• Static typing fixes the type of a name before the run (C, Java); dynamic typing carries the type on

the value (Python).

• A type describes one value; a data structure describes an arrangement of many.

Test yourself

1. What three things does a type settle? The set of allowed values, the operations allowed on them, and how the value is represented in memory.

2. Why does 'A' + '1' not give 66? Because + is selected by the type. On strings it joins; on integers it adds. The characters are not being read as their numeric codes.

3. Which of the three promises decides what a structure costs? The representation. The set of values and the operations decide what is legal; the representation decides what is cheap.

4. Give one difference between a Python integer and a C integer that matters. A Python integer grows to fit any whole number; a C int is fixed width and overflows silently when the value is too large.

5. State the difference between static and dynamic typing. Static: the type belongs to the name and is fixed and checked before the run. Dynamic: the type belongs to the value and is checked while the program runs.

6. Is int a data structure? Explain. No. It is a type, describing one value. A data structure describes how many values are arranged, such as an array of integers.

Python int: no fixed maximum. 2 ** 200 =
1606938044258990275541962092341162602522202993782792835301376

float: largest and smallest, from the machine itself
  max float : 1.7976931348623157e+308
  min normal: 2.2250738585072014e-308
  digits it can be trusted to: 15

what happens past the top of a float:
  max * 2 = inf

A float that grows past its largest value becomes inf rather than wrapping. A C integer that grows past its largest value wraps to a negative number silently, which is the more dangerous behaviour and the reason overflow is a standard examination topic.

Where the primitives stop, and the paper begins

Here is the wall, and the whole of the rest of this book is the answer to it.

A primitive holds one value. Consider the smallest realistic problem: the marks of the students in a class.

mark1 = 78
mark2 = 65
mark3 = 91

print("average of three:", (mark1 + mark2 + mark3) / 3)
print()
print("now do it for sixty students, with sixty named variables.")
print("and then sort them.")
print("and then find the student ranked seventh.")

average of three: 78.0

now do it for sixty students, with sixty named variables.
and then sort them.
and then find the student ranked seventh.

Three problems appear at once, and none of them is about arithmetic.

You cannot write sixty variables and mean it. The program would have to be rewritten for a class of sixty one.

You cannot loop over separately named variables. A loop needs a way to say "the next one", and separate names have no next.

You cannot sort them. Sorting means moving values around by position, and a name is not a position.

What is needed is a way to hold many values under one name, reachable by position. That is the array, it is the next structure in this book, and every other structure here is a response to something the array cannot do.

Quick revision

• The primitive types are integer, real, character and boolean; each holds a single value.
• Python has no separate character type (a one-letter string) and its booleans are a kind of integer.
• // is integer division, / is real division.
• Floats are approximations: 0.1 + 0.2 is not exactly 0.3, so never compare floats with ==;

compare the difference against a tolerance.

• Floats have a largest value and overflow to inf. Fixed width integers in C wrap silently instead.
• Python integers have no fixed maximum.
• A primitive holds one value. A problem with many values needs many values under one name, reachable

by position, and that is where data structures begin.

Test yourself

1. Name the four primitive families and what each holds. Integer (whole numbers), real or float (numbers with a fractional part), character (one symbol), boolean (true or false).

2. Why should two floats not be compared with ==? Because a float is a binary approximation of a decimal value, so arithmetic leaves tiny errors: 0.1 + 0.2 gives 0.30000000000000004. Compare the absolute difference against a small tolerance.

3. What is the result of 7 // 2 and how does it differ from 7 / 2? 7 // 2 is 3, integer division discarding the fraction. 7 / 2 is 3.5.

4. What happens when a float exceeds its maximum, and how does a fixed width C integer differ? The float becomes inf. The C integer wraps around to a negative value with no warning, which is the more dangerous of the two.

5. Give three reasons sixty separately named variables cannot hold a class's marks. The program cannot be written for an unknown class size; a loop has no way to move to the next one; and sorting needs positions, which names do not have.

6. What property must the next structure have, that a primitive does not? It must hold many values under one name and let any of them be reached by position.

Where every structure in this paper sits

Here is the whole syllabus placed on the map, so the rest of the book has somewhere to hang.

Two rows in that table are the interesting ones, and both are examined.

The heap is a tree that lives in an array. It is non-linear as an idea and linear in memory, and chapter 82 shows the index arithmetic that makes that work.

The hash table is neither linear nor non-linear. It has no order at all. That is what it gives up in exchange for finding things instantly, and chapter 108 is about that bargain.

Quick revision

• Linear: items in a sequence, each with one before and one after. Array, linked list, stack, queue.
• Non-linear: an item may have many successors. Tree, graph.
• The test for linear: can the items be written in one row with neighbours preserved?
• Static: size fixed at creation, one block of memory. Dynamic: grows and shrinks during the run.
• The two divisions are independent: a linked list is linear and dynamic.
• Primitive structures hold one value; non-primitive are built from them and split into linear and

non-linear.

• Python's list is dynamic on the outside and a static array on the inside, which it replaces with a

bigger one when it fills.

• The heap is non-linear as an idea and linear in memory. The hash table has no order at all.

Test yourself

1. State the test that decides whether a structure is linear. Whether the items can be written in a single row so that every item's neighbours in the row are its neighbours in the structure.

2. Is a linked list static or dynamic? Is it linear? Dynamic and linear. It is the standard example that the two divisions are independent.

3. Give the four boxes of the linear/non-linear against static/dynamic table, with an example in each. Static linear: array. Dynamic linear: linked list. Static non-linear: a heap in a fixed array. Dynamic non-linear: tree or graph.

4. Why is a hash table hard to place on the linear/non-linear division? Because it has no order among its items at all. It is not a sequence and it is not a branching arrangement; the position of an item is computed from its key.

5. Draw the primitive against non-primitive classification. Data structures split into primitive (int, float, char, bool) and non-primitive; non-primitive splits into linear (array, linked list, stack, queue) and non-linear (tree, graph).

6. Python's list grows when you append to it. Does that make it a dynamic structure, and what is it underneath? It behaves dynamically, and underneath it is a static array that is replaced by a larger one, with everything copied across, when it fills.

n =  1000   linear search:  1000 comparisons   binary search:  9
n =  2000   linear search:  2000 comparisons   binary search: 10
n =  4000   linear search:  4000 comparisons   binary search: 11
n =  8000   linear search:  8000 comparisons   binary search: 12

Read the two columns down. The data doubles four times. The linear search doubles with it. The binary search adds one.

That is the difference between O(n) and O(log n), and it is the single most important pattern in this paper. You do not need to memorise it; you need to have seen it happen.

What the counts do not say

Binary search needs the data sorted. Sorting costs something, and if the data changes constantly you pay that cost over and over. This is question 1 again: how often does each operation run?

That is why the answer to "which is better, linear or binary search" is, correctly, it depends on how often the data changes, and an examiner asking the question is asking for exactly that.

The three questions, as a checklist

Keep this beside you while reading the rest of the book. Every structure here is introduced with an answer to it.

The fourth is not a question so much as a warning, and it is the one that catches people. A hash table refuses order. A stack refuses the middle. A static array refuses to grow. A structure's refusals are as much a part of choosing it as its strengths.

Quick revision

• Ask three things: which operations run most, what each costs here, and what the structure costs in

memory.

• Cost means how the work grows with the data, not seconds.
• Counted operations are exact and machine independent; prefer them to timings.
• Linear search doubles when the data doubles; binary search adds one step. O(n) against O(log n).
• Binary search needs sorted data, so "which is better" depends on how often the data changes.
• Add a fourth question in practice: what does this structure refuse to do?
• One line of a requirement can change the answer, as adding "in order" rules out a hash table.

Test yourself

1. State the three questions. Which operations does the problem do most often; what does each cost in this structure; what does the structure cost in memory beyond the data.

2. Data doubles from 4,000 to 8,000. What happens to a linear search and to a binary search? The linear search doubles, from about 4,000 comparisons to about 8,000. The binary search adds one, from 11 to 12.

3. Why is "which is better, linear or binary search" not answerable as asked? Because binary search needs sorted data. If the data changes often the sorting cost dominates, and the right answer depends on how often each operation runs.

4. A system searches constantly and inserts twice a year. Which question settles the choice? Question 1. Search frequency outweighs insertion by such a margin that insertion cost is nearly irrelevant.

5. The requirement gains one line: "and list the students in roll number order". What does that rule out? A hash table, which has no order and cannot produce the next key without inspecting every key.

6. Why does this book count comparisons instead of timing the search? Because a count is exact and the same on every machine, while a timing belongs to one machine on one day.

BagAsList    -> (2, True, False)
BagAsCounts  -> (2, True, False)

One function, stock_report, ran against two structures that share not one line of storage code. One keeps a row of items; the other keeps a table of counts. The caller could not tell the difference, because the ADT is what it was written against.

That is an ADT doing its job.

What the two representations actually cost

They are interchangeable to the caller and they are not equivalent to the machine, which is the second half of the lesson.

class BagAsList:
    def __init__(self):
        self._items = []

    def add(self, item):
        self._items.append(item)

    def size(self):
        return len(self._items)


class BagAsCounts:
    def __init__(self):
        self._counts = {}

    def add(self, item):
        self._counts[item] = self._counts.get(item, 0) + 1

    def size(self):
        return sum(self._counts.values())


import sys

N = 50000
kinds = 5

as_list = BagAsList()
as_counts = BagAsCounts()
for i in range(N):
    item = "kind-%d" % (i % kinds)
    as_list.add(item)
    as_counts.add(item)

print("items added            :", N)
print("distinct kinds         :", kinds)
print("both report the size   :", as_list.size(), as_counts.size())
print("counts version smaller :",
      sys.getsizeof(as_counts._counts) < sys.getsizeof(as_list._items))

items added            : 50000
distinct kinds         : 5
both report the size   : 50000 50000
counts version smaller : True

Fifty thousand items of five kinds. The row keeps fifty thousand entries; the table keeps five. Same ADT, same answers, wildly different memory.

So the ADT tells you what you may ask for, and the choice of representation tells you what it will cost. Both are needed, and separating them is what lets you change the second without breaking every program that relies on the first.

Why the University prints the syllabus this way

Read MU's own labels again. "ADT for linked list". "Stack ADT for Stack". "Queue ADT". "ADT for Tree Structure". "Priority Queue ADT". "Graph ADT". "Hash Table ADT".

Seven of the eight structures in this paper are introduced by their ADT. That is deliberate, and it means the examinable content for each structure is in two parts: what it promises and how it is built. A question asking you to "write the ADT for a stack" is asking for the first, and an answer that starts with an array has answered a different question.

Quick revision

• An ADT is a set of values plus the operations on them, described by behaviour and not by

representation.

• The missing representation is the point, not an omission.
• The operations must say what happens in the impossible cases, such as removing an absent item.
• One ADT can have many representations; a caller written against the ADT works with all of them.
• The representations are not equivalent in cost, which is why the choice still matters.
• MU introduces seven of this paper's eight structures by their ADT, so "write the ADT for X" is a

standard question and it is not asking for code.

Test yourself

1. Define an Abstract Data Type. A set of values together with the operations allowed on them, specified by what the operations do and deliberately not by how the values are stored.

2. What is deliberately left out of an ADT, and why is that not a weakness? The representation. Leaving it out is what lets the representation be changed without breaking any program written against the ADT.

3. An ADT for a bag says remove on an absent item is an error. Is that part of the ADT or part of the implementation? Part of the ADT. What happens in an impossible case is behaviour, and a user needs to know it.

4. Two bags, one a row of items and one a table of counts, gave identical answers. What does that show, and what does it not show? It shows they implement the same ADT, so a caller cannot tell them apart. It does not show they cost the same: with 50,000 items of 5 kinds the table is far smaller.

5. Why is the ADT written before the implementation is chosen? Because the ADT states the problem and the implementation is one answer to it. Choosing storage first fixes the costs before anyone has said what operations matter.

6. "Write the ADT for a stack." What should your answer contain and what should it not? It should contain the values it holds and each operation with what it needs, returns and does, including overflow and underflow. It should not contain an array, a linked list or any code.

A student is examined on the first two. A programmer is disciplined by the third.

How it is signalled in code

Python has no way to truly forbid access, so it uses a convention that every Python programmer understands, and this book follows it throughout.

A name beginning with a single underscore is private. self._items means this is mine, do not touch it, and if you do, nothing is promised. A name without one is public and is part of the ADT.

Look back at the previous chapter: BagAsList stored self._items with the underscore, and MarksV1 above stored self.items without one. That single character is the difference between a class that can be changed later and a class that cannot, and it was the trap in the experiment.

In C++ and Java the compiler enforces it with private. In C you achieve it by putting the structure's fields in one file and only the function declarations in the header.

What you still need to know

Encapsulation hides the representation from the caller. It does not hide it from the designer, and it must not hide it from you in an examination.

You still have to know that a linked list stores an address beside every value, because that is what makes its insertion cheap and its indexing expensive. Hiding is about what a program may depend on, not about what a student may know.

That is the balance this paper keeps: the ADT for the promise, the implementation for the cost, and both examinable.

Quick revision

• A program written against the ADT survives a change of representation; one written against the

representation breaks.

• The break is silent, at a distance, and happens in code nobody edited.
• The rude function was correct when written; it became wrong because it depended on something never

promised.

• Hiding the representation is called encapsulation; the guarantee is information hiding.
• Python signals private with a leading underscore; C++ and Java enforce it with private; C does it

by keeping fields out of the header.

• A user may depend on the ADT and on the documented costs, never on the internals.
• Encapsulation hides the representation from the caller, not from the designer or the student.

Test yourself

1. Two functions computed the same average. Why did only one break when the storage changed? One asked the collection through its operations, which did not change. The other reached into a field it was never promised, and that field no longer existed.

2. Was the broken function wrong when it was written? No. It was correct against the first version. It became wrong when the storage changed, because it depended on something outside the ADT.

3. Why is this kind of break described as "at a distance"? Because the person who changed the storage never touched the broken function and may not know it exists. The fault appears somewhere else entirely.

4. What is encapsulation, and what does it buy? Hiding a structure's representation behind its operations. It buys the freedom to change the representation later without breaking the programs that use the structure.

5. What does a leading underscore mean in this book's code? That the name is private: part of the implementation, not part of the ADT, and nothing about it is promised to a caller.

6. If the representation is hidden, why must you still learn how a linked list is stored? Because the storage decides the costs, and choosing a structure is a decision about costs. Encapsulation limits what a program may depend on, not what a designer needs to know.

size            : 4
next up         : Tum Hi Ho
after bump      : Ilahi
played          : Ilahi
now next up     : Tum Hi Ho
size            : 3
empty playlist  : refused, as the ADT says: play_next on an empty playlist

Every line of that run is the ADT table being obeyed, including the last one: the impossible case behaves the way the design said it would, because it was decided at step 4 and not improvised in the code.

The same method on the practical's own examples

The practical asks for a Student, a Book or an Employee. The method does not change; only step 2 does, because it comes from the problem.

Student. Holds a roll number, a name and marks per subject. Operations: create, record a mark, total, average, has passed. Impossible cases: a mark outside 0 to 100 is an error; average of no marks is an error, not zero, because zero is a real average and "no marks" is not.

Book. Holds an ISBN, a title, an author, a number of copies. Operations: create, lend, return, copies available. Impossible cases: lending when none are available is an error; returning more copies than were lent is an error.

That last one is the habit this chapter is teaching. A good ADT refuses impossible things loudly, and the place to decide that is the design table, before any code exists.

Quick revision

• Design an ADT in five steps: what it holds, which operations the problem needs, what each does, what

happens when it cannot, and only then the representation.

• The operations come from the problem statement, not from a standard list.
• Every operation needs its impossible case decided: empty, absent, full, duplicate.
• Returning None for an error is a defect: the caller cannot tell it from a real value.
• Choose the representation last, and check it against the operations that run most.
• A good ADT refuses impossible things loudly, and that refusal is part of the design, not of the code.

Test yourself

1. List the five steps of designing an ADT. Say what it holds; list the operations the problem needs; say what each needs, returns and does; decide every impossible case; then choose the representation.

2. Why is the representation chosen last? Because it is an answer to the question the ADT states. Choosing storage first fixes the costs before anyone has said which operations matter.

3. play_next on an empty playlist raises an error. Why is returning None worse? Because the caller cannot distinguish "the playlist was empty" from "a song whose value is None", so the mistake is carried on silently instead of being reported where it happened.

4. Design the operations for a Book ADT in a library, with one impossible case each. Book(isbn, title, author, copies); lend(), error when no copies are available; give_back(), error when more are returned than were lent; available(), never fails.

5. Which two of the five steps do students usually skip, and why do they matter? Deciding the impossible cases and choosing the representation last. The first is where most marks and most bugs are; the second is what keeps the design honest about cost.

6. In the Playlist ADT, which single operation is not at an end of the list, and why does that matter? bump, which reaches into the middle. It is the one operation a simple end-based structure cannot do cheaply, so it is the one that decides the representation.

Three changes carry all the value: the duplicate is gone, the two missing operations are in, and subjects() returns a copy, so a caller cannot reach into the record. The cost column is now part of the promise.

Handing out the insides, demonstrated

The defect above is worth seeing happen, because it looks harmless.

class LeakyRecord:
    def __init__(self):
        self._marks = {}

    def record(self, subject, mark):
        self._marks[subject] = mark

    def get_marks(self):
        return self._marks            # the defect: the real thing


class SafeRecord:
    def __init__(self):
        self._marks = {}

    def record(self, subject, mark):
        if not 0 <= mark <= 100:
            raise ValueError("a mark must be between 0 and 100")
        self._marks[subject] = mark

    def get_marks(self):
        return dict(self._marks)      # a copy


for cls in (LeakyRecord, SafeRecord):
    r = cls()
    r.record("Data Structures", 78)
    outside = r.get_marks()
    outside["Data Structures"] = 100          # a caller being careless
    outside["Invented Subject"] = 99
    print("%-12s after an outsider edited what it was handed: %s"
          % (cls.__name__, r.get_marks()))

LeakyRecord  after an outsider edited what it was handed: {'Data Structures': 100, 'Invented Subject': 99}
SafeRecord   after an outsider edited what it was handed: {'Data Structures': 78}

The leaky record now holds a mark of 100 that nobody recorded and a subject that does not exist, and no operation of the ADT was used to do it. Every guarantee the structure made is gone, including the range check, which record applies and a direct edit walks straight past.

The tension, said plainly

Minimal and convenient are in tension, and an examiner may ask you to argue it.

Add average and you have broken minimality but saved every caller a division and prevented a class of mistakes. Refuse it and the ADT is pure and everybody writes the same three lines.

The rule worth stating: add an operation when it is used often enough that callers would otherwise repeat it, and when the structure can implement it better than a caller could. average passes both. sum_of_marks beside total passes neither.

Quick revision

• Three tests: complete (does everything the problem needs), minimal (nothing redundant), honest about

cost (every operation's cost documented).

• Incomplete shows up as a user reaching inside the structure to do a required job.
• Two names for one operation is the clearest failure of minimality.
• Returning the internal container destroys every guarantee, including validation, and is the worst of

the common defects; return a copy.

• Printing and formatting are a different job and do not belong in the ADT.
• Minimality is a guide: add an operation when callers would otherwise repeat it and the structure can

do it better.

Test yourself

1. State the three tests for judging an ADT. Complete, minimal, and honest about cost.

2. An ADT hands back its internal list. Name two guarantees that breaks. Any validation it performs, since a direct edit bypasses it; and every documented cost, since the structure can be changed behind its back by code it does not control.

3. Why is print_report wrong in a StudentRecord ADT? Formatting output is a different responsibility. Including it ties the structure to one output medium and prevents its use with files, pages or printers.

4. average can be built from total and a count. Should it be in the ADT? Yes. Minimality is a guide, not a law: it is used constantly and the structure implements it once and correctly, instead of every caller repeating the division.

5. total and sum_of_marks both exist. Which test fails, and why does it matter later? Minimality. Both must be kept working in every future version of the structure, for no benefit.

6. How does incompleteness usually reveal itself in practice? A user has to reach inside the structure to do something the problem requires, because no operation offers it.

Row major order, and why a 2D array is really 1D

A two dimensional array is stored as one row of cells too, one row of the table after another. This is row major order, and it is examinable because the address formula follows from it.

For an array with C columns, starting at base, with cells of size w:

BASE, COLS, CELL = 2000, 5, 4

print("A is 3 rows x 5 columns, base 2000, 4 bytes a cell")
print()
print("element | offset in cells | address")
for i, j in [(0, 0), (0, 4), (1, 0), (2, 3)]:
    cells = i * COLS + j
    print("A[%d][%d]  | %14d | %d" % (i, j, cells, BASE + cells * CELL))

A is 3 rows x 5 columns, base 2000, 4 bytes a cell

element | offset in cells | address
A[0][0]  |              0 | 2000
A[0][4]  |              4 | 2016
A[1][0]  |              5 | 2020
A[2][3]  |             13 | 2052

Notice A[0][4] and A[1][0] are next to each other in memory, four bytes apart. The row boundary exists only in your head; the machine sees one long run of cells.

Some languages, notably Fortran, store column major instead, down the columns first. The formula then becomes base + ((j x R) + i) x w. An examination question naming a language is asking which of the two you use.

What an array promises, as an ADT

The top three are why arrays are everywhere. The bottom three are why this paper has ten more structures in it.

Quick revision

• An array is a contiguous block of equal-sized cells.
• Address of item i is base + (i x cell size): one multiply, one add, independent of i and of the

array's length. That is O(1) access.

• Indices start at 0 so the arithmetic needs no correction.
• Cells must be equal in size, so a C array holds one type; a Python list stores equal-sized addresses

pointing elsewhere.

• The block is contiguous, so the size is fixed when it is created.
• 2D arrays are stored row major: base + ((i x C) + j) x w. Fortran uses column major.
• A row boundary is not in memory; the cells of one row run straight into the next.

Test yourself

1. Write the address formula for the ith item of a one dimensional array and say why it is O(1). base + (i x w), where w is the cell size. It is one multiplication and one addition whatever i is and however long the array is, so the cost does not grow with the data.

2. Why must all cells be the same size? Because the address is computed by multiplying the index by the cell size. Unequal cells make that multiplication meaningless.

3. A Python list can hold an integer and a string at once. How is that consistent with equal cells? The list stores equal-sized addresses, not the values. The values live elsewhere; the row itself is uniform.

4. Give the row major address of A[2][3] where A has 5 columns, base 2000 and 4 byte cells. Offset in cells is (2 x 5) + 3 = 13, so the address is 2000 + 13 x 4 = 2052.

5. Why can an array not grow? Because its cells must be contiguous, and the memory immediately after the block may already be in use. Growing means allocating a new block and copying.

6. Which single property of the array causes both its greatest strength and its greatest weakness? Contiguity. It makes the address computable, which gives O(1) access, and it fixes the size at creation, which makes growth and middle insertion expensive.

Cost three: growth, and the trick that hides it

A true static array cannot grow: its block is fixed. To hold one more item you allocate a bigger block and copy everything across.

Done naively, one cell at a time, that is ruinous. Python does something cleverer, and it is worth seeing, because it explains a puzzling thing every Python programmer has noticed.

import sys

print("appending one at a time, watching the underlying block:")
print()
row = []
last = sys.getsizeof(row)
grows = 0
for i in range(1000):
    row.append(i)
    now = sys.getsizeof(row)
    if now != last:
        grows += 1
        if grows <= 8:
            print("  at %4d items the block was replaced" % len(row))
        last = now

print()
print("items appended      : 1000")
print("times the block grew:", grows)
print("copies per append, on average: about", round(1000 / grows / 100) / 10 if grows else 0)

appending one at a time, watching the underlying block:

  at    1 items the block was replaced
  at    5 items the block was replaced
  at    9 items the block was replaced
  at   17 items the block was replaced
  at   25 items the block was replaced
  at   33 items the block was replaced
  at   41 items the block was replaced
  at   53 items the block was replaced

items appended      : 1000
times the block grew: 28
copies per append, on average: about 0.0

A thousand appends caused the block to be replaced thirty times, not a thousand. The list does not grow by one; it grows by a proportion, so the gaps between growths get wider as it gets bigger.

That is why appending is described as amortised constant time: any one append might be expensive, but the expensive ones are rare enough that the average over many appends is constant. Chapter 107 uses the same idea again for hash tables.

The three costs, together

Look at that table as a shopping list for the next structure. What would be better?

Something where inserting and deleting cost nothing wherever you are, because nothing has to move. The price will be the top row: you will lose the computed address, and reaching item i will mean walking to it.

That trade is the linked list, and it is the next chapter.

Quick revision

• Inserting at position k moves every item after k: O(n) at the front, O(n) in the middle, free at the

end.

• Deleting closes the hole the same way, with the same costs.
• A static array cannot grow; growth means a new block and a full copy.
• Python's list grows by a proportion, not by one, so 1,000 appends replaced the block about 30 times.
• That makes appending amortised constant: rare expensive operations averaged over many cheap ones.
• "Insertion into an array is expensive" is too crude: at the end it is free, and the cost elsewhere is

proportional to how much of the array sits after the insertion point.

• The structure that fixes this must give up the computed address, which is the linked list's bargain.

Test yourself

1. How many items move when you insert at the front of an array of 8,000? All 8,000, and the moves must be done from the back forward or items overwrite one another.

2. Why is inserting at the end of an array cheap when inserting at the front is not? Because the cost is the number of items sitting after the insertion point. At the end there are none.

3. What does amortised constant time mean, and why does appending to a Python list qualify? That occasional expensive operations are rare enough for the average over many to be constant. The list grows by a proportion, so 1,000 appends caused about 30 block replacements, not 1,000.

4. A deletion from the front of an array of 8,000 items reported 7,999 moves. Why not 8,000? Because the item being deleted does not move; the 7,999 items after it each shift down one place.

5. Which array operation is O(log n), and what does it require? Search, when the array is sorted, using binary search. It requires the data to be in order.

6. What must the next structure give up in exchange for cheap insertion anywhere? The computed address, and so constant-time access to item i: reaching an item will mean walking to it.

class Node:
    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node


def as_row(head):
    out, walk = [], head
    while walk is not None:
        out.append(walk.data)
        walk = walk.next
    return out


head = Node("A", Node("B", Node("C")))
print("before:", as_row(head))

# Insert "NEW" between A and B. Nothing is moved or copied.
new = Node("NEW")
new.next = head.next          # 1. the new node points at B
head.next = new               # 2. A points at the new node
print("after :", as_row(head))
print("nodes moved in memory:", 0)

before: ['A', 'B', 'C']
after : ['A', 'NEW', 'B', 'C']
nodes moved in memory: 0

Two assignments, and it would be two assignments if the list held ten million nodes. Compare the array, which moved 8,000 items to do the same job.

The order of those two assignments is not free. Reverse them and head.next is overwritten before the new node has recorded it, and the rest of the list is lost. Chapter 20 does that deliberately and shows the wreckage.

What it costs

Nothing is free. The linked list pays in three places.

Memory. Every node carries an address beside its value. On a 64 bit machine that is 8 extra bytes per item, so a list of a million small values carries 8 MB of pure overhead.

Access. There is no address arithmetic any more. To reach item 500 you must start at the head and follow 500 links. Reaching item i is O(n), where the array was O(1).

Locality. The nodes are scattered, so the machine's cache, which fetches neighbouring memory in blocks, helps far less than it does with an array. This is why an array often beats a linked list in practice even when the counting says otherwise, and chapter 22 measures exactly that.

Quick revision

• A node holds a value and the address of the next node.
• The nodes may sit anywhere; the order lives in the next fields, not in the positions.
• The head is a variable holding the address of the first node. It is not a node. Lose it and the list

is unreachable.

• The last node's next is null (None in Python, NULL in C), and that is what ends the chain.
• Insertion needs two assignments and moves nothing, whatever the length of the list.
• The order of those assignments matters: point the new node forward first.
• It costs one address per item in memory, O(n) access instead of O(1), and poorer cache behaviour.

Test yourself

1. What two parts does a node have? The data, and next: the address of the following node.

2. Is the head a node? What happens if it is lost? No, it is a variable holding the address of the first node. If it is lost the entire list becomes unreachable even though every node is intact.

3. What marks the end of a singly linked list, and why can it not be left blank? The last node's next field holds null. It is a real value that the traversal tests against; a blank or uninitialised field would be followed into nonsense.

4. How many assignments insert a node after a known node, and how many items move? Two assignments, and nothing moves, whatever the list's length.

5. Give the three costs of a linked list against an array. One address of memory per item; O(n) access to item i instead of O(1); and scattered nodes, which use the cache poorly.

6. Draw a three node list with the head and the terminator marked. An arrow labelled head into the first box; each box split into data and next; arrows from each next to the following box; and the last next shown as a cross or null rather than left empty.

empty: is_empty = True | length = 0 | contents = []
one  : is_empty = False | length = 1 | contents = ['only']
three: is_empty = False | length = 3 | contents = ['A', 'B', 'C']

Look at prepend and see why it needs no special case at all:

When the list is empty, self.head is None, so the new node's next becomes None, which is exactly right for a single node list. When the list is not empty, the new node points at the old first node, which is also exactly right. One line, no if.

That is the mark of a well written linked list operation: the empty case falls out of the general case rather than being bolted on beside it. Where it cannot, the special case is written first and deliberately.

Why length is O(n) here, and what to do about it

length above walks the entire list counting nodes. For an array, length is stored and is O(1).

There are two honest answers, and an examiner may ask for both.

Walk and count. Simple, nothing to keep in step, O(n).

Keep a counter in the list object, incremented on every insertion and decremented on every deletion. O(1) to read, but now every operation that changes the list must remember to update it, and the day one forgets, the structure lies about its own size.

This book keeps the counter from chapter 20 onwards and says so where it does, because by then the list is used inside stacks and queues where length is asked for constantly.

Quick revision

• The ADT is the operations and their behaviour: create, is_empty, length, prepend, append, search,

insert_at, delete, traverse. It names no node, no next and no head.

• The empty list is head = None, and every operation must work on it.
• Ask three questions of every operation: what if empty, what if one node, does it change the head.
• self.head = Node(value, self.head) prepends correctly whether or not the list is empty, with no

special case.

• A good linked list operation makes the empty case fall out of the general case.
• length by walking is O(n); a stored counter makes it O(1) but must be maintained by every operation

that changes the list.

Test yourself

1. Write the linked list ADT. What must your answer not mention? The operations with what each needs, returns and does. It must not mention nodes, next pointers or the head, which are implementation.

2. How is an empty linked list represented, and why is it the hard case? head is null. It is hard because every operation must behave correctly when there is no first node, and operations that change the head must write the new head back.

3. Why does self.head = Node(value, self.head) need no test for emptiness? Because when head is None the new node's next becomes None, which is correct for a one node list; and when head is a node the new node points at it, which is correct too.

4. State the three questions to ask of any linked list operation. What does it do when the list is empty; what when it has exactly one node; and does it change the head, and if so has it assigned it.

5. Why is length O(n) on this list but O(1) on an array? The array stores its length. The list must walk from the head to the end, counting, because nothing records how many nodes there are.

6. Give the cost of keeping a length counter in the list object. Reading becomes O(1), but every insertion and deletion must update it, and any operation that forgets leaves the structure reporting a size it does not have.

Number 2 stops early. Testing while walk.data instead of while walk is not None works on most data and then silently stops at the first empty string, zero or None in the list. Test the node, never the value inside it.

Number 3 skips the first node. Advancing before using visits nodes 2 to n. It is easy to write when converting a for loop out of habit.

What traversal costs

One visit per node, so n steps for n nodes: O(n), and there is no faster way. A linked list has no shortcut to the middle, so anything that needs to see the whole list costs a full walk.

That is worth stating plainly because it is the source of several later results. length is O(n). append without a tail pointer is O(n). Reaching item i is O(n). All three are the same walk.

Traversing with an index, and why it is a trap

Students who learned arrays first sometimes write this:

If item_at(i) walks from the head, that loop is not O(n). It is O(n squared): the first item costs 1 step, the second 2, the last n, and the total is about n squared over 2. On a list of 10,000 that is about 50 million steps to do what a single traversal does in 10,000.

class Node:
    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node


def build(n):
    head = None
    for value in reversed(range(n)):
        head = Node(value, head)
    return head


def item_at(head, i):
    """Walk to item i. Returns (value, steps)."""
    walk, steps = head, 0
    while i > 0:
        walk = walk.next
        steps += 1
        i -= 1
    return walk.data, steps


def by_traversal(head):
    steps, walk = 0, head
    while walk is not None:
        steps += 1
        walk = walk.next
    return steps


def by_index(head, n):
    total = 0
    for i in range(n):
        _, steps = item_at(head, i)
        total += steps + 1
    return total


for n in (250, 500, 1000, 2000):
    head = build(n)
    print("n = %4d   one traversal: %5d steps   indexed loop: %8d steps"
          % (n, by_traversal(head), by_index(head, n)))

n =  250   one traversal:   250 steps   indexed loop:    31375 steps
n =  500   one traversal:   500 steps   indexed loop:   125250 steps
n = 1000   one traversal:  1000 steps   indexed loop:   500500 steps
n = 2000   one traversal:  2000 steps   indexed loop:  2001000 steps

Read the right column down: the data doubles and the work goes up four times. That is the signature of O(n squared), and it comes from writing an array's loop over a linked structure.

Quick revision

• Traversal: walk = head, then while walk is not null, use walk.data and walk = walk.next.
• Every linked list algorithm is that shape with something added.
• The empty list needs no special case: the loop never runs.
• Three classic errors: forgetting to advance (hangs for ever), testing walk.data instead of the node

(stops at the first falsy value), advancing before using (skips the first node).

• Traversal is O(n) and there is no shortcut, which is why length, append without a tail, and access by

index are all O(n).

• Looping by index over a linked list is O(n squared): doubling the data quadrupled the work in the run

above.

Test yourself

1. Write the traversal pattern in three lines. walk = head; while walk is not null: use walk.data; walk = walk.next.

2. Why does a correct traversal need no special case for the empty list? Because head is null, so the loop condition fails immediately and the body never runs.

3. What happens if walk = walk.next is omitted, and why is that worse than a crash? The loop never ends. It hangs rather than failing, so there is no error message and no line number to look at.

4. Why test walk is not None rather than walk.data? Because a node may legitimately hold an empty string, a zero or None, and testing the data would stop the traversal at that node instead of at the end of the list.

5. A loop calls item_at(i) for i from 0 to n-1. What is its cost, and why? O(n squared), because each item_at walks from the head: 1 step, then 2, up to n, which totals about n squared over 2.

6. In the run above, n doubled from 1000 to 2000. What happened to the indexed loop's steps? They went from about 500,000 to about 2,000,000, four times as many, which is the signature of O(n squared).

n = 1000 | sorted linear:  1000 comparisons | binary: 10 comparisons but   9996 pointer steps
n = 2000 | sorted linear:  2000 comparisons | binary: 11 comparisons but  21995 pointer steps
n = 4000 | sorted linear:  4000 comparisons | binary: 12 comparisons but  47994 pointer steps

The comparisons did drop to about 10, exactly as binary search promises. But the pointer steps went up, to ten times the length of the list, because every one of those ten comparisons had to walk from the head to find its element.

So binary search on a linked list is not merely no better; it is considerably worse. The structure decides which algorithms are available to it, and that is the real lesson.

What this tells you about choosing

The third row is why Module 2 exists. Module 1 gives you two structures, each good at one thing and bad at the other, and the binary search tree is the structure that refuses to choose.

Quick revision

• Search is a traversal with a comparison: O(n).
• Best case 1 comparison, worst case n, average about n/2 when present; an unsuccessful search always

costs n.

• On a sorted list you may stop early once you pass the target, which halves the average unsuccessful

search but does not change the order of growth.

• Binary search needs to jump to the middle; a linked list has no way in except from the front.
• Measured, binary search over links used about 10 comparisons but ten times the list length in pointer

steps, so it is worse than the plain walk.

• The structure decides which algorithms are available to it.

Test yourself

1. Give the best, worst and average comparisons for searching a linked list of n nodes. Best 1, worst n, average about n/2 when the value is present. An unsuccessful search always costs n.

2. What early exit does a sorted linked list allow, and does it change the complexity? You may stop as soon as a value greater than the target is reached. It improves the average unsuccessful search but the complexity stays O(n).

3. Why can binary search not be used efficiently on a linked list? Binary search must jump to the middle of a range. A linked list can only be entered at the head, so each jump costs a walk, and the walking dominates.

4. In the measured run, what happened to comparisons and to pointer steps under binary search? Comparisons fell to about 10, as promised, but pointer steps rose to roughly ten times the length of the list, making it worse overall than a single traversal.

5. Which structure would you choose for frequent searching with frequent insertion, and why not a list or a sorted array? A binary search tree, which does both in O(log n). A sorted array searches well but inserts in O(n); a linked list inserts well but searches in O(n).

6. State the general lesson this chapter illustrates. The structure determines which algorithms are available. An algorithm's stated complexity assumes the operations it needs are cheap, and on a different structure they may not be.

Two per node, at every size. That is what O(1) per operation looks like when you count it rather than time it.

Against the array

The same job on an array, from chapter 12: inserting at the front moves every existing item, so inserting n items at the front of an array costs about n squared over 2 moves in total.

The array column grows by a factor of a hundred each time the list column grows by ten. This one operation is the entire argument for the linked list.

Where prepending is the natural thing to do

Three places in this paper, all of them later chapters, use prepending because it is free:

• A stack (chapter 33) pushes and pops at the front, so both operations are O(1).
• Reversing a list is a traversal that prepends each node onto a new list.
• Chaining in a hash table (chapter 104) prepends each colliding key onto the front of its bucket,

because the bucket's order does not matter and the front is cheapest.

Quick revision

• Prepend: build the node, point it at the old head, then move the head. Two assignments.
• The order is load bearing: pointing the new node forward must come first, or the rest of the list is

lost.

• It works on an empty list with no special case, because the new node's next becomes null.
• It is O(1): measured at 2 pointer assignments per node at every size from 100 to 100,000.
• Prepending reverses the order of insertion.
• Inserting n items at the front of an array costs about n squared over 2 moves; the linked list costs

2n assignments.

• Stacks, list reversal and hash table chaining all prepend because it is free.

Test yourself

1. Write the prepend operation in three lines. new = Node(value); new.next = head; head = new.

2. What happens if the two assignments are done in the wrong order? head = new first would overwrite the only reference to the old first node, so new.next = head would then point the new node at itself and the rest of the list would be unreachable.

3. Why does prepend need no special case for the empty list? Because when head is null the new node's next becomes null, which is exactly the correct shape for a one node list.

4. What is the cost of prepending, and what evidence is given for it here? O(1). Counted, it is exactly 2 pointer assignments per node at every size from 100 to 100,000 nodes.

5. Values C, B, A are prepended in that order. What does the list contain? A, B, C. Prepending reverses the order of insertion.

6. Give two places later in this paper where prepending is chosen because it is free. The stack, which pushes and pops at the front; and chaining in a hash table, where a colliding key is put at the front of its bucket because the bucket's order does not matter.

append A -> ['A'] | tail holds A
append B -> ['A', 'B'] | tail holds B
append C -> ['A', 'B', 'C'] | tail holds C

appended  100 nodes with a tail:   200 assignments, 2 per node
appended  200 nodes with a tail:   400 assignments, 2 per node
appended  400 nodes with a tail:   800 assignments, 2 per node
appended  800 nodes with a tail:  1600 assignments, 2 per node

Two per node at every size, the same as prepend. The 318,801 steps for 800 nodes became 1,600.

The general habit

This is worth naming, because the paper does it four more times.

When an operation recomputes something that could have been remembered, remember it. The cost is a little memory and the discipline of keeping the remembered thing correct.

And the matching warning, which is the same every time: anything remembered must be updated by every operation that could invalidate it. A tail pointer that is not updated on deletion of the last node is worse than no tail pointer at all, because the list still looks correct.

What the tail cannot fix

A tail pointer makes appending cheap. It does not make deleting from the end cheap, and that catches people.

To delete the last node you must set the second to last node's next to null, and a singly linked list gives you no way to find the second to last node except by walking from the head. The tail pointer tells you where the end is, not what came before it.

Deleting from the end of a singly linked list is O(n) even with a tail pointer. Fixing that needs a backward link, which is the doubly linked list of chapter 26.

Quick revision

• A singly linked list has no way to find its end except by walking; the naive append is O(n).
• Building a list by naive appending is O(n squared): 800 nodes cost 318,801 pointer steps.
• The append traversal stops on the last node, testing walk.next is not null, not walk is not null.
• A tail pointer makes append O(1): measured at 2 assignments per node at every size.
• On the first node, head and tail are both set to it.
• Anything remembered must be maintained by every operation that could invalidate it.
• A tail pointer does not make deletion from the end cheap: that needs the second to last node, which

only a backward link gives you.

Test yourself

1. Why is appending to a singly linked list O(n) without a tail pointer? Because nothing records where the list ends, so the last node must be found by following the chain from the head.

2. What is the cost of building an n node list by naive appending, and what did the run show? O(n squared). Doubling the nodes quadrupled the steps: 100 nodes cost 4,851 steps and 800 cost 318,801.

3. Why is the loop condition walk.next is not null rather than walk is not null? Because the operation must stop on the last node in order to modify it. The ordinary traversal condition would walk past the end.

4. What must be set when the first node is appended to an empty list? Both head and tail must be set to the new node.

5. State the general habit this chapter introduces, and its matching danger. Remember what would otherwise be recomputed. The danger is that anything remembered must be updated by every operation that could invalidate it, or the structure lies while still appearing to work.

6. Does a tail pointer make deleting the last node O(1)? Explain. No. Deleting the last node requires setting the second to last node's next to null, and a singly linked list can only find that node by walking from the head. It stays O(n) until a backward link exists.

Every case behaves: the first node, a middle node, the last node, the only node, an absent value and an empty list. The empty list needed no special case at all, because the loop simply never runs and the error is raised at the end.

What it costs, and the honest statement of it

Removing a known node, when you already hold its predecessor, is two assignments: O(1).

Removing a node by value requires finding it first, which is a search: O(n).

Students often say "deletion from a linked list is O(1)", and examiners mark it wrong, because the sentence is missing its condition. The correct statement is:

Deletion is O(1) given the predecessor, and O(n) if the node must be found.

That distinction returns in chapter 29, where a doubly linked list can delete a known node in O(1) without its predecessor being supplied, and in chapter 104, where a hash table's chains are kept short precisely so that this search stays cheap.

The node that is removed but not gone

In C, unlinking a node leaks its memory unless you free it, and freeing it before reading its next reads memory you have given back. The order is: remember walk.next, unlink, then free.

In Python the garbage collector handles it once nothing refers to the node. It is worth knowing that this is a service the language is performing, not a property of linked lists.

Quick revision

• To remove a node you must modify the node before it, and a singly linked list cannot look backwards.
• So deletion walks with two pointers, previous and walk.
• Four cases: empty list (error), first node (move the head), any other node (`previous.next =

walk.next`), absent (error).

• Removing the first node changes the head, and the new head must be written back.
• Deletion is O(1) given the predecessor, O(n) if the node must be found by value. The unqualified

claim "deletion is O(1)" is wrong.

• In C, unlink first and free afterwards, having already saved walk.next.

Test yourself

1. Why is finding the node to delete not enough? Because deletion changes the node before it, and a node in a singly linked list holds no reference back to whatever points at it. The predecessor must be tracked on the way in.

2. Write the two pointer loop for deletion. previous = null; walk = head; while walk is not null and walk.data is not the target: previous = walk; walk = walk.next.

3. What tells you that the node to be removed is the first one, and what must you do then? previous is still null. Set head = walk.next, and make sure the new head is written back to the list.

4. Give the correct complexity statement for deletion, with its condition. O(1) if the predecessor is already known, O(n) if the node has to be found by value.

5. In C, in what order must unlinking and freeing be done, and why? Save walk.next first, then unlink, then free. Freeing before reading next would read memory that has been given back.

6. Removing "E" from a five node list examined five nodes. Removing "A" examined one. What does that show? That the cost of removal by value is the cost of the search, so it depends on where the value sits, not on the unlinking, which is always two assignments.

Two details in that run are examinable.

Insertion allows k equal to the length (appending), while deletion does not (there is no item there). That is why the two range checks differ, and getting them the same way round is a common error.

The walk is k-1 steps, not k. Inserting at position 4 walked 3.

The wrong order, run

Chapter 13 warned that new.next = walk.next must come before walk.next = new. Here is what the other order actually does.

class Node:
    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node


def as_row(head, cap=8):
    """Walk, but stop after cap nodes so a broken list cannot hang this."""
    out, walk, n = [], head, 0
    while walk is not None and n < cap:
        out.append(walk.data)
        walk = walk.next
        n += 1
    if walk is not None:
        out.append("... still going")
    return out


head = Node("A", Node("B", Node("C")))
walk = head                       # insert after A

new = Node("NEW")
walk.next = new                   # WRONG: the predecessor points at the new node first
new.next = walk.next              # and now the new node points at ITSELF

print("after the wrong order:", as_row(head))
print("does NEW point at itself?", new.next is new)

after the wrong order: ['A', 'NEW', 'NEW', 'NEW', 'NEW', 'NEW', 'NEW', 'NEW', '... still going']
does NEW point at itself? True

The list now contains a cycle: NEW points at itself, so any traversal runs for ever. B and C are still in memory, perfectly intact, and completely unreachable.

This is why the order is taught as a rule rather than left to be worked out each time: the failure is not an error message, it is a program that never returns.

The cost

The assignments are constant everywhere. It is the walking that costs, so the position decides the price. That is the reverse of the array, where the assignments were the cost and the position decided how many items had to move.

And a tail pointer helps only the last of those rows, and only for insertion, for the reason chapter 18 gave: the end can be reached, but the node before the end cannot.

Quick revision

• One procedure covers every position: walk to k-1, then two assignments. Position 0 is the special

case, since nothing precedes it.

• Insert allows k equal to the length; delete does not. The range checks are deliberately different.
• The walk is k-1 steps, not k.
• The assignment order is load bearing: point the new node forward first. Reversed, the new node points

at itself, the list gains a cycle, and every traversal runs for ever while the rest of the list stays intact and unreachable.

• Assignments are O(1) at every position; the walk is what costs, so the cost is O(1) at the front and

O(n) elsewhere.

• This is the reverse of the array, where the shifting was the cost.

Test yourself

1. Write the general insert-at-k procedure. If k is 0, prepend. Otherwise walk to the node at position k-1, set new.next = walk.next, then walk.next = new.

2. Why does insertion permit k equal to the length while deletion does not? Because inserting at the length means appending after the last item, which is a real position. Deleting at the length would delete an item that is not there.

3. How many steps does the walk take to insert at position 4? Three: the walk stops at position 3, the node before the insertion point.

4. Exactly what happens if the two assignments are reversed? The predecessor is pointed at the new node first, so walk.next is already the new node when new.next = walk.next runs, and the new node points at itself. The list has a cycle, traversals never end, and the remaining nodes become unreachable.

5. Why is this failure worse than an error message? Because nothing reports it. The program hangs, and the data that was lost is still in memory and perfectly intact, so nothing looks corrupted.

6. What is the cost of insertion at the front, the middle and the end of a singly linked list? O(1) at the front, O(n) in the middle and O(n) at the end. The two assignments are constant everywhere; the walk to position k-1 is what costs.

Read the first two rows together, because they are the whole bargain: the array wins the first, the list wins the second, and no structure in Module 1 wins both.

The sentence that is almost always wrong

"Linked lists are better than arrays for insertion."

It needs a condition, and without it examiners mark it down. Inserting into a linked list is O(1) once you are standing at the right place. Getting there is O(n). So inserting into a linked list by position is O(n) overall, exactly like the array.

The linked list wins when the position is already known: while traversing, at the front, at a node you already hold. That is why chapter 104 uses a linked list for hash table chains, where insertion is always at the front, and why the stack and the queue are built on one.

When to choose which, as a rule

Quick revision

• Advantages: O(1) insertion and deletion given the position; no fixed size; no wasted capacity; no

large contiguous block needed; stacks, queues and deques build on it.

• Disadvantages: O(n) access to item i; an address of memory per item; no backward link; poor cache

behaviour; no binary search even when sorted.

• The array wins access; the list wins insertion; neither wins both.
• "Better for insertion" is only true when the position is already known, because reaching a position

is O(n).

• Deleting the last node is O(n) even with a tail pointer.

Test yourself

1. Give three advantages of a singly linked list over an array. Insertion and deletion at a known position are O(1); the size is not fixed and no capacity is wasted; and it needs no single large contiguous block of memory.

2. Give three disadvantages. Access to item i is O(n); every node costs an extra address of memory; and there is no backward link, so deletion needs the predecessor tracked on the way in. Cache behaviour and the loss of binary search are two more.

3. Why is "linked lists are better for insertion" incomplete? Because insertion is O(1) only once you are at the position. Reaching position k is O(n), so insertion by position costs the same as the array's.

4. Name two places in this paper where the linked list's insertion advantage is genuinely realised. Hash table chaining, where insertion is always at the front of a bucket; and the stack, where every operation is at one end. The queue with a tail pointer is a third.

5. Which operation is O(n) on a linked list even with a tail pointer, and why? Deleting the last node, because the node before it must be modified and only a forward walk can find it.

6. A program stores a few thousand integers and mostly reads them by index in a tight loop. Which structure and why? The array. Indexing is O(1) against O(n), and the contiguous layout uses the cache well, which matters more than the counting suggests.

The consequence, and it surprises people: an array often beats a linked list at operations the counting says the list should win, once the data is large enough for cache to matter, because the array's 1,000 cheap moves can beat the list's 2 expensive pointer chases.

This book does not print a timing to prove that, for the reason chapter 1 gave. What it does is state it and name it, because an examiner asking "is a linked list always better for insertion" is asking about exactly this.

The comparison, as the practical wants it written

Choosing between them, as one sentence

If the work is dominated by reaching items by position, use the array. If it is dominated by inserting and removing at positions you are already standing at, use the linked list. If it is both, you need a structure from Module 2.

That last clause is the bridge. Every structure in Module 2 exists because Module 1's two structures each fail at half the job.

Quick revision

• Counted head to head: building 4,000 items by prepending cost the array 8,002,000 moves and the list

8,000 assignments; reading the last item cost the array 1 and the list 4,000.

• The array's prepending work quadruples when n doubles; the list's doubles.
• They are opposites, not better and worse.
• Counting cannot see cache: an array's items are fetched together in blocks, a list's nodes are

scattered, so an array often wins in practice even where the count says otherwise.

• Array: fixed size, contiguous, O(1) access, expensive insertion except at the end.
• Linked list: grows at run time, scattered, O(n) access, O(1) insertion at a known position.
• If the work needs both cheap access and cheap insertion, neither is enough, and that is why Module 2

exists.

Test yourself

1. At n = 4000, what did building by prepending cost each structure, and why do they differ so much? The array did 8,002,000 moves and the list 8,000 assignments. Each array insertion shifts about n items while each list insertion costs two assignments whatever the length.

2. At the same size, what did reading the last item cost each? The array 1 unit, the list 4,000. The array computes the address; the list must walk.

3. What effect does counting fail to capture, and which structure does it favour? Cache behaviour. Memory is fetched in blocks, so an array's neighbouring items come along for free while a linked list's scattered nodes may each need a fresh fetch. It favours the array.

4. Give the four rows of the comparison that concern memory. The array is a fixed contiguous block and wastes unused capacity; the list is scattered nodes and costs one address per item.

5. State in one sentence when to choose each. The array when the work is reaching items by position; the linked list when the work is inserting and removing at positions you are already at.

6. Why does this comparison point forward to Module 2? Because each structure fails at half the job, and a problem needing both cheap access and cheap insertion cannot be solved by either. Trees and hash tables are the answers.

P(x)        = 5x^4 + 3x^2 + 7
degree      = 4
terms held  = 3
P(2)        = 99

Q(x)        = 3x^1000 + 5
degree      = 1000
terms held  = 2
an array for Q would need 1001 cells to hold 2 numbers

Check P(2) by hand: 5 times 16 is 80, plus 3 times 4 is 12, plus 7, which is 99. The program agrees.

The two invariants

The representation makes two promises, and every operation in the next two chapters depends on both.

1. Exponents are strictly decreasing. No two nodes share an exponent, and they are in order. This is what lets addition walk the two lists together in one pass.

2. No coefficient is zero. A term that cancels is removed, not kept with a coefficient of 0. This is what keeps a sparse polynomial sparse.

The second is easy to forget when writing addition, and chapter 24 shows what happens when it is.

Measured: where each representation wins

def array_cells(terms):
    """An array indexed by exponent needs degree + 1 cells."""
    return max(e for _, e in terms) + 1


def list_nodes(terms):
    """The linked list needs one node per non-zero term."""
    return sum(1 for c, _ in terms if c != 0)


cases = [
    ("dense, degree 4",      [(5, 4), (2, 3), (3, 2), (1, 1), (7, 0)]),
    ("sparse, degree 1000",  [(3, 1000), (5, 0)]),
    ("one term, degree 50",  [(1, 50)]),
    ("dense, degree 10",     [(i + 1, i) for i in range(11)]),
]

print("%-22s %8s %8s   %s" % ("polynomial", "array", "list", "better"))
for name, terms in cases:
    cells, nodes = array_cells(terms), list_nodes(terms)
    # a list node holds two numbers and an address, so count it as 3 units
    better = "list" if nodes * 3 < cells else "array"
    print("%-22s %8d %8d   %s" % (name, cells, nodes * 3, better))

polynomial                array     list   better
dense, degree 4               5       15   array
sparse, degree 1000        1001        6   list
one term, degree 50          51        3   list
dense, degree 10             11       33   array

The honest answer is it depends on sparseness, and the table says where the line is. A node costs about three units against an array cell's one, so the list wins once fewer than about a third of the terms are present.

That is the right way to answer "why use a linked list for a polynomial" in an examination: not "because it is dynamic", but because a sparse polynomial wastes most of an array, and the list charges only for the terms that exist.

Quick revision

• A polynomial is stored as a linked list of terms, each node holding a coefficient and an exponent.
• Two invariants: exponents strictly decreasing, and no zero coefficients.
• The array representation indexes by exponent and needs degree + 1 cells whatever the number of terms.
• A sparse polynomial, with few terms relative to its degree, wastes almost all of an array: 3x^1000 + 5

needs 1,001 cells to hold 2 numbers.

• A node costs about three units to an array cell's one, so the list wins when fewer than about a third

of the terms are present.

• For a dense polynomial the array is better, and saying so is part of the answer.

Test yourself

1. What does each node of a polynomial list hold? A coefficient, an exponent, and the address of the next term.

2. State the two invariants of this representation. Exponents are strictly decreasing, with no repeats; and no coefficient is zero.

3. How many cells does an array need for 3x^1000 + 5, and how many nodes does the list need? 1,001 cells against 2 nodes.

4. Define a sparse polynomial. One with few non-zero terms relative to its degree.

5. Give the examination answer to "why use a linked list for a polynomial". Because a sparse polynomial leaves almost all of an array empty, while the list charges only for the terms that exist. For a dense polynomial the array is the better choice.

6. Evaluate 5x^4 + 3x^2 + 7 at x = 2 and show the working. 5 times 16 is 80, 3 times 4 is 12, plus 7, giving 99.

P(x)      = 5x^4 + 3x^2 + 7
Q(x)      = 2x^4 + 4x^3 + 1x
P + Q     = 7x^4 + 4x^3 + 3x^2 + 1x + 7
comparisons: 4
check at x = 2: 99 + 66 = 165 | sum polynomial gives 165

cancellation: (5x^2 + 3x) + (-5x^2 + 2) = 3x + 2
terms kept  : [(3, 1), (2, 0)]

everything cancels -> 0 | terms: []

Three things in that run are the answer to the examination question.

The sum is correct, and it is checked independently: evaluating P and Q at x = 2 and adding gives 165, and evaluating the sum polynomial gives 165 too. That is a real check, not a restatement.

The cancelled term is gone. 5x^2 and -5x^2 produced no node at all, and the answer is 3x + 2, with two terms, not three.

Everything cancelling gives the zero polynomial, an empty list, printed as 0. An empty result is a legitimate answer and the code must produce it rather than failing.

The cost

One pass, and each comparison advances at least one of the two lists. So for polynomials with m and n terms, addition is O(m + n), which is the best possible: you cannot add them without looking at every term.

Compare the array representation: adding two arrays indexed by exponent costs O(larger degree), whether or not the terms exist. For the sparse case that is enormously worse. 3x^1000 + 5 added to itself is 2 comparisons on lists and 1,001 additions on arrays.

Subtraction, in one line

Subtraction needs no new algorithm: negate every coefficient of the second polynomial and add. An examiner asking for subtraction is checking that you noticed.

Quick revision

• Both lists are in decreasing exponent order, so the largest remaining exponent of the answer is at one

of the two current nodes: one pass suffices.

• Three cases: A's exponent larger, B's larger, or equal. When equal, add the coefficients.
• If the coefficients cancel to zero, attach nothing: a zero term breaks the representation's invariant.
• After the loop, attach whatever remains of the unexhausted list. Forgetting the tail is a standard

error.

• Cost is O(m + n), which is optimal; the array version costs O(larger degree) whether the terms exist

or not.

• Everything cancelling gives the empty list, which prints as 0 and is a valid answer.
• Subtraction is negation of the second polynomial followed by addition.

Test yourself

1. Why does one pass suffice to add two polynomials? Because both lists are in decreasing exponent order, so the next term of the answer is always one of the two nodes currently being looked at.

2. Give the three cases inside the merge loop. A's exponent greater: take A's term. B's greater: take B's. Equal: add the coefficients and take the result if it is not zero.

3. What must happen when two coefficients cancel, and why? No node is attached. Keeping a zero term breaks the invariant that no coefficient is zero, and it makes a sparse polynomial less sparse for no benefit.

4. What is the commonest omission after the merge loop? Attaching the remaining terms of whichever list is not yet exhausted.

5. Give the complexity of list addition and of array addition, and say when the difference matters. O(m + n) for lists, where m and n are the term counts; O(larger degree) for arrays. The difference matters for sparse polynomials: adding 3x^1000 + 5 to itself is 2 comparisons against 1,001 additions.

6. How is subtraction implemented? Negate every coefficient of the second polynomial and then add. No separate algorithm is needed.

P(x)   = 5x^2 + 3
Q(x)   = 2x + 4
P x Q  = 10x^3 + 20x^2 + 6x + 12
term multiplications: 4

independent check at x = 3:
  P(3) x Q(3) = 48 x 10 = 480
  the product polynomial at 3 gives 480
  they agree: True

(1x^4 + 1x^3 + 1x^2 + 1x + 1) x (1x^2 + 1x + 1)
  = 1x^6 + 2x^5 + 3x^4 + 3x^3 + 3x^2 + 2x + 1
  term multiplications: 15 = 5 x 3
  terms in the answer : 7

The small product can be checked by hand: (5x^2 + 3)(2x + 4) is 10x^3 + 20x^2 + 6x + 12. The program agrees, and the evaluation check at x = 3 agrees independently.

The larger one shows the shape: 5 terms times 3 terms is 15 multiplications, and the answer has 7 terms, because the 15 partial products collapsed onto 7 distinct exponents.

The cost, and the honest verdict

Multiplication is O(m n) multiplications, and that is unavoidable: every pair of terms contributes.

But the collection costs more than it should here. Each row of partial products is merged into the answer, and the answer grows, so the merging is roughly O(m n) again in the best arrangement and worse in a careless one. Written naively, appending every partial product and then sorting and collecting, it is O(m n log(m n)).

Now compare the array representation, indexed by exponent. Multiplication there is:

Two loops, no merging, no ordering to maintain, no cancellation to check. It is simpler and faster for a dense polynomial, because the array's index does the collecting for free.

So the honest verdict, and the one worth writing in an answer:

The linked representation is chosen for sparse polynomials and for addition. It is not chosen because it is better at everything, and multiplication is where it shows.

That is the pattern this whole paper keeps repeating. A structure is a bargain, and part of knowing it is knowing what you paid.

Quick revision

• Multiplying: coefficients multiply, exponents add. m terms times n terms gives m n partial products.
• The partial products arrive out of order and many share an exponent, so they must be collected.
• The clean method is to multiply one term of P into a running answer using polynomial addition, which

keeps the answer ordered and collected throughout.

• Cost is O(m n) multiplications, plus collection; a naive approach adds a sort and becomes

O(m n log(m n)).

• The array representation multiplies with two loops and result[i + j] += p[i] * q[j], with the index doing the collecting for free, so it is simpler and faster for dense polynomials. - The linked representation is chosen for sparseness and for addition, not because it is better at everything.

Test yourself

1. What happens to coefficients and exponents when two terms are multiplied? The coefficients multiply and the exponents add.

2. How many partial products does multiplying an m term by an n term polynomial give? m times n.

3. Why is multiplication harder on a linked list than addition was? The partial products come out unordered and many share an exponent, so they must be collected, whereas addition's single merge produced an already ordered, already collected answer.

4. Describe the clean method used in this chapter. Multiply each term of P by the whole of Q to make a row, and add that row into a running answer using polynomial addition, which keeps the answer ordered and collected at every step.

5. Write the array version of polynomial multiplication in one line, and say why it is simpler. result[i + j] = result[i + j] + p[i] * q[j] over all i and j. The index collects terms of equal exponent automatically, so there is no merging, no ordering and no cancellation check.

6. State the honest verdict on the two representations. The linked list is for sparse polynomials and for addition; the array is better for dense polynomials and for multiplication. The linked representation is a bargain, not an improvement in every direction.

forward        : ['A', 'B', 'C', 'D']
backward       : ['D', 'C', 'B', 'A']
length         : 4
head.prev      : None
tail.next      : None
consistency    : consistent

one node: head is tail: True | prev: None | next: None
consistency    : consistent
empty    : [] [] consistent

The backward traversal is the new capability, and it costs nothing extra: it is the same loop following prev from the tail.

The invariant, and why it is checked

A doubly linked list has an invariant that a singly linked one does not:

For every node x with a next, x.next.prev must be x.

The two chains must agree. Every operation has to maintain both, and an operation that updates one and forgets the other leaves a list that traverses correctly forwards and wrongly backwards, or vice versa. That defect is invisible until somebody walks the other way.

This is why the class above carries a check method and why the rest of this book calls it after every operation it demonstrates. It is the same discipline as chapter 18's tail pointer: anything remembered twice must be kept in step, and the way to be sure is to verify it rather than trust it.

Quick revision

• A doubly linked node holds prev, data and next.
• The first node's prev is null and the last node's next is null; a one node list has both in the same

node.

• The backward link removes the predecessor problem, so deleting a known node is O(1).
• Backward traversal becomes possible: the same loop from the tail following prev.
• The ADT gains insert_before, delete(node) and traverse_backward.
• The invariant is that x.next.prev is x for every node with a next; both chains must always agree.
• An operation that updates one chain and forgets the other leaves a defect invisible in one direction.

Test yourself

1. What three fields does a doubly linked node hold? prev, the address of the previous node; data; and next, the address of the following node.

2. What is the first node's prev, and the last node's next? Both are null. In a one node list, that single node has both.

3. Which problem from the singly linked list does the second link remove, and what does it buy? The predecessor problem. Deleting a node you already hold becomes O(1), because its previous node can be reached directly instead of being found by walking.

4. State the invariant of a doubly linked list. For every node x that has a next, x.next.prev must be x. The forward and backward chains must agree.

5. What kind of defect does breaking that invariant produce, and why is it hard to find? One that traverses correctly in one direction and wrongly in the other. It is invisible until somebody walks the other way, and until then every test passes.

6. Why does the class in this chapter carry a check method? Because the invariant is maintained by hand in every operation, and the reliable way to know it holds is to verify it after each operation rather than trust that it was remembered.

start          : ['A', 'B', 'D'] ['D', 'B', 'A'] ok
insert C after B: ['A', 'B', 'C', 'D'] ['D', 'C', 'B', 'A'] ok
insert E at end : ['A', 'B', 'C', 'D', 'E'] ['E', 'D', 'C', 'B', 'A'] ok
insert Z at head: ['Z', 'A', 'B', 'C', 'D', 'E'] ['E', 'D', 'C', 'B', 'A', 'Z'] ok
delete the head : ['A', 'B', 'C', 'D', 'E'] ['E', 'D', 'C', 'B', 'A'] ok
delete the tail : ['A', 'B', 'C', 'D'] ['D', 'C', 'B', 'A'] ok
delete a middle : ['A', 'C', 'D'] ['D', 'C', 'A'] ok
delete the only : [] [] ok | head None tail None

Eight operations, and after every one both chains were walked and compared. The forward and backward readings are reverses of each other at every step, which is the invariant holding.

The order that corrupts it, run

class DNode:
    def __init__(self, data):
        self.prev = None
        self.data = data
        self.next = None


def chain(head, cap=8):
    out, walk, n = [], head, 0
    while walk is not None and n < cap:
        out.append(walk.data)
        walk = walk.next
        n += 1
    if walk is not None:
        out.append("... still going")
    return out


a, b = DNode("A"), DNode("B")
a.next, b.prev = b, a
head = a

n = DNode("NEW")
a.next = n                # WRONG: A redirected before NEW recorded what followed
n.next = a.next           # so NEW now points at ITSELF
n.prev = a

print("forward from the head:", chain(head))
print("did B survive? B is still an object:", b.data,
      "| reachable from the head:", "B" in chain(head))

forward from the head: ['A', 'NEW', 'NEW', 'NEW', 'NEW', 'NEW', 'NEW', 'NEW', '... still going']
did B survive? B is still an object: B | reachable from the head: False

The same failure as chapter 20, and for the same reason: a.next was overwritten while it was still the only record of where B was. B is intact and unreachable, and the list has a cycle.

The rule is worth stating once and keeping: when rewiring pointers, write the new node's links first. Nothing that is still needed may be overwritten before it has been copied.

The costs, stated exactly

The last row is the honest one and examiners like it. Deleting by value is O(n) on both, because the search dominates. The doubly linked list wins only when the node is already in hand, which is exactly what happens while traversing, and what a hash table's bucket or a cache's entry gives you.

Quick revision

• Insertion after p: set the new node's prev and next first, then p.next, then s.prev if s exists,

otherwise move the tail. Four assignments.

• Deletion of a held node: p.next = s and s.prev = p, each conditional on the end, otherwise move head

or tail. Two assignments, no walk.

• The order rule: write the new node's links first; never overwrite a reference still needed.
• Reversing that order gives a self-pointing node, a cycle, and unreachable nodes that are still intact.
• Deleting a held node is O(1) here and O(n) on a singly linked list.
• Deleting by value is O(n) on both, because the search dominates.
• Clear a deleted node's links so a stale reference cannot walk back into the list.

Test yourself

1. Write the four assignments that insert N after P, and say which is conditional. N.prev = P; N.next = S; P.next = N; and S.prev = N only if S exists, otherwise the tail moves to N.

2. Write the deletion of a held node X. If X.prev exists, X.prev.next = X.next, else head = X.next. If X.next exists, X.next.prev = X.prev, else tail = X.prev.

3. State the ordering rule for rewiring pointers, and what happens when it is broken. Set the new node's links first; never overwrite a reference that is still needed. Broken, the new node ends up pointing at itself, the list gains a cycle and the following nodes become unreachable while remaining intact.

4. Deleting a held node is O(1) here and O(n) on a singly linked list. Why? Because deletion must modify the previous node, and the doubly linked node holds its address directly, while the singly linked one can only find it by walking from the head.

5. Is deleting by value faster on a doubly linked list? No. The search is O(n) on both, and it dominates. The advantage applies only when the node is already in hand.

6. Why does the deletion above set the removed node's links to null? So that a stale reference to the removed node cannot be used to walk back into a list it is no longer part of.

Every behaviour of a real back button is there, including the one people forget: visiting a new page from the middle discards the forward history. "data-structures" is gone, and forward returns nothing.

That behaviour falls out of the structure. self.current.next = node overwrites the old forward link, and nothing else refers to what came after, so it is dropped.

Undo and redo, built

The same structure, one behaviour different: undo does not discard, it moves.

class DNode:
    def __init__(self, data):
        self.prev = None
        self.data = data
        self.next = None


class Editor:
    """Text with undo and redo, as a doubly linked list of states."""

    def __init__(self):
        self.current = DNode("")            # the empty document is a state

    def type(self, text):
        """A new state. Anything that had been undone is discarded."""
        node = DNode(self.current.data + text)
        node.prev = self.current
        self.current.next = node
        self.current = node

    def undo(self):
        if self.current.prev is None:
            return False
        self.current = self.current.prev
        return True

    def redo(self):
        if self.current.next is None:
            return False
        self.current = self.current.next
        return True

    def text(self):
        return repr(self.current.data)


e = Editor()
for word in ("Data ", "Structures ", "notes"):
    e.type(word)
print("typed        :", e.text())
print("undo         :", e.undo(), e.text())
print("undo         :", e.undo(), e.text())
print("redo         :", e.redo(), e.text())
print("undo to start:", e.undo(), e.undo(), e.text())
print("undo again   :", e.undo(), "(nothing left to undo)")
print()
e.redo()
e.type("REPLACED")
print("typing after an undo:", e.text())
print("redo now            :", e.redo(), "(the old future was discarded)")

typed        : 'Data Structures notes'
undo         : True 'Data Structures '
undo         : True 'Data '
redo         : True 'Data Structures '
undo to start: True True ''
undo again   : False (nothing left to undo)

typing after an undo: 'Data REPLACED'
redo now            : False (the old future was discarded)

Undo and redo are just prev and next. The whole feature is a cursor on a doubly linked list, and the rule that typing after an undo discards the redo history is the same one the browser had.

Why not an array for these?

Both could be arrays with an index. It would work, and for a browser's history it would be fine.

The doubly linked list wins when entries are removed from the middle. A cache that holds the most recently used items must, on every access, move an item to the front, which means deleting it from wherever it is. On an array that is O(n); with a doubly linked node in hand it is O(1). That structure, a hash table pointing at nodes of a doubly linked list, is how a least-recently-used cache is built, and it is the most common real use of this structure in working software.

Quick revision

• Backward traversal is the forward loop from the tail, following prev.
• A singly linked list can produce it only by reversing itself or using a stack, costing an extra pass

and extra memory.

• The real gift is a cursor: a held position that can move either way in O(1).
• Browser history: visit pushes a node after the cursor and discards what was ahead; back and forward

move the cursor.

• Undo and redo are the same structure; typing after an undo discards the redo history for the same

reason.

• An array with an index would do for these; the doubly linked list wins when items are removed from the

middle, as in a least-recently-used cache.

Test yourself

1. Write the backward traversal. walk = tail; while walk is not null: use walk.data; walk = walk.prev.

2. How would a singly linked list produce a backward traversal, and at what cost? By reversing the list, or by pushing every node onto a stack and popping it. Either costs an extra O(n) pass, and the stack costs O(n) extra memory.

3. What is a cursor and why does the second link make one possible? A held position in the list that can move either way. The backward link makes moving to the previous node O(1), which a singly linked list cannot do at all.

4. In the browser history, what happens to the forward pages when you visit a new page from the middle? They are discarded. The cursor's next is overwritten by the new node and nothing else refers to the old continuation.

5. How are undo and redo implemented here? As moving the cursor to prev and to next over a list of states. Typing creates a new state after the cursor and discards anything that had been undone.

6. Give the case where a doubly linked list clearly beats an array with an index. When items must be removed from the middle. Moving an item to the front of a least-recently-used cache is O(1) with a node in hand and O(n) on an array.

n = 1000 | delete the last node: singly walked  998 steps, doubly walked 0
n = 2000 | delete the last node: singly walked 1998 steps, doubly walked 0
n = 4000 | delete the last node: singly walked 3998 steps, doubly walked 0
n = 8000 | delete the last node: singly walked 7998 steps, doubly walked 0

The singly linked list's work doubles with the data; the doubly linked list's is zero at every size. That column of zeros is what 8 bytes a node bought.

The table

When to choose which

Use a singly linked list when the work is at the front, when memory is tight, or when the structure is only ever walked forwards. A stack, a queue with a tail, and a hash table's chains all qualify, which is why this paper's later structures mostly use it.

Use a doubly linked list when you hold nodes and delete them, when you need the node before one you have, or when something must be traversed both ways. Caches, editors' undo stacks, browser history and schedulers qualify.

Use neither when the work is reaching item i. Both are O(n) for that, and the array is O(1).

The honest note on the memory

The 8 bytes per node is real and it is usually not what decides. A node in a real program carries an object header and often a pointer to its value as well, so the second link is a small fraction of the total. Chapter 22's cache argument matters far more in practice than the extra 8 bytes.

Where the 8 bytes does decide is in the small and the enormous: a microcontroller with kilobytes of memory, or a list of hundreds of millions of nodes. Both are outside this paper, but the reasoning is the same one it teaches.

Quick revision

• The second link costs one address per node, measured here at exactly 8 bytes, and 8 MB per million

nodes.

• Insertion goes from 2 assignments to 4; both chains must be maintained and a defect in the invariant

is invisible from one side.

• It buys O(1) deletion of a held node, O(1) deletion of the last node, O(1) insertion before a node,

and backward traversal.

• Measured, deleting the last node walked 7,998 steps at n = 8,000 on a singly linked list and 0 on a

doubly linked one.

• Search is O(n) on both; the advantage is only for held nodes.
• Choose singly for front-only work and tight memory; doubly for held nodes, backward movement and

deletion from the middle; neither when the work is indexing.

Test yourself

1. What exactly does the second link cost, in memory and in assignments? One address per node, measured at 8 bytes, and insertion goes from two assignments to four.

2. Name the four things it buys. O(1) deletion of a held node, O(1) deletion of the last node, O(1) insertion before a held node, and backward traversal.

3. At n = 8,000, how many steps did each structure take to delete the last node? The singly linked list walked 7,998; the doubly linked list walked none.

4. Does the second link make searching faster? No. Search is O(n) on both. The advantage applies only once a node is held.

5. Give one structure in this paper that deliberately uses a singly linked list, and say why. A hash table's chains, where insertion is always at the front and the chain is only ever walked forwards, so the second link would be paid for and unused. The stack is another.

6. Why is the 8 bytes per node usually not the deciding factor? Because a real node also carries an object header and often a reference to its value, so the extra address is a small fraction of the total, and cache behaviour usually matters more.

push blue   -> pile is now ['blue']
push green  -> pile is now ['blue', 'green']
push red    -> pile is now ['blue', 'green', 'red']

pop        -> red   , leaving ['blue', 'green']
pop        -> green , leaving ['blue']
pop        -> blue  , leaving []

empty now  : True

what went in : blue, green, red
what came out: red, green, blue
reversed     : True

A stack reverses. Items come out in the opposite order to the way they went in, and that is not a side effect: it is the most useful thing about it. Reversing anything is pushing it all and popping it all.

Where stacks are already working in your programs

Three of these come back later in this paper.

Function calls. Every call pushes a frame holding the local variables and where to return; every return pops it. This is literally called the call stack, and it is why infinite recursion gives a "stack overflow".

Undo. Chapter 28 used a doubly linked list because redo was wanted too. Undo alone is a stack.

Expression evaluation. Chapters 37 and 38 convert and evaluate expressions with a stack, because brackets nest.

Depth first search. Chapter 95 explores a graph with a stack, and chapter 62 walks a tree with one. The reason is the same in both: going deeper is nesting.

Quick revision

• A stack allows insertion and removal at one end, the top, only. Last in, first out.
• Operations: push, pop, peek, is_empty.
• The restriction is the feature: every operation is O(1), the structure fits anything nested, and the

middle cannot be reached into by mistake.

• A stack refuses the middle, the bottom, searching and ordering. A problem needing any of those is not

a stack problem.

• A stack reverses: pushing everything and popping everything gives the reverse order.
• Already at work in the call stack, undo, expression evaluation and depth first search.

Test yourself

1. What does LIFO stand for and what does it mean? Last in, first out: the most recently pushed item is the next one popped.

2. Name the four stack operations and what each does. Push adds at the top, pop removes and returns the top, peek returns the top without removing it, and is_empty reports whether there is anything there.

3. Give three consequences of restricting a list to one end. Every operation is O(1); the structure matches any nested problem; and the middle cannot be reached into by accident.

4. What does a stack refuse to do? Reach the middle, reach the bottom, search, and impose any order other than the order of insertion.

5. Why does a stack reverse a sequence? Because the first item pushed is at the bottom and is therefore popped last, so the output order is the exact reverse of the input order.

6. Give three places a stack is already at work in an ordinary program. The call stack holding function frames and return addresses; the undo feature of an editor; and expression evaluation, where brackets nest.

Two of those three None values mean different things: one is a real item that was pushed, one is the stack saying it is empty. The caller cannot distinguish them, so the error is carried forward into whatever uses the value, and it surfaces somewhere else entirely.

That is the same argument as chapter 9's, and it is why the ADT specifies the error rather than leaving it to the implementer.

A note on what pop returns

There are two conventions and both appear in textbooks:

Pop removes and returns the top. One operation. This is what this book uses and what most languages do.

Pop removes; top or peek returns. Two operations, so removing without looking is possible. C++'s std::stack works this way.

An examination answer may use either, as long as it is consistent and says which. What is wrong is a pop that returns the item in the specification and does not in the code.

The ADT in the form the examination wants

If the question says "write the stack ADT", the expected answer is roughly:

Adding the cost line is worth a mark and almost nobody writes it.

Quick revision

• The stack ADT: push, pop, peek, is_empty, size. All O(1).
• It names no array and no linked list.
• Underflow: popping or peeking an empty stack. Applies to every implementation.
• Overflow: pushing onto a full stack. Applies only to a fixed capacity stack, so to the array version

and not the linked one.

• Errors are part of the specification. Returning None instead makes a real None item and an empty stack

indistinguishable to the caller.

• Two conventions for pop exist; either is acceptable if stated and applied consistently.

Test yourself

1. Write the stack ADT. A collection with access at one end. push(item) adds at the top, overflow if full; pop() removes and returns the top, underflow if empty; peek() returns the top without removing it, error if empty; is_empty(); size(). All operations are O(1).

2. Define underflow and overflow, and say which implementations each applies to. Underflow is popping or peeking an empty stack and applies to every implementation. Overflow is pushing onto a full stack and applies only to a fixed capacity stack, which is the array version.

3. Why is returning None on underflow a defect? Because None may be a legitimate item. The caller cannot tell a real value from the stack reporting emptiness, so the mistake travels to somewhere unrelated before it causes a visible failure.

4. Can a linked stack overflow? Not in the sense the ADT means. It has no fixed capacity, so it fails only when the machine runs out of memory altogether.

5. Give the two conventions for pop, and what makes an answer wrong. Pop removes and returns the top; or pop removes while a separate top or peek returns it. An answer is wrong when the specification and the code disagree, not when it picks one convention.

6. What line does almost nobody write in this answer, and why is it worth a mark? That every operation is O(1). It is part of what the ADT promises and it is what makes the stack worth choosing.

Both error conditions of chapter 31 are real here: underflow on the empty stack, and overflow, which the linked version of the next chapter cannot produce.

Two details worth marks

peek does not change top. It is the one operation that reads without moving, and writing self.top -= 1 into it by habit is a common slip. The run above checks it: size is still 3 after peek.

The popped cell is cleared. self.cells[self.top] = None is not required for correctness, because top already says that cell is not in use. It is there so the popped object is not kept alive by a reference nobody can reach. In C the equivalent is that the cell still holds a stale pointer, and reading it is a real bug.

The capacity problem

The array stack's one weakness is the number you have to choose at the start.

Too small and it overflows on valid input. Too large and memory sits reserved and unused. And there is often no good way to know: the depth of a stack used for bracket matching depends on the input.

Two answers exist.

Grow it, as Python's list does: when full, allocate a bigger block, copy, continue. This makes push amortised O(1) rather than O(1), by the argument of chapter 12, and it means overflow effectively disappears.

Use links, which is the next chapter, and have no capacity at all.

Quick revision

• Fields: a fixed block of cells, and top, the index of the topmost item, with -1 meaning empty.
• push: increment top, then write. pop: read, then decrement. The order is the mirror; reversing either

is an off-by-one that overwrites or re-reads.

• full is top == capacity - 1; size is top + 1.
• peek reads without changing top.
• Both error conditions are real here: underflow and overflow.
• Clear the popped cell so a dead item is not kept alive, and in C so a stale pointer is not left.
• The capacity must be chosen in advance, which is the weakness; growing the block or using links are

the two answers.

Test yourself

1. What does top hold, and what value means the stack is empty? The index of the topmost item. -1 means empty, because an empty stack has no topmost item.

2. Write push and pop in terms of top. push: check full, top = top + 1, then cells[top] = item. pop: check empty, item = cells[top], then top = top - 1.

3. What goes wrong if push writes before incrementing? It overwrites the item already at the top instead of adding above it, so the stack silently loses an item on every push.

4. Give the conditions for full and for size. Full is top == capacity - 1. Size is top + 1.

5. Which error can this implementation raise that a linked stack cannot, and why? Overflow, because the capacity is fixed at creation. A linked stack has no maximum until the machine runs out of memory.

6. Why clear the cell when popping, given that top already marks it unused? So the popped object is not kept alive by an unreachable reference; and in C, so a stale pointer is not left in the cell to be read by mistake.

The ADT proved: one caller, both stacks

Chapter 7 claimed that a caller written against the ADT works with any implementation. Here it is, on the two stacks this paper builds.

class ArrayStack:
    def __init__(self, capacity):
        self.cells = [None] * capacity
        self.top = -1

    def is_empty(self):
        return self.top == -1

    def push(self, item):
        self.top += 1
        self.cells[self.top] = item

    def pop(self):
        item = self.cells[self.top]
        self.top -= 1
        return item


class Node:
    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node


class LinkedStack:
    def __init__(self, capacity=None):
        self.head = None

    def is_empty(self):
        return self.head is None

    def push(self, item):
        self.head = Node(item, self.head)

    def pop(self):
        node = self.head
        self.head = node.next
        return node.data


def reverse_with(stack_class, text):
    """A caller written against the ADT. It never asks how the stack is built."""
    stack = stack_class(len(text))
    for character in text:
        stack.push(character)
    out = []
    while not stack.is_empty():
        out.append(stack.pop())
    return "".join(out)


for cls in (ArrayStack, LinkedStack):
    print("%-12s reversed 'Data Structures' to %r"
          % (cls.__name__, reverse_with(cls, "Data Structures")))

ArrayStack   reversed 'Data Structures' to 'serutcurtS ataD'
LinkedStack  reversed 'Data Structures' to 'serutcurtS ataD'

One function, two structures sharing no storage code, identical results. That is the ADT doing its job, and it is also the reversal property of chapter 30 put to work.

Array against links, for a stack

Neither is better in general. Use the array when the maximum depth is known, which it often is, and the contiguous memory then makes it genuinely faster. Use links when it is not, and accept the address per item.

Quick revision

• A linked stack makes the top of the stack the head of the list.
• push prepends, pop removes the head, peek reads the head. All O(1) by chapter 17.
• The head is chosen because it is the only end of a singly linked list where adding and removing are

both free.

• There is no capacity, so overflow does not arise; underflow still does.
• The same caller runs unchanged against the array stack and the linked stack, which is what the ADT

promises.

• Choose the array when the maximum depth is known, for the contiguous memory; choose links when it is

not.

Test yourself

1. Which end of the linked list is the top of the stack, and why that one? The head. It is the only end of a singly linked list where both adding and removing are O(1); the tail needs a walk to delete even with a tail pointer.

2. Write push and pop for a linked stack. push: head = Node(item, head). pop: check empty, item = head.data, head = head.next, return item.

3. Which of the two error conditions does a linked stack still have? Underflow. Overflow does not arise because there is no fixed capacity.

4. What did the one-caller demonstration show, and what did it not show? That a function written against the ADT works unchanged on both implementations. It did not show that they cost the same: memory per item and cache behaviour differ.

5. Give two reasons to prefer the array stack when the maximum depth is known. No address of memory per item, and contiguous storage, which the cache handles better than scattered nodes.

6. A program pushes an unknown number of items, possibly very many. Which implementation, and why? The linked stack, because it has no capacity to choose in advance and therefore cannot overflow on valid input.

Reading a stack empties it. Two stacks restore the order, because reversing twice is the identity, and that trick is the standard way to copy a stack without a third structure.

The table

Look at how many rows say "not possible". That is the point of the structure, and an examination answer that lists them as weaknesses without saying so has missed the argument.

When a stack is the wrong choice

Three signs, and each points at a specific later chapter.

You need the item that arrived first. That is a queue, chapter 40. You need the largest or most urgent item. That is a priority queue, chapter 78. You need to search, or to look at the middle. That is a list, a tree or a hash table.

Quick revision

• Advantages: every operation O(1); an exact match for nested problems; simple enough to be correct;

cannot be reached into; reverses for free.

• Disadvantages: no access except the top; no search; no ordering by value; fixed capacity on the array

version; traversal destroys it.

• The refusals are deliberate, and saying so is part of the answer.
• Reading a stack empties it; pushing what you read onto a second stack restores the original order,

because reversing twice is the identity.

• Wrong choice when you need the oldest item (queue), the most urgent (priority queue), or the middle (a

list, tree or hash table).

Test yourself

1. Give three advantages of a stack. Every operation is O(1); it matches nested problems exactly, since the most recently opened thing must close first; and it is simple enough to be correct, with no positions or ordering to get wrong.

2. Give three disadvantages. Only the top is reachable; there is no search; and traversal destroys the stack. Fixed capacity on the array version is a fourth.

3. Why is "no access to the middle" not simply a defect? Because it is the restriction that makes every operation O(1) and makes the structure impossible to misuse. It is the design, not an omission.

4. How do you read every item of a stack and still have the stack afterwards? Pop into a second stack and then pop that back into the first. Reversing twice restores the original order.

5. A problem needs the item that has been waiting longest. Is a stack right? No. That is first in, first out, which is a queue.

6. Can a stack tell you whether an item is present? Not without popping until it is found, which destroys the stack. A stack has no contains operation.

'()'       True   balanced
'([])'     True   balanced
'([)]'     False  ')' at position 2 closes a '['
'(('       False  '(' is never closed
')('       False  ')' at position 0 closes nothing
'(]'       False  ']' at position 1 closes a '('
'{[()]}'   True   balanced
'{[(])}'   False  ']' at position 3 closes a '('
''         True   balanced
'a(b[c]d)e' True   balanced
'(()(()))' True   balanced

Every case is now right, including the three the counter got wrong, and the answer says why rather than just no. Two more worth noting: the empty string is balanced, which is correct and is the kind of edge case an examiner adds; and other characters are simply ignored, which is what makes it usable on real text.

Why the stack is the right structure, in one sentence

Because the bracket that must close next is always the one that opened most recently, and that is the definition of last in, first out.

That sentence is worth memorising. It is the answer to "why a stack" for this problem and for every other nested problem in the paper.

The cost

One pass over the text, with one push or one pop per bracket. O(n) time.

The stack holds at most the depth of nesting, so O(d) memory, where d is the deepest nesting. For (((((...))))) that is O(n); for normal text it is small.

Quick revision

• Balanced means every opening bracket is matched by a closing bracket of the same kind, without

crossing.

• A counter fails: it remembers how many are open and forgets which kinds, so it accepts ([)] and

(].

• The stack algorithm: push openings; on a closing bracket, fail if empty, else pop and compare kinds;

at the end, balanced exactly when the stack is empty.

• Three failure cases: closing with nothing open, closing the wrong kind, and something left open.
• The empty string is balanced; other characters are ignored.
• Why a stack: the bracket that must close next is always the one that opened most recently.
• O(n) time, O(d) memory where d is the deepest nesting.

Test yourself

1. Why does a counter accept ([)]? Because it only counts how many brackets are open. It never records that the open bracket was round, so it cannot see that a square bracket closed it.

2. Give the three failure cases the stack algorithm detects. A closing bracket when the stack is empty; a closing bracket whose kind does not match the popped opening bracket; and a non-empty stack at the end.

3. Write the algorithm in four lines. For each character: push it if it opens. If it closes, fail when the stack is empty, else pop and fail when the kinds do not match. At the end, balanced exactly when the stack is empty.

4. In one sentence, why is a stack the right structure here? Because the bracket that must close next is always the one that opened most recently, which is last in, first out.

5. Is the empty string balanced? Is a(b[c]d)e? Both are. The empty string has nothing unmatched, and characters that are not brackets are ignored.

6. Give the time and memory costs, and say what determines the memory. O(n) time, one pass with one push or pop per bracket. O(d) memory, where d is the deepest nesting, because that is the most the stack ever holds at once.

The conversions, run

The program below converts by building the expression tree implicitly through full bracketing, so the three forms can be printed together and checked against each other.

def to_forms(expression):
    """Given a fully bracketed infix expression as nested tuples, print all three."""

    def infix(node):
        if not isinstance(node, tuple):
            return node
        left, operator, right = node
        return "(%s %s %s)" % (infix(left), operator, infix(right))

    def prefix(node):
        if not isinstance(node, tuple):
            return node
        left, operator, right = node
        return "%s %s %s" % (operator, prefix(left), prefix(right))

    def postfix(node):
        if not isinstance(node, tuple):
            return node
        left, operator, right = node
        return "%s %s %s" % (postfix(left), postfix(right), operator)

    return infix(node=expression), prefix(expression), postfix(expression)


cases = [
    ("A + B",              ("A", "+", "B")),
    ("A + B x C",          ("A", "+", ("B", "x", "C"))),
    ("(A + B) x C",        (("A", "+", "B"), "x", "C")),
    ("A + B x C - D",      (("A", "+", ("B", "x", "C")), "-", "D")),
    ("(A + B) x (C - D)",  (("A", "+", "B"), "x", ("C", "-", "D"))),
]

print("%-20s %-24s %-18s %s" % ("meaning", "infix, bracketed", "prefix", "postfix"))
for name, tree in cases:
    infix_form, prefix_form, postfix_form = to_forms(tree)
    print("%-20s %-24s %-18s %s" % (name, infix_form, prefix_form, postfix_form))

meaning              infix, bracketed         prefix             postfix
A + B                (A + B)                  + A B              A B +
A + B x C            (A + (B x C))            + A x B C          A B C x +
(A + B) x C          ((A + B) x C)            x + A B C          A B + C x
A + B x C - D        ((A + (B x C)) - D)      - + A x B C D      A B C x + D -
(A + B) x (C - D)    ((A + B) x (C - D))      x + A B - C D      A B + C D - x

Read rows two and three together. The infix strings differ only by brackets; the postfix strings differ by the order of the symbols, with no brackets at all. That is the whole idea.

The precedence table to memorise

For this paper, the operators and their precedence, highest first:

Brackets are not an operator; they override the table.

The one to be careful about is ^. It is right associative, so 2 ^ 3 ^ 2 is 2 ^ (3 ^ 2), which is 2 to the 9th, 512, and not (2 ^ 3) ^ 2, which is 64. Examiners use this.

Quick revision

• Infix: operator between operands. Prefix (Polish): operator before. Postfix (Reverse Polish): operator

after.

• Infix is ambiguous without precedence, associativity and brackets; the string alone does not say what

it means.

• Prefix and postfix need none of those: the order of symbols fixes the meaning.
• Hand method: fully bracket in precedence order, then move each operator just after its closing bracket

for postfix, or just before its opening bracket for prefix, and drop the brackets.

• Precedence: ^ highest and right associative, then x / %, then + -, both left associative.
• 2 ^ 3 ^ 2 is 512, not 64.

Test yourself

1. Write A + B * C in prefix and postfix. Prefix + A x B C; postfix A B C x +.

2. Write (A + B) * C in postfix, and say how it differs from the answer above. A B + C x. The symbols are in a different order; no brackets are needed to tell the two apart.

3. Why do prefix and postfix need no brackets? Because the position of each operator relative to its operands fixes which operands it applies to, so there is no ambiguity for precedence or brackets to resolve.

4. Give the hand method for converting infix to postfix. Fully bracket the expression in precedence order, move each operator to just after its closing bracket, then remove the brackets.

5. State the precedence and associativity of the operators in this paper. ^ is highest and right associative; x, / and % are next and left associative; + and - are lowest and left associative.

6. Evaluate 2 ^ 3 ^ 2 and say why the answer is not 64.

1. Exponent is right associative, so it is 2 ^ (3 ^ 2), which is 2 to the 9th, not (2 ^ 3) ^ 2.

A + B x C - D
token  output                   stack
A      A
+      A                        +
B      A B                      +
x      A B                      + x
C      A B C                    + x
-      A B C x +                -
D      A B C x + D              -
end    A B C x + D -

A + B x C              -> A B C x +
( A + B ) x C          -> A B + C x
A + B x C - D          -> A B C x + D -
( A + B ) x ( C - D )  -> A B + C D - x
A ^ B ^ C              -> A B C ^ ^
A - B - C              -> A B - C -
A x ( B + C ) / D      -> A B C + x D /

A + B )      refused: a ')' with no matching '('
( A + B      refused: a '(' that is never closed

Follow the trace at the -. The stack held + x. Minus has lower precedence than both, so both were popped to the output before minus was pushed. That single step is the algorithm.

Now compare the last two rows of the conversions, which is where associativity shows:

A ^ B ^ C gives A B C ^ ^. The first ^ stayed on the stack when the second arrived, because exponent is right associative, so the rightmost exponent is applied first.

A - B - C gives A B - C -. The first - came out when the second arrived, because minus is left associative.

Those two lines are the standard examination trap, and the program settles them.

Checking the conversions

The conversions above agree with chapter 36's, which were produced by a completely different method (walking a fully bracketed tree). Two independent methods agreeing is worth more than either one checked by eye.

Row by row: A + B x C gave A B C x + in both; ( A + B ) x C gave A B + C x in both; A + B x C - D gave A B C x + D - in both; ( A + B ) x ( C - D ) gave A B + C D - x in both.

The cost

Each token is pushed at most once and popped at most once, so the work is proportional to the number of tokens: O(n) time. The stack holds at most the operators currently waiting, so O(n) memory in the worst case, which is an expression like ((((A)))).

Quick revision

• Operands go straight to the output; operators wait on a stack.
• On an operator, pop while the top has higher precedence, or equal precedence and the new operator is

left associative; then push.

• ( is pushed; ) pops to the output until ( is found, and the ( is discarded, not output.
• At the end, pop everything left; a ( still there means it was never closed.
• A ^ B ^ C gives A B C ^ ^ (right associative) and A - B - C gives A B - C - (left

associative).

• O(n) time, O(n) memory in the worst case.

Test yourself

1. What happens to an operand, and what happens to an operator? An operand goes straight to the output. An operator waits on the stack until an operator arrives that does not need to wait for it.

2. State the popping rule for an incoming operator o. Pop while the stack top is an operator with higher precedence, or with equal precedence when o is left associative. Then push o.

3. Convert (A + B) x C and show why brackets disappear. A B + C x. The ( is pushed and discarded when the ) arrives; the ) forces the + out before the x is considered, so the grouping is carried by the order of the output symbols.

4. Convert A ^ B ^ C and A - B - C, and explain the difference. A B C ^ ^ and A B - C -. Exponent is right associative so the waiting ^ is not popped when a second arrives; minus is left associative so the waiting - is.

5. What are the two bracket errors, and when is each detected? A ) with nothing matching, found when the stack empties while searching for a (; and a ( never closed, found when it is still on the stack at the end.

6. Give the time and memory costs and say why. O(n) time, because each token is pushed and popped at most once. O(n) memory in the worst case, since the stack may hold every operator, as in a deeply bracketed expression.

5 3 - 2 x
token  action                       stack
5      push 5                       [5]
3      push 3                       [5, 3]
-      5 - 3 = 2                    [2]
2      push 2                       [2, 2]
x      2 x 2 = 4                    [4]
answer: 4

2 3 +          = 2 + 3            -> 5
5 3 -          = 5 - 3            -> 2
2 3 4 x +      = 2 + 3 x 4        -> 14
2 3 + 4 x      = (2 + 3) x 4      -> 20
2 3 2 ^ ^      = 2 ^ (3 ^ 2)      -> 512
2 3 ^ 2 ^      = (2 ^ 3) ^ 2      -> 64
10 2 / 3 -     = 10 / 2 - 3       -> 2.0

2 +      refused (not enough operands): operator '+' needs two operands
2 3      refused (two values left): the expression left 2 values, not 1
4 0 /    refused (division by zero): division by zero in the expression

Two rows settle chapter 36's warning with arithmetic: 2 3 2 ^ ^ is 512 and 2 3 ^ 2 ^ is 64. Those are the postfix forms of 2 ^ (3 ^ 2) and (2 ^ 3) ^ 2, and the difference is entirely in the order of the symbols.

Rows three and four are the same check for precedence: 2 3 4 x + is 14 and 2 3 + 4 x is 20.

Conversion and evaluation together

The two chapters compose: convert an infix expression, then evaluate the result, and compare against the value the expression should have.

PRECEDENCE = {"+": 1, "-": 1, "x": 2, "/": 2, "^": 3}
RIGHT = {"^"}


def to_postfix(tokens):
    output, stack = [], []
    for token in tokens:
        if token not in PRECEDENCE and token not in "()":
            output.append(token)
        elif token == "(":
            stack.append(token)
        elif token == ")":
            while stack and stack[-1] != "(":
                output.append(stack.pop())
            stack.pop()
        else:
            while (stack and stack[-1] != "("
                   and (PRECEDENCE[stack[-1]] > PRECEDENCE[token]
                        or (PRECEDENCE[stack[-1]] == PRECEDENCE[token]
                            and token not in RIGHT))):
                output.append(stack.pop())
            stack.append(token)
    while stack:
        output.append(stack.pop())
    return output


def evaluate(tokens):
    stack = []
    for token in tokens:
        if token in PRECEDENCE:
            right, left = stack.pop(), stack.pop()
            stack.append({"+": left + right, "-": left - right,
                          "x": left * right, "/": left / right,
                          "^": left ** right}[token])
        else:
            stack.append(int(token))
    return stack[0]


checks = [
    ("2 + 3 x 4",            2 + 3 * 4),
    ("( 2 + 3 ) x 4",        (2 + 3) * 4),
    ("10 / 2 - 3",           10 / 2 - 3),
    ("2 ^ 3 ^ 2",            2 ** 3 ** 2),
    ("7 - 2 - 1",            7 - 2 - 1),
    ("2 x ( 3 + 4 ) / 7",    2 * (3 + 4) / 7),
]
print("%-22s %-20s %-8s %-8s %s" % ("infix", "postfix", "ours", "Python", "agree"))
for infix, expected in checks:
    postfix = to_postfix(infix.split())
    ours = evaluate(postfix)
    print("%-22s %-20s %-8s %-8s %s"
          % (infix, " ".join(postfix), ours, expected, ours == expected))

infix                  postfix              ours     Python   agree
2 + 3 x 4              2 3 4 x +            14       14       True
( 2 + 3 ) x 4          2 3 + 4 x            20       20       True
10 / 2 - 3             10 2 / 3 -           2.0      2.0      True
2 ^ 3 ^ 2              2 3 2 ^ ^            512      512      True
7 - 2 - 1              7 2 - 1 -            4        4        True
2 x ( 3 + 4 ) / 7      2 3 4 + x 7 /        2.0      2.0      True

Every row is checked against Python's own evaluation of the same expression, which knows nothing about our stack. Six independent agreements, including both associativity cases.

The cost

One pass, one push or one pop pair per token: O(n) time. The stack holds at most the operands not yet consumed, so O(n) memory, worst case for an expression like 1 2 3 4 5 + + + +.

Quick revision

• Push operands; on an operator pop two, apply, push the result; one value should remain at the end.
• The first value popped is the RIGHT operand. This matters for -, /, % and ^ and hides for +

and x.

• No precedence and no brackets are needed: the conversion already resolved them.
• 2 3 2 ^ ^ is 512 and 2 3 ^ 2 ^ is 64.
• Errors: too few operands for an operator; more than one value left at the end; division by zero.
• O(n) time and O(n) memory.

Test yourself

1. Give the evaluation algorithm in two lines. Push each operand. On each operator, pop two values, apply the operator and push the result. At the end exactly one value remains and it is the answer.

2. Which popped value is the right operand, and which operators does it matter for? The first one popped. It matters for -, /, % and ^; for + and x the mistake is invisible.

3. Evaluate 5 3 - 2 x step by step. Push 5, push 3; the - pops 3 then 5 and pushes 5 - 3 = 2; push 2; the x pops 2 and 2 and pushes 4. The answer is 4.

4. Evaluate 2 3 2 ^ ^ and 2 3 ^ 2 ^, and say which infix expressions they are. 512 and 64. They are 2 ^ (3 ^ 2) and (2 ^ 3) ^ 2.

5. Name three errors the evaluator must detect. An operator with fewer than two operands available; more than one value remaining at the end; and division by zero.

6. Why does evaluation need no precedence rules? Because the postfix form already encodes the grouping in the order of its symbols, which is exactly what the conversion did.

infix                    prefix, by stack     prefix, by tree      agree
A + B                    + A B                + A B                True
A + B x C                + A x B C            + A x B C            True
( A + B ) x C            x + A B C            x + A B C            True
A + B x C - D            - + A x B C D        - + A x B C D        True
( A + B ) x ( C - D )    x + A B - C D        x + A B - C D        True
A ^ B ^ C                ^ A ^ B C            ^ A ^ B C            True
A - B - C                - - A B C            - - A B C            True

Every row was produced twice, by the reversal trick and by walking a bracketed tree, and the two agree. The last two rows are the associativity cases, and they are exactly where this chapter's first draft failed: with nothing flipped, A - B - C converted to - A - B C, which means A - (B - C) and is wrong.

Evaluating prefix

Postfix was evaluated left to right. Prefix is evaluated right to left, and the two pops come off in the opposite order.

The reason is symmetry: in prefix the operator comes before its operands, so scanning backwards means the operands are already on the stack when the operator is reached, and the nearer one is the left operand.

OPERATORS = {"+", "-", "x", "/", "^"}


def apply_operator(operator, left, right):
    if operator == "+":
        return left + right
    if operator == "-":
        return left - right
    if operator == "x":
        return left * right
    if operator == "/":
        return left / right
    return left ** right


def evaluate_prefix(tokens):
    """Scan right to left. The FIRST pop is the LEFT operand."""
    stack = []
    for token in reversed(tokens):
        if token in OPERATORS:
            left = stack.pop()             # note: the reverse of postfix
            right = stack.pop()
            stack.append(apply_operator(token, left, right))
        else:
            stack.append(int(token))
    if len(stack) != 1:
        raise ValueError("the expression left %d values, not 1" % len(stack))
    return stack[0]


def evaluate_postfix(tokens):
    stack = []
    for token in tokens:
        if token in OPERATORS:
            right = stack.pop()
            left = stack.pop()
            stack.append(apply_operator(token, left, right))
        else:
            stack.append(int(token))
    return stack[0]


checks = [
    ("+ 2 3",            "2 3 +",            2 + 3),
    ("- 5 3",            "5 3 -",            5 - 3),
    ("+ 2 x 3 4",        "2 3 4 x +",        2 + 3 * 4),
    ("x + 2 3 4",        "2 3 + 4 x",        (2 + 3) * 4),
    ("^ 2 ^ 3 2",        "2 3 2 ^ ^",        2 ** (3 ** 2)),
    ("^ ^ 2 3 2",        "2 3 ^ 2 ^",        (2 ** 3) ** 2),
    ("- - 7 2 1",        "7 2 - 1 -",        7 - 2 - 1),
]
print("%-14s %-14s %-8s %-8s %-8s %s" % ("prefix", "postfix", "prefix", "postfix",
                                         "Python", "all agree"))
for prefix, postfix, expected in checks:
    a = evaluate_prefix(prefix.split())
    b = evaluate_postfix(postfix.split())
    print("%-14s %-14s %-8s %-8s %-8s %s"
          % (prefix, postfix, a, b, expected, a == b == expected))

prefix         postfix        prefix   postfix  Python   all agree
+ 2 3          2 3 +          5        5        5        True
- 5 3          5 3 -          2        2        2        True
+ 2 x 3 4      2 3 4 x +      14       14       14       True
x + 2 3 4      2 3 + 4 x      20       20       20       True
^ 2 ^ 3 2      2 3 2 ^ ^      512      512      512      True
^ ^ 2 3 2      2 3 ^ 2 ^      64       64       64       True
- - 7 2 1      7 2 - 1 -      4        4        4        True

Three independent evaluations agree on every row: the prefix evaluator, the postfix evaluator, and Python's own arithmetic. The two exponent rows differ from each other by 448, which is the associativity difference surviving both notations correctly.

The four conversions, summarised

The bottom two rows use the evaluators of this chapter and chapter 38 with the arithmetic replaced by string building, which is a neat thing to notice and occasionally asked for.

Quick revision

• Prefix puts the operator before its operands; it needs no brackets and no precedence, like postfix.
• Infix to prefix: reverse the tokens, swap the brackets, run the infix to postfix algorithm with every

operator's associativity flipped, then reverse the output.

• Forgetting the associativity flip in step 3 is the standard error, and it shows on A - B - C, which

comes out as - A - B C instead of - - A B C.

• Prefix is evaluated scanning right to left, and the first value popped is the LEFT operand, the

reverse of postfix.

• Every conversion here was produced twice, by the stack and by a bracketed tree, and every evaluation

three times, including by Python itself.

• Converting back to infix is the same evaluator with the arithmetic replaced by string building.

Test yourself

1. Give the four steps of infix to prefix conversion. Reverse the expression; swap every opening bracket with a closing one; run the infix to postfix algorithm with every operator's associativity flipped; reverse the result.

2. Why must associativity be flipped in step 3? Because reversing the expression reverses the direction in which associativity groups. Left associative operators must be handled as right associative, and the exponent as left associative, for the duration of the conversion.

3. Convert A + B x C to prefix. + A x B C.

4. How is prefix evaluated, and how do the pops differ from postfix? Scanning right to left. The first value popped is the left operand, which is the reverse of postfix, where the first popped is the right operand.

5. Evaluate ^ 2 ^ 3 2 and ^ ^ 2 3 2. 512 and 64. They are 2 ^ (3 ^ 2) and (2 ^ 3) ^ 2.

6. How would you convert postfix back to infix? Run the postfix evaluator with the arithmetic replaced by string building: pop two operands and push the string (left operator right).

On an array, removing from the front means shifting everything down, which is O(n), or leaving a gap and moving the front marker, which wastes the space in front and eventually reports the queue as full when it is nearly empty. Chapter 42 demonstrates that failure and chapter 44 fixes it.

Neither problem arose for the stack. The second end is what costs.

Where queues are already working

Job scheduling. MU names this application by name, and chapter 48 builds it: processes waiting for the processor, served in arrival order.

Printing. Documents sent to a printer are served in the order they were sent.

Breadth first search. Chapter 94 explores a graph level by level with a queue, exactly as chapter 62 walks a tree with one. The stack goes deep; the queue goes wide.

Buffers. Data arriving faster than it can be handled waits in a queue, and the circular queue of chapter 44 is the standard implementation.

Quick revision

• A queue adds at the rear and removes from the front: first in, first out.
• Operations: enqueue, dequeue, front, is_empty.
• Rear, back and tail mean the adding end; front and head mean the removing end.
• A stack reverses the order; a queue preserves it. That is the deepest difference.
• A stack works at one end, a queue at two, and the second end is what makes the implementations harder.
• On an array, removing from the front shifts everything or wastes the space in front; on links, one end

needs a pointer kept to it.

• Used for job scheduling, printing, breadth first search and buffers.

Test yourself

1. What does FIFO mean and how does it differ from LIFO? First in, first out: the item that has waited longest is removed next. LIFO removes the most recently added item.

2. Name the queue operations and the two ends. Enqueue at the rear, dequeue from the front, front or peek to look without removing, and is_empty. Rear, back and tail name the adding end; front and head the removing end.

3. Four items go into a stack and a queue in the same order. How do the outputs differ? The stack gives them back reversed; the queue gives them back in the original order.

4. Why are queue implementations harder than stack implementations? Because a queue works at two ends. On a linked list one end needs a pointer kept to it; on an array, removing from the front either shifts everything or leaves unusable space at the front.

5. Give the two problems the array queue has, and which chapters solve them. Shifting everything down on every dequeue, which is O(n); or moving a front marker, which wastes the space in front and reports full when nearly empty. Chapter 42 demonstrates it and chapter 44 fixes it with wrap-around.

6. Name three places a queue is already at work. Job scheduling for the processor, documents waiting at a printer, and breadth first search of a graph or tree. Buffers for data arriving faster than it is handled are a fourth.

new queue: empty = True | size = 0
enqueue Asha   -> ['Asha']                     front is Asha
enqueue Rohit  -> ['Asha', 'Rohit']            front is Asha
enqueue Meera  -> ['Asha', 'Rohit', 'Meera']   front is Asha

dequeue -> Asha | now ['Rohit', 'Meera']
dequeue -> Rohit | now ['Meera']
front   -> Meera | size is still 1

dequeue  on an empty queue -> dequeue from an empty queue: underflow
front    on an empty queue -> front of an empty queue: underflow

Notice the third enqueue line: the front is still Asha, not Meera. Adding at the rear never changes the front, which sounds obvious and is exactly what the array implementation of chapter 42 gets wrong in a subtle way.

The ADT in examination form

The word should in the last line is deliberate, and it is what chapters 42 to 44 are about: a naive array implementation does not achieve it, and getting to O(1) is the work.

Quick revision

• The queue ADT: enqueue at the rear, dequeue from the front, front, is_empty, size.
• It names no implementation, and every operation should be O(1).
• Underflow applies to every implementation; overflow only where capacity is fixed.
• Know the alternative names: insert and add for enqueue, delete and serve for dequeue, head for front,

back and tail for rear.

• Adding at the rear never changes the front.
• The naive array implementation does not achieve O(1), which is the point of the next three chapters.

Test yourself

1. Write the queue ADT. A collection with insertion at the rear and removal at the front. enqueue(item) adds at the rear, overflow if full; dequeue() removes and returns the front, underflow if empty; front() returns the front without removing it; is_empty(); size(). All operations should be O(1).

2. Which implementations can overflow, and which can underflow? Any fixed capacity implementation can overflow, which means the array versions. Every implementation can underflow.

3. Give three alternative names for dequeue. Delete, remove, serve. Some textbooks also write pop, which is best avoided because of the stack.

4. Does enqueueing change the front of the queue? No, unless the queue was empty. Adding happens at the rear.

5. Why does the ADT say operations "should" be O(1) rather than "are"? Because it is a target the implementation must achieve. The naive array queue does not: its dequeue shifts every remaining item and is O(n).

6. What is the difference between front() and dequeue()? front() returns the front item and leaves the queue unchanged; dequeue() removes it and returns it, reducing the size by one.

That is the drift, and it is not an edge case: it happens to every array queue built this way, always.

The obvious fix, and what it costs

The natural response is to keep the front at index 0: on every dequeue, shift everything down one place.

class ShiftingQueue:
    """Keep the front at 0 by shifting on every dequeue. No drift, but a cost."""

    def __init__(self, capacity):
        self.capacity = capacity
        self.cells = [None] * capacity
        self.rear = 0
        self.moves = 0

    def is_empty(self):
        return self.rear == 0

    def size(self):
        return self.rear

    def enqueue(self, item):
        if self.rear == self.capacity:
            raise OverflowError("genuinely full")
        self.cells[self.rear] = item
        self.rear += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from an empty queue")
        item = self.cells[0]
        for i in range(1, self.rear):          # everything moves down one
            self.cells[i - 1] = self.cells[i]
            self.moves += 1
        self.rear -= 1
        self.cells[self.rear] = None
        return item


for n in (500, 1000, 2000, 4000):
    q = ShiftingQueue(n)
    for i in range(n):
        q.enqueue(i)
    for _ in range(n):
        q.dequeue()
    print("n = %4d | %d items through the queue cost %8d element moves"
          % (n, n, q.moves))

n =  500 | 500 items through the queue cost   124750 element moves
n = 1000 | 1000 items through the queue cost   499500 element moves
n = 2000 | 2000 items through the queue cost  1999000 element moves
n = 4000 | 4000 items through the queue cost  7998000 element moves

The drift is gone and the space is used properly. But look at the column: doubling the traffic quadruples the work. Every dequeue is now O(n), so passing n items through the queue is O(n squared).

That is not an acceptable queue. The ADT of chapter 41 said every operation should be O(1), and this one has traded a space defect for a time defect.

The two failures, side by side

Neither is acceptable, and each fails where the other succeeds. What is needed is the drifting queue's O(1) dequeue with the shifting queue's use of space, and the answer is to let rear wrap around to the beginning of the array when it reaches the end.

That is the circular queue, and it is chapter 44.

Quick revision

• The simple array queue keeps front and rear as indices that only move up.
• Both operations are O(1), but every dequeue abandons the cell it leaves behind.
• The queue therefore reports itself full when rear reaches the end, however few items it holds: run

here at capacity 5, size 3, refusing a fourth item with two cells free.

• The free cells are all in front of front, where rear can never reach them.
• Shifting everything down on dequeue fixes the space and makes dequeue O(n), so passing n items through

costs O(n squared): 4,000 items cost 7,998,000 element moves.

• The fix that keeps both is to let the indices wrap around, which is the circular queue.

Test yourself

1. Why does the simple array queue report itself full while nearly empty? Because full is tested as rear reaching the capacity, and both markers only move up. Every dequeue abandons a cell at the front that nothing can reuse.

2. In the run, what were the capacity, the size and the number of free cells when it refused an item? Capacity 5, size 3, two free cells, both in front of the front marker.

3. What does shifting on every dequeue fix, and what does it break? It fixes the wasted space, because the front stays at index 0. It breaks the cost: dequeue becomes O(n) and passing n items through the queue becomes O(n squared).

4. At n = 4,000, how many element moves did the shifting queue perform? 7,998,000, which is about n squared over 2.

5. State what a correct array queue must achieve that neither of these does. O(1) enqueue and O(1) dequeue, while using every cell of the array.

6. What single change achieves it? Letting the front and rear indices wrap around to the beginning of the array when they reach the end, which is the circular queue.

No drift, no shifting, no capacity, and the 50,000 items that passed through cost nothing extra: compare chapter 42, where 4,000 items cost nearly eight million element moves.

The two cases that break student code

Both are visible in the run above and both are about the rear pointer, which is the thing the structure has to remember.

Enqueue onto an empty queue. There is no rear node to attach to, so front and rear must both be set to the new node. Forgetting this attaches the node to nothing and the queue stays empty.

Dequeue that empties the queue. The front becomes null, and the rear must be cleared too. Forgetting this leaves the rear pointing at a node that is no longer in the queue, and the next enqueue attaches the new node to a removed node. The queue then looks empty and loses everything added afterwards.

The run tests both: the queue is emptied completely, the rear is checked to be null, and then a new item is enqueued and found correctly.

Array against links, for a queue

Both are O(1) once written correctly. Choose the circular array when the maximum is known and the contiguous memory is worth having, and links when it is not.

Quick revision

• The front is the head and the rear is the tail. That is the only assignment giving O(1) both ways on a

singly linked list.

• Removing from the tail would need the node before it, which requires a walk.
• Enqueue onto an empty queue sets both front and rear to the new node.
• Dequeue that empties the queue must clear the rear as well, or the next enqueue attaches to a removed

node and the queue silently loses everything.

• No capacity, so no overflow; underflow still applies.
• Against the circular array: same costs, no capacity, but an address per item and poorer cache

behaviour.

Test yourself

1. Which end of the list is the front of the queue, and why that way round? The head is the front. Removing from the head is O(1) while removing from the tail would need the node before it, which a singly linked list can only find by walking.

2. What must enqueue do when the queue is empty? Set both the front and the rear pointers to the new node, since there is no rear node to attach to.

3. What must dequeue do when it removes the last item, and what breaks if it does not? Clear the rear pointer as well. Otherwise the rear still points at the removed node, and the next enqueue attaches to a node outside the queue, so the queue appears empty and loses the items added after it.

4. Can a linked queue overflow? Not in the ADT's sense; it has no fixed capacity and fails only when the machine runs out of memory.

5. Compare the cost of passing 4,000 items through a linked queue and through the shifting array queue of chapter 42. The linked queue does a constant amount of work per item. The shifting queue performed 7,998,000 element moves for 4,000 items, because each dequeue shifted everything down.

6. When would you prefer the circular array queue? When the maximum size is known, since it avoids an address per item and its contiguous storage uses the cache better.

new         [.    .    .    .    .   ] f=0 r=0 n=0
A B C in    [A    B    C    .    .   ] f=0 r=3 n=3 order: ['A', 'B', 'C']
2 out       [.    .    C    .    .   ] f=2 r=3 n=1 order: ['C']
D E in      [.    .    C    D    E   ] f=2 r=0 n=3 order: ['C', 'D', 'E']

now the wrap: rear is at the end of the array and there are free cells at the front
F in        [F    .    C    D    E   ] f=2 r=1 n=4 order: ['C', 'D', 'E', 'F']
G in        [F    G    C    D    E   ] f=2 r=2 n=5 order: ['C', 'D', 'E', 'F', 'G']

the queue is full now: True with size 5 of capacity 5
enqueue H -> enqueue onto a full queue: overflow

draining it in order:
   dequeue -> C   [F    G    .    D    E   ] f=3 r=2 n=4
   dequeue -> D   [F    G    .    .    E   ] f=4 r=2 n=3
   dequeue -> E   [F    G    .    .    .   ] f=0 r=2 n=2
   dequeue -> F   [.    G    .    .    .   ] f=1 r=2 n=1
   dequeue -> G   [.    .    .    .    .   ] f=2 r=2 n=0

Follow the line marked "D E in": rear has become 0. It reached 5, the capacity, and wrapped to the beginning. The next enqueue puts F in cell 0, which chapter 42 had abandoned for ever.

The queue now uses every cell, it holds 5 items in a 5 cell array, and it correctly refuses the sixth. The drift is gone and both operations are still two assignments.

Note the order line while the queue is wrapped: the items are C, D, E, F, G but they sit in the array as F, G, C, D, E. The order lives in the markers, not in the positions, which is why order walks with the modulo rather than reading the array left to right.

The cost

Compare chapter 42's two attempts: the drifting queue had O(1) operations and wasted space, the shifting queue had full space use and O(n) dequeue. The circular queue has both, and the only thing it costs is a little index arithmetic.

The trap in reading the array

Printing the cells left to right does not print the queue. In the run above the array read F G C D E while the queue was C, D, E, F, G. An examination answer that reads the block in order has misread the structure.

Always report a circular queue from front, stepping with the modulo, for count items.

Quick revision

• The array is treated as a ring: every index advance is (index + 1) mod capacity.
• This reuses the cells freed at the front, which the drifting queue abandoned.
• enqueue writes at rear then advances it; dequeue reads at front then advances it. Both O(1).
• A separate count is kept for size, empty and full.
• The queue occupies the stretch from front round to rear and may wrap past the end of the array.
• The order lives in the markers, not the positions: reading the array left to right does not give the

queue's order.

• It achieves what neither chapter 42 attempt did: O(1) both ways with every cell usable.

Test yourself

1. What single change turns the drifting queue into a circular one? Advancing the indices with modulo the capacity, so that after the last cell they continue at the first.

2. Write the enqueue and dequeue operations. enqueue: check full, cells[rear] = item, rear = (rear + 1) mod capacity, increment the count. dequeue: check empty, item = cells[front], front = (front + 1) mod capacity, decrement the count.

3. In the run, the array held F G C D E and the queue was C, D, E, F, G. Explain. The queue starts at front, which was 2, and wraps round the end of the array. The order is given by stepping from front with the modulo, not by reading the cells left to right.

4. Compare the circular queue with the two attempts of chapter 42. The drifting queue was O(1) but abandoned a cell per dequeue. The shifting queue used all the space but made dequeue O(n). The circular queue is O(1) both ways and uses every cell.

5. When does a circular queue genuinely overflow? Only when it actually holds capacity items, unlike the drifting queue, which reported full whenever rear reached the end.

6. How should a circular queue be printed? From front, stepping with (front + step) mod capacity for count items. Reading the array in index order misreports it whenever the queue is wrapped.

2. Sacrifice one cell

Never let the queue hold more than capacity - 1 items. Then a full queue always leaves one gap, so the markers never coincide when full.

For: no extra field at all. Against: one cell of the array is never used, and the tests are less obvious. A queue declared with capacity 5 holds 4.

This is the version many textbooks print, so it must be recognised, and the full test is the line to memorise: (rear + 1) mod capacity == front.

3. Keep a flag

Hold a boolean saying whether the last operation was an enqueue. If the markers coincide and the last operation was an enqueue, it is full; if it was a dequeue, it is empty.

For: all cells usable, only one bit. Against: the flag has to be correct after every operation, and reasoning about it is harder than either of the others. Rarely used.

All three, run side by side

class CountQueue:
    def __init__(self, capacity):
        self.capacity, self.cells = capacity, [None] * capacity
        self.front = self.rear = self.count = 0

    def is_empty(self):
        return self.count == 0

    def is_full(self):
        return self.count == self.capacity

    def enqueue(self, item):
        if self.is_full():
            return False
        self.cells[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity
        self.count += 1
        return True


class SacrificeQueue:
    def __init__(self, capacity):
        self.capacity, self.cells = capacity, [None] * capacity
        self.front = self.rear = 0

    def is_empty(self):
        return self.front == self.rear

    def is_full(self):
        return (self.rear + 1) % self.capacity == self.front

    def enqueue(self, item):
        if self.is_full():
            return False
        self.cells[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity
        return True


for cls in (CountQueue, SacrificeQueue):
    q = cls(5)
    accepted = 0
    while q.enqueue(accepted):
        accepted += 1
    print("%-16s capacity 5 accepted %d items before reporting full"
          % (cls.__name__, accepted))

CountQueue       capacity 5 accepted 5 items before reporting full
SacrificeQueue   capacity 5 accepted 4 items before reporting full

There is the cost of the second method, measured: a five cell array holding four items.

Which to write in an examination

Either of the first two, stated clearly. The marks are for:

1. Explaining why the ambiguity exists: both states give front == rear.
2. Naming the method chosen.
3. Giving the correct full and empty tests for that method, which is where answers go wrong by mixing

the count method's empty with the sacrifice method's full.

Mixing them is the error to avoid. If you keep a count, use count == 0 and count == capacity. If you sacrifice a cell, use front == rear and (rear + 1) mod capacity == front.

Quick revision

• In a circular queue with only front and rear, empty and full both give front == rear.
• Three answers: keep a count; sacrifice one cell; keep a flag.
• Count: empty is count == 0, full is count == capacity. All cells usable, one field to maintain.
• Sacrifice: empty is front == rear, full is (rear + 1) mod capacity == front. No extra field,

one cell lost, so capacity 5 holds 4.

• Flag: a boolean recording whether the last operation was an enqueue. Rarely used.
• In an answer: say why the ambiguity exists, name the method, and give that method's own two tests

without mixing them.

Test yourself

1. Why can front and rear alone not distinguish full from empty? Because in both states the two markers hold the same value: an empty queue has never advanced rear past front, and a full one has advanced it all the way round to meet front again.

2. Give the full and empty tests for the count method. Empty is count == 0; full is count == capacity.

3. Give the full and empty tests for the sacrifice method. Empty is front == rear; full is (rear + 1) mod capacity == front.

4. What does the sacrifice method cost, exactly? One cell of the array. A queue declared with capacity 5 can hold only 4 items, as the run showed.

5. Describe the flag method and say why it is rare. Keep a boolean recording whether the last operation was an enqueue; when the markers coincide it distinguishes full from empty. It is rare because the flag must be maintained correctly by every operation and is harder to reason about than a count.

6. What is the standard error in answering this question? Mixing the methods: using the count method's empty test with the sacrifice method's full test, or the reverse. Each method has its own pair and they must be used together.

arrived in this order:
   bulk print       urgency 5
   routine backup   urgency 5
   routine report   urgency 5
   ALARM            urgency 1
   another backup   urgency 5

a queue serves them in arrival order, so the ALARM was served
after 3 less urgent jobs had gone first.
order served: ['bulk print', 'routine backup', 'routine report', 'ALARM']

the queue cannot do better, because the only thing it knows
about a job is WHEN IT ARRIVED. Urgency is invisible to it.

The queue behaved perfectly correctly and produced the wrong result, because arrival order was the wrong rule for this problem. No implementation detail fixes that: it is the ADT.

What is needed is a structure that serves by priority rather than by arrival, and that is the priority queue of chapter 78, built on the heap of chapter 81. Module 1 ends here on purpose, and Module 2 opens by picking it up.

The table

Stack, queue and deque, in one line each

The three linear restricted structures of Module 1, as an examiner may ask them compared:

Quick revision

• Advantages: all operations O(1); fair, with bounded waiting and no starvation; matches anything that

waits; decouples producer from consumer; the structure for breadth first work.

• Disadvantages: only the front is reachable; no search; traversal destroys it; the array version needs

a capacity; and it cannot serve by urgency.

• The last one is an ADT limitation, not an implementation one: a queue knows only when an item arrived.
• Demonstrated: an alarm arriving fourth is served fourth, behind three routine jobs.
• The fix is the priority queue of chapter 78, which is where Module 2 begins.

Test yourself

1. Give three advantages of a queue. Every operation is O(1); it is fair, with each item's wait bounded by the number ahead of it and no starvation; and it decouples a producer from a consumer, which is what a buffer does.

2. Give three disadvantages. Only the front is reachable; there is no search; and traversal destroys the queue unless items are re-enqueued as they are read.

3. Why can a queue not serve an urgent item first? Because the only thing it knows about an item is when it arrived. Urgency is not part of the ADT, so no implementation can recover it.

4. In the run, how many jobs went before the ALARM, and was the queue faulty? Three. The queue was not faulty; it applied arrival order correctly, and arrival order was the wrong rule for the problem.

5. What structure fixes that, and where is it built? The priority queue, chapter 78, implemented with the heap of chapter 81.

6. Compare the stack, queue and deque in one line each. A stack adds and removes at one end (last in, first out); a queue adds at one end and removes at the other (first in, first out); a deque adds and removes at either end.

Why not just use a deque for everything?

If a deque does the work of both, why does this paper teach three structures?

Chapter 34 answered it for the stack and the answer is the same here: the restriction is the feature.

A structure that permits only what the problem needs cannot be misused. Code that receives a stack cannot accidentally take from the bottom; code that receives a queue cannot accidentally serve the most recent arrival. Hand those same functions a deque and both mistakes become possible, and both would be silent.

There is a secondary reason: a deque needs a doubly linked list or a circular array with two moving ends, so it is more complex to implement correctly than either of the structures it contains.

The two restricted deques

Textbooks name two variants and examiners occasionally ask for them:

Input restricted deque. Insertion at one end only; deletion at both. Output restricted deque. Insertion at both ends; deletion at one end only.

Both exist to recover some of the safety that the full deque gives up.

Implementation

Two choices, both already built in this module.

A doubly linked list (chapters 26 to 29). Both ends are reachable and both directions are available, so all four operations are O(1) directly.

A circular array (chapter 44) with both front and rear able to move in either direction, using modulo arithmetic in both directions. front = (front - 1 + capacity) mod capacity is the backward step, and the + capacity is there because a negative index would otherwise result.

A singly linked list is not suitable: removing from the rear is O(n) by chapter 18, so one of the four operations cannot be made constant.

Quick revision

• Deque is a double ended queue, pronounced "deck"; MU prints it "Dequeues", which is not the dequeue

operation.

• Four operations: add_front, add_rear, remove_front, remove_rear.
• Used at one end it is a stack; used at both it is a queue. It contains them both.
• The restricted structures are still preferred, because a structure that permits only what is needed

cannot be misused.

• Input restricted allows insertion at one end only; output restricted allows deletion at one end only.
• Implement with a doubly linked list, or a circular array stepping both ways, with

(front - 1 + capacity) mod capacity for the backward step.

• A singly linked list cannot do it in O(1), because removing from the rear is O(n).

Test yourself

1. What does deque stand for and how is it different from dequeue? Double ended queue. Dequeue is the operation that removes from the front of a queue; a deque is a structure open at both ends.

2. Name the four operations. add_front, add_rear, remove_front, remove_rear.

3. Which pairs of operations make a deque behave as a stack and as a queue? Adding and removing at the same end gives a stack; adding at one end and removing at the other gives a queue.

4. If a deque can do both jobs, why keep the stack and the queue? Because the restriction prevents misuse: code given a stack cannot take from the bottom and code given a queue cannot serve the newest arrival. A deque allows both mistakes, silently.

5. Define the input restricted and output restricted deques. Input restricted permits insertion at one end only and deletion at both; output restricted permits insertion at both ends and deletion at one end only.

6. Why can a singly linked list not implement a deque efficiently, and what is the backward step in a circular array? Because removing from the rear requires the node before it, which is O(n). In a circular array the backward step is (index - 1 + capacity) mod capacity, with the + capacity preventing a negative index.

Measured, by running the same four jobs in a different order:

from collections import deque


def fcfs_average_wait(jobs):
    ready = deque(sorted(jobs, key=lambda j: j[1]))
    clock, waits = 0, []
    while ready:
        name, arrival, burst = ready.popleft()
        start = max(clock, arrival)
        waits.append(start - arrival)
        clock = start + burst
    return sum(waits) / len(waits)


long_first = [("P1", 0, 8), ("P2", 1, 2), ("P3", 2, 3), ("P4", 3, 1)]
short_first = [("P1", 0, 1), ("P2", 1, 2), ("P3", 2, 3), ("P4", 3, 8)]

print("the SAME four burst times, arriving in two different orders")
print()
print("longest first : average waiting time %.2f" % fcfs_average_wait(long_first))
print("shortest first: average waiting time %.2f" % fcfs_average_wait(short_first))
print()
print("identical work, identical policy, and the average wait differs")
print("entirely because of the order the jobs happened to arrive in.")

the SAME four burst times, arriving in two different orders

longest first : average waiting time 6.25
shortest first: average waiting time 1.00

identical work, identical policy, and the average wait differs
entirely because of the order the jobs happened to arrive in.

The same four jobs, the same total work, the same policy. The average wait is more than six times worse in one case, decided by nothing but arrival order.

What the queue cannot do about it

The obvious improvement is to serve the shortest job first. That would give the best possible average waiting time, and it is a standard result.

A queue cannot do it. Chapter 46 gave the reason: a queue knows only the order in which items arrived. To serve the shortest job first, the structure would have to be able to find the smallest burst time among everything waiting, and a queue has no way to look at anything but its front.

So the structure has to change, and what is needed is:

• add a job with a priority, in this case its burst time
• remove the job with the best priority, not the oldest

That is the priority queue, its ADT is chapter 79, and the structure that makes both operations cheap is the heap of chapter 81.

Where Module 1 ends

Module 1 has built five structures and each one answered a limitation of the one before it.

And Module 1 ends with a limitation of its own that none of them can answer: none of these structures can find anything. Not the most urgent job, not a particular value, not the largest item, without looking at everything.

That is what Module 2 is about, from its first chapter to its last.

Quick revision

• Jobs waiting for the processor sit in a queue; serving them in arrival order is first come first

served.

• Turnaround time is completion minus arrival; waiting time is turnaround minus burst.
• A scheduler is judged on the average waiting time.
• The convoy effect: one long job at the front delays every short job behind it. Measured here, the same

four jobs gave average waits of 6.25 and 1.00 depending only on arrival order.

• Serving the shortest job first would be better, and a queue cannot do it, because it knows only

arrival order.

• That needs a structure that removes by priority rather than by age: the priority queue of chapter 78,

built on the heap of chapter 81.

Test yourself

1. Define turnaround time and waiting time. Turnaround is completion time minus arrival time, the total time in the system. Waiting is turnaround minus burst time, the time spent not running.

2. For a job arriving at 3 with a burst of 2 that starts at 16, give all three figures. Completion 18, turnaround 15, waiting 13.

3. What is the convoy effect? One long job at the front of the queue delaying every short job behind it, however small those jobs are.

4. The same four jobs were run in two arrival orders. What were the average waits, and what does that show? 6.25 with the longest first and 1.00 with the shortest first. The policy and the total work were identical, so the difference came entirely from arrival order, which is what first come first served is at the mercy of.

5. Why can a queue not serve the shortest job first? Because a queue knows only the order of arrival and can see only its front. Finding the smallest burst time requires looking at everything waiting, which is not a queue operation.

6. What limitation does Module 1 end on, and where is it answered? None of its structures can find anything without looking at everything: not the most urgent item, not a particular value, not the largest. Module 2 answers it, beginning with the tree.

A doubly linked list adds a backward link: one address per node, insertion goes from two assignments to four, and it buys O(1) deletion of a held node, O(1) deletion of the last node, and backward traversal. Its invariant is that x.next.prev is x, and both chains must always agree.

Polynomials are the named application: one node per non-zero term, exponents strictly decreasing, no zero coefficients. Addition is a one pass merge, O(m + n). The array representation is better for dense polynomials and for multiplication.

Stacks

Access at one end only, the top. Last in, first out. push, pop, peek, is_empty, size, all O(1).

Underflow is popping an empty stack and applies to every implementation. Overflow is pushing onto a full one and applies only to a fixed capacity, so to the array version.

The array stack keeps top as the index of the topmost item, with -1 meaning empty. push increments then writes; pop reads then decrements. The linked stack makes the top the head of the list, because that is the only end where adding and removing are both free.

Applications. Balanced delimiters: a counter fails because it forgets which kind of bracket was opened, and accepts ([)]. Expression conversion: infix needs precedence, associativity and brackets, while postfix and prefix need none, which is why machines use them. Shunting yard converts; postfix is evaluated by pushing operands and applying operators to the top two, with the first value popped being the right operand.

2 ^ 3 ^ 2 is 512, not 64: the exponent is right associative.

Queues

Add at the rear, remove from the front. First in, first out. All operations should be O(1).

The naive array queue drifts: both markers only move up, so every dequeue abandons a cell, and the queue reports itself full while nearly empty. Shifting on dequeue fixes the space and makes dequeue O(n). The circular queue fixes both by advancing indices with (index + 1) mod capacity.

In a circular queue, empty and full both give front == rear. The three answers are: keep a count (count == 0, count == capacity); sacrifice one cell (front == rear, (rear + 1) mod capacity == front); or keep a flag. Do not mix one method's test with another's.

The linked queue takes the head as front and the tail as rear. Its two traps are enqueueing onto an empty queue, which must set both pointers, and the dequeue that empties it, which must clear the rear.

Job scheduling is the named application. Turnaround is completion minus arrival; waiting is turnaround minus burst. First come first served suffers the convoy effect: one long job delays every short one behind it.

A deque is open at both ends and contains the stack and the queue as special cases; the restricted structures are still preferred, because a structure that permits only what is needed cannot be misused.

The six "advantages and disadvantages", in one line each

MU asks this per structure, and they are different answers.

Singly linked list. For: O(1) insertion and deletion at a known position, no fixed size, no wasted capacity, no contiguous block needed. Against: O(n) access, an address per item, no backward link, poor cache behaviour, no binary search even when sorted.

Doubly linked list. For: O(1) deletion of a held node and of the last node, O(1) insertion before a node, backward traversal. Against: a second address per item, four assignments per insertion, two chains to keep in step.

Stack. For: all operations O(1), an exact match for nested problems, impossible to misuse. Against: only the top is reachable, no search, traversal destroys it, fixed capacity on the array version.

Queue. For: all operations O(1), fair with bounded waiting, decouples producer from consumer. Against: only the front is reachable, no search, and it cannot serve by urgency.

What Module 1 cannot do

None of these structures can find anything without looking at everything: not the most urgent job, not a particular value, not the largest item. Searching is O(n) on every one of them except a sorted array, which cannot then be cheaply changed.

Module 2 is the answer to exactly that.

The five mark answers most likely to be asked

1. Write the ADT for a stack, or a queue, or a linked list. (Operations, behaviour, errors, costs. No

code.)

1. Advantages and disadvantages of one named structure. (Its own, not another's.)
2. Convert an infix expression to postfix or prefix, with the stack traced.
3. Evaluate a postfix or prefix expression, with the stack traced.
4. Why does a circular queue need a count or a sacrificed cell?
5. Insert or delete a node at a given position in a linked list, with the pointer assignments in order.
6. Add two polynomials represented as linked lists.
7. First come first served scheduling: compute turnaround and waiting times, and name the convoy effect.

Test yourself

1. Give the access, front insertion and search costs of an array and of a singly linked list. Array: O(1) access, O(n) front insertion, O(n) search or O(log n) if sorted. Singly linked list: O(n) access, O(1) front insertion, O(n) search.

2. State the ordering rule for linked list pointer assignments and what happens when it is broken. Point the new node forward before redirecting its predecessor. Reversed, the new node points at itself, the list gains a cycle and the following nodes become unreachable while remaining intact.

3. Why does a counter fail to check balanced brackets? It records how many brackets are open and not which kinds, so it accepts crossing pairs such as ([)] and mismatched pairs such as (].

4. Give the empty and full tests for both standard circular queue methods. With a count: empty is count == 0, full is count == capacity. Sacrificing a cell: empty is front == rear, full is (rear + 1) mod capacity == front.

5. What does a doubly linked list buy, and what does it cost? It buys O(1) deletion of a held node and of the last node, O(1) insertion before a node, and backward traversal. It costs one address per node, four assignments per insertion, and a second chain to keep in step.

6. What single thing can none of Module 1's structures do? Find anything without examining everything: the most urgent item, a particular value or the largest. Only a sorted array searches quickly, and it cannot then be changed cheaply.

import bisect, random


def insert_moves(data, value):
    position = bisect.bisect_left(data, value)
    return len(data) - position


random.seed(11)
print("%6s | %-26s | %s" % ("n", "sorted array", "linked list"))
print("%6s | %10s %14s | %10s %12s"
      % ("", "search", "avg moves", "search", "insert"))
for n in (1000, 2000, 4000, 8000):
    data = list(range(0, n * 2, 2))

    worst_search = 0
    lo, hi = 0, len(data) - 1
    while lo <= hi:
        worst_search += 1
        lo = (lo + hi) // 2 + 1

    sample = [random.randrange(0, n * 2) for _ in range(200)]
    average_moves = sum(insert_moves(data, v) for v in sample) // len(sample)

    print("%6d | %10d %14d | %10d %12d"
          % (n, worst_search, average_moves, n, 2))

     n | sorted array               | linked list
       |     search      avg moves |     search       insert
  1000 |         10            542 |       1000            2
  2000 |         11           1040 |       2000            2
  4000 |         12           1942 |       4000            2
  8000 |         13           3846 |       8000            2

Now the wall is visible. At n = 8,000:

The sorted array searches in 13 comparisons and pays 3,846 element moves for an average insertion. The linked list inserts in 2 assignments and pays 8,000 comparisons for a search.

Each is excellent at one column and hopeless at the other, and the gap widens as the data grows.

What would fix it

Look at what makes binary search fast: at every step it discards half the remaining candidates. That is the whole of it. Thirteen steps for eight thousand items, because thirteen halvings of 8,000 reach 1.

Now ask what the structure would have to look like to allow that without being a line.

It would need, at each point, a value and a way to go two directions: everything smaller this way, everything larger that way. Then searching is: compare, go one way, and half the data is gone.

That is a tree. The ability to discard half at every step is what it buys, and because the halves are joined by links rather than by position, inserting does not shift anything.

Searching for 30: compare with 50, go left, half the tree is gone. Compare with 25, go right. Compare with 30, found. Three comparisons for seven values.

The promise of Module 2

The first row is the answer to this chapter. The third row is better still and gives up order entirely, which chapter 108 is about.

And each one has its own bargain, which is the habit Module 1 taught and Module 2 keeps.

Quick revision

• Every linear structure is fast at searching or fast at changing, never both.
• A sorted array searches in O(log n) and inserts in O(n); a linked list inserts in O(1) at a known

position and searches in O(n).

• Measured at n = 8,000: 13 comparisons for the array's worst case search against an average of 3,846

element moves to insert; 2 assignments to insert into the list against 8,000 comparisons to search it.

• Binary search is fast because it discards half the candidates at every step.
• A tree allows that without being a line: a value with a smaller side and a larger side, joined by

links, so nothing shifts when something is inserted.

• A balanced binary search tree gives O(log n) for search, insert and delete; a hash table gives O(1)

average and gives up order.

Test yourself

1. Why can a sorted array not also be fast at insertion? Because its order is carried by position, so inserting in the right place requires moving everything after it.

2. Give the two measured costs at n = 8,000 from this chapter. The sorted array searched in 13 comparisons at worst and moved an average of 3,846 elements per insertion. The linked list inserted in 2 assignments and took 8,000 comparisons to search.

3. What exactly makes binary search fast? It discards half the remaining candidates at every comparison, so the number of steps is the number of halvings needed to reach one item, which is about log n.

4. What must a structure provide to allow halving without being a line? At each point, a value and two directions: everything smaller one way and everything larger the other, joined by links rather than by position.

5. Why does inserting into a tree not shift anything? Because the order is carried by the links, not by positions in a block, so a new node is attached by changing pointers.

6. Give the costs a balanced binary search tree promises. O(log n) for search, insertion and deletion.

nodes            : ['A', 'B', 'C', 'D', 'E', 'F', 'G']
root             : ['A']
leaves           : ['D', 'F', 'G']
internal nodes   : ['A', 'B', 'C', 'E']
degree of each   : {'A': 2, 'B': 2, 'C': 1, 'D': 0, 'E': 1, 'F': 0, 'G': 0}
degree of the tree: 2
edges            : 6
children of B    : ['D', 'E']
siblings of D    : ['E']
ancestors of G   : ['E', 'B', 'A']
descendants of B : ['D', 'E', 'G']

a leaf is a node with NO CHILDREN, not a node at the lowest level:
   D is at level 2 and is a leaf: True
   G is at level 3 and is a leaf: True

The two properties that make it a tree

A collection of nodes and edges is a tree exactly when both hold:

1. It is connected: every node is reachable from the root. 2. It has no cycles: there is no way to leave a node and return to it.

Two consequences follow, and both are examinable:

A tree with n nodes has exactly n - 1 edges. Every node except the root is reached by exactly one edge from its parent. The run above counted 7 nodes and 6 edges.

There is exactly one path between any two nodes. More than one would make a cycle; none would mean it is not connected.

The ADT

As always it names no representation: links, an array, or a list of children.

Quick revision

• A tree is empty, or a root with zero or more subtrees, each itself a tree. The definition is

recursive, which is why tree algorithms are recursive.

• Root: the only node with no parent. Leaf: a node with no children, whatever its level. Internal: a

node with at least one child.

• Siblings share a parent; ancestors are on the path up to the root; descendants are everything below.
• Degree of a node is its number of children; degree of the tree is the largest of those.
• A tree is connected and has no cycles.
• n nodes means exactly n - 1 edges, and exactly one path between any two nodes.
• The ADT names root, parent, children, is_leaf, insert, delete and traverse, and no representation.

Test yourself

1. Give the recursive definition of a tree. A tree is either empty, or a root node together with zero or more subtrees, each of which is itself a tree, joined to the root by an edge.

2. Define a leaf, and say what it is not. A node with no children. It is not "a node at the lowest level": a leaf may be at any level, as D at level 2 and G at level 3 both are.

3. What is the degree of a node and the degree of a tree? The degree of a node is its number of children. The degree of the tree is the largest degree of any of its nodes.

4. How many edges has a tree of n nodes, and why? Exactly n - 1. Every node except the root is reached by exactly one edge from its parent.

5. Give the two properties that make a collection of nodes a tree. It is connected, so every node is reachable from the root, and it has no cycles.

6. In the chapter's tree, name the ancestors of G and the descendants of B. Ancestors of G: E, B, A. Descendants of B: D, E, G.

size of the tree : 7
height of the tree: 3
height of an empty tree: -1
depth of each node: {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2, 'G': 3}
deepest node depth: 3
leaves           : ['D', 'F', 'G']

the relation that must hold: height of the tree == the greatest depth
   height = 3 | greatest depth = 3 | equal: True

a single node tree: size 1 height 0 depth 0, and it is both root and leaf: ['only']

The relation holds: the height of the tree equals the greatest depth of any node. That is not a coincidence, it is what both definitions mean, and an answer that gives different numbers for the two has made an off-by-one somewhere.

Why height is the number that matters

Every cost in this module is stated in terms of height, not size.

Searching a binary search tree walks from the root to a leaf, so it costs at most the height. Inserting walks to the place where the node belongs: at most the height. Deleting: at most the height.

So the whole question of whether a tree is fast becomes: how does the height grow as nodes are added?

Two extremes, and chapters 68 and 69 are about the gap between them:

The best case. Every level is full. A tree of height h holds up to 2 to the power (h+1) minus 1 nodes, so n nodes need a height of about log2(n). For a million nodes, height 20.

The worst case. Every node has one child, so the tree is a line. Height n - 1. For a million nodes, height 999,999, and the tree is a linked list with extra steps.

import math


def best_height(n):
    """Smallest possible height for n nodes in a binary tree."""
    return math.ceil(math.log2(n + 1)) - 1


print("%10s | %12s | %14s" % ("nodes", "best height", "worst height"))
for n in (10, 100, 1000, 10**6):
    print("%10d | %12d | %14d" % (n, best_height(n), n - 1))
print()
print("the whole of balancing, chapters 69 to 74, is about staying in the left column")

     nodes |  best height |   worst height
        10 |            3 |              9
       100 |            6 |             99
      1000 |            9 |            999
   1000000 |           19 |         999999

the whole of balancing, chapters 69 to 74, is about staying in the left column

A million nodes in a height of 19, or in a height of 999,999, depending entirely on shape. That is the difference between O(log n) and O(n), and it is why half of Module 2's tree chapters are about keeping the first shape.

Quick revision

• Depth of a node: edges from the root down to it. The root has depth 0.
• Height of a node: edges on the longest path down to a leaf. A leaf has height 0.
• Height of the tree: the height of the root, equal to the greatest depth of any node.
• Size: the number of nodes.
• Level: this book counts the root as level 0; many Indian textbooks count it as level 1. State your

convention in an answer.

• An empty tree has height -1 by convention, so a one node tree has height 0.
• Every cost in this module is in terms of height, not size.
• Best height for n nodes is about log2(n); worst is n - 1. A million nodes: 19 against 999,999.

Test yourself

1. Define depth and height, and give both for a leaf. Depth is the number of edges from the root down to the node; height is the number of edges on the longest path from the node down to a leaf. A leaf has height 0 and whatever depth its position gives it.

2. What is the height of an empty tree, and why that value? Conventionally -1, so that a single node tree has height 0 and the relation between height and the maximum number of nodes still works.

3. Which relation must hold between the height of a tree and the depths of its nodes? The height of the tree equals the greatest depth of any node. Different numbers mean an off-by-one.

4. State the two level conventions and what to do in an examination. Level equals depth, so the root is at level 0; or level equals depth plus one, so the root is at level

1. State which you are using and be consistent.

5. Why are tree costs stated in terms of height rather than size? Because searching, inserting and deleting all walk from the root towards a leaf, so each costs at most the height.

6. Give the best and worst height for a binary tree of 1,000,000 nodes. Best about 19, when every level is full; worst 999,999, when every node has a single child and the tree is a line.

The disadvantages

1. The costs are about height, not size, and height depends on shape. This is the big one. A binary search tree built from sorted input degenerates into a line, and every O(log n) becomes O(n). Chapter 68 demonstrates it.

2. Balance has to be maintained, and it is not free. The AVL tree of chapters 71 to 74 keeps the shape, and pays with rotations on insertion and deletion and a balance factor stored in every node.

3. More memory per item than an array. Two child addresses per node, plus whatever balancing needs.

4. Poorer cache behaviour than an array, for the reason chapter 22 gave: the nodes are scattered.

5. It is beaten by a hash table when order is not needed. O(log n) is not O(1), and chapter 100's hash table gives constant average time. The tree's answer is that it keeps the order, which the hash table throws away.

The comparison

The tree's column is the only one with no "not possible" in it, and that is its real argument: it is the structure that is good at everything without being best at anything.

When a tree is the wrong choice

When order is never needed and speed is everything. Use a hash table. When the data never changes. Use a sorted array: binary search is simpler, uses less memory and uses the cache better. When the data is tiny. A linear search over twenty items beats anything, and is easier to get right.

Quick revision

• A balanced tree searches, inserts and deletes in O(log n): a billion items in about thirty steps.
• Each extra step doubles the number of nodes the tree can hold.
• Advantages: all three operations logarithmic; the order is kept and available; growth without

shifting; naturally recursive algorithms; it models hierarchy directly.

• Disadvantages: the cost is in the height, which depends on shape, and an unbalanced tree degenerates

to O(n); balancing costs rotations and stored information; two addresses per node; poor cache behaviour; and a hash table is faster when order is not needed.

• The tree is the only structure in the comparison with no "not possible" against it.
• Wrong choice when order is never needed, when the data never changes, or when the data is tiny.

Test yourself

1. How many steps does a balanced tree need to search a billion items, and what does one extra step buy? About thirty. One extra step doubles the number of nodes the tree can hold.

2. Give three advantages of a tree over a sorted array. Insertion and deletion are O(log n) rather than O(n); it grows and shrinks without shifting anything; and it does not need a single contiguous block of memory.

3. Give the main disadvantage, exactly. The costs are in terms of height, and height depends on shape. An unbalanced tree, such as one built from sorted input, degenerates into a line and every operation becomes O(n).

4. What can a search tree do that a hash table cannot? Produce the items in sorted order, answer what the next key after a given one is, and report the smallest or largest. A hash table has no order at all.

5. What does a hash table do better, and what is the tree's answer? It searches and inserts in O(1) on average rather than O(log n). The tree's answer is that it keeps the order, which the hash table gives up to get that speed.

6. Name two situations where a tree is the wrong choice. When order is never needed and a hash table's constant time is wanted; and when the data never changes, where a sorted array is simpler, smaller and better for the cache.

Strictly binary, and the other names

Several adjectives are attached to binary trees and examinations mix them. Chapter 56 separates the three that matter; one more belongs here:

A strictly binary tree (also called a proper or full binary tree in some books) is one in which every node has either zero or two children, never exactly one.

That property has a neat consequence proved in the next chapter: in a strictly binary tree the number of leaves is always one more than the number of internal nodes.

The ADT

The tree ADT of chapter 51, with children replaced by two named fields.

The last row is where a binary tree differs most from a list: there is no single obvious order to visit the nodes in, and the four standard answers are the next four chapters.

Quick revision

• A binary tree is empty, or a root with a left subtree and a right subtree, each a binary tree.
• At most two children, not exactly two.
• Left and right are distinguished: a node with only a left child differs from one with only a right.
• That ordering is what makes a decision possible at each node, and so what turns a walk into a search.
• Two values make 2 distinct binary trees, three values make 5; the counts are the Catalan numbers, and

only one shape of many is balanced.

• A strictly binary tree has every node with zero or two children, never one.
• A binary tree has no single obvious traversal order, which is why there are four.

Test yourself

1. Give the recursive definition of a binary tree. It is either empty, or a root together with two binary trees, the left subtree and the right subtree.

2. Why is "at most two children" not the same as "exactly two"? Because a node may have none, one or two. A tree where every node has zero or two is a strictly binary tree, which is a special case.

3. Why does it matter that left and right are distinguished? Because it allows a rule such as "everything smaller is on the left", which is what makes a search possible. In a general tree the children are unordered and no such rule can be stated.

4. How many distinct binary trees hold two values, and three? Two and five. They are the Catalan numbers.

5. What is a strictly binary tree? One in which every node has either zero children or two, never exactly one.

6. Why does a binary tree need four traversals when a list needed one? Because a list has one obvious order, front to back, while a binary tree has a node and two subtrees, and the node may be visited before, between or after them, with level order as a fourth answer.

Notice that S, the number of nodes with one child, cancels out. The relation holds whatever the shape.

All four, checked over every tree

An example proves nothing. The program below generates every binary tree shape up to 7 nodes and checks all four properties on each one.

import math


class BNode:
    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right


def all_shapes(n):
    """Every binary tree shape with exactly n nodes."""
    if n == 0:
        return [None]
    out = []
    for left_size in range(n):
        for left in all_shapes(left_size):
            for right in all_shapes(n - 1 - left_size):
                out.append(BNode(left, right))
    return out


def size(node):
    return 0 if node is None else 1 + size(node.left) + size(node.right)


def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))


def level_counts(node):
    counts = {}

    def walk(current, level):
        if current is None:
            return
        counts[level] = counts.get(level, 0) + 1
        walk(current.left, level + 1)
        walk(current.right, level + 1)

    walk(node, 0)
    return counts


def leaves_and_twos(node):
    if node is None:
        return 0, 0
    if node.left is None and node.right is None:
        return 1, 0
    left_leaves, left_twos = leaves_and_twos(node.left)
    right_leaves, right_twos = leaves_and_twos(node.right)
    twos = left_twos + right_twos + (1 if node.left and node.right else 0)
    return left_leaves + right_leaves, twos


checked = 0
for n in range(1, 8):
    trees = all_shapes(n)
    for tree in trees:
        h = height(tree)
        counts = level_counts(tree)
        # property 1
        assert all(c <= 2 ** level for level, c in counts.items()), "property 1"
        # property 2
        assert size(tree) <= 2 ** (h + 1) - 1, "property 2"
        # property 3
        assert h >= math.ceil(math.log2(n + 1)) - 1, "property 3"
        # property 4
        leaves, twos = leaves_and_twos(tree)
        assert leaves == twos + 1, "property 4"
        checked += 1
    print("n = %d: %4d distinct shapes, all four properties hold" % (n, len(trees)))

print()
print("binary tree shapes checked in total:", checked)
print("every one of them satisfies all four properties")