—

Artificial Computational Intelligence

Abstract Data Types: Stacks, Queues, Lists, and Vectors

Published: 2026-08-09

Level: postgraduate

Audience: Postgraduate students studying data structures and algorithm analysis

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

The master method and the recursion tree — covered in Lecture 3 (Analyzing Recursive Algorithms)
Solving recurrences and the substitution method — covered in Lecture 3 (Analyzing Recursive Algorithms)
Time complexity and asymptotic analysis — covered in Lecture 1 (Data Structures and Algorithm Design)

Abstract Data Types: Stacks, Queues, Lists, and Vectors

4.1 Recap — Master Theorem Applicability and the Substitution Method

4.1.1 The Recursion-Tree View of the Master Theorem

Hook. We stopped at the master theorem last time, and a student asked a sharp question: can the master theorem be applied incrementally? The answer is no — and the reason lives in the recursion tree, because every idea in the master theorem is just a picture of that tree.

The previous session ended at the master theorem, and a question from the class asked whether the master theorem can be applied incrementally. The answer starts with the recursion tree, because the master theorem's concepts come directly from that tree. Each node in the recursion tree represents one subproblem, and each term of the recurrence maps to something concrete in that tree.

Intuition. Think of a family tree: one ancestor problem sits at the root, and every child is a smaller copy of the same kind of problem. The recursion tree is that family tree for computation. The root node is the whole problem of size $n$ . It has $a$ children, each a subproblem of size $n / b$ . Each of those children has $a$ children of its own, each of size $n / b^{2}$ , and so on down to the leaves, which are problems of size 1. The analogy holds exactly: the tree records who divides into whom, and the master theorem just adds up the work done at every node of that family tree.

The master theorem's standard form is:

$T (n) = a T (\frac{n}{b}) + f (n)$

In words: "a problem of size $n$ is divided into $a$ subproblems of size $n / b$ , and $f (n)$ is the cost involved in that division." Here $T (n)$ is the running time on an input of size $n$ , $a$ is the number of subproblems created at each step, $b$ is the factor by which each subproblem shrinks, and $f (n)$ is the work spent splitting the problem and combining the results. Every node of the recursion tree is a subproblem of size $n / b$ , and the sum of the costs $f$ over all nodes, together with the work at the leaves, is what the recurrence is adding up.

Formalize — reading the recurrence from the tree. With $a \geq 1$ and $b > 1$ , the tree has three numbers you can read directly:

Height (number of levels): each level divides the input size by $b$ . Starting from $n$ , the leaf level is reached when $n / b^{h} = 1$ , so the height is $h = lo g_{b} n$ — the number of times you can split $n$ into $b$ roughly equal parts.
Number of nodes at depth $j$ : the root has $a$ children, each of those has $a$ children, so level $j$ holds $a^{j}$ nodes.
Work at depth $j$ : every node at depth $j$ works on a subproblem of size $n / b^{j}$ , and each such node costs $f (n / b^{j})$ . So the whole level costs $a^{j} f (n / b^{j})$ .

Adding every level gives the total:

$T (n) = leaf work Θ (n^{l o g_{b} a}) + j = 0 \sum l o g_{b} n - 1 a^{j} f (\frac{n}{b ^{j}})$

The first term is the work at the leaves: there are $a^{l o g_{b} n} = n^{l o g_{b} a}$ leaves, and each costs constant time $Θ (1)$ , so together they cost $Θ (n^{l o g_{b} a})$ . The summation is the combined cost of all splitting and combining steps at the internal levels. The three cases of the master theorem are just three ways this sum can behave: leaf-dominated, level-balanced, or root-dominated.

The master theorem applies only when we are able to include recursion in the problem and to divide a problem into subproblems of smaller size — the classic divide-and-conquer shape. In the discussion a garbled variant such as $c \cdot T (n / m)$ was floated — a division into parts of unequal or different sizes — and that is exactly the case where the theorem does not apply. To see why, compare with the standard reference form: the theorem needs the same split $b$ for every subproblem. A recurrence such as $T (n) = T (n /3) + T (2 n /3) + f (n)$ splits the problem into two parts of different sizes, so there is no single $b$ and the shape $a T (n / b)$ fails. Likewise, a coefficient $c$ multiplying one $T (n / m)$ term only fits the form when it really means " $c$ identical subproblems of size $n / m$ " — if the parts differ, the recursion tree becomes irregular, the levels no longer all hold equal work, and the master theorem has no case to apply.

Worked trace — adding up the tree by hand. Take the level-balanced shape $T (n) = 2 T (n /2) + c n$ with $c$ a constant.

Depth 0: 1 node, cost $c n$ .
Depth 1: 2 nodes, each cost $c (n /2)$ , total $c n$ .
Depth 2: 4 nodes, each cost $c (n /4)$ , total $c n$ .
Depth $j$ : $2^{j}$ nodes, each cost $c (n / 2^{j})$ , total $c n$ — the same $c n$ at every level.

The tree has $lo g_{2} n + 1$ levels, so the internal total is $c n \cdot lo g_{2} n$ , and the $Θ (n)$ leaf work is swallowed by the leading term:

$T (n) = c n l g n + Θ (n) = Θ (n l g n)$

This is exactly case 2 of the master theorem: $f (n) = c n$ and $n^{l o g_{2} 2} = n$ are the same order, and the answer multiplies by the log factor. Now try the leaf-dominated shape $T (n) = 9 T (n /3) + n$ : level $j$ costs $9^{j} \cdot (n / 3^{j}) = 3^{j} n$ , which grows with depth, so the geometric sum is dominated by the deepest level — the leaves — giving $Θ (n^{l o g_{3} 9}) = Θ (n^{2})$ , exactly case 1. Sense-check both: the balanced case pays the same tax at every level (hence "times $l g n$ "), while the bushy case's leaf level alone overwhelms everything above it.

Scope — when the theorem is allowed. The master theorem needs three conditions:

$a \geq 1$ subproblems, each of size $n / b$ with $b > 1$ — the split must be equal every time (floors and ceilings such as $⌊ n /2 ⌋$ are fine; they change nothing asymptotically).
$f (n)$ must be a nonnegative, asymptotically growing function — the cost of dividing and combining.
The theorem's cases compare $f (n)$ with the leaf cost $n^{l o g_{b} a}$ . Case 1 needs $f (n)$ polynomially smaller than $n^{l o g_{b} a}$ ; case 3 needs $f (n)$ polynomially larger and a regularity condition $a f (n / b) \leq c f (n)$ for some constant $c < 1$ .

If $f (n)$ is smaller or larger only by a logarithmic factor — for example $T (n) = 2 T (n /2) + n l g n$ , where $f (n)$ sits in the gap between cases 2 and 3 — the theorem says nothing, and you must fall back on another method.

Visual intuition. Picture the recursion tree with the level number (0 to $lo g_{b} n$ ) on the vertical axis and the total cost of that level on the horizontal axis. For $T (n) = 3 T (n /4) + c n^{2}$ , the root level costs $c n^{2}$ , the next level costs $a f (n / b) = 3 c (n /4)^{2} = (3/16) c n^{2}$ , and each level below is a fixed fraction smaller — the level costs shrink geometrically, so the root dominates and $T (n) = Θ (n^{2})$ . For $T (n) = 2 T (n /2) + c n$ , every level costs exactly $c n$ , there are $l g n + 1$ levels, so the total is $c n l g n$ — case 2's log factor is literally "one copy of the per-level cost for every level." For $T (n) = 9 T (n /3) + n$ , the level costs grow geometrically and the leaves dominate: $n^{l o g_{3} 9} = n^{2}$ . Takeaway: decide which end of the tree holds the money — root, middle, or leaves — and you have already decided the case.

Pitfalls.

Applying the theorem to an unequal split. $T (n) = T (n /3) + T (2 n /3) + c n$ looks divide-and-conquer, but there is no single $b$ . The master theorem does not apply; the recursion-tree method still does (it gives $O (n l g n)$ ).
Forgetting the "polynomially" qualifier. $T (n) = 2 T (n /2) + n l g n$ is not case 3 even though $n l g n > n$ . The gap between cases 2 and 3 is exactly where a student's answer silently goes wrong.
Quoting the shape without the tree. If you cannot explain each term of $a T (n / b) + f (n)$ through the tree — $a$ children, size $n / b$ , cost $f$ per node — you do not yet understand when the theorem applies.

4.1.2 Where the Master Theorem Does Not Apply

When a recurrence does not match the shape $a T (n / b) + f (n)$ , three alternatives remain: solve the recurrence directly; use the substitution method; or draw the recursion tree and add up the levels by hand.

The substitution method in two steps. The reference textbook defines it exactly this way:

Guess the form of the solution. For example, guess $T (n) = O (n l g n)$ for $T (n) = 2 T (n /2) + n$ .
Prove the guess by induction. Assume the bound holds for all smaller inputs, substitute it into the recurrence, and show the algebra closes: $T (n) = 2 \cdot c (n /2) l g (n /2) + n = c n l g n - c n + n \leq c n l g n$ , which holds for $c \geq 1$ . The name "substitution" comes from the last step — you substitute the guessed form into the recurrence's right-hand side.

The catch is the first step. To guess the solution you need to be something of an expert, with experience of having seen similar recurrences before. Only that experience makes a reasonable guess possible.

Worked proof in full. For $T (n) = 2 T (⌊ n /2 ⌋) + n$ , guess $T (n) = O (n l g n)$ and prove $T (n) \leq c n l g n$ for $n \geq n_{0}$ :

$T (n) = 2 T (⌊ \frac{n}{2} ⌋) + n \leq 2 \cdot c ⌊ \frac{n}{2} ⌋ l g ⌊ \frac{n}{2} ⌋ + n \leq 2 c \cdot \frac{n}{2} l g \frac{n}{2} + n = c n l g n - c n + n \leq c n l g n (the recurrence) (inductive hypothesis on the smaller input) (drop the floor: it only shrinks the bound) (using l g (n /2) = l g n - l g 2 = l g n - 1) (holds when c \geq 1)$

Every line follows from the one above it — no hidden algebra. The base cases are handled by choosing $n_{0}$ large enough that the boundary conditions also satisfy the bound.

The instructor did not cover the substitution method in class, but that is not a reason to skip it — it is in the textbook, and students should read it. The reason it was skipped is the first step: to guess the solution you need to be something of an expert, with experience of having seen similar recurrences before. Only that experience makes a reasonable guess possible. The method is still useful the other way around: you can guess a solution and then use other methods to verify whether your guess is correct — that is how these problems are normally checked. The recursion tree remains the direct fallback whenever the master theorem is not applicable.

One useful note on emphasis: most of the problems we deal with in real life, on a daily basis, do have the divide-and-conquer shape, which is why so much attention goes to the master theorem rather than to the general methods.

Recap + Bridge. The master theorem is a shortcut for recurrences with the exact $a T (n / b) + f (n)$ shape; the recursion tree is its picture and its fallback; the substitution method is the general guess-then-prove tool you use to check answers. This closes the algorithms-analysis thread — next, the course turns to data structures, starting with the most basic building blocks: stacks, queues, lists, and vectors.

Exam note: a master theorem question is expected in the assessments; be able to state when the theorem applies, interpret each term of $T (n) = a T (n / b) + f (n)$ through the recursion tree, and know what to do when it does not apply. Practice writing the two substitution-method steps from the textbook even though the method was not covered in class.

4.1.3 Student Questions and Answers

Q: Can we apply the master theorem incrementally? A: No. The master theorem applies only where a problem can be divided into $a$ subproblems of size $n / b$ with a division cost $f (n)$ . Think in terms of the recursion tree: each node is a subproblem of size $n / b$ , and $f (n)$ is the cost at that node. If the recurrence cannot be split that way, the master theorem is not applicable — solve the recurrence directly, use the substitution method, or work the recursion tree by hand.

Q: Can we use the substitution method to verify whether our answer is correct? A: Yes, that is exactly how it is normally done — you make a guess at the solution and then use other methods to verify whether your guess is correct. Guess first, then prove or check the guess by substitution.

Q: The quiz seems very difficult. Is it? A: No. Practice more questions and then start attempting. Doing more problems before you begin is the fix.

4.2 Abstract Data Types

4.2.1 Type, Data Type, and Abstract Data Type

Hook. When you declare a variable, the compiler checks its type before you can do anything with it. Why does a language bother? Because the type — and the operations the type allows — is the contract between your program and the machine. This section unwraps that idea, step by step, from plain type up to abstract data type.

The course now switches from algorithms analysis to data structures: the first half of the course talks about data structures in detail and the second half talks about algorithms in detail. After asymptotic notations, we already know how to analyze the time complexity of an algorithm and how to interpret a complexity given in asymptotic notation. The goal now is to study data structures and analyze them in terms of their performance, starting from the most basic ideas.

The chain of definitions begins with a type — a collection of values having similar properties. If something is of type Boolean, it can take only the value true or the value false. If something is of data type integer, it can take only a set of values that satisfies the properties of integers. So the type answers "which kind of data": character, string, Boolean, integer, and so on.

Formalize — the three-step ladder.

Type. A collection of values having similar properties. It answers what kind of data: Boolean holds true or false; integer holds whole numbers.
Data type. A type together with a collection of operations to manipulate the type. The values alone are not enough — we also say what can be done with them. An integer type, for example, is not just the set of whole numbers; it also comes with the operations $+$ , $-$ , $\times$ , and so on.
Abstract data type (ADT). A type of class for objects whose behavior is defined by a set of values and a set of operations. The practical difference from a data type: an ADT is a logical description of how we view the data and the operations that are allowed on the data, without concern for how they will be implemented. When the term data type is used in the strict sense, it means an actual implementation of an ADT — the realization of a data type as a software component.

In plain words: "I know I have a collection of values and I know what operations are possible on those values, but I am not aware how to implement that — that is the implementer's job." The ADT is a method for achieving abstraction for data structures and algorithms: it describes what each operation does, but not how it does it, and it is independent of its implementation.

Worked example — the counter, all three rungs. Take something tiny and familiar: a counter that counts how many items have been processed.

Type: the values are the nonnegative whole numbers $0, 1, 2, \dots$ — "what kind of data" the counter holds.
Data type: the values plus operations — increment (add 1), reset (set to 0), read (return the current count). The values alone cannot be used; the operations make the type usable.
Abstract data type: the same operations described without implementation — we say increment adds 1 to the count, but not whether the count lives in a CPU register, a memory cell, or a database row. That decision belongs to the implementer.

The point of the ladder: the user of the counter depends only on the ADT description (values + operations); the implementer chooses the hardware and code. Swap the implementation and the user's program still works — exactly the guarantee the course's stack and queue ADTs will provide.

Intuition — the restaurant menu. The ADT is the menu: it lists the dishes (values) and what you can do with them (operations), but you never see the kitchen. The kitchen's actual recipes, stoves, and ingredient shelves are the implementation — the data type in the strict sense. Two different restaurants can serve the same menu with completely different kitchens, just as two programmers can implement the same ADT with different internals. The analogy holds as long as the menu stays the same; the moment the menu changes, every kitchen has to catch up — which is why ADT design matters before implementation.

Why does this matter? Every time we write a program we cannot go ahead and implement every structure from scratch — we do not know the system specifications in advance. So we talk about the software realization of a data type: we know what data is possible and what operations are possible on that data, and the how is decided later, when we actually implement it.

4.2.2 Why We Need ADTs — the Word-Processor Cursor

Worked analogy — editing with a cursor. How do you edit a word document? If you had to insert a word between two existing words, you would need to remember the exact position of the character where the change has to be made — which line number, which character number. But nobody edits that way: the word processor gives you a cursor. The cursor is an abstraction of that index position. You manipulate the data through the cursor without worrying about how the position is tracked internally.

Map the pieces explicitly:

The document text is the data.
Move-left, move-right, type, delete are the operations.
The cursor is the handle through which you perform the operations — you never mention "line 3, character 17" to the editor.

That is precisely what an ADT does: we do not worry about how something is implemented; we worry about the data and the operations possible on the data. The ADT is a model plus operations. The cursor analogy returns later in the session, where the same idea becomes the position abstraction in linked lists — the same mental model, a different structure.

4.2.3 Linear and Non-linear ADTs

The ADTs covered in the course are the stack, the queue, and the list. Vector is also covered briefly even though it is not exactly in the syllabus — the vector concept is needed later when algorithms are discussed. Sequences and iterators appear in the textbook but are not part of the syllabus; they should still be read from the textbook. Many students already know these data structures, but the lecture treats them from the beginning for those meeting them for the first time.

All of these are linear data structures. A linear data structure has data elements arranged in a sequential manner: we can access the data one after the other by following a linear order, and each element is connected to the previous element and the next element. Starting from one element, we reach the next by following the order (a "plus one" step in the memory location or a link to the next node). The data is ordered in a sequential, one-dimensional manner — there is no hierarchy.

Visual intuition. Picture a train of boxcars: each car holds one element and is coupled to exactly one car ahead and one car behind — a single-file line with no branches. Start at the first car and you can visit every car, one after another, in a straight order. Now picture a tree: branches split and rejoin, and "next" is not unique — that is a non-linear structure. The linear/non-linear split is exactly this train-versus-tree distinction, and the session's structures — the stack, the queue, and the list — are all trains, not trees.

Pitfalls.

Confusing a data type with an ADT. A data type (in the strict sense) is an implemented ADT — the code, the memory layout, the actual software component. The ADT is only the logical description. Saying "the stack is the array" collapses the two; the array is one implementation of the stack ADT.
Thinking abstraction means "no operations." The ADT does not drop operations — it fixes them. The abstraction is about how the operations work internally, not about which operations exist.
Expecting index access from every linear structure. "Linear" means a one-dimensional order you can walk through, not that you can jump to position $k$ in constant time — that property belongs only to certain implementations, as the linked lists later in the session will show.

Recap + Bridge. A type names the kind of values; a data type adds the operations; an ADT fixes the operations but hides the implementation — the cursor is your everyday proof that this design works. The course now studies the linear ADTs one by one, starting with the stack, whose whole behavior is described by just a handful of operations.

4.2.4 Student Questions and Answers

Q: What do you mean by a type? Is it a kind, a class, properties of data, a data representation? A: A type is a collection of values having similar properties. For example, Boolean can take only true or false, and integer can take only values that satisfy the properties of integers.

Q: What do you mean by a linear data structure? One dimensional? No hierarchy? Goes in one direction? Sequential memory access? A: A linear data structure has data elements arranged in a sequential manner. We are able to access the data one after the other by following a linear order, and each element is connected to the previous element and the next element. That is why we call it linear — the data is ordered in a sequential manner, in one direction.

4.3 Stack

4.3.1 The Stack ADT and Its Operations

Hook. Undo a mistake in any editor and the app steps back through your history, one action at a time, newest first. Why can it always "step back" so naturally? Because the editor keeps your history on a stack — and the stack's LIFO rule is the only idea behind it.

A stack — a container of objects that are inserted and removed according to the LIFO principle: last in, first out. Objects can be inserted at any time, but only the last object inserted can be removed. The name comes from the way plates are arranged in a dispenser: when plates are stacked in a hotel dispenser, the first plate placed in is the last plate that comes out. Inserting an item is known as pushing onto the stack; popping is synonymous with removing an item.

Intuition — the plate dispenser and the bangle stack. The professor's picture is the spring-loaded plate dispenser in a hotel: you push a plate on top, and the dispenser pops the top plate off first; the plate that went in first comes out last. The same principle in miniature: a stack of bangles on a wrist — pushing a bangle on, popping it off — is exactly push and pop. Where the analogy breaks: a dispenser holds a physical limit of plates, while a stack as an ADT has no built-in limit — any size limit comes from the implementation, not from the concept.

Visual intuition. Picture the stack as a vertical column: the bottom holds the first element pushed, the top holds the last. Push drops a new plate on top of the column; pop lifts the top plate off. size() is the height of the column; top() is the plate you would grab next without lifting it off; is_empty() asks whether the column has any plates at all. The array implementation lays this column sideways — index 0 is the bottom, index $t$ is the top — but the picture stays the same: every action happens at exactly one end, the top.

The stack is studied as an ADT. Most programming languages give you a stack by default, but that is because the language has already implemented a stack in the backend, often using an array. The point of the ADT view is that the stack supports a fixed set of operations:

Formalize — the stack ADT contract. The stack supports two fundamental operations:

push(O) — insert object $O$ at the top of the stack. The element to push is an argument.
pop() — remove from the stack and return the top object. If the stack is empty, return an error.

These two are supported by a few supporting methods:

size() — return the number of objects in the stack.
is_empty() — return a Boolean value indicating whether the stack is empty (false if it has at least one element).
top() — return the value of the top object on the stack without removing it; return an error if the stack is empty.

The contrast between top and pop matters: pop removes from the stack and returns the top object; top only returns the value, and the object remains on the stack.

Notice what the contract deliberately leaves out: how the objects are stored, whether the top is tracked by an index or a pointer, how much memory is used. Any implementation that honors these five methods is a stack from the caller's point of view — that is the ADT promise from section 4.2.

4.3.2 Array Implementation of the Stack

To create a stack using an array, we specify a maximum size $n$ for the stack, because an array needs a limit. The stack consists of an $n$ -element array $S$ and an integer variable $t$ , which is the index of the top element in the array. Array indices start at 0, so the valid indices run from 0 to $n - 1$ , and $t$ points at the top element.

$t = - 1 initially, because the stack is empty$

The professor's warning — what does $t$ mean? One point that people implementing stacks regularly confuse is the meaning of $t$ : is $t$ the empty location where the next element will be inserted, or the last element currently in the stack? In this implementation $t$ is the top element in the stack. Because array indices start at 0, we initialize $t = - 1$ , so that when the first element is inserted $t$ points at index 0. As elements are added, $t$ is incremented; at the end, $t$ points to the top element in the array.

The push algorithm: first check whether the stack is full — "if size equals $n$ , return an error." If there are already $n$ elements present, we cannot push more. Otherwise, increment the pointer and store the new element:

$push (O) : if t = n - 1 then error; else t \leftarrow t + 1; S [t] \leftarrow O$

The full condition $t = n - 1$ is exactly the spoken condition "if size equals $n$ ": with $t$ holding the index of the top element, the number of elements is $t + 1$ , so the stack is full precisely when $t + 1 = n$ , that is, $t = n - 1$ . The reference implementation states the check the same way through the size method (if size() = n then raise a stack-full error), and then performs the identical steps $t \leftarrow t + 1$ and $S [t] \leftarrow O$ — the two formulations are the same test in different words.

The pop algorithm: "if is empty, then return an error; otherwise $t \leftarrow t - 1$ ." Popping means removing the top element and returning that object; the only real operation is decrementing $t$ . Because $t$ has been decremented, the returned element is at index $t + 1$ :

$pop () : if is_empty then error; else t \leftarrow t - 1; return S [t + 1]$

The reference version performs the same update but keeps a temporary: $e \leftarrow S [t]$ , then clear the vacated cell ( $S [t] \leftarrow null$ ), then $t \leftarrow t - 1$ , then return $e$ . The result is identical — the element at the old top index is returned and $t$ moves down by one.

The supporting methods are equally simple. size just returns $t + 1$ — since we started counting from index 0, adding 1 converts the top index into a count. is_empty checks whether the top value is less than 0; if $t = - 1$ , the stack is definitely empty. top returns $S [t]$ after the empty check — it returns the top element and does not remove it.

4.3.3 Worked Example — Tracing Push and Pop on the Array

Trace with real numbers. Suppose the stack is created with $n = 5$ , so the array has indices 0 to 4, and $t$ is initialized to $- 1$ .

Step	Operation	Check	$t$ before	Action	$t$ after	Array $S$	Result
1	push("A")	full? $- 1 = 4$ ? no	$- 1$	$t \leftarrow 0$ ; $S [0] \leftarrow A$	0	A, ·, ·, ·, ·	—
2	push("B")	full? $0 = 4$ ? no	0	$t \leftarrow 1$ ; $S [1] \leftarrow B$	1	A, B, ·, ·, ·	—
3	push("C")	full? $1 = 4$ ? no	1	$t \leftarrow 2$ ; $S [2] \leftarrow C$	2	A, B, C, ·, ·	—
4	top()	empty? $t = - 1$ ? no	2	return $S [2]$	2	A, B, C, ·, ·	returns C; C stays
5	pop()	empty? no	2	$t \leftarrow 1$ ; return $S [2]$	1	A, B, C, ·, ·	returns C; B is new top
6	size()	—	1	return $t + 1 = 2$	1	A, B, C, ·, ·	returns 2
7	is_empty()	—	1	return $1 < 0$ ? false	1	A, B, C, ·, ·	returns false

Note the order in step 5: decrement first, then return $S [t + 1]$ . The array cell still holds C, but $t = 1$ says the stack has two elements, A and B, with B on top.

If we keep popping: pop returns B, then pop returns A, and $t = - 1$ . A further pop finds the stack empty and returns an error. Sense-check: three pushes then three pops empty the stack — every element that went in, in reverse order, came out.

4.3.4 Time Complexities of Stack Operations

Every stack operation in the array implementation runs in $O (1)$ — constant time. Push is just an insertion at a known index; pop is a single decrement; top, size and is_empty are single reads or comparisons. Nothing scans the array.

The practical meaning of constant time: the time taken by the algorithm does not depend on the size of the input. It is not exactly one unit of time — it can be anything — the only meaning is that it does not grow with the input size. That is why it is always meaningful to say big-O of 1: whether the stack holds 10 elements or 10 million, push, pop, top, size, and is_empty each perform a fixed number of elementary operations — an arithmetic step, a comparison, an array read or write.

Pitfalls.

Reading " $O (1)$ " as "one microsecond." Constant time means the growth rate is flat, not that the constant is 1. A push that costs 50 instructions is still $O (1)$ ; a push that costs 1 instruction per element would be $O (n)$ .
Calling top and expecting removal. Top is a read; pop is a read plus a removal. The two differ by exactly one step, which is why students mix them up under time pressure.
__Confusing is_empty with "no space."__ An empty stack can still be in a full array — emptiness is about $t = - 1$ , fullness is about $t = n - 1$ . The two conditions live at opposite ends of the index range.

Exam note: be able to justify each stack operation as $O (1)$ — name the fixed number of steps each one takes (one comparison, one increment, one array access) — and explain why "constant time" does not mean "exactly one unit of time."

4.3.5 Disadvantage of the Array Implementation and the Dynamic-Array Fix

The array implementation has a clear disadvantage: there is an upper bound $n$ on the size of the stack. At the start we often do not know exactly how many elements the stack will hold, so we might set $n$ too large — wasting memory — or too small — running out of space. The array implementation always forces us to specify an upper bound.

The dynamic-array fix. In real systems, arrays do not stay fixed. When the array becomes full — in the discussion, when 75% of the array is full, a load factor of 0.75 — the system allocates new storage and reallocates the array; memory is allocated dynamically. The usual growth is to double the array, going for $2 n$ .

Why double instead of growing by one? "Every time increasing the size by 1 will affect the time complexity" — growing by a single slot makes resizing happen constantly. Why not triple, $3 n$ ? That would waste memory again. Doubling is the mid-ground: few resizes, modest waste.

The same logic quantified: with doubling, $n$ elements trigger about $lo g_{2} n$ resizes total, and the total copying work over all resizes is $1 + 2 + 4 + \dots + n \approx 2 n$ — so the average cost per push stays constant even though any single resize costs $O (n)$ . With growth by one, every single push copies all existing elements, and the average cost becomes $O (n)$ .

Work the doubling arithmetic on a tiny case. Start with a stack of capacity 1 and push 8 elements; each push that finds the array full triggers a doubling that copies the current contents:

$push 1: push 2: push 3: push 5: push 9: capacity 1 \to 1 element (no copy) array full \to copy 1, grow to 2 array full \to copy 2, grow to 4 array full \to copy 4, grow to 8 array full \to copy 8, grow to 16$

The copies total $1 + 2 + 4 + 8 = 15$ cell moves for 16 pushes' worth of growth — less than twice the final size, so the amortized cost per push is a constant. Sense-check: growing by one instead would copy 0, 1, 2, 3, ..., 7 cells — about 28 moves for the same 8 elements, and the total grows like $n^{2} /2$ , which is why "increase by 1" turns push into a linear-time operation on average.

Real-world: this load-factor-plus-doubling behavior is exactly how dynamic arrays work inside modern language runtimes, so a stack built on a dynamic array avoids the fixed upper-bound problem without giving up $O (1)$ amortized pushes.

4.3.6 Applications of the Stack

The stack appears everywhere in everyday computing:

Undo operations — in almost every application, undo works on a stack of previous states; each new action is pushed, and undo pops the most recent one. This is the hook of this section, now with a name: LIFO history.
Web browser back button — browsers store the addresses of recently visited sites on a stack of addresses. Each time a user visits a new site, the address is pushed onto the stack; the back button pops back to the previously visited site. (The textbook's own opening example for the stack ADT.)
Procedure calls — function calls use the system stack: each call pushes its frame (return address, parameters, local variables), each return pops it. A debugger's "call stack" is literally this stack; unlimited recursion runs it out of memory.
Reversing a word — store the characters of the word in a stack one by one, then pop them all; the popped order is the reverse of the stored order. A very simple example of the LIFO property: push W, O, R, D gives top = D, and pop, pop, pop, pop yields D, R, O, W. Trace it: push W → stack W; push O → W, O; push R → W, O, R; push D → W, O, R, D (D on top). Pop: D, then R, then O, then W — the word comes out backwards, with no loop over positions and no second array.
Even everyday objects behave like stacks: the plates dispenser in hotels is the origin of the name, and a stack of bangles on a wrist — pushing a bangle on, popping it off — is the same principle in miniature.

4.3.7 Stock Span Problem (Homework)

The stock span problem is a very popular problem — the kind of question that shows up constantly in interviews. It is assigned as homework, and it is deliberately simple. Given a list of prices of a single stock for $n$ number of days, find the stock span for each day. The stock span for a day is the number of consecutive days prior to the current day on which the price of the stock was less than or equal to the price at the current day.

The problem is to be solved with a stack, in at most $O (n)$ time — scanning each day once. Searching online for "stock span problem" (a plain web search engine like Google) returns the solution immediately, but the assignment is to understand the problem first and solve it yourself with a stack, then post the solution where the course shares materials. The naive approach without a stack is not effective; the $O (n)$ solution is the point.

Worked sketch — the $O (n)$ idea. Prices for six days: $100, 80, 60, 70, 60, 75$ . The span of day $i$ is the count of consecutive days ending at $i$ whose price is at most today's price (today included).

Day 1 (100): no prior days — span 1.
Day 2 (80): day 1 price 100 > 80, so the run stops — span 1.
Day 3 (60): 80 > 60 — span 1.
Day 4 (70): day 3 (60) $\leq$ 70, day 2 (80) $>$ 70 — span 2.
Day 5 (60): 70 > 60 — span 1.
Day 6 (75): days 5, 4, 3 (60, 70, 60) $\leq$ 75, day 2 (80) $>$ 75 — span 4.

Answer: $[1, 1, 1, 2, 1, 4]$ . The stack keeps indices of decreasing prices; each day pops the smaller-or-equal prices from the top, and the span is the distance to the new top. Because every index is pushed once and popped once, the total work is $O (n)$ . Sense-check: the last span counts today plus three prior days — exactly the four consecutive days 3–6 whose prices never exceeded 75.

Real-world: stock span is a stand-in for the "previous greater element" pattern used in financial charting and in many competitive programming problems — whenever you must answer "how far back do I look before something bigger appears," the same stack trick applies.

4.3.8 Student Questions and Answers

Q: Why can't we say the complexity is theta of 1 instead of big O of 1? A: When we say the time complexity of an algorithm is constant, we mean the time taken does not depend on the size of the problem. It is not exactly one unit of time — it can be any constant. That is why it is always meaningful to say big O of 1.

Q: Does top remove the top object, like pop does? A: No. Pop removes from the stack and returns the top object. Top only returns the value of the top object — the object remains on the stack. The difference is removal.

Q: When the dynamic array is full, why not just increase the size to n plus 1? A: If we keep increasing the size by 1, resizing happens over and over and that affects the time complexity. So we mostly go for 2n. And why not 3n? That wastes memory again. Doubling is the mid-ground.

4.3.9 Pitfalls, Recap, and Real-World Connections

Pitfalls — the exam-favorite traps.

The $t$ meaning trap. Remember: $t$ is the top element's index, not the next empty slot. Everything else — $t = - 1$ for empty, size $= t + 1$ , the full test $t = n - 1$ — follows from that single decision. Rederive, never memorize: empty means "no top," so the top index must start at $- 1$ .
Popping an empty stack. Check is_empty before touching $S [t + 1]$ ; reading an index below 0 is an array-out-of-bounds error, not a "nice empty answer."
Expecting LIFO order from a queue-like workflow. If you push A, B, C and pop twice, you get C then B — never A. A stack has no "front"; the only door is the top.
Confusing the stack ADT with its array. The array with the top index is one implementation; a linked list of nodes is another. The exam asks about the ADT contract and about the array implementation separately.

Recap + Bridge. The stack is the LIFO container: push on top, pop from the top, everything $O (1)$ in the array implementation, with the dynamic-array doubling fix removing the size limit. Next we meet the stack's sibling — the queue — where the door moves to the other end: first in, first out.

Real-world: beyond undo, back buttons, and call stacks, the LIFO discipline shows up in expression evaluation (matching brackets, postfix arithmetic), in compilers' symbol-table handling of scopes, and in hardware stacks in embedded processors. Any place where "the most recent thing must be handled first" is a stack — which is why the ADT, not any particular array, is the idea that travels.

Worked mini-trace — matching brackets. Check whether the expression " $(() [])$ " is balanced. Push every opening bracket; on every closing bracket, pop the top and compare kinds:

read '(' — push: stack = (.
read '(' — push: stack = ( (.
read ')' — pop; it is '(' and we saw ')' — match.
read '[' — push: stack = ( [.
read ']' — pop; it is '[' and we saw ']' — match.
read ')' — pop; it is '(' and we saw ')' — match.

The stack ends empty, so the expression is balanced. If a closing bracket had met the wrong opener — say ')' over '[' — the mismatch would be caught at the pop. One pass, one stack, $O (n)$ — a textbook-sized version of the LIFO idea in action.

4.4 Queue

4.4.1 The Queue ADT and Its Operations

Hook. When you stand in line at a ticket counter, you do not expect the last person to arrive to be served first — the person who waited longest goes next. That single fairness rule, first in, first out, is the entire definition of a queue.

A queue — a container of objects that are inserted and removed according to the FIFO principle: first in, first out. The first element in is the first element out. Elements may be inserted at any time, but only the element that has been in the queue the longest may be removed. Elements are inserted at the rear end and removed from the front end.

A useful contrast: the way people enter and leave a lift is an example of a stack, not a queue — the first person in is, ideally, the last person out. A queue is the ticket-counter line: first in line, first served.

Formalize — the queue ADT contract. The queue supports two fundamental methods:

enqueue(O) (nq) — insert the object $O$ at the rear end of the queue.
dequeue() (dq) — remove from the queue and return the object at the front. There is no argument to dequeue, because its job is remove-and-return.

The supporting methods are size, is_empty, and front. Where the stack had top, the queue has front: it returns, but does not remove, the front object.

Compare with the stack: both are linear containers, both have size/is_empty, both are $O (1)$ per operation in their array forms — the only real difference is which end does the work. The stack works and removes at the top; the queue inserts at the rear and removes at the front. That one change forces the queue's implementation to track two ends instead of one — which is exactly the complication of the next subsection.

Dimension	Stack	Queue
Order rule	LIFO — last in, first out	FIFO — first in, first out
Insertion end	top (push)	rear (enqueue)
Removal end	top (pop)	front (dequeue)
Peek method	top()	front()
Pointers tracked in an array implementation	one (top index $t$ )	two (front $f$ , rear $r$ )
Everyday picture	plate dispenser, undo history	ticket-counter line, print spooler

When to pick which: need the most recent thing first — stack; need fairness and arrival order — queue. The queue's price for fairness is the second pointer and the wrap-around machinery of the next subsections.

4.4.2 Array Implementation of the Queue

For the array implementation, a maximum size $n$ is specified. The queue consists of an $n$ -element array $Q$ and two integer variables, because two ends have to be tracked:

$f$ — the index of the cell of $Q$ storing the first element of the queue, which is the next candidate to be removed by a dequeue operation.
$r$ — the index of the next available array cell, where the next element will be inserted. Unlike $f$ , $r$ does not point at an occupied cell.

Array indices run from 0 to $n - 1$ , and initially $f = r = 0$ is the empty-queue condition. When an element is inserted, $r$ is incremented to point at the next available location; when an element is removed, $f$ advances.

4.4.3 Worked Example — Repeated Enqueue and Dequeue Failure

Trace with real numbers. What happens if we repeatedly enqueue and dequeue a single element? Walk through it with a small array, say $n = 4$ , indices 0 to 3:

Step	Operation	Cell used	$f$	$r$	Array $Q$
0	start	—	0	0	·, ·, ·, ·
1	enqueue "a"	$Q [0]$	0	1	a, ·, ·, ·
2	dequeue	—	1	1	a, ·, ·, ·
3	enqueue "a"	$Q [1]$	1	2	a, a, ·, ·
4	dequeue	—	2	2	a, a, ·, ·
5	enqueue "a"	$Q [2]$	2	3	a, a, a, ·
6	dequeue	—	3	3	a, a, a, ·

At the end, $f = 3$ and $r = 3$ . Now $f = r$ — the condition that signals an empty queue — and if we try to insert one more element, we get an array out of bound error, because there are only $n$ valid locations, 0 to $n - 1$ , in the linear array.

The critical observation: even though there is plenty of room in the queue — every location we deleted from is now empty — we cannot insert the next element, because we have reached the end of the array and both pointers sit at the same spot. The linear array has no way to reuse the freed locations at the front. Sense-check: the queue truly is empty (one element, in, out, four times), yet the array is "stuck" at its right edge — the pointers walked off the end without ever circling back.

4.4.4 Wrap-Around (Circular Array) Configuration

To avoid this problem we use a wrap-around configuration: a circular array that goes from 0 to $n - 1$ and then immediately back to 0. If there are empty locations at the beginning of the array, we come back after $n - 1$ and store elements there.

Instead of incrementing by one and stopping, the increments wrap with a modulo:

$r \leftarrow (r + 1) mod n on enqueue$

$f \leftarrow (f + 1) mod n on dequeue$

In the normal configuration $f$ is always less than or equal to $r$ ; in the wrapped-around configuration $r$ can be less than $f$ , because the array is circular.

Now the empty/full ambiguity appears: when the array is empty we have $f = r$ , but when the array is full, $r$ wraps around and overlaps $f$ , so the full condition is also $f = r$ . To distinguish the two states we impose a constraint: the queue can hold at most $n - 1$ objects. If it were allowed to store $n$ objects, $r$ would overlap the front pointer exactly at full capacity and we could not tell full from empty. Giving up one cell resolves the ambiguity — one wasted slot is the price of the wrap-around design.

4.4.5 Worked Example — Insertion After a Wrap, and the Size Formula

Worked example 1 — inserting after the wrap. Take a circular array with $n = 8$ , indices 0 to 7. Suppose elements have filled positions 0 to 6, $r$ points at index 7, and the front element has been deleted from position 0, leaving $f = 1$ . The zeroth location is now empty. To insert the next element, we compute $7 + 1 = 8$ , then $8 mod 8 = 0$ , and we can insert the element at location 0. This is the whole trick of the wrap-around configuration: "we take the modulo $n$ so that it will go back to the first empty location available at the beginning of the array again."

Worked example 2 — the size formula. The size of the queue is computed as:

$size = (n - f + r) mod n$

Take $n = 8$ , $f = 0$ , and $r = 5$ (the rear points at the next available empty cell). Then $8 - 0 + 5 = 13$ , and $13 mod 8 = 5$ . The queue holds five elements — count them: the occupied cells are 0, 1, 2, 3, 4. The formula gives the right answer.

The formula works both in the normal configuration (where $f \leq r$ ) and in the wrapped-around configuration (where $r < f$ ). Check the wrapped case with numbers: if $f = 6$ and $r = 2$ , then $8 - 6 + 2 = 4$ , and $4 mod 8 = 4$ — cells 6, 7, 0, 1 are occupied, which is exactly four elements. Without the modulo, $n - f + r$ would be a number larger than the true count; the modulo wraps it back. Sense-check: the count can never exceed $n - 1$ , and $(n - f + r) mod n$ always lands in $0, \dots, n - 1$ .

Visual intuition — the clock face. Draw the circular array as a clock face with positions 0 to $n - 1$ arranged clockwise. The rear pointer $r$ is the hand that always points at the next free slot; the front pointer $f$ is the hand that points at the oldest waiting element. Enqueue moves $r$ one step clockwise (wrapping from $n - 1$ back to 0); dequeue moves $f$ one step clockwise. The size of the queue is the clockwise arc from $f$ to $r$ . When the two hands coincide, $f = r$ , the queue is empty — and because the $n - 1$ rule forbids ever filling the last slot, the hands can never lap each other, so "hands together" always means empty.

4.4.6 Time Complexities of Queue Operations

The enqueue algorithm: if $size = n - 1$ , return an error — we do not allow the last location to become occupied, because it would overlap and create the empty/full confusion. Otherwise, the element is enqueued into $Q [r]$ (since $r$ points at the next available cell), and then $r$ is incremented with the wrap-around: $r \leftarrow (r + 1) mod n$ .

The dequeue algorithm: if the queue is empty, return an error. Otherwise, assign null to $Q [f]$ — the cell being vacated is cleared — and advance the front: $f \leftarrow (f + 1) mod n$ .

The is_empty check is simply $f = r$ . With the $n - 1$ constraint in place, this condition applies only to the empty state. The front method returns $Q [f]$ after the empty check. All the queue methods run in $O (1)$ time: each performs a constant number of comparisons, arithmetic steps, and array accesses — one modulo step included — and none of them scans the array.

Put the two workhorse methods side by side as pseudocode:

$enqueue (O) : dequeue () : if (n - f + r) mod n = n - 1 then error Q [r] \leftarrow O; r \leftarrow (r + 1) mod n if f = r then error temp \leftarrow Q [f]; Q [f] \leftarrow null; f \leftarrow (f + 1) mod n return temp$

The enqueue guard checks the size against $n - 1$ — the queue must never fill the last cell, or full would become indistinguishable from empty. The dequeue clears the vacated cell before advancing the front, so stale elements never linger. Both algorithms touch a fixed number of cells — that is the $O (1)$ justification in code form.

4.4.7 Applications of the Queue

Multi-programming in operating systems: processes waiting for a resource or a processor form queues, and scheduling hands the resource to the front of the line. The round-robin scheduler is a queue in action: each thread is dequeued for a time slice, then re-enqueued at the rear.
The normal queue in front of a ticket counter: customers are served first in, first out — the everyday picture that gave the structure its name.
Anything that must preserve arrival order — printers, message lines, and so on — is naturally a queue: print jobs, chat messages, and network packets all keep arrival order because a queue keeps it for them.

4.4.8 Implementing a Queue Using Two Stacks

A queue can be implemented with two stacks, and the lecture works through the mechanics in full. We have two stacks, S1 and S2, and only push and pop operations are available on each. We want the pair to behave like a queue.

Design A — making the dequeue operation costly. Push the elements into S1: 1, 2, 3, 4, 5, with 5 on top. If this arrangement is a queue, the element that must be dequeued first is 1 — but a plain pop from S1 gives 5. So: pop every element from S1 and push it onto S2 (pop 5, push 5; pop 4, push 4; pop 3, push 3; pop 2, push 2; pop 1, push 1). Now S2 holds 5, 4, 3, 2, 1 with 1 on top. A single pop from S2 returns 1 — that is the dequeue.

The process is not over: to keep the queue consistent, push everything back from S2 into S1 (1 is gone, so 2, 3, 4, 5 return to S1, with 5 on top). The next dequeue should give 4, and the whole dance repeats: pop from S1 $n$ times and push to S2, pop once from S2, then pop from S2 $n - 1$ times and push back to S1.

A single dequeue involves, in total: pushing elements into S1, popping them from S1, pushing them into S2, one pop on S2, then moving everything back. The dequeue has become an $O (n)$ operation — the queue primitive that used to be constant time now costs linear time.

Design B — making the enqueue operation costly instead. Reverse the approach: while S1 is not empty, pop everything from S1 and push it into S2; enqueue the new element into S2 (it lands on top); then push everything back from S2 to S1 so the new element ends up at the bottom — the last position in the queue. For example, with 1, 2, 3, 4, 5 in S1 (1 on top, so that a plain pop dequeues the front), enqueuing 6 means: move 1..5 to S2, push 6, move everything back so S1 holds the queue 1, 2, 3, 4, 5, 6 — the front 1 back on top and the new element 6 at the bottom. Now enqueue is the $O (n)$ operation and dequeue is a plain $O (1)$ pop from S1.

Worked trace of Design B with the stack contents drawn. Start with S1 = [1, 2, 3] (1 on top — the front of the queue):

Step	S1 (top on the right)	S2 (top on the right)	Why
start	[3, 2, 1]	[]	queue = 1, 2, 3
move to S2	[]	[1, 2, 3]	pop 1, 2, 3 from S1, push onto S2 — order flips, 3 on top
enqueue 4 into S2	[]	[1, 2, 3, 4]	4 lands on top of S2
move back to S1	[4, 3, 2, 1]	[]	pop 4, 3, 2, 1 and push onto S1 — 4 ends at the bottom, 1 on top

Now S1's top is 1 — the queue's front — so dequeue is one pop; and 4, the newest element, sits at the bottom, the last position in the queue. Sense-check: two enqueues in a row each flip the entire contents twice, which is why this design pays $O (n)$ inside enqueue and keeps dequeue at $O (1)$ .

In one line: both designs exist — either enqueue is costly and dequeue is cheap, or dequeue is costly and enqueue is cheap — because all the rearranging happens at one time, inside one of the two operations. A smarter variant (in the reference textbooks' exercises) moves elements from S1 to S2 only when S2 is empty and leaves them there, giving $O (1)$ amortized behavior — but the lecture's point is the direct trace: one of the two operations pays $O (n)$ per call.

4.4.9 Student Questions and Answers

Q: Why is the two-stack operation not logarithmic? If there are about n elements, why should it take n steps? A: Every time we pop, there are about n, then n minus 1, then n minus 2 elements to move — but in between we may also enqueue, so the count goes back up. On average we are moving n elements. One operation — either enqueue or dequeue — is big O of n, because all the rearranging happens at one time inside that single operation.

Q: Why are we implementing a queue using stacks at all? A: Because it is one possible implementation, and that is the reason to study these structures as ADTs — the backend implementation can be made in different ways. Using two stacks involves too much time complexity and we would not do that ideally, but if you ever want to, there are ways to do it.

Q: The two-stack procedure seems confusing. Is it hard? A: It is a very simple procedure — consider two stacks, assume only push and pop are available, and you need the pair to behave like a queue. If you keep repeating the steps over and over you will only get more confused. Do not overthink it; think with a cool mind. It is not rocket science, just simple logic.

4.4.10 Pitfalls, Recap, and Real-World Connections

Pitfalls.

Using $f$ and $r$ as if the array were linear. The moment $r$ passes $n - 1$ , it must wrap to 0 — forgetting the modulo is how the repeated-enqueue example's out-of-bounds error happens in real code.
Forgetting why the queue holds only $n - 1$ objects. The extra slot is not waste by accident; it is the price of distinguishing full from empty when both satisfy $f = r$ .
Answering "size" by subtracting pointers. $(n - f + r) mod n$ handles both configurations; plain $r - f$ gives a wrong negative answer in the wrapped-around configuration.
Treating enqueue and dequeue as symmetric in the two-stack design. They are not: exactly one of them pays $O (n)$ , and which one depends on the design chosen.

Recap + Bridge. The queue is FIFO: insert at the rear, remove at the front; its array implementation needs two pointers, a modulo for wrapping, and an $n - 1$ capacity rule; the two-stack construction shows the ADT mindset — same contract, wildly different backend costs. Next, the course drops the "contiguous array" assumption entirely and stores elements in scattered nodes connected by pointers: the linked list.

Real-world: queues are the fairness machinery of computing — OS process schedulers, print spoolers, message brokers, and packet buffers all use FIFO order. In networking, a router's packet queue is exactly this ADT; in operating systems, the runnable-process queue is the round-robin picture from section 4.4.7. Wherever "arrival order must be respected," the queue is the right ADT.

4.5 Singly Linked List

4.5.1 Nodes, Head, Tail, and Traversal

Hook. An array keeps its elements side by side in one memory block. What if you could not reserve that block — only scattered boxes anywhere in memory? The linked list answers with a simple deal: every box stores its element and the address of the next box. The boxes themselves can live anywhere; the addresses form the chain.

A linked list — a data structure consisting of a sequence of nodes. Each node stores a reference to an object — the element — and a link to the next node. Because each node carries a pointer to the next node, the linked list is again a linear data structure: we can access the next element from the current one. The first and last nodes of the list are usually called the head and the tail. Moving from one node to another by following a next reference is known as traversing the list, or link hopping, or pointer hopping. The order of the elements is determined by the chain of next links going from each node to its successor.

Formalize — the node. A node is the unit cell of the list. In a singly linked list, a node holds exactly two things:

an element — the object the node stores (say, the string "ATL" or a number),
a next link — a reference (pointer) to the next node in the sequence.

The node class is written in code exactly like that: a field for the element and a field for the pointer. In the reference implementation, the list object itself keeps a head pointer and a size counter; whether it also keeps a tail pointer is a design choice we examine below.

One critical property: we do not keep track of any index numbers for the nodes in a linked list. By examining a single node we cannot tell whether it is the second, the fifth, or the twentieth node in the list — there are no positions like the indices of an array, only pointers. To implement a singly linked list, we define a node class holding an element and a pointer to the next element; that is exactly how it is written in a programming language.

4.5.2 Insert and Remove at Head and Tail

Insert at the head: to insert a new node when the list is given, make the next pointer of the new node point to the first element of the already existing list, then make the new node the head. Two operations: fix the new node's pointer, update the head.

Insert at the tail: this needs access to the tail of the existing list. Make the next pointer of the existing tail point to the new node, and make the new node the tail.

Removal from the head: the reverse process. Change the head pointer to the node pointed to by the current head — the second node becomes the head — and then remove the old first element.

Removal from the tail is not easy in a singly linked list: there is no pointer from the tail back to the node that precedes it, so we cannot fix the previous node's link without a full traversal.

Worked traces on the list A → B → C. Assume the list keeps both a head pointer and a tail pointer.

Insert X at the head. Make X's next pointer point to A (the current head), then set head = X. The list becomes X → A → B → C. Two pointer touches, $O (1)$ — the head pointer is the door.
Insert Y at the tail. The tail pointer already names C. Make C's next pointer point to Y, then set tail = Y. The list becomes A → B → C → Y. Two pointer touches, $O (1)$ — the tail pointer is the second door.
Remove from the head. Read head's successor: the node A after X. Set head = A, and X is out of the list. The list becomes A → B → C. One pointer read plus one pointer write, $O (1)$ .
Remove from the tail. The tail pointer names C, but C does not know its predecessor B. The only way to find B is to walk the chain from the head — A → B — and only then can B.next be set to null (the end marker) and tail = B. The walk makes this $O (n)$ .

Sense-check the pattern: every constant-time case uses a pointer we already hold (head or tail); the linear case needs a pointer that a singly linked node cannot provide — the one pointing at it.

Scope — what makes the four cases differ in cost. Insert at head and removal from head are cheap because the head pointer is always available — "without head, we cannot use the list." Insert at tail is cheap only if the list keeps an explicit tail pointer; without it, reaching the last node costs a walk from the head. Removal from the tail is expensive in a singly linked list regardless: the predecessor of the tail is unreachable from the tail itself, so finding it forces a full traversal from the head.

4.5.3 Why Insert-Before Is Costly

Insert-before operations are also hard in a singly linked list. To insert a node before the node holding element ATL, we cannot do it directly from ATL — ATL only knows its own next pointer, not the node that points at it. We must traverse from the head of the list and reach ATL; only then do we learn which node is pointing to ATL. Then we make that node point to the new node, and the new node point to ATL.

The algorithm looks like: insert_before(N, O) — if N is the head, insert O at the first location. Otherwise, traverse the list by following next pointers until N is found, remembering the node M whose next pointer points to N; then insert the new node after M. The traversal makes this an $O (n)$ operation — the time grows with the length of the list.

Intuition — the one-way street. A singly linked list is a one-way street: every node points only to the car ahead of it, never to the car behind. To insert a car before the node holding ATL, the new car must be placed between the unknown predecessor and ATL, and the predecessor's bumper sticker must be changed to point at the new car. ATL cannot tell you who is behind it — so you must drive from the start of the street and read every bumper until you find the car pointing at ATL. That drive is the $O (n)$ traversal.

4.5.4 Time Complexities and Their Assumptions

The table below is the singly linked list complexity summary, with the assumptions made explicit. Everything hinges on the node-based approach: operations are described on given nodes, and the list keeps explicit head and tail pointers.

Operation	Time	Assumption
size	$O (1)$	a size variable is incremented on every insert
is_empty	$O (1)$	—
first	$O (1)$	a head pointer is stored
last	$O (1)$	a tail pointer is stored; otherwise $O (n)$ traversal
after(node)	$O (1)$	the node is given; follow its next pointer
before(node)	$O (n)$	traverse from head to find the predecessor
replace / swap elements	$O (1)$	the two nodes are given; pointer adjustment
insert_first	$O (1)$	head pointer available
insert_last	$O (1)$	tail pointer available; otherwise $O (n)$
insert_after	$O (1)$	node given
insert_before	$O (n)$	must find the predecessor by traversal
remove(node)	$O (n)$	must find the node pointing at the given node

If a tail pointer is not kept, "last" and "insert last" cost $O (n)$ : we must traverse from the head to reach the last node. The head pointer, by contrast, is always mandatory — "without head, we cannot use the list" — which is why nobody questions first; the tail is the one that must be explicitly mentioned. The after operation is constant time only when the node itself is given: after(B) is answered by reading B's next pointer, and both B and its successor are already known. Replace and swap are constant because, with both nodes given, only the pointers need adjusting. Remove is $O (n)$ : to remove ATL we must first find which node points to ATL, and that requires traversing from the beginning. Do not confuse the "3" seen in the worked diagram with an exponent — remove is $O (n)$ , not $O (n^{3})$ ; the 3 is a step number.

Visual intuition. Picture the list as a horizontal chain of boxes, each with a rightward arrow to the next box. Mark the leftmost box head and the rightmost tail. For after(B), the arrow from B already lands on a known box — one hop, $O (1)$ . For before(B), the needed arrow is the incoming one, and in a singly linked list no arrow points left — the only way to find the box that points at B is to walk the chain from the head, one arrow per box, $O (n)$ . The visual takeaway: singly linked lists answer "what comes next" instantly and "what came before" only after a walk.

4.5.5 Worked Examples — Insert After B and Insert Before B

Worked example 1 — insert after the node B (constant time). The list is A → B → C, and we want to insert the element E after B.

The node B is given, so we already know B and its next pointer — we know C as well, because B's next pointer points to C.
Make B's next pointer point to E.
Make E's next pointer point to C.

The list becomes A → B → E → C. These are just pointer-adjustment operations; we do not have to traverse the list to find B or C, because B is given and its successor is known. The operation is $O (1)$ . Sense-check: three pointer touches (read B.next, write B.next, write E.next), no matter how long the list is — even with a million nodes, the answer comes from B alone.

Worked example 2 — insert before the node B (linear time). The list is A → B → C, and we want to insert F before B.

We know B, and we know B's next pointer points to C — but that is of no use.
For F to sit before B, A must point to F and F must point to B. We have no idea about A, and B does not know its predecessor.
The only way to find A is to start from the beginning of the list and traverse until we reach B; on the way we learn which node is pointing to B.
Then we make A's next pointer point to F, and F's next pointer point to B.

The list becomes A → F → B → C. That traversal costs $O (n)$ — in a list of length $n$ , B might be the last node, and the walk visits every node before it. Sense-check: the expensive part is not the two pointer writes; it is finding A, and finding A requires walking the chain.

Worked example 3 — remove ATL (linear time). To remove ATL we must find the node pointing to ATL first — only then can we cut it and make it point past ATL to ATL's successor. Finding that predecessor is a traversal from the beginning of the list, so removal of a node costs $O (n)$ time in a singly linked list. Once the predecessor is found, the surgery is two pointer writes: predecessor.next ← ATL.next, and ATL is out of the chain. Sense-check: removal is the mirror of insert-before — both are $O (n)$ for the same reason: the missing reverse link.

4.5.6 How a Linked List Lives in Memory

In memory, a linked list does not need contiguous memory allocation. The nodes can be scattered anywhere; the pointers identify where the next node is. That is the fundamental difference from an array, which occupies one continuous block.

Scope — the trade-off that never goes away. Because nodes may be scattered, a linked list never suffers "we ran out of space in this block" the way a fixed array does — a new node can be allocated anywhere. The price is the reverse: following a pointer may jump to a distant memory address, and modern CPUs prefer nearby data (cache). An array reads neighbors fast but needs one contiguous block; a linked list tolerates fragmented memory but pays for pointer chasing. That is why real systems pick based on the access pattern, not on one structure being "better."

Real-world: the linked list's non-contiguous storage is exactly what makes it attractive for situations where memory blocks are fragmented, though the pointer chasing costs cache misses compared with arrays.

4.5.7 Student Questions and Answers

Q: First, last and after — are they really big O of 1? Last should be N, because we need to traverse. A: Yes, O(1), under the assumptions that we store a head pointer and a tail pointer explicitly. First is O(1) because the head pointer gives the first node directly. Last is O(1) only if we keep a tail pointer; without it, finding the last node means traversing from head, and last becomes O(n). After is O(1) when the node is given — the element and its next pointer are right there.

Q: Why is insert before a node big O of n? We are given the node B. A: Being given B does not help: you know B and its next pointer (pointing to C), but to insert before B you need A, the node pointing to B. You do not know A, and nothing in B reveals it. So you have to start from the beginning of the list, traverse till you reach B, and learn which node points to B. That traversal is why insert before is big O of n.

Q: For after, we need to find the element first and then return the next, so it cannot be constant time. A: The assumption in the node-based approach is that the node is given — after B means "the node B is given." The element and the next pointer are given along with it, so no search is needed. That is what makes after constant time. The story changes only if we ask "after the element whose value is B" — then we must search.

Q: What about inserting at a random position, like position 7? A: That cannot be done in the node-based approach, because a linked list has no index numbers — only pointers. Position-based insertion is a different abstraction: positions are just an abstraction, and that is what we talk about next with the position ADT. For a linked list, you either work node-based or position-based; positions are not array indices.

4.5.8 Pitfalls, Recap, and Real-World Connections

Pitfalls.

Quoting $O (1)$ without the assumption. "after is $O (1)$ " is true only when the node is handed to you. Ask "after the element whose value is B" and you must first search for B — different problem, different cost.
Reading a complexity table row in isolation. Every row depends on the head/tail pointers and the "node given" contract; change the contract and the row changes (last and insert_last collapse to $O (n)$ without a tail pointer).
Breaking the chain when inserting or removing. Order the pointer writes carefully — if you overwrite B.next before saving C, the rest of the list is lost. The worked examples show the two-write pattern; the failure mode is doing the writes in the wrong order.
Treating "3" as an exponent. In the lecture's diagram the number 3 labels a step; remove is $O (n)$ , never $O (n^{3})$ .

Recap + Bridge. The singly linked list trades contiguous memory for scattered nodes joined by next pointers: everything at or after a given node is $O (1)$ , everything needing the predecessor is $O (n)$ , because the links only go forward. The obvious repair — give every node a link backward too — is exactly the doubly linked list, next.

Real-world: singly linked lists appear wherever a growing, never-reversing chain is needed — free lists in memory allocators, adjacency lists in graph algorithms, the internal buckets of hash tables, and the undo-adjacent "history of moves" in games. The "previous greater element" pattern of the stock span problem is also a disguised pointer-chasing idea: the stack plays the role of the backward links the list lacks.

4.6 Doubly Linked List

4.6.1 Two Links per Node

Hook. The singly linked list's one pain point was the missing backward link — every "find the predecessor" operation cost a walk. What if each node simply stored the answer to "who is behind me"? That single addition turns every $O (n)$ operation from the previous section into $O (1)$ .

A doubly linked list — the same idea as a singly linked list with one addition: each node carries a link to the previous node as well as a link to the next node. The node class holds an element, a previous pointer, and a next pointer. Every pointer update now involves four pointers instead of two — the next and previous of both affected nodes — and that is the only real complexity. The implementation typically uses header and trailer sentinel nodes: the header sits before the first element and the trailer sits after the last, so the list is never empty in the implementation and edge cases collapse.

Formalize — the sentinels. A sentinel is a dummy node that stores no element. The header has a valid next pointer but a null previous pointer; the trailer has a valid previous pointer but a null next pointer. An empty list is just header ⇄ trailer, pointing at each other. The payoff: "is the list empty?" becomes "is header.next the trailer?", and inserting at the very front or removing the very last element are the same four-pointer routine as everywhere else — no special cases in the code. The reference implementation stores only the two sentinels and a size counter.

4.6.2 Inserting a Node Between Two Nodes

Suppose the list runs from JFK to SFO and we want to insert a new node between them. Four pointer adjustments are needed: JFK's next pointer is made to point to the new node; the new node's next pointer is made to point to SFO; SFO's previous pointer is made to point to the new node; and the new node's previous pointer is made to point to JFK. The diagram makes the symmetry visible — the whole operation is adjusting pointers, nothing else.

Visual intuition — the four arrows. Draw the chain as JFK → SFO with two arrows between the boxes: JFK's outgoing arrow (JFK.next) and SFO's incoming arrow (SFO.prev) currently point at each other. Inserting the new node N rewrites exactly four arrows: JFK.next → N, N.next → SFO, SFO.prev → N, N.prev → JFK. The two old arrows are overwritten, nothing else moves. After the operation every node again has one arrow in and one arrow out — the chain's "two-lane road" look is the picture to remember. Removal reverses the same four arrows: to drop PVD, JFK.next is pointed straight at SFO and SFO.prev straight at JFK, and PVD is left with no arrows touching it.

Removal is the mirror image. To remove PVD from a chain ..., JFK, PVD, SFO, ...: make JFK's next pointer point to SFO, and make SFO's previous pointer point to JFK. PVD is out of the list. Again, pure pointer adjustment.

4.6.3 Worked Example — Remove Last Using the Trailer

Trace the four steps. The remove_last algorithm: if the size is zero, the list is empty. Otherwise, with the trailer sentinel in place:

trailer.get_previous() — this gives the last node (the node before the trailer), call it the node $w$ . "This is the previous pointer from the last node."
w.get_previous() — this gives the node before the last node, call it $v$ . "The node before the last node."
trailer.set_previous(v) — the trailer's previous pointer now skips the removed node.
v.set_next(trailer) — the predecessor's next pointer points at the trailer.

These statements are exactly the pointer adjustment seen in the insertion diagram. The time complexity: given the trailer (tail) pointer, removing the last element needs only pointer adjustments — about four pointer updates — so remove_last is $O (1)$ . The same idea applies to add_first: with the header pointer already there, just perform the four pointer adjustments and increment the size; removal decrements the size. Sense-check: the trailer reveals the last node in one hop, and that node reveals its predecessor in one more hop — no traversal, no loop, constant work.

4.6.4 Worked Example — Add After a Node

Trace the five lines. To add the node Z after the node V (Z is new, V is given):

w = v.get_next() — read V's next pointer; this value is W.
z.set_previous(v) — Z's previous pointer points to V.
z.set_next(w) — Z's next pointer points to W.
w.set_previous(z) — W's previous pointer points to Z.
v.set_next(z) — V's next pointer points to Z.

That is it — five lines, four pointer updates. The time complexity is $O (1)$ . Sense-check: V and W were both known before the first line ran — V was given and W came from V's own next pointer — so nothing required a search.

4.6.5 Worked Example — Remove a Node

Trace the catch. To remove Z (given), with neighbors V and W:

v = z.get_previous() — read Z's previous pointer to get V.
w = z.get_next() — read Z's next pointer to get W.
v.set_next(w) — V's next pointer skips Z.
w.set_previous(v) — W's previous pointer skips Z.

The whole trick — the "catch" — is that once Z is given, Z itself reveals both neighbors: z.get_previous() gives V and z.get_next() gives W. No traversal anywhere. Removal is $O (1)$ . Sense-check: compare with the singly linked list, where removing a node meant first finding its predecessor; here the node being removed hands you the predecessor for free.

4.6.6 Time Complexities of the Doubly Linked List

In the node-based approach, all the operations that were $O (n)$ in the singly linked list become $O (1)$ in the doubly linked list. Insert before, remove, remove last — all of them — because the node is given and the header and trailer pointers are already stored. The values that were $O (n)$ for the singly linked list are all constant time here, since we are only adjusting pointers. This is a clear improvement over the singly linked list.

Operation	Singly linked	Doubly linked
before(node)	$O (n)$ — traverse for predecessor	$O (1)$ — read previous pointer
insert_before	$O (n)$ — find the predecessor	$O (1)$ — predecessor given by node
remove(node)	$O (n)$ — find the node pointing at it	$O (1)$ — node reveals both neighbors
remove_last	$O (n)$ without a tail walk	$O (1)$ — trailer reveals the last node
after, insert_after	$O (1)$	$O (1)$
first, last, insert_first, insert_last	$O (1)$ with head/tail pointers	$O (1)$ with header/trailer

When to pick which: use a doubly linked list whenever you must frequently move backward or remove arbitrary given nodes at $O (1)$ ; keep a singly linked list when forward-only access suffices and you want half the pointer storage per node. The extra previous pointer doubles the pointer fields and makes every update touch twice as many links — the price of the backward superpower.

Exam note: be ready to trace the four pointer adjustments for insert and remove in a doubly linked list and to justify why the complexity drops from $O (n)$ to $O (1)$ — the answer is always the same: the node is given, and the node carries both neighbor links.

4.6.7 Student Questions and Answers

Q: Why are all these operations big O of 1 in the doubly linked list, when insert before was big O of n in the singly linked list? A: In the node-based approach, the node is given — you are given the node before or after which you are operating. Once you know Z, you know the next of Z and the previous of Z, so you know V and W. With the node in hand and the header and trailer pointers already stored, every operation is just pointer adjustment, which is constant time.

Q: Is it safe to give everyone direct access to the node for these insert and delete operations? A: No, it is not safe. The node is where the element and the pointers are stored, and operations manipulate the pointers directly. If someone messes up the pointers, the list breaks. So we abstract the concept of the node by using the ADT position — users manipulate positions, not raw nodes.

4.6.8 Pitfalls, Recap, and Real-World Connections

Pitfalls.

Updating only two pointers during an insert. A doubly linked insert needs four pointer writes (the two links of the new node plus the two links of its neighbors); skipping one leaves the list inconsistent in one direction.
Forgetting that sentinels exist. With header and trailer in place, "first" and "last" operations never touch null pointers — a null dereference usually means the sentinel design was dropped halfway.
Saying "doubly linked is always better." Every node now stores two links, and every update touches four pointers; the win is real only for backward moves and given-node removals.
Handing out raw nodes. The safety lesson of this section: exposing nodes invites pointer corruption — which is precisely the motivation for the position ADT next.

Recap + Bridge. The doubly linked list adds one previous pointer per node and makes every node-based operation $O (1)$ , at the cost of extra links and four-pointer updates. But now a new worry appears: giving users raw nodes is dangerous — so the next section wraps the node behind an ADT position, keeping the $O (1)$ behavior and the safety at the same time.

Real-world: doubly linked lists back the navigation history of browsers and editors (move forward and back through pages), the LRU cache eviction order in operating systems and databases (remove a given entry and move it to the head, both $O (1)$ ), and doubly linked deques in standard libraries. Any structure that must answer "what came before" as fast as "what comes next" is a doubly linked list.

4.7 The Position ADT and the List ADT

4.7.1 Why Abstract the Node — Safety

Hook. The doubly linked list is fast, but it has a hidden danger: the node stores the pointers, and every operation rewrites those pointers. Hand the raw node to a careless caller and the chain can be corrupted in one bad assignment. The fix is a layer of indirection — let users hold a position instead of a node.

The node-based approach works, but it is not safe to hand out raw nodes: the node stores the element and the pointer fields, and insert and delete mutate those pointers. A careless caller can corrupt the chain. The fix is to abstract the node behind an ADT called position.

A position — a place of an element relative to others in the list — an abstraction of a node, nothing more. The list is viewed as a collection of elements, each stored at a particular position, with the positions arranged in a linear order. Users never manipulate nodes directly; they manipulate only positions. The hardware implementation is still nodes and pointers — we are only wrapping them.

4.7.2 Position as an ADT

Position itself is an ADT supporting one operation, element:

$p . element () returns the element stored at position p$

For example, $p . element ()$ might be Baltimore, $q . element ()$ New York, and $r . element ()$ Paris. Positions are always defined relatively: position P is always after some position and before some other position. A position does not change even if the element stored at it is replaced or swapped — if Baltimore and New York are swapped, P is still P; only $p . element ()$ changes.

The word-processor analogy returns: the cursor in the word document is exactly a position. When we edit, we do not mention line numbers and character numbers; we operate through the cursor. For a linked list, the cursor-and-character-position abstraction is the position ADT.

Scope — what a position is and is not. A position is not an array index: it carries no number, and it stays meaningful only while its element is in the list. It is defined relative to its neighbors — after one position, before another. It changes identity only when the element is deleted (the position dies with its element); replacing or swapping the element leaves the position itself untouched. A position from one list is meaningless in another list — passing it around is an error the implementation must guard against.

4.7.3 The List ADT Methods

Viewing the list as an ADT through positions, the methods are:

$L . first ()$ — return the position of the first element of the list.
$L . last ()$ — return the position of the last (tail) element.
$L . is_first (p)$ — Boolean: is $p$ the first position?
$L . is_last (p)$ — Boolean: is $p$ the last position?
$L . before (p)$ — the position before $p$ .
$L . after (p)$ — the position after $p$ .
$L . size ()$ and $L . is_empty ()$ — the usual supporting methods.
$L . replace (p, e)$ — replace the element at position $p$ with element $e$ .
$L . swap (p, q)$ — swap the elements at positions $p$ and $q$ .
$L . add_first (e)$ , $L . add_last (e)$ , $L . add_before (p, e)$ , $L . add_after (p, e)$ , $L . delete (p)$ — the insertion and deletion family, all expressed through positions.

Many more methods can be defined; these are the ones on the screen. When these functions are implemented on a doubly linked list, the backend performs the node and pointer adjustments we already traced — the position is only an abstraction, and the actual adjustments depend on whether the implementation is singly or doubly linked.

List ADT method	On a doubly linked backend	On a singly linked backend
first(), last()	$O (1)$ — header/trailer sentinels	$O (1)$ with head and tail pointers; last() is $O (n)$ without a tail pointer
before(p), after(p)	$O (1)$ — follow p's links	after(p) $O (1)$ ; before(p) $O (n)$ — must walk from the head
add_after(p, e), add_before(p, e)	$O (1)$ — four pointer updates	add_after $O (1)$ ; add_before $O (n)$ — needs the predecessor
replace(p, e), swap(p, q)	$O (1)$ — element fields only	$O (1)$
delete(p)	$O (1)$ — p reveals both neighbors	$O (n)$ — must find the node pointing at p
size(), is_empty()	$O (1)$ — counter	$O (1)$

The table is the payoff of the last three sections in one view: the position abstraction keeps the interface identical, while the cost of each method is decided entirely by the backend's links. That is why the same list ADT runs at different speeds on different implementations — and why the doubly linked list is the standard backend for the position-based list.

4.7.4 Worked Example — Tracing Positions in a List

Walkthrough with real elements. Work through the example exactly as presented. Start with an empty list $L$ :

$L . add_last (8)$ — inserts 8; returns position $P$ . The list holds the element 8 at $P$ .
$L . first ()$ — with a single element, the first position is $P$ . Returns $P$ .
$L . add_after (P, 5)$ — inserts 5 after $P$ ; returns the new position $Q$ . The list is 8 at $P$ , 5 at $Q$ .
$L . before (Q)$ — the position before $Q$ is $P$ . Returns $P$ .
$L . add_before (Q, 3)$ — inserts 3 before $Q$ ; returns a new position $R$ . The list is 8 at $P$ , 3 at $R$ , 5 at $Q$ .
$R . element ()$ — returns 3, the element stored at $R$ .
$L . after (P)$ — the position after $P$ is $R$ . Returns $R$ .
$L . before (P)$ — there is nothing before $P$ , so none (null) is returned.
$L . add_first (9)$ — inserts 9 at the front; returns a new position $S$ . The list is 9 at $S$ , 8 at $P$ , 3 at $R$ , 5 at $Q$ .
$L . delete (L . last ())$ — the last position is $Q$ (holding 5); delete it, and the delete returns the element removed, 5.
$L . replace (P, 7)$ — the element at position $P$ is replaced with 7. Position $P$ itself is unchanged.

At every step, the caller works only with positions — never with nodes — and every operation runs in $O (1)$ time, exactly as in the doubly linked list implementation underneath. "Just get used to that position concept. That's it. You can do your ADT doubly linked list implementation." Sense-check: the final list is 9 at $S$ , 7 at $P$ , 3 at $R$ — three elements, and the two mutating steps (delete and replace) never changed any position's identity, only what the list holds.

4.7.5 Student Questions and Answers

Q: Does the position change when we replace or swap the element stored at it? A: No. The position is a place of an element relative to others in the list. Even if we replace or swap the element stored at P, the position P does not change — only $p . element ()$ returns the new value. The position is defined relative to the other positions, not by the value it holds.

4.7.6 Pitfalls, Recap, and Real-World Connections

Pitfalls.

Treating a position as an index. Positions have no numbers; "position 3" is meaningless. Navigation is relative — before(p), after(p) — and always takes $O (1)$ on a doubly linked backend.
Holding a position after deletion. Delete invalidates the position; using it afterwards is an error. This is the one operation that destroys a position's identity.
Mixing positions across lists. A position belongs to exactly one list; passing a position of list $A$ into an operation of list $B$ is invalid.
Forgetting the cost contract. The position ADT inherits the backend's costs: on a doubly linked list every position operation is $O (1)$ ; on a singly linked list, before(p) and add_before would pay $O (n)$ .

Recap + Bridge. The position ADT wraps the node so users manipulate places, not pointers: the list ADT's methods — first, last, before, after, add_before, add_after, replace, swap, delete — all take and return positions, all $O (1)$ on the doubly linked backend. With that, the linked-list family is complete; the final structure of this session returns to the array side of the world: the vector, whose "index" concept is called a rank.

Real-world: position-based lists are how text editors model the document — the cursor is a position, and every edit (insert text at the cursor, delete the selection) is a position operation, which is why the word-processor analogy is the standard motivation in the textbooks. Richer editors extend the same idea to numbered bookmarks that survive edits: a bookmark is a position object that stays valid while its character stays in the document.

4.8 Vector

4.8.1 Rank and the Definition of a Vector

Hook. Every position-based method from the last section works without numbers — but sometimes you want a number: "give me the $k$ -th element." The vector is the structure that says "yes" — each element answers to an integer called its rank, and the lookup is instant.

The vector is not exactly in the syllabus, but it is worth understanding quickly because it is needed later when algorithms are discussed. The question "what is a vector, and what is the difference between a vector and an array?" gets several answers in class — a vector is dynamic, a vector can be resized, a vector has direction (that part is just its size; the physics meaning is not what matters here), it is a legacy class in Java — and the settled description is this:

In a vector, each element is referred to using an integer from 0 to $n - 1$ , where the integer is the number of elements of the list that precede that element. That number is called the rank of the element — the rank is used as an index. The first element has rank 0 because no elements precede it; the second has rank 1 because one element precedes it; the third has rank 2; the last element has rank $n - 1$ .

$rank (e) = number of elements preceding e in the sequence$

A linear sequence that supports access to its elements by their rank is called a vector. The storage underneath is an array (static or dynamic) — a vector is an abstraction over array storage.

Intuition — the numbered row. Picture a row of numbered lockers: locker 0, locker 1, locker 2, ... The vector is the abstraction "the element whose rank is $k$ lives in the $k$ -th position of the row" — the rank is the index, and the underlying array just happens to be the row. The physics "vector" (an arrow with direction and length) is a different meaning of the same word: the class discussion noted it, but in this course a vector is only the rank-addressed sequence. Where the analogy breaks: an array is the storage; a vector is the access contract on top of the storage — the storage can be a static array or a dynamic one, and swapping the storage does not change the vector's behavior.

4.8.2 Worked Example — Ranks Change When the Sequence Is Updated

Trace with real numbers. The rank of an element changes whenever the sequence is updated — on both insertion and deletion. Consider the vector [2, 4, 6, 8, 10]:

The rank of 6 is 2 — two elements, 2 and 4, precede it.
Insert 12 at the beginning: the vector becomes [12, 2, 4, 6, 8, 10], the size increases, and the rank of 6 is now 3 — three elements, 12, 2 and 4, precede it.

Every rank after the insertion point shifts by one. Deleting an element shifts ranks the other way. The ranks of the elements are not stable properties of the elements; they are properties of the current sequence. Sense-check: after the insert, the old element at rank $k$ sits at rank $k + 1$ for every element that came after the insertion point — exactly one shift per element, which is why insertions at the front cost linear time in the next subsection.

4.8.3 Time Complexities of Vector Operations

element_at_rank(r) — $O (1)$ . The rank is used as an index, so element at rank 2 is just $V [2]$ — a direct array access, like an array with a slightly different concept behind the index.
replace_at_rank(r, o) — $O (1)$ . Replace the element at rank r with the new one; a single write to $V [r]$ .
insert_at_rank(r, o) — $O (n)$ . To insert 7 at rank 2 in the vector, 7 goes to position 2, and every element from rank 2 onward — 6, 9, 10 — must be moved down one location to make room. Adjusting all the elements after the insertion point is a linear-time operation. The same happens in an array when we insert at a random position; sequential ordering is the cause.
remove_at_rank(r) — $O (n)$ . To remove 7, every element after it must be adjusted back one location. Removal is also an $O (n)$ operation, for the same sequential-ordering reason.

Worked trace — remove at a rank in the middle. Take the vector [12, 2, 4, 6, 8, 10] and remove the element at rank 3 (the 6):

Save the element: $e = V [3] = 6$ .
Shift every element at rank 4 and beyond left by one: $V [3] \leftarrow V [4] = 8$ , $V [4] \leftarrow V [5] = 10$ .
The vector now holds [12, 2, 4, 8, 10] with size 5, and the operation returns 6.

Two elements moved, out of five — and in general, a removal at rank $r$ moves $n - r - 1$ elements, which is $n$ in the worst case (rank 0) and 0 at the very end (rank $n - 1$ ). Insert at rank works the same way in reverse: every element at rank $r$ and above shifts right first, then the new element is written into the vacated cell. Sense-check: the rule "element of rank $i$ lives at index $i$ " forces exactly these shifts — that is the whole reason insert and remove cost $O (n)$ .

Scope — where the asymmetry comes from. The cost is not magic; it follows from the rule that "the element of rank $i$ lives at index $i$ ." Reading and replacing touch one cell — $O (1)$ . Inserting or removing must preserve the rule, so every element after the point of change shifts by one cell — $O (n)$ worst case, and $O (n)$ on average even if ranks are chosen uniformly, because on average half the elements must move. The end of the vector is the exception: insert at rank $n$ and remove at rank $n - 1$ shift nothing and run in $O (1)$ . A circular-array trick can make rank-0 updates $O (1)$ too, but it gives up the simple "rank $i$ at index $i$ " picture.

4.8.4 Vector Memory and the Vector-Array Distinction

The vector stores its elements like an array — in continuous blocks, in contiguous memory allocation. If the vector's storage becomes full, a new memory block is allocated dynamically. But the vector ADT is an abstraction: do not confuse the concept with the actual implementation and memory allocation. Like an array, the storage may be a static array or a dynamic array; the vector is the rank-accessed abstraction on top of it.

Real-world: the dynamic-array behavior behind vectors is the standard growth strategy in many languages' built-in sequence types, which is why appends stay cheap on average.

4.8.5 Student Questions and Answers

Q: What do you know about a vector? Is it dynamic, resizable, like an array, or with a direction? A: A vector is dynamic and can be resized, and we store the elements exactly like we store them in an array. The direction idea is just its size; it is not what matters. In a vector each element is referred to using an integer — its rank — which is the number of elements that precede it in the sequence.

Q: Why is insert at a rank big O of n, while element at rank and replace are big O of 1? A: Element at rank and replace at rank are direct reads and writes at an index — constant time. Insert at rank must keep the sequential ordering: every element after the insertion point has to be moved down one location to make room, so the work grows with the size of the vector. Remove at rank has the same reason — everything after the removed element shifts back.

4.8.6 Pitfalls, Recap, and Real-World Connections

Pitfalls.

Reading "vector" as the physics arrow. In this course a vector is the rank-addressed sequence; the direction-and-length meaning is a different word that happens to share the name.
Forgetting that ranks are not stable. An element's rank is a property of the current sequence; after any insert or delete, later ranks all shift. Code that caches a rank and reuses it after an update silently reads the wrong element.
Quoting $O (1)$ for insert at rank. Only reads and writes are constant; insert and remove are $O (n)$ because every following element must move to keep the sequential ordering.
Confusing the vector with its storage. The vector is the abstraction; the array (static or dynamic) is the implementation. Dynamic growth changes the storage, not the concept.

Recap + Bridge. The vector is the rank-addressed linear sequence over array storage: element_at_rank and replace are $O (1)$ , insert and remove are $O (n)$ , and ranks shift with every update. This closes the session's structure family — stack, queue, list, position list, vector — and hands the course its toolbox for the algorithms half. Next session begins the trees, the first non-linear data structures.

Real-world: the vector is the everyday workhorse of modern programming — the default dynamic sequence type in many languages (the textbook's "extendable table" and its Java counterpart), used wherever elements must be fetched by position quickly and appended cheaply. Spreadsheets, image row buffers, and adjacency lists for dense graphs all lean on rank-addressed storage; the doubling growth rule from the stack section is exactly what keeps their appends amortized $O (1)$ .

Exam Guidance Summary

Master theorem: expect at least one question on the master theorem. Know when it applies — only for recurrences of the divide-and-conquer shape $T (n) = a T (n / b) + f (n)$ — and how to interpret the terms through the recursion tree: $a$ children per node, subproblems of size $n / b$ , cost $f (n)$ per node. If it does not apply, know the fallbacks: solve the recurrence directly, use the substitution method, or draw the recursion tree.
Substitution method: not covered in class, but do not skip it — read it from the textbook. Expect to be able to explain the two steps (guess the solution, then prove it by solving the recurrence with induction) and to use it to verify a guessed answer.
Quiz practice: practice more questions before attempting; the difficulty concerns were addressed directly — more practice is the remedy.
Stack and queue: be able to write and justify the $O (1)$ complexities of every stack and queue operation in the array implementations, including the wrap-around circular queue with its $n - 1$ element constraint and the size formula $(n - f + r) mod n$ . The top-versus-pop distinction and the constant-time meaning of big-O of 1 are classic conceptual questions. Also be ready to trace the two-stack queue and state which operation pays $O (n)$ .
Linked lists: be ready to trace pointer adjustments in singly and doubly linked lists, and to justify each row of the complexity table, with the assumptions (head pointer, tail pointer, node given) stated explicitly. Know why insert-before and remove are $O (n)$ in a singly linked list and $O (1)$ in a doubly linked list, and that remove is $O (n)$ , not $O (n^{3})$ .
Position ADT: work through the position walkthrough — add_last, first, add_after, before, add_before, after, add_first, delete, replace — and understand that positions are abstractions of nodes, with all operations $O (1)$ on the doubly linked list backend.
Vector: vectors are touched only briefly and are not exactly in the syllabus, but the concept (rank-based access, ranks shifting on update, $O (1)$ element-at-rank/replace, $O (n)$ insert/remove at rank) will be needed for the algorithms half of the course. Sequences and iterators are also not in the syllabus, but read them from the textbook.
Stock span problem: assigned as homework; solve it with a stack in $O (n)$ time and post the solution. It is a very popular problem — a strong candidate for interview-style questions.
Assignment: an individual assignment to implement a data structure and an algorithm, in Python — Java is under consideration, and at most two languages (Python and Java) will be allowed. It runs roughly from September 10 to October 30, giving about one month. Submission can be a notebook from your local machine; there is no requirement to use a specific platform. Go through the Python implementation in the textbook in advance, since the assignment expects you to implement what has been taught.
Course structure: the first half of the course covers data structures in detail, the second half covers algorithms in detail — the current topics sit in the first half, and trees begin in the next session.

Key Industry Applications

Web browsers: the address history of recently visited sites is stored on a stack of addresses; visiting a site pushes its address, and the back button pops back to the previous site.
Undo operations: nearly every application implements undo with a stack of previous states — the most recent action is pushed, undo pops it.
Procedure calls: function calls and returns use the system stack — the call stack every debugger shows you. Each call pushes a frame holding the return address, parameters, and local variables; each return pops it.
Reversing a word: push the characters of a word onto a stack, then pop them all to get the reversed word — the simplest demonstration of LIFO.
Stock span problem: a financial charting classic; the "consecutive days with price less than or equal to today" computation is the previous-greater-element pattern, solved in $O (n)$ with a stack. Searching online for "stock span problem" returns the solution directly.
Multi-programming: operating systems keep waiting processes in queues; the round-robin scheduler dequeues a thread for its time slice and re-enqueues it at the rear. The ticket-counter queue is the everyday picture of FIFO — first in line, first served.
Printers and message lines: anything that must preserve arrival order — print jobs, chat messages, network packets — is naturally a queue.
Lift (elevator) passengers: the first person in is ideally the last person out — a stack in real life (the professor's contrast with the queue).
Plates dispensers in hotels: the origin of the stack's name — plates stacked, with the first plate placed in coming out last.
Word processors: the cursor is an everyday ADT — an abstraction of the index position of a character, letting us edit without naming line and character numbers; the position ADT of the list is the same idea.
Dynamic arrays in language runtimes: growing storage by doubling (about a 0.75 load factor before reallocation) is the standard trick that keeps push operations fast on average — the dynamic-array fix for the stack's fixed size.
Non-contiguous storage: linked lists can scatter nodes anywhere in memory — pointers, not contiguous blocks, hold the list together; doubly linked lists back browser history navigation and LRU caches.
Textbook implementations: Data Structures and Algorithms in Python by Goodrich (the main textbook) and Data Structures and Algorithms in Java by Goodrich and Tamassia both implement every structure from this session — push, pop, the linked lists, the position-based list — with many application exercises, and the code can be copied and run in a notebook to check understanding.

DSA Lecture 4 notes · Abstract Data Types: Stacks, Queues, Lists, and Vectors

Data Structures and Algorithms· postgraduate· 2026-08-09

Sections Breakdown

14.1 Recap — Master Theorem Applicability and the Substitution Method

Reading the master theorem from the recursion tree: when it applies, why unequal splits break it, and the substitution method's guess-then-prove recipe.

24.2 Abstract Data Types

The definition ladder from type to data type to abstract data type, the word-processor cursor motivation, and the linear ADTs covered in the course.

34.3 Stack

The LIFO stack ADT, its array implementation with top index t, the O(1) operations, the dynamic-array doubling fix, applications, and the stock span problem.

44.4 Queue

The FIFO queue ADT, the circular-array wrap-around with its n-1 capacity rule and size formula, O(1) operations, applications, and the two-stack construction.

54.5 Singly Linked List

Nodes, head and tail pointers, and traversal: operations at or after a given node are O(1), operations needing the predecessor cost O(n).

64.6 Doubly Linked List

The doubly linked list with header and trailer sentinels: four pointer updates make every node-based operation O(1).

74.7 The Position ADT and the List ADT

Why raw nodes are unsafe, the position ADT with its element() operation, and the position-based list ADT methods on a doubly linked backend.

84.8 Vector

The vector as a rank-accessed linear sequence: ranks shift on every update, element_at_rank and replace are O(1), insert and remove are O(n).

9Exam Guidance Summary

The professor's exam-facing guidance: master theorem questions, O(1) justifications, complexity-table assumptions, the position walkthrough, the stock span homework, and the assignment.

10Key Industry Applications

Where the session's structures appear in the real world: browser back and undo, call stacks, schedulers and print spoolers, word-processor cursors, and dynamic arrays.

Postgraduate students studying data structures and algorithm analysis

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Recap — Master Theorem Applicability and the Substitution Method

Must-know: The master theorem applies only to T(n) = aT(n/b) + f(n) with equal subproblem sizes; the recursion tree has height log_b n, a^j nodes at depth j, and leaf work n^{log_b a}; when the shape fails, solve directly, use substitution (guess then prove by induction), or sum the recursion tree by hand.

$T (n) = a T (\frac{n}{b}) + f (n)$

Top pitfall: Applying the theorem to unequal splits such as T(n/3) + T(2n/3), or to f(n) only a logarithmic factor away from the critical value (the gap between cases).

Self-check: Why does T(n) = T(n/3) + T(2n/3) + cn fall outside the master theorem?

Abstract Data Types

Must-know: An ADT is a logical description of values plus operations, independent of implementation; a data type in the strict sense is an implemented ADT.

Top pitfall: Confusing the ADT (logical description) with a data type (an actual implementation); assuming linear means constant-time random access.

Self-check: Why is the cursor in a word processor an ADT in miniature?

Connects to: 4.7

Stack

Must-know: Array-based stack: t is the index of the top element, initialized to -1; push checks t = n-1 (equivalently size = n) then t += 1, S[t] = O; pop decrements t and returns S[t+1]; size = t + 1; is_empty checks t = -1; all operations are O(1).

$push (O) : if t = n - 1 then error; else t \leftarrow t + 1; S [t] \leftarrow O$

Top pitfall: Confusing t as the next empty location instead of the top element; constant time does not mean exactly one unit of time.

Self-check: After push A, push B, push C, top(), pop(): what is t and what is the top element?

Connects to: 4.4, 4.5

Queue

Must-know: Circular-array queue: f = r means empty; hold at most n-1 objects; r = (r+1) mod n on enqueue, f = (f+1) mod n on dequeue; size = (n - f + r) mod n; all methods O(1). Two-stack queue: exactly one operation pays O(n).

$size = (n - f + r) mod n$

Top pitfall: Forgetting the modulo wrap; forgetting why the queue holds at most n-1 objects (to distinguish full from empty when f = r).

Self-check: In a circular array with n = 8, f = 6, r = 2, how many elements are in the queue?

Connects to: 4.3, 4.5

Singly Linked List

Must-know: Node-based singly linked list: first/after/insert_after are O(1) given the node and head pointer; last/insert_last are O(1) only with an explicit tail pointer; before/insert_before/remove are O(n) because the predecessor requires a traversal; remove is O(n), not O(n^3).

Top pitfall: Quoting O(1) for after without the 'node is given' assumption; confusing the step number 3 in the diagram with an exponent.

Self-check: In the list A -> B -> C, why is insert after B O(1) but insert before B O(n)?

Connects to: 4.6, 4.7

Doubly Linked List

Must-know: Doubly linked node holds element + prev + next; insert/remove between two given nodes is four pointer adjustments (or five lines for add-after) and O(1); remove_last uses the trailer: w = trailer.prev, v = w.prev, trailer.prev = v, v.next = trailer.

Top pitfall: Updating only two pointers during an insert; handing raw nodes to users (pointer corruption is why the position ADT exists).

Self-check: To remove node Z in a doubly linked list, where do V and W come from?

Connects to: 4.5, 4.7

The Position ADT and the List ADT

Must-know: A position is a place of an element relative to others; it supports only element(); it does not change when its element is replaced or swapped, only when the element is deleted; the list ADT methods first/last/before/after/add_before/add_after/replace/swap/delete are all O(1) on a doubly linked list.

$p . element () returns the element stored at position p$

Top pitfall: Treating a position as an index number, or reusing a position after its element has been deleted.

Self-check: After L.replace(P, 7) in the walkthrough, does position P change?

Connects to: 4.6, 4.8

Vector

Must-know: Rank of an element = number of elements preceding it (first has rank 0, last has rank n-1); a vector is a rank-accessed linear sequence over array storage; element_at_rank and replace_at_rank are O(1), insert_at_rank and remove_at_rank are O(n) because of sequential ordering; ranks shift on every update.

$rank (e) = number of elements preceding e in the sequence$

Top pitfall: Confusing the vector concept with its storage, or assuming ranks are stable properties of elements — they shift with every insert and delete.

Self-check: Insert 12 at the front of [2, 4, 6, 8, 10]: what is the new rank of 6?

Connects to: 4.5, 4.7

Exam Guidance Summary

Must-know: At least one master theorem question is expected; be ready to justify every O(1) stack/queue operation and every row of the linked list complexity tables with its assumptions.

$T (n) = a T (n / b) + f (n)$

Top pitfall: Assuming the master theorem applies to unequal splits or to f(n) in the gap between cases; forgetting assumptions in complexity justifications.

Self-check: Which three fallbacks remain when the master theorem does not apply?

Key Industry Applications

Must-know: Undo, browser back, and the call stack are stacks; process scheduling, printers, and message lines are queues; the cursor is the everyday position abstraction.

Self-check: Why is the browser back button a stack rather than a queue?

Previous LectureLecture 03 · Analyzing Recursive Algorithms

Next LectureLecture 05 · Trees and Heaps

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.