Introduction to Data Structures & Algorithms

COMS1017A & COMS1021A

Dr Richard Klein

Semester 2, 2021[Updated: 2021-10-26]

2
Contents

Course Outline 7

1 Data Structures & Algorithms 13

1.1 Analysis of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Best, Worst or Average? . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 When do we actually care? . . . . . . . . . . . . . . . . . . . . . 15
1.4 What are we ignoring? . . . . . . . . . . . . . . . . . . . . . . . . 18
1.5 Abstract Data Types . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.7 TODO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2 C++ Fundamentals 21
2.1 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Setting up your environment . . . . . . . . . . . . . . . . . . . . 25

3 Arrays & Vectors 27

3.1 Abstract Data Type: Lists . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Memory Management . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Contiguous Memory & Pointer Arithmetic . . . . . . . . . . . . . 29
3.4 Increasing the size of an array . . . . . . . . . . . . . . . . . . . . 30
3.5 std::array and std::vector . . . . . . . . . . . . . . . . . . . . 32
3.6 Reallocation & Complexity . . . . . . . . . . . . . . . . . . . . . 34
3.7 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.8 Additional Reading . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4 Linked Lists 39
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 When arrays aren’t good enough . . . . . . . . . . . . . . . . . . 40
4.3 Linked Lists – forward_list . . . . . . . . . . . . . . . . . . . . 42
4.4 Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.5 Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3
4 CONTENTS

4.6 Doubly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.7 Other Linked List Structures . . . . . . . . . . . . . . . . . . . . 52
4.8 Drawbacks of Linked Structures . . . . . . . . . . . . . . . . . . . 53
4.9 Lab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.10 Additional Reading . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5 Stacks 57
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2 Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.3 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.4 std::stack<T, C> . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.6 Lab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.7 Project: Solving Sudokus . . . . . . . . . . . . . . . . . . . . . . 64
5.8 Additional Reading . . . . . . . . . . . . . . . . . . . . . . . . . . 64

6 Queues 65
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.2 Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.3 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.4 std::queue<T, C> . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.5 Project – The Shortest Path in a Maze (BFS) . . . . . . . . . . . 68
6.6 Additional Reading . . . . . . . . . . . . . . . . . . . . . . . . . . 74

7 Binary Search Trees 75

7.1 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.2 Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
7.3 Binary Search Tree . . . . . . . . . . . . . . . . . . . . . . . . . . 77
7.4 Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
7.5 Lab: Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . 80
7.6 Additional Reading . . . . . . . . . . . . . . . . . . . . . . . . . . 85

8 Balanced Trees 87
8.1 AVL Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

9 Binary Heaps 89
9.1 Lab: Binary Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . 89

10 Sorting 93
5
6 CONTENTS
Course Outline

https://www.youtube.com/watch?v=kcaMqEbhAcg

Lecturer
Lecturer: Dr Richard Klein
Office: UG12, TWK Mathematical Sciences Building
Email: richard.klein@wits.ac.za

COVID-19
Due to COVID-19, this course will be presented entirely online. This online book
will be updated regularly with new text, videos, and other resources. There will
be several quizzes (usually weekly). There will also be labs and projects. These
will be made available via Moodle and all submissions should be done on Moodle.
I believe that a very important aspect of learning is interacting with
peers/tutors/lecturers. Keeping this social element alive during online teaching
is difficult, but I encourage you to interact regularly on Discord and Moodle.
Academic integrity is of absolute importance. Communication during quizzes,
sharing of answers or practicals, and all forms of plagiarism are taken very
seriously by the university and will result in failing the course (FCM) and/or
being reported to the legal office. In most cases, I encourage you to help each
other with problems but be aware of the line between helping someone and
giving them the answer. A good rule of thumb: if I am struggling, I can show
someone a section of my code for assistance, but I cannot look at theirs. We
will be monitoring Moodle logs closely and will be checking all submissions for
plagiarism.

Timetable
In the timetable, there is a double lecture and triple lab for IDSA each week:
• Tuesday: 10:15-12:00

7
8 CONTENTS

• Thursday: 14:15-17:00

However, the vast majority of this course will be presented in an asynchronous

manner. Prerecorded videos, readings and demos will be the most common
mode of teaching in this course. The only synchronous aspect of the course will
be the weekly tutorial sessions which will take place via Discord.

You will be assigned a tut group and each week you must meet your tutor for
a live audio/video call. The tutors will be able to answer any theory/practical
questions that you may have during this session. These tutorial sessions are
compulsory and will contribute to Satisfactory Performance. They will take
place on Thursday afternoons during the lab session.

Learning Management System

We will use Moodle for this course. Please go to https://courses.ms.wits.ac.za/
moodle/course/view.php?id=184. Log in with your student number and usual
Wits password. You should already be enrolled in the course.

We will not use Ulwazi in this course at all.

Communication
All official communication will be posted to the announcements forum on
Moodle. Moodle will email these announcements, but it is still your responsi-
bility to ensure that you’re receiving these announcements.

For live chat, please use the discord server which you can subscribe to here:
https://discord.gg/yWRjJmgsGa. I suggest that you use the discord server
in place of student WhatsApp groups which are There are desktop, web and
mobile apps available for the various platforms. The tutors and I will be online
as often as possible.

Just as in COMS1018A (IAP), there is a request-help channel. If you have a

question that needs help specifically from a tutor, or if you need someone to look
at code then please create a ticket there. You should then post your question in
the private support channel discord makes for you. Once the question has been
answered, then you can close the ticket. Only you and the tutors will be able
to see your question, so you are free to post your code there.

In general, please try to use public channels to speak with me and the tutors
unless it is about code that you shouldn’t be posting publicly - it is useful for
others to be able to see the answers to your questions. Please do not email
general questions to me unless it only relates to you personally or is sensitive in
some way. I am always happy to help where I can, but avoiding duplication is
important in large classes like this one. I will always respond to discord queries
before emails.
CONTENTS 9

Consultations
Due to the number of students in this course, it is really important to book time
with me if you would like a live one-on-one consultation. You can book time
slots directly into my calendar using https://calendly.com/kleinric/idsa. You
can book up to 7 days in advance and calendly will send you a calendar invite
with a Google Meet or Teams link in it. Please, test that your chosen platform
is working before the meeting. You can invite others to the meeting as well if
your friends have similar questions.
If you have bandwidth or data issues, you can tell Google Meet not to receive
video. If you don’t have any of these issues, feel free to keep your video on, it’s
nice to chat face-to-face and still get to see you, even if we’re not on campus!

Textbook
The structures presented in this course are fairly common and you will find many
resources that cover this content online. I try to avoid prescribing a textbook
for this course because of the associated costs. However, if you can buy a book
or are funded, then I strongly recommend trying to get a copy of:
• Mark Allen Weiss, Data Structures and Algorithm Analysis in
C++ (Fourth Edition), Pearson, 2014 (Weiss, 2014)
I also recommend the following books:
• M Goodrich, R Tamassia, D Mount, Data Structures & Algo-
rithms (Second Edition), Wiley & Sons, 2011 (Goodrich et al.,
2011)
• N Dale, C Weems, T Richards, C++ Plus Data Structures (Sixth Edition),
Jones & Bartlett Learning, 2018 (Dale et al., 2018)
The best, most comprehensive book about algorithm analysis is Cormen et al.
(2009) and is prescribed by almost every major Computer Science course worth
attending. This book is advanced and covered every major algorithm. It is also
prescribed in honours, so might be worth getting if you are planning to stick
around:
• TH Cormen, CE Leiserson, RL Rivest, and C Stein. Introduc-
tion to Algorithms. MIT press. 2009. (Cormen et al., 2009)
For a book on introductory programming in C++ see:
• Bjarne Stroustrup, Programming – Principles and Practice Using C++
(2nd Edition), Addison-Wesley, 2014 (Stroustrup, 2014)

Other Resources
Where relevant I will post links to other resources as well. I encourage you
to use Google, StackOverflow and YouTube generally. More specifically MIT
10 CONTENTS

OpenCourseware: Intro to Algorithms, GeeksForGeeks: Data Structures and

GeeksForGeeks: Fundamentals of Algorithms have particularly strong content
on Data Structures and Algorithms.
For general C++ assistance these are worth checking out as well:
• Geeks for Geeks: C++
• MIT OpenCourseware - Intro to C++
• learncpp.com
If you find any other good resources, please share these resources with others in
the class as well using the forums.

Grading
The entire course will take place online. There will be no in-person assessments
in 2021. The mark breakdown is as follows:

Item Weight
Participation* 4%
Projects 20%
Labs 13%
Quizzes 13%
Exam (Lab) 25%
Exam (Written) 25%

*Constructive participation includes asking and answering questions on the Moo-

dle forums/Q&As, sharing resources, and participating in relevant discussions.
These grading schemes are subject to change based on the evolution of the
COVID-19 pandemic, lockdown and input from moderators.

Tentative Schedule
Block 3

Week Topics
1 C++ Revision: abstraction, functions, recursion, static/dynamic memory allocation, pointers an
2 Classes
3 Arrays & Vectors
4 Linked Lists
5 Linked Lists
6 Stacks & Queues
7 Stacks & Queues
CONTENTS 11

Block 4

Week Topics
1 Complexity Analysis
2 Binary Search Trees
3 Balanced Trees (AVL Trees)
4 Priority Queues & Binary Heaps
5 Sorting Algorithms (Bubble, Insertion, Selection, AVL and Heap Sorts)
6 Sorting Algorithms (Mergesort & Quicksort)

Satisfactory Performance
This outline extends the general undergraduate computer science course out-
line. At least 80% of labs and quizzes must be completed. There are both lab
and theory components to this course, you must achieve at least 35% for both
components to pass the course, regardless of your average.
12 CONTENTS
Chapter 1

Data Structures &

Algorithms

1.1 Analysis of Algorithms

In your previous algorithms course, the focus was on programming and problem
solving only. We cared about whether we could get the right answer but did
not consider the quality of the algorithm. Suppose now that you have two
algorithms that both return the correct answer. How do you compare them?
How do you decide which algorithm is better and when?
This is the idea of Algorithm Analysis, which aims to understand the resource
requirements of an algorithm, measured in both time (algorithm runtime)
and space (memory requirements). Computational Complexity theory then
extends these ideas beyond a specific solution and focuses on all possible
algorithms/solutions that could exist. For example, we know that to sort a
list of 𝑛 numbers by comparing their values an algorithm will need to make at
least of the order 𝑛𝑙𝑜𝑔(𝑛) comparisons on average, and in Honours, you will be
able to prove this! This is one of the reasons you need all the different proof
techniques from DCS - to prove an algorithm is correct, to prove its complexity,
and to prove that it is or is not optimal.
When considering the computational complexity of an algorithm, we think about
two things:
1. How much time it takes to complete.
2. How much memory it needs to complete.
Let’s say that the size of the input is 𝑛, then we need to count the number of
operations that the algorithm performs and try to come up with a function in
terms of 𝑛… for example 𝑓(𝑛) = 43𝑛2 + 3𝑛 + 42. In a case like this, we would say

13
14 CHAPTER 1. DATA STRUCTURES & ALGORITHMS

that the runtime is quadratic because the function that describes it is quadratic
in the size of the input. So the time complexity is quadratic.
In the second case, we would try to do the same thing, but rather than modelling
the runtime, we would need to model the amount of RAM that is needed for
the algorithm to finish. For example, if an algorithm requires 𝑔(𝑛) = 42𝑛 + 3
bytes of memory, then we would say that the memory requirements are linear
because as the size of the input grows, the amount of memory we need grows
linearly. The space complexity is linear.
https://www.youtube.com/watch?v=b_Tr25QDnpY

1.2 Best, Worst or Average?

In the examples from above, the code always took the same amount of time
to run for a specific sized input. But we know that sometimes algorithms will
perform differently in different cases – even if the size of the input is the
same. For example, how many times do we run the == operation in the code
below?
def search(mylist, searchValue):
for v in mylist:
if v == searchValue:
return True
return False

Well… it depends on the values given to the algorithm. If the input list is
[1, 2, 3, 4, 5, 6, 7, 8, 9] and the search value is 42, then we will do 𝑛 comparisons
(where 𝑛 is the length of the list). This is called the worst-case because it
causes us to do the most work for inputs of size 𝑛. On the other hand, if the
search value was 1 when we would only do a single comparison and then the
function would return. This is called the best-case because it causes us to do
the least work for inputs of size 𝑛.
We can also consider something called the average case. Here, we use the
statistical definition of expectation and we calculate the total amount of work
we expect to do by weighting it by the probability of us actually having to
do that amount of work. For example, a QuickSort might make 𝑎𝑛2 + 𝑏𝑛 + 𝑐
comparisons to sort a list in the worst case, but if we look really carefully, this
can only actually happen in one or two of the 𝑛! permutations of the list. So
even though the worst case is quadratic, it is so rare that the average case is still
really really good! We will look at QuickSort in detail later on in this course.
We leave average case analysis to second and third years, and we will only focus
on the best and worst-case analysis of the algorithms considered in this course.
Note: The best and worst cases have NOTHING to do with the size
of the input, only the configuration. An input of length 0 is NOT
1.3. WHEN DO WE ACTUALLY CARE? 15

the best case!

1.3 When do we actually care?

1. Sort the following list of numbers: [4, 6, 0, 5]
2. Sort the follow list of numbers: [79, 206, 4, 344, 323, 216, 278, 341, 55,
220, 320, 205, 36, 399, 160, 364, 303, 223, 325, 5, 199, 284, 256, 66, 65, 27,
203, 16, 301, 336, 138, 315, 76, 68, 103, 282, 202, 300, 167, 39, 46, 124,
197, 34, 141, 97, 270, 236, 342, 299, 84, 15, 77, 170, 334, 275, 250, 207,
135, 338, 390, 244, 252, 215, 266, 93, 384, 251, 296, 355, 335, 81, 31, 332,
373, 64, 98, 305, 107, 110, 23, 243, 351, 234, 378, 41, 184, 118, 277, 286,
306, 294, 186, 7, 123, 173, 192, 152, 11, 183, 87, 86, 137, 357, 26, 74, 175,
231, 20, 317, 18, 263, 392, 122, 185, 78, 106, 228, 80, 67, 24, 318, 394, 181,
254, 398, 279, 151, 159, 248, 326, 145, 247, 174, 91, 101, 13, 130, 125, 385,
90, 131, 289, 71, 308, 89, 349, 237, 72, 163, 136, 85, 375, 272, 182, 35, 290,
30, 212, 246, 257, 348, 293, 134, 213, 28, 253, 316, 387, 264, 133, 63, 120,
230, 142, 393, 32, 302, 214, 119, 258, 171, 319, 369, 95, 157, 57, 298, 400,
132, 102, 139, 140, 367, 259, 113, 117, 224, 304, 333, 208, 331, 368, 17, 380,
164, 324, 379, 179, 195, 14, 51, 33, 121, 274, 180, 108, 235, 295, 191, 200,
150, 340, 269, 345, 376, 116, 313, 262, 187, 61, 114, 267, 83, 194, 126, 177,
155, 281, 9, 388, 147, 261, 99, 82, 395, 209, 172, 53, 94, 366, 42, 374, 347,
178, 40, 280, 193, 44, 245, 372, 165, 88, 268, 54, 363, 352, 310, 115, 211,
127, 226, 128, 389, 287, 391, 276, 377, 383, 59, 129, 217, 353, 249, 314, 38,
166, 96, 358, 196, 312, 149, 168, 29, 241, 307, 229, 397, 8, 354, 176, 148,
239, 260, 111, 232, 297, 153, 190, 356, 221, 328, 58, 218, 198, 162, 285, 3,
109, 21, 337, 343, 381, 265, 386, 25, 283, 371, 233, 227, 238, 242, 146, 19,
2, 321, 240, 327, 69, 6, 359, 311, 204, 330, 73, 56, 169, 396, 271, 189, 361,
309, 210, 37, 105, 365, 201, 52, 10, 49, 350, 329, 219, 346, 112, 43, 154,
360, 161, 62, 339, 362, 382, 22, 322, 291, 370, 75, 48, 1, 100, 70, 92, 104,
60, 45, 273, 222, 255, 288, 158, 144, 292, 143, 156, 188, 50, 12, 225, 47]
No one cares how long it takes to sort four numbers, even a bad algorithm should
sort that quickly, but as the input size (𝑛) grows we start to care very quickly.
So we prefer to only think about what happens when 𝑛 is very large, or even as
𝑛 → ∞. In this case, we are talking about the Asymptotic Complexity of
the algorithm. When we talk about complexity in this way, we are comparing
the runtime or space requirements of different algorithms when 𝑛 is large enough
to matter.
On top of this, these values only matter if they are general. No one cares if
my T-1000 computer is crazy fast and blows all the other computers away1 . If
your computer really is that fast, then we’d want to be sorting bigger more
complicated lists. So mathematically, 𝑛 tends to infinity, and practically, 𝑛 is
big enough for it to matter on your computer.
1 Ok, they probably do care, but that’s purely about street cred.
16 CHAPTER 1. DATA STRUCTURES & ALGORITHMS

This also means that we shouldn’t get too bogged down in counting every single
thing. Consider this code below:
def pow(x, n):
out = 1.0
i = 0
while i < n:
out = out * x
i = i + 1
return out

Suppose that an assignment takes 𝑎 time units, integer comparison takes 𝑏,

floating point multiplication takes 𝑐 time units, integer addition takes 𝑑 time
units. Then we end up with the following analysis:
def pow(x, n):
out = 1.0 # a
i = 0 # a
while i < n: # b * (n+1)
out = out * x # (a+c) * n
i = i + 1 # (a+d) * n
return out

So in the first two lines we assign values to out and i, after that our loop runs.
We do 𝑛 comparisons where we enter the loop and on comparison 𝑛 + 1, 𝑖 ≮ 𝑛
and the loop stops. In side the loop, we perform the calculation and then assign
it to the variable. This happens each of the 𝑛 times that we enter the loop. So
in total:
𝑡𝑖𝑚𝑒 = 2𝑎 + 𝑏(𝑛 + 1) + (𝑎 + 𝑐)𝑛 + (𝑎 + 𝑑)𝑛 (1.1)
= 2𝑎 + 𝑏𝑛 + 𝑏 + 𝑎𝑛 + 𝑐𝑛 + 𝑎𝑛 + 𝑑𝑛 (1.2)
= (𝑏 + 2𝑎 + 𝑐 + 𝑑)𝑛 + (2𝑎 + 𝑏) (1.3)
= 𝑒𝑛 + 𝑓, (1.4)
where 𝑒 and 𝑓 are some constants that are very specific to my hardware and
operating system and are not useful to anyone else. Ever. The important
thing here is that this is a linear function and that it will be linear on every
machine, everywhere, forever. So we try to pick a dominant operation and count
how many times it is performed. We’ll see that this is usually a comparison,
assignment or pointer operation.
So when we do this type of analysis, we want to compare the shape of the graphs
and ignore the constants that are specific to my machine. We are simply asking:
as 𝑛 becomes very very large, how do the runtime and memory requirements
of the algorithm grow? We like to think of the complexity belonging to a class
such as constant, linear, quadratic, cubic, logarithmic, exponential, linearithmic,
factorial etc.
We write these as:
1.3. WHEN DO WE ACTUALLY CARE? 17

Class Notation
Constant 𝑂(1)
Linear 𝑂(𝑛)
Quadratic 𝑂(𝑛2 )
Cubic 𝑂(𝑛3 )
Logarithmic 𝑂(𝑙𝑜𝑔(𝑛))
Exponential 𝑂(2𝑛 )
Linearithmic 𝑂(𝑛𝑙𝑜𝑔(𝑛))
Factorial 𝑂(𝑛!)

This is called Big-Oh notation. If 𝑓(𝑛) ∈ 𝑂(𝑔(𝑛)) this means that 𝑔 multiplied
by a constant is an upper bound of 𝑓, when 𝑛 is big enough. Don’t panic. We
will look at the maths formally later on once you have done a bit more work
in DCS. For now just remember: if we say that an algorithm takes 𝑂(𝑛) time,
then the runtime is bounded above by a linear function.

We also have Big-Ω (Big Omega), which means it is bounded below: if we say
the algorithm takes Ω(𝑛) time, then the runtime is bounded below by a linear
function. This means we do at least a linear amount of work. Finally, we have
Big-Θ (Big Theta), which means that it is bounded above and below. So Θ(𝑛)
is exactly linear function.

Don’t panic about these definitions yet. We’ll look at them carefully later on
and we’ll talk about the maths when we need it. For now, we will only think
about Big-Oh.

In the pow function above, we saw that the amount of work that we did (number
of operations) is a linear function of the size of the input, 𝑛. We can write this
in Big-Oh notation as 𝑂(𝑛).

In the search function above, we had a best and a worst-case. In the best case,
the number we’re looking for is at the front. So in the best case, we only ever
do 1 comparison. This means that regardless of how big 𝑛 is, we always do
a constant amount of work. So in the best case, search takes 𝑂(1) time. In
the worst case, when the number wasn’t there, we had to compare the search
value to every number in the list. This means that we need to do 𝑛 comparisons
because there were 𝑛 numbers. So the amount of work is linear and we can
write 𝑂(𝑛).

Have a look at the graphs on Big-Oh Cheat Sheet. See how the different classes
grow at different speeds as 𝑛 increases. Using the graphs, try to order the classes
in the table above from best to worst.
18 CHAPTER 1. DATA STRUCTURES & ALGORITHMS

1.4 What are we ignoring?

When we say that an algorithm takes 𝑂(1) time, it means that it takes the same
amount of time regardless of how big or small the input is. When we say that
an algorithm takes 𝑂(𝑛) time, it means that it takes a linear amount of time
regardless of how big or small the input is - as the input size grows, the runtime
increases linearly. When we say that an algorithm takes 𝑂(𝑛2 ) time, it means
that as the input size grows, the runtime grows quadratically.
These shapes and growth rates are very important when 𝑛 is very large because
the shape is the most important thing in telling us how well our algorithm
scales to larger input. If I double the input size on a 𝑂(𝑛) algorithm, the
runtime doubles, but if I double the input size on a 𝑂(𝑛2 ) algorithm, the runtime
quadruples. So we now know which algorithm is likely to work well when 𝑛 gets
bigger.
BUT… we need to be careful claiming that one algorithm is better than another.
When an algorithm is 𝑂(1) it takes a constant amount of time, but that constant
could be 4 nanoseconds or it could be 4 hours. When an algorithm is 𝑂(𝑛)
it takes a linear amount of time, but the linear function could be 42𝑛 + 6 or
42000000𝑛+6000000. They are both the same in terms of asymptotic complexity
- but they are definitely not the same in terms of efficiency.
We are also tempted to think that a 𝑂(1) is always better than 𝑂(𝑛). This is
certainly the case when 𝑛 is large enough, but the constants that are hidden
inside the Big-Oh (the 𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓... from the previous examples) might matter
in practice. A constant time of 4 million seconds is almost certainly worse than
4𝑛 seconds - unless we know that 𝑛 is likely to be larger than 4 million.
Asymptotic complexity is an important tool to analyse algorithms and under-
stand how well they scale with the size of the input, but it is not the only thing
to consider and we should bear in mind that sometimes the constants matter.

1.5 Abstract Data Types

A core aspect of Computer Science is abstraction. We can’t deal with all the
details all of the time and so sometimes we need to think at a high level to solve
a full problem, but at a low level to solve specific aspects of the problem. When
reading in a collection of numbers in Python, you probably said something like
myList.append(42). You asked python to add a number to the list, but you
did not tell python how to do so. Python gave us an interface that says what
can do with the list and we could just use the interface without ever having to
think about what was happening underneath. This is a high level of abstraction
and the more details that are hidden, the higher the abstraction. Likewise, in
C++ when you used vectors, you didn’t think about how the numbers were
being represented in memory. You just had a list of numbers and you could add
to and remove from the back. Again, the language gave us an interface and we
1.6. CONCLUSION 19

could just tell C++ what we wanted it to do.

In both of these cases, having the python list/C++ Vector allowed us as the
programmer to think about how to solve our problem using a list of things,
rather than us having to think about how to build our own list. We know that
for a list we should be able to add items, remove items, get the number of items
stored in it, and fetch each item in the list. This is a sensible set of operations
that we might want to perform on a list, whether it is a list of students, a list of
Tweets, or a list of my favourite chocolates. We add things, we remove things,
we fetch things.
When we only declare an interface for a structure to store or manage data we
can think of this as an Abstract Data Type (ADT) - for example, a list. We
care about how we can use the object through its interface, but we don’t care
about how that interface was actually implemented.
Think of a car. We only use the steering wheel, the brake pedal, the accelerator
pedal, the clutch and the gear lever. Using only those 5 things, we can drive
from one point to another. Those 5 things make up the interface to the car
and we don’t need to know anything about the implementation (the engine, the
gearbox, the… other things that make a car go…). This hides details from us
and makes things easier to code.
One potential issue is that when we don’t know anything about the implementa-
tion, we might use it very inefficiently. We don’t know how python implements
lists and so if we are constantly adding and remove items, it might be slow our
algorithm down substantially - it might even change the asymptotic complexity
if we think that myList.push_back(42) is constant, but actually takes 𝑂(𝑛)
time. If we call the function 𝑛 times, we do 𝑂(𝑛2 ) amount of work instead
of 𝑂(𝑛) - this could be the difference between 1000 operations and 1000000
operations.
By understanding how we can represent data in memory efficiently, we can
improve the efficiency of our algorithms substantially. To do this, we need to
think of the abstract data type which declares the interface (what we can do
with it) and then based on which operations we perform often, we then think
about how we might implement or define the data type so that these functions
are efficient.

1.6 Conclusion
By studying and analysing various structures, and the algorithms that manage
them, we can learn to write code that is not just correct, but also efficient
and scalable. This is a core aspect of Computer Science and you will study
Algorithmic Analysis and Complexity Theory in the first, second and third years,
as well as honours. In IDSA we will study, analyse and implement the data
structures. We’ll consider time and space complexity and we’ll see how using
20 CHAPTER 1. DATA STRUCTURES & ALGORITHMS

these structures can change the efficiency of the programs that we implement.
In DCS you will learn a number of techniques from discrete mathematics, and
you will learn a number of different proof techniques. Next year, in Analysis
of Algorithms (AA), you will put the two together and you will learn to prove
mathematically that algorithms are correct and that they are efficient. In third
year you will start to look at Advanced Analysis of Algorithms where you learn
about different problem classes themselves and you will learn to prove that an
algorithm is optimal by finding lower bounds on the amount of work that needs
to be done. In Honours, you’ll learn more advanced algorithm and analysis
techniques and you’ll be able to analyse recursive and stochastic algorithms.
This is a core aspect of what it means to be a computer scientist and I suggest
that you invest in IDSA and DCS as much as possible so that you have a strong
foundation to build on in future years.

1.7 TODO
Sorry, this introduction was very text-heavy, as we move forward there will be
significantly more demo videos and explanations throughout the text.
1. Make sure that you registered in the Moodle course for IDSA.
2. Install Discord, join the server and say hi!
3. Download the “C++ Revision Notes” pdf from Moodle and ensure that
you’re comfortable with the concepts discussed there. If you’re unsure
about anything, please post on Discord and we can discuss things. You
will also be able to discuss these ideas with your tutors during the first
online tutorial session.
4. There will be a lab on Thursday. Make sure that you have set up your
local C++ programming environment.
Chapter 2

C++ Fundamentals

2.1 Classes
In C++ (and all programming languages that support Object Orientation) we
are able to create our own types by connecting many of the primitive types
together. The normal primitive types are the ones that come with C++ and
are built into the language – such as int, float, char, double and pointers.
Note that a vector and all the other types that you #include into your files are
usually classes and not primitive types. They have been added to C++ through
the Standard Template Library.
A vector is a good example of why we might like a class. We will study them in
more detail later on, but fundamentally, vectors store an integer that tracks the
number of items being stored, it tracks the amount of memory that has been
reserved and it keeps a pointer to that memory. It is useful to bundle these 3
variables into a single object that we can think of as a vector. We can then
perform operations on that vector, such as push_back() or size(). When we
group a number of types together into a single new type, this is called a Class.
A class is a new type of variable – for example, Car is a Class, but a specific
instance of a Car is an object.
class Car{
public:
int num_wheels, num_doors;
string colour;
int coolness;

Car(){
// This is a constructor, which runs when the car is created
// It should allocate memory and setup variables.
num_wheels = 4;

21
22 CHAPTER 2. C++ FUNDAMENTALS

num_doors = 4;
coolness = 10;
}
~Car(){
// This is a destructor, which runs when the car is destroyed
// It should free memory and clean up any mess that it made (opened any files etc
}

float price(){
// This is a member function
if(colour == "Pink"){
return 100*coolness + 10*num_wheels;
}else{
return 10*coolness + 5*num_wheels;
}
}
};

void main(){
Car richardsCar;
richardsCar.num_wheels = 5; // We have a spare wheel
richardsCar.colour = "Pink"; // Because I can
richardsCar.coolness = 1000000; // Obviously

Car stevesCar;
stevesCar.num_wheels = 3; // We've lost a wheel or two
stevesCar.colour = "Blue";
stevesCar.coolness = 1;

In the example above, Car is a class, it tells the compiler that we can have
variables of type Car. richardsCar on the other hand, is an instance of a Car
and we would say that richardsCar is an object. We see that the Car type has
some members called num_wheels, num_doors, colour and coolness. These
are values that are associated with each car that we create. In the example
above we see that richardsCar and stevesCar are both instances of Cars and
therefore each one has its own version of num_wheels, coolness etc.

Classes can contain more than just data. They can also contain member func-
tions. These functions belong to the class and usually operate on the data stored
inside the class. For example, we have a function called price. This function
only makes sense in the context of an actual instance of a Car. So we could ask
“How much would you pay for richardsCar or stevesCar?” but you wouldn’t
ever ask “How much would you pay for Car?”
2.1. CLASSES 23

In C++, classes are just like normal variable types. We can pass an instance of
a car into a function by value or by reference. We can also get the address of
that object as well.
class Car{...};

void print(Car& curr){ // The car is passed by reference

cout << "There are " << curr.num_wheels << " wheels"
<< "and the car is " << curr.colour << "." << endl;
}
void paint(Car* curr, string new_colour){ // A pointer to the car is passed
// When we have a pointer to an object we have two different ways
// of accessing members:
// A) Access the member function/variable through the pointer
curr->colour = new_colour;
// B) or Dereference the pointer and access the member
(*curr).colour = new_colour;
}

void broken_paint(Car curr, string new_colour){

// Watch out, here we pass the car by VALUE
// This means that the function receives a copy of the car object
// and if we make any changes, they do not affect the original car
curr.colour = new_colour;
}

void main(){
Car richardsCar;
richardsCar.num_wheels = 5; // We have a spare wheel
richardsCar.colour = "Pink"; // Because I can
richardsCar.coolness = 1000000; // Obviously

Car stevesCar;
stevesCar.num_wheels = 3; // We've lost a wheel or two
stevesCar.colour = "Blue";
stevesCar.coolness = 1;

// Print takes references to the object.

print(richardsCar); // There are 5 wheels and the car is Pink.
print(stevesCar); // There are 3 wheels and the car is Blue.

// Paint takes pointers to the object and we need to pass the address.
paint(&richardsCar, "Neon Pink"); // Richard's car is now Neon Pink.
paint(&stevesCar, "Jungle Grey"); // Steve's car is now Jungle Grey.

// broken_paint takes a copy of the object

24 CHAPTER 2. C++ FUNDAMENTALS

broken_paint(richardsCar, "Black"); // Richard's car is still Neon Pink

}

There are many finer details to objects and Object Orientation as a program-
ming paradigm. We can do fancy things like abstract/virtual classes, interfaces,
inheritance and polymorphism which allow us to create modular, reusable code.
This is the main standard for programming in industry and you should learn
as much about this paradigm as you can. You will learn about these concepts
more formally in second and third-year courses.
For now, the important thing to remember about classes is that they allow us
to build abstractions – you don’t know how a vector or a car works, but you
know what member functions you can call and the documentation should tell
you what those functions do. We don’t need to know how the class achieves
those goals, just that the class will make sure it works. When you used a vector
in IAP, you knew that you could use myVector.push_back(thing) even though
you didn’t know how that function manipulated the underlying memory. The
class abstracts away, or hides, the implementation details from you and you can
focus on solving the actual problem that you care about.
However, we can’t completely ignore what the class is doing. Just because
we’re making a single function call, doesn’t mean that the object is not doing
a lot of work. These functions may contain loops, they may perform various
memory allocations and could do any amount of work that we don’t know about.
It is important to know that the way we are using classes is efficient. This is
why we will look at a number of different data structures (like vectors) and
algorithms (like push_back) to understand their computational complexity.
This will allow you to use the right structure for the job and you’ll know that
your code will still be efficient and scalable.
Here is another detailed description of classes and how they work:
https://www.youtube.com/watch?v=-re_xRIonSs
There are also some more explanations if you are still not comfortable with
classes:
1. https://www.youtube.com/watch?v=2BP8NhxjrO0
2. https://www.youtube.com/watch?v=ABRP_5RYhqU&t=71s
3. https://www.youtube.com/watch?v=-IrueTrxNHA&t=202s
Additional Reading:
1. Chapter 1.5 (the basics covered here) – Goodrich et al. (2011)
2. Chapter 2 (more advanced) – Goodrich et al. (2011)
3. Chapter 1.4 – Weiss (2014)
4. Chapter 2.3, 2.4 – Dale et al. (2018)
Goodrich et al. (2011) cover this topic particularly nicely.
2.2. POINTERS 25

2.2 Pointers
Pointers are discussed in some detail in Section 10 of the “C++ Revision Notes”
on Moodle. Please ensure that you’ve gone through those notes in detail. We
will revisit the idea of pointers and dynamic memory allocation multiple times
in this course.
I strongly recommend that you read through these sites and examples as well:
• https://www.geeksforgeeks.org/pointers-in-c-and-c-set-1-introduction-
arithmetic-and-array/
• https://www.geeksforgeeks.org/pointers-c-examples/
Additional Reading:
1. Chapter 1.5 – Weiss (2014)

2.3 Setting up your environment

There are a few different ways to get your environment set up. I suggest that you
use QtCreator as your IDE and the instructions and video below explain how to
set that up using the online installer. The offline installers are have mirrored on
Moodle and you can access them at https://courses.ms.wits.ac.za/software/Qt.

2.3.1 Linux
While connected to the internet, open a terminal and run:
sudo apt install build-essential git qgit git-gui meld qt5-default qtcreator libsdl2-* libclang-c

You have all the software you need to complete this course.

2.3.2 Windows/MacOS
MinGW is a version of g++ for Windows. You can download MinGW-64 di-
rectly from http://mingw-w64.org/doku.php. This will give you a terminal and
technically everything that you need to compile. MinGW can also be installed
as part of QtCreator (see the steps below).
If you would prefer to use CLion there is a tutorial here: https://www.jetbra
ins.com/help/clion/quick-tutorial-on-configuring-clion-on-windows.html. Wits
has licences for all the JetBrains products, just sign up for an account with your
Wits email address.
Installing Qt:
• Download the online installer: https://www.qt.io/download-thank-you?o
s=windows or https://www.qt.io/download-thank-you?os=macos or the
offline installer from https://courses.ms.wits.ac.za/software/Qt.
26 CHAPTER 2. C++ FUNDAMENTALS

• You need to sign up for an account, unfortunately. This is new and I don’t
like it, but there isn’t really anything else to do.
• When selecting components, select:
– Qt 5.15.0 → MinGW 8.1.0 64-bit (Qt that was compiled with
MinGW). If you’re using the offline installer then the version is
5.12.x. The exact compiler version will likely change, but as long as
it supports C++11 it will be fine.
– Developer and Designer Tools → MinGW 8.1.0 64-bit
(MinGW Compiler - g++ for Windows) + the two defaults.
– Watch out that this could be a pretty large download. Unfortunately,
I’m not sure how big it is though. Alternative below…
• You can open the .pro files that I supply with the labs.
https://www.youtube.com/watch?v=uMjYgNC1s2c

2.3.3 Virtual Box

If you are struggling with the setup above, I have prepared a VirtualBox as well
that already contains all the relevant software needed for the course. You can
download VirtualBox from https://www.virtualbox.org/wiki/Downloads (or
https://courses.ms.wits.ac.za/software/VirtualBox/ if you need it zero-rated)
and you can download the image from https://courses.ms.wits.ac.za/~richard
/IDSA-2021.ova.
1. Install VirtualBox and Extensions.
2. File → Import Appliance.
3. All the default values should be fine.
4. If you ever need it, the password is 1234.
Chapter 3

Arrays & Vectors

3.1 Abstract Data Type: Lists

• Suppose you want to sort a list of numbers…
• Suppose you want to print a list of student grades…
• Suppose you want to store a list of dank memes…
In many problems, we need to keep or manipulate a list of some type of object.
In the examples above these objects are numbers, grades, and memes, but re-
gardless of the object that we are storing, the operations that we would perform
on the list are usually the same:
1. Add an object to the list (at the front, at the back, or before index i)
2. Remove an object from the list (at the front, at the back, or at index i)
3. Get an object from the list (at the front, at the back, or at index i)
4. Get the size of the list
When we think of a list in this way, we are specifying what we would like to
do with a list (i.e. the interface or declaration) but not how the list itself
is represented in memory (i.e. the implementation or definition). When we
define the interface in this way, we are defining an Abstract Data Type and in
this case, the ADT is a list.
In future, when we’re working on our algorithms, we can just use a list to store
all our objects and we don’t need to think about how the list was implemented,
only what we want to do with the list. This abstraction allows us to think
about our problem at a high level, without having to think about the details of
memory management, efficiency, correctness etc.
But someone has to think about these things at some point to code them into
the language. It’s also important that if you are going to use these structures in
your code that you know when they are good or bad. This is important because:

27
28 CHAPTER 3. ARRAYS & VECTORS

for(int i = 0; i < n; ++i){

myList.push_back(i);
}

will do a linear amount of work – 𝑂(𝑛) – if push_back is constant, but it will

do a quadratic amount of work – 𝑂(𝑛2 ) – if push_back is linear.1
Unfortunately, there is no free lunch. Being fast at one operation often means
a trade-off in the speed of another or even increasing the memory requirements.
We will see this happen many times and often we have to choose the data struc-
ture that is optimal for the operation that happens most often. For example, if
we create the list once, but then search it many times we probably care more
about the get operations over the push_back operations. If we are only ever
adding and removing at the back of the list, then it is important the push_back
and pop_back are fast, but get(index) doesn’t matter at all.
In the long run, knowing the pros and cons of various data structures allows you
to select the correct implementation to ensure your algorithms run efficiently.
Our first implementation of a list will be using blocks of contiguous memory
called arrays, but before we talk about our first list implementation, let’s discuss
memory management.

3.2 Memory Management

https://www.youtube.com/watch?v=vy8jVKUhclY

Remember
• There are two spaces where we can allocate memory: The stack and the
heap.
• Automatic variables are allocated on the stack.
• Dynamic memory is allocated on the heap.
• Frames are like Pancakes: You add to the top of the stack, you remove
from the top of the stack.
• The call stack holds a frame for every function that gets called. The
frame contains space for all the automatic variables inside the function.
• When the function finishes, the frame gets popped off of the call stack. We
always remove it from the top of the stack. All the automatic variables
are automatically destroyed.
• Dynamically allocated memory is controlled by us and we are in charge of
returning it to the operating system when we’re finished.
• Dangling points point to memory that we no longer own. Don’t derefer-
ence them!
1 We do something like 𝑎𝑛 + 𝑏 steps, 𝑛 times. We’ll look at this case in more detail later.
3.3. CONTIGUOUS MEMORY & POINTER ARITHMETIC 29

• Allocate with square brackets (p = new int[42]) → delete with square

brackets (delete [] p)
• Allocate without square brackets (p = new int) → delete without square
brackets (delete p)
• If we forget to return dynamically allocated memory to the operating
system (delete or delete[]) then we have a memory leak.

3.3 Contiguous Memory & Pointer Arithmetic

One thing that makes arrays appealing is that they are extremely fast to access,
no matter how many items are stored in them. This is because all the items
are stored contiguously. This means that all the blocks of memory are allocated
consecutively – directly next to each other. When we allocate space for 𝑛
items, we allocate one large block of 𝑛 ∗ datatype size bytes. In fact, in the C
programming language you have to calculate the number of bytes yourself and
then cast to the correct type. The C++ approach is much safer.
// Automatic Variables - C and C++
// Note that the size cannot be a variable, it must be a number known at compile-time.
int myList[42];

// Dynamic Allocation
int* myListC = (int*) malloc(n*sizeof(int)); // C [Not typesafe]
int* myListCpp = new int[n]; // C++

Figure 3.1 shows the myList pointer which contains the address of the first
object stored in the array. In this case, the first object is stored at 0x04 and
each integer takes up 32 bits (4 bytes).
Because every object/block in the memory is the same size, we can calculate
the address of an item at index 𝑖 by taking the address of the first item in
the array and adding 𝑖 ∗ datatype size to it. For example, to get the address of
myList[4] we would say myList + i*sizeof(int). However, as the compiler
knows what type of pointer we are dealing with, it already knows to multiply
the index by the size of the data type. It does this automatically, so we rather
just say myList + i and the compiler will do the extra work for us. To get the
value we simply dereference this new pointer.
This process is called pointer arithmetic.

Index Object Value

0 myList[0] *(myList+0)
1 myList[1] *(myList+1)
2 myList[2] *(myList+2)
3 myList[3] *(myList+3)
4 myList[4] *(myList+4)
30 CHAPTER 3. ARRAYS & VECTORS

Index Object Value

… … …
i myList[i] *(myList+i)

We can also use pointer arithmetic with a 2D array:

int **myList = new int*[n];
for(int i = 0; i < n; ++i){
myList[i] = new int[m];
}

// These two lines are the same:

myList[i][j] = 42;
*(*(myList+i)+j) = 42;

Notice that to calculate the address of an object in a 1D array it is one multipli-

cation, an addition and one pointer deference. Regardless of how many items
there are in the array (𝑛), it will always take the same amount of time to fetch
the object. This means that we can access an item in an array in constant
time – 𝑂(1).

3.4 Increasing the size of an array

As arrays require all memory to be contiguous (otherwise we would not be able
to do pointer arithmetic), it means that all the memory needs to be allocated
at the start when the array is created – if we allocated the memory in multiple
stages, then we’d have no guarantee that each allocation would be next to
the previous. Once the block of memory has been allocated, the operating
system might allocate other variables in the space neighbouring the current
block. Unfortunately, this means that once the block has been allocated, we
cannot expand the size of that block because we can’t be sure that the memory
adjacent to it is free.
If after the allocation, we later decided that the array isn’t big enough, we would
need to make a new, bigger array, and then copy all the items that need across
into the new buffer. Finally, we would free the old block of memory because it
is no longer needed. For example, we might use the following code.
void reallocate(size_t new_size){
int* new_buffer = new int[new_size]; // Allocate a new, bigger array
for(int i = 0; i < n_items; ++i){
new_buffer[i] = data[i]; // Copy all the old items into the new buffer
}
delete [] data; // Delete the old buffer
data = new_buffer; // Make the data buffer point to the new memory
3.4. INCREASING THE SIZE OF AN ARRAY 31

Figure 3.1: Memory Layout of an Array

n_allocated = new_size; // Remember the size of the new buffer

}

Here are some examples of how to increase the size of an array and how to
analyse the amount of time taken to do so.

https://www.youtube.com/watch?v=ssWdVH2wodo

You’ll notice in the code and examples above that all the memory used is dy-
namically allocated – we always used the new keyword. Unfortunately, when you
call a function, the stack frame size for that function’s automatic memory needs
to be known upfront. This means that it is impossible to resize an array that
was allocated on the call stack – doing so would require that we resize the stack
frame for the function. The compiler needs to know the size of these frames
at compile-time. So when working with arrays allocated on the stack, you are
stuck with the size that was used when the code was compiled.2

Similarly, there is no way to manually free the memory that was allocated on the
stack, and the runtime system will only reclaim that memory once the function
is finished.
2 In C++ dynamically sized arrays are not allowed on the stack. However, the g++ compiler

does allow this by changing the size of the stack frame, but it is not part of the C++ standard
and this only works in very specific circumstances. This is a feature of C99 (not C++) called
Variable Length Arrays that g++ decided to implement. You should avoid using it because
other compilers won’t necessarily support it. Also, the stack is usually not big enough for
large arrays and these can cause stack overflows – large arrays should never be allocated on
the call stack. Every time I compile your code on Moodle, I explicitly tell g++ to disable the
VLA extensions.
32 CHAPTER 3. ARRAYS & VECTORS

3.5 std::array and std::vector

In the C++ Standard Template Library (STL) there are two implementations
of array types: std::array and std::vector, which represent arrays with
automatic (stack) and dynamic (heap) memory allocation respectively. These
classes encapsulate the ideas that we’ve spoken about above and provide you
with several convenient functions to help you write your code. You can trust
that these classes are implemented correctly and efficiently, which can save you
a lot of debugging compared to writing your own versions.

Both of these classes provide size to fetch the number of items, operator[](i)
to fetch the value stored at index i without bounds checking, at(i) to fetch the
value stored at index i with bounds checking and many other functions. Both
containers use contiguous memory and pointer arithmetic for their underlying
storage.

Because std::array allocates its memory on the stack, you need to know the
size at compile-time. On the other hand, std::vector represents a dynamically
allocated array where the storage is on the heap. This means that it can real-
locate, expanding or shrinking its memory as necessary. A vector<int> would
look similar to the following declaration:3
class vector{
int* data; // Pointer to storage buffer
size_t n_items; // Number of items stored
size_t n_allocated; // Amount of memory allocated
}

We can then use the following code:

void fun(){
vector<int> v;
for(int i = 0; i < 5; ++i){
v.push_back(i);
}
// ...
}

The resulting memory layout would be as shown in 3.2. Note that the vector’s
member variables (data, n_items, n_allocated) are allocated on the stack,
but the actual storage is dynamically allocated on the heap.

In contrast an std::array<int, 5> would have the layout shown in

@ref{fig:arrlayout}. Note that the storage is allocated on the stack itself and
the class does not need to store the number of items or the size of the current
allocation because those cannot change during the objects lifetime.

3 Excluding template declarations

3.5. STD::ARRAY AND STD::VECTOR 33

Figure 3.2: Memory Layout of a Vector

Figure 3.3: Memory Layout of an Array

34 CHAPTER 3. ARRAYS & VECTORS

3.6 Reallocation & Complexity

The vector class manages 3 main variables: the number of items in the array,
the amount of space allocated, and a pointer to the allocated space. The vector
maintains storage space that is slightly larger than necessary. When the user
tries to add to the back of the array using the push_back function, the vector
will first check whether there is any free space – if there is space then the item
is simply inserted into the next available block, if not the vector allocates twice
as much space as before, copies all the current items into the new space, and
then frees the old memory buffer. This strategy finds a good balance between
keeping space available for items to be added (thus minimising reallocations and
copies) and keeping too much unused space which wastes resources that other
programs may need.
Conversely, when removing an item from the back of the list we want to make
sure that we give memory back to the operating system when it is no longer
necessary. We don’t want to reallocate and copy every time an item is removed
– as that would be slow. A naïve approach would be to reallocate every time the
vector is half empty but this creates a problem when the user adds and removes
items repeatedly as illustrated below.
1. n_items: 5, n_allocated: 8
2. pop… n_items: 4, half empty, reallocate
3. n_items: 4, n_allocated: 4
4. push… n_items: 5, storage is full, reallocate
5. n_items: 5, n_allocated: 8
6. pop… n_items: 4, half empty, reallocate
7. n_items: 4, n_allocated: 4
8. push… n_items: 5, storage is full, reallocate
9. n_items: 5, n_allocated: 8
This causes a large number of unnecessary reallocations – which are slow. The
better strategy is to reallocate with twice the space when the vector is full,
and then to half the amount of allocated space when the vector is less than a
quarter full. This strikes a balance where the vector does not waste too much
space when removing items but does not reallocate and copy too quickly,4 .
https://www.youtube.com/watch?v=jS7yVu8QTBQ
Accessing items or indexing into the vector using the operator[] or the at()
functions simply uses pointer arithmetic in the background, this means that
these functions take constant time – 𝑂(1).
Getting the size (number of items in the vector) or the capacity of the allocated
storage involves simply returning those values, which are stored inside the class
– 𝑂(1).
4 This strategy is followed by most implementations, although the exact coefficient is

implementation-dependent.$
3.7. QUESTIONS 35

Pushing a new item to the back of the vector has two cases. In the best case,
there is already space available to perform the insert and the value is just copied
into the memory buffer. This takes constant time – 𝑂(1). In the worst case,
there is no extra space in the buffer and the vector needs to reallocate memory,
copy all the items across, and then free the old memory. In this case, we have
𝑛 items and each item gets copied once. Therefore we do 𝑂(𝑛) operations.

Similarly, when popping from the back of the vector we have two cases again.
In the best case, we aren’t wasting too much space and so we don’t have to
reallocate. So the vector simply removes the item from the buffer in constant
time – 𝑂(1).5 In the worst case, we decide that we are starting to waste too
much memory and we reallocate, which makes 𝑛 copies again taking us linear
time – 𝑂(𝑛).

These worst cases seem bad, but by choosing those reallocation thresholds very
carefully, we can mathematically prove that over 𝑛 insertions and/or deletions
we still only do a linear amount of work. This is called Amortised Analysis and
we say that these functions take Amortised Constant Time. You will learn to
do this type of analysis in fourth-year and it shows that even with reallocations,
the vector is very efficient.

Another operation that we might care about is inserting or removing at the

front of the vector. Unfortunately, there is no way to do this in constant time.
If there is still open space at the back of the vector, then we can copy each item
one block to the right to create space at the front. This involves 𝑛 copies and
is therefore linear time. If there is no space at the back of the vector, then we
need to reallocate and once again copy all the items across, again resulting in
linear time.

https://www.youtube.com/watch?v=dUbrk-RHr_0

Note that the time complexity of C++ STL containers and algorithms is part
of the ISO C++ Standard. This means that for a compiler to be standards
compliant, its STL implementation needs to be at least as efficient as men-
tioned by the standard. Have a look at the different functions offered by the
std::vector as well as the associate complexity of each. A reference can be
found here: http://www.cplusplus.com/reference/vector/vector/.

3.7 Questions
1. How would you implement a push_front(int value) function for a
std::vector?
5 In a real vector, the STL uses ‘placement new’ to construct objects, so when it manually

destructs the objects when necessary. This is the only time you should ever manually call a
destructor. This is more sophisticated C++ than we’ll cover in this course, so for our purposes,
we’ll consider that the objects are simple and can just be overwritten – like an int.
36 CHAPTER 3. ARRAYS & VECTORS

1. Are there best and worst cases, or does it always have the same
asymptotic complexity?
2. What is the complexity?
2. How would you implement a push_at(int value, int idx) function for
a std::vector?
1. Are there best and worst cases, or does it always have the same
asymptotic complexity?
2. What is the complexity?
3. You would like to create a custom vector object. You don’t ever need the
push_back function but you do need a push_front function. How would
you implement it and what would the complexity be?
4. What is the purpose of the begin and end functions of the std::vector
and std::array?
5. Why is the return type of vector<int>::operator[] and vector<int>::at
an int& rather than an int?
6. What does the reserve function do?
7. What does the resize function do?
8. When would you prefer a std::array over a std::vector?
9. Exactly how many items are in the vector after the following code com-
pletes? [Try to do this without running the code.]
vector<int> v;
for(int i = 0; i < n; ++i){
v.push_back(i);
}

10. Exactly how many items are in the vector after the following code com-
pletes? [Try to do this without running the code.]
vector<int> v;
for(int i = 0; i < n*n; ++i){
v.push_back(i);
}

11. Exactly how many items are in the vector after the following code com-
pletes? [Try to do this without running the code.]
vector<int> v;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
v.push_back(i);
}
}
3.8. ADDITIONAL READING 37

12. Exactly how many items are in the vector after the following code com-
pletes? [Try to do this without running the code.]
vector<int> v;
for(int i = 0; i < n; ++i){
for(int j = 0; j < i; ++j){
v.push_back(i);
}
}

13. Exactly how many items are in the vector after the following code com-
pletes? [Try to do this without running the code.]
vector<int> v;
int i = n;
while(i > 0){
v.push_back(i);
i /= 2; // Hint: Integer division
}

3.8 Additional Reading

• https://www.geeksforgeeks.org/introduction-to-arrays/
• https://www.geeksforgeeks.org/arrays-in-c-cpp/
• http://www.cplusplus.com/reference/vector/vector/
• Chapter 3.1, 3.2, 3.3, 3.4 – Weiss (2014)
• More detailed and advanced: Chapters 17, 18 and 19 – Stroustrup (2014)
38 CHAPTER 3. ARRAYS & VECTORS
Chapter 4

Linked Lists

4.1 Introduction
4.1.1 Arrays
https://www.youtube.com/watch?v=HFJIXfTbxxU

So far we’ve used arrays to implement lists of objects. For example, if we wanted
a list of 6 integers, we would use the following code:
int myList[6]; // Allocated on the Stack
int *myList = new int[6]; // Dynamically Allocated on the Heap

On the first line, space for the array will be reserved on the call stack when the
frame for this function is created. Because the array will be inside the frame,
we need to know the size of the array when the frame is allocated. This means
that you can’t have a function that reads in a number and then uses the stack to
allocate an array of that size, because the stack frame has already been created.1
On line 2, new[] will ask the operating system for 6×sizeof(int) bytes from
the Heap or Freestore. The operating system will find a convenient place in
RAM to reserve this memory and will return the address of the first object in
the array. We store the address inside the pointer myList. We may be left with
the following memory layout:

Once the operating system has allocated the block of memory, the size of the
block cannot be changed. If we suddenly decided that the array isn’t big enough,
we would need to make a new, bigger array and then copy all the items that we
need across. After copying the 𝑛 items to the new memory, we would have to
free the old one. For example:

1 Recall that we discourage the use of compiler-specific extensions such as VLAs.

39
40 CHAPTER 4. LINKED LISTS

Figure 4.1: Memory Layout of an Array

int *newArray = new int[10]; // Allocate a bigger array

for(int i = 0; i < 6; i++){ // Loop over the original array

newArray[i] = myList[i]; // Copy the values to the new array
}

delete [] myList; // Deallocate the original array

myList = newArray; // Make the pointer point to the new one

Note: Even though the realloc function from C99 changes the size of a mem-
ory block/array, in practice, it can only make the array longer if there is free
space after the original one. If there is no free space, it will allocate new memory
and copy the contents across – just as shown above.

4.1.2 Questions
1. If you have an array of size 𝑛 that needs to be increased to size 2𝑛, how
many copies must your program make?
2. If it takes 3 time steps to copy a single number, how long does the copy
take?
3. If the list of 2𝑛 items fills up and we now need to increase the size to 3𝑛,
how many copies will the program have done in total?

4.2 When arrays aren’t good enough

https://www.youtube.com/watch?v=ess7iLaaJIw
4.2. WHEN ARRAYS AREN’T GOOD ENOUGH 41

Let’s say that we have a program that must read numbers into an array until
it reads −1. We have no idea how much memory to allocate at the start of
our program. If we try to allocate too much it might fail because the operating
system can’t find enough contiguous space.2 If we allocate too little, we might
waste a lot of time copying items to new arrays every time it fills up. If we had
to reallocate 4 times, then it means the first item added to the list needs to be
moved 4 times as well. It would be useful if we could come up with some data
structure that allows us to change the size of the list without any major cost
in both time and memory requirements (space).

Suppose you have a program where there is an array of 100 integers. I need you
to insert a number at the beginning of the list and each number shifts over
by one. The last number in the list is removed. To do this, you first need to
move all the numbers one item to the right - list[98] moves to list[99] etc.
When you have moved all the numbers in the list, you are now free to add the
new item to list[0].

Suppose you have a program where you need to delete the 𝑖𝑡ℎ number in an
array. While we can fetch the number in constant time3 all the numbers in the
array need to be consecutive in memory. If we just removed the number and
left everything where it was, we’d leave our array with a hole in the middle –
this would break the array because the objects are no longer contiguous. To fix
this, we need to shift every item from 𝑖 onwards, one block to the left.

4.2.1 Questions
1. If you have an array of 𝑛 items, how many ‘move/copy’ operations must
you do to insert a number at the front of the list?
2. If you have an array of 𝑛 items and you want to delete the item at the
front, how many ‘move/copy’ operations must you do?
3. If you want to insert 𝑛 items into a list that is already 𝑛 items long, exactly
how many ‘move/copy’ operations should you do?

4.2.2 Linked Structures

In the previous examples, we end up doing a lot of extra work because we have to
make sure that the memory is contiguous but cannot ask the Operating System
to allocate new memory next to the old memory. If we could come up with a
new structure that didn’t require contiguous memory, then we would be able
to allocate and free memory as necessary without worrying where the memory
actually was and without needing to copy all the old items into the new memory
each time.
2 Contiguous memory is when all of the allocated blocks are next to each other/consecutive

in memory. Similar to continuous, except we’re talking about discrete blocks.

3 Thanks to pointer arithmetic.
42 CHAPTER 4. LINKED LISTS

The idea behind this type of structure is to allocate separate pieces of memory
on the heap and then link them together like a chain, using pointers.

4.3 Linked Lists – forward_list

https://www.youtube.com/watch?v=SEuTA41nWpQ
Linked lists consist of a number of links or nodes. Each one contains a value
and a pointer to the next node in the list.

Figure 4.2: Link for a Linked List

We can code it as a class or a struct.

class Link{
public:
int value;
Link *next;
};

struct Link{
int value;
Link *next;
}

The idea is that we simply store a pointer to the first link (sometimes called a
node), and then each node stores the address of the next node. So as long as we
remember where the first item is, we can follow its ‘next pointer’ to get to the
next link in the chain. The last link’s next pointer should contain the nullptr
because there is no next link to point to.
To create the list in Figure 4.3 we might use the following code:
class Link{
public:
4.3. LINKED LISTS – FORWARD_LIST 43

Figure 4.3: A Linked List

int value;
Link *next;
Link(int v) : value(v), next(nullptr){
/* Initialise value with v and set next to the nullptr */
}
};

class LinkedList{
public:
Link* head;

LinkedList() : head(nullptr){
/* The line above initialises head to be the nullptr */
}
~LinkedList() {
/* Traverse the list and deallocate each link */
}
};

int main(){
LinkedList myList;
44 CHAPTER 4. LINKED LISTS

for(int i = 5; i > 0; --i){

// Create a new link
Link *tmp = new Link(i*i);
// Insert at the front:
tmp->next = myList.head;
myList.head = tmp;
}

// Traverse the list and print each value

Link *curr = myList.head;
while(curr != nullptr){
cout << curr->value << endl;
curr = curr->next;
}
}

Notes:

1. myList is an instance of the LinkedList class.

2. It contains a pointer that always points to the head of the list – the first
link.
3. By keeping a pointer to the head, we can easily insert items into the front
of the list.
4. The next pointer in the last node must contain the nullptr so that we
know when to stop during a traversal.
5. To get to any item in the list we need to traverse the list from the head.
We do this by repeatedly following the next pointers until we reach the
desired node.
6. Note that the myList (i.e. the instance of LinkedList, which is an object
containing only a single pointer) is an automatic variable that is allocated
on the stack. It is part of the stack frame for the main function. All the
individual Link instances are dynamically allocated using the new keyword,
so those objects live on the heap.
7. When the list is destroyed we should make sure we clean up any memory
that we have allocated to avoid memory leaks. The LinkedList destructor
should traverse the list deallocating all the links that were allocated using
new. The list itself (myList) was automatically allocated on the stack, so
we do not manually free that memory.
8. Just like with a chain, if we break a link we will lose access to the links
that follow it. We need to be careful to avoid memory leaks, so we need
to copy the value of the current link’s next pointer before we delete it.
Otherwise, we would drop the rest of the chain and would not be able to
free the remaining links.
4.4. OPERATIONS 45

4.4 Operations
https://www.youtube.com/watch?v=4WzVV0BgqEs
We’d like to consider the following operations. Where T is the type of object
stored in the list.
1. void push_front(T value)
2. void pop_front()
3. Link* get_link(int i)
4. T& at(int i)
5. void push_back(T value)
6. void pop_back()
7. void insert(int index, T value)
8. void erase(int index)
9. size_t size()
10. iterator begin()
11. iterator end()

4.4.1 push_front
https://www.youtube.com/watch?v=aAPrQ8ptyuU
To insert an item at the front of the list, we simply create a new link with the
relevant value and set its next pointer to the first item in the list. We then
point the head at the new item.
Show/Hide Code
// Create a new link
Link *tmp = new Link(42);

// New link's next points to the first item

tmp->next = head;
// Head points to the new link which is now at the front
head = tmp;

Analysis: Regardless of how many items there are in the list (𝑛), it will always
take us 1 memory allocation, 3 pointer assignments and 1 pointer dereference to
insert at the front of the list. We don’t care about these constants, we just care
that it will always take the same amount of time, so we say that this operation
takes constant time – 𝑂(1).
46 CHAPTER 4. LINKED LISTS

4.4.2 pop_front
https://www.youtube.com/watch?v=dBDfRd4HfV0
To remove the item from the front of the list, we need to update the head to
point to the next item and then delete the link that was originally at the front.
Note:
1. We need to make sure we still have a pointer to the item, otherwise, we
would have a memory leak.
2. We can’t delete the item and then update head because after deleting the
first item, we wouldn’t be able to access the next pointer. Again we would
have a memory leak.
Show/Hide Code
// Remember the first item
Link *tmp = head;
// Increment the head
head = head->next;
// Free the item
delete tmp

Analysis: Regardless of how many items there are in the list (𝑛), it will always
take us 1 memory deallocation, 2 pointer assignments and 1 pointer dereference
to delete at the front of the list. We don’t care about these constants, we just
care that it will always take the same amount of time, so we say that this
operation takes constant time – 𝑂(1).

4.4.3 get_link
https://www.youtube.com/watch?v=Qo1SlH4Zp_E
To get the link at index i, we need to traverse4 to the correct link in the chain.
This is like when you pick up a chain and move from link to link to link until
you get to the one you want.
Show/Hide Code
// Start at the front of the list
Link *curr = head;
// Until we're at the ith link, go to the next one
for(int c = 0; c < i; ++c){
curr = curr->next;
}
// curr now points to the ith link, return it etc.
return curr;

4 Like traversing terrain… NOT transverse. That is a type of wave.

4.4. OPERATIONS 47

Analysis: In the worst case we traverse to the end of the list, in which case,
we do 𝑛 − 1 traversal steps (curr = curr->next). This is a linear function, so
we say that we do 𝑂(𝑛) operations.
Beware… get_link is a linear function, so the code below is not linear. What
is the complexity of the following code segment?
LinkedList myList;
//... fill the list with items ...
for(int i = 0; i < n; ++i){
Link *curr = myList.get_link(i);
cout << curr->value << endl;
}

4.4.4 at
https://www.youtube.com/watch?v=S3prNWIvqWQ
To get the value at index i, we need to traverse to the correct link and then
return the value stored inside it. This is easy to implement because we already
have a get_link function.
Show/Hide Code
// Get the link
Link* curr = get_link(i);
// Return a reference to the value
return curr->value;

Analysis: The call to get_link is 𝑂(𝑛) and then there is another 1 dereference
operation. This results in a linear function plus a constant, which is still a linear
function. So the complexity is still 𝑂(𝑛) in the worst case.

4.4.5 push_back
https://www.youtube.com/watch?v=wWjxwD4wz80
To add to the back of the list, you need to traverse to the last link in the
chain. You can do this with a while loop. Traverse until the curr->next ==
nullptr, which means that curr is pointing at the last link. Once you have a
pointer to the last link, it is straightforward to allocate a new link and add it
to the chain.
Show/Hide Code
// Left as an exercise for the reader.

Analysis: For a list with 𝑛 items, push_back will take O(n) operations. How
could you alter the linked list data structure to achieve 𝑂(1) performance for
this function?
48 CHAPTER 4. LINKED LISTS

4.4.6 pop_back
https://www.youtube.com/watch?v=zQQ9tXaqBJw
To remove the last item in the list, we need to update the next pointer in the
link before the last one. This means that we should traverse to the second last
link in the list, use its next pointer to deallocate the relevant memory, and then
set the next link to the nullptr.
Show/Hide Code
// Left as an exercise for the reader.

Analysis: For a list with 𝑛 items, how many operations does it take to insert
at the end of the list? Would your strategy to improve the performance of
push_back work to improve the performance of pop_back? Why or why not?

4.4.7 insert
https://www.youtube.com/watch?v=dU5nJTRzqr4
To insert at an arbitrary position, 𝑖, in the list, we need to traverse to the link
before 𝑖, i.e. 𝑖 − 1. We then create the new link and set its next pointer to point
to the item currently at position 𝑖. The next pointer at 𝑖 − 1 should now point
to the new link.
Show/Hide Code
// Create the new link
Link *nl = new Link(value);
// Get the link at i-1
Link *curr = get_link(i-1);
// Point to the old link i
nl->next = curr->next;
// Point to the new link i
curr->next = nl;

// Does this code work when i = 0?

// Does this code work when i = n-1?
// Does this code work when i = n?

4.4.8 erase
https://www.youtube.com/watch?v=D7h9eQ2pkTI
To delete the value at an arbitrary position, 𝑖, in the list, we need to traverse to
the link before 𝑖, i.e. 𝑖 − 1. The next pointer at 𝑖 − 1 needs to point to the link
at 𝑖 + 1. This removes the link from the list after that we free the memory for
link 𝑖. We need to be careful to store the address of the link that we’re deleting
4.5. ITERATORS 49

so that we can deallocate the memory – otherwise, we would have a memory

leak.
Show/Hide Code
// Left as an exercise to the reader

4.4.9 Size
https://www.youtube.com/watch?v=XkJvvm-1e7w
To get the size of the list we simply traverse from the front to the back counting
the number of links until we reach the nullptr.
Analysis: In Big-Oh notation, how many operations will this function take?
How can we alter the structure so that this happens in 𝑂(1)?

4.5 Iterators
4.5.1 What?
An iterator is an object that allows the programmer to traverse a container.
Think of an iterator like a more sophisticated pointer. A C++ iterator5 must
provide two functions:
1. The dereference operator – T& operator*() – which returns a reference
to the current object.
2. The increment operator – operator++() – which advances the iterator to
the next object in the container.
In C++, all containers should have begin and end functions which return it-
erators. The begin function should return an iterator that references the first
item in the container, while the end function should return a ‘one past the end’
iterator – this is an iterator that we would get if we called the increment oper-
ator one last time after hitting the last object. You should never dereference a
one past the end iterator.
For vectors/arrays, pointers satisfy all the requirements of an iterator.
Thing* MyVector::begin(){
return data;
}
Thing* MyVector::end(){
return data+n_items;
}

The dereference (*) operator follows the pointer to the relevant object and
because the objects are all contiguous, the increment (++) operator advances
5 http://www.cplusplus.com/reference/iterator/
50 CHAPTER 4. LINKED LISTS

the pointer from object 𝑖 to 𝑖 + 1. Links in a linked list are not contiguous so
this kind of pointer arithmetic will not work here. We need to build an iterator
that acts in the same way, but knows that when incremented it should follow
the next pointer in the link.

The iterator should store a pointer to a link in the list. The dereference operator
should return a reference to the value in the link. The increment operator
should advance our link pointer to the following link using next. For example:
class LinkedListIterator{
private:
Link* pointer;
public:
// Default constructor: The iterator contains a nullptr
// This represents a one-past-the-end iterator
LinkedListIterator() : pointer(nullptr) {}
// The iterator should store a link to the pointer provided
LinkedListIterator(Link* p) : pointer(p) {}

Thing& operator*(){
return pointer->value; // Return the relevant value
}
LinkedListIterator& operator++{
pointer = pointer->next; // Traverse to the next link in the chain
return *this; // We need to return a reference to this LinkedListIterator
}
};

We can then write the begin() and end() functions for our LinkedList as
follows:
LinkedListIterator LinkedList::begin(){
return LinkedListIterator(head); // Pointer to the first link
}
LinkedListIterator LinkedList::end(){
return LinkedListIterator(); // Pointer one past the last link (nullptr)
}

4.5.2 Why?
The obvious question is then: why do we care about iterators when we know how
to access the items already? The answer is abstraction. By using iterators to
traverse the container, it doesn’t matter what the underlying container is, the
Standard Template Library (STL) is written so that many of the algorithms
only need an iterator to function. This means that as long as your container
provides the correct iterators, then you can use all the built-in algorithms that
come with C++.
4.6. DOUBLY LINKED LISTS 51

To manually iterate over a vector we could write:

for(int i = 0; i < myVector.size(); ++i){
cout << myVector[i] << endl;
}

To manually iterate over a linked list we could write:

for(Link* curr = myList.head;
curr->next != nullptr;
curr = curr->next){

cout << curr->value << endl;

}

Both code segments above are correct and are equally efficient. However, the
code for each looks really different. This is undesirable as it makes the code
harder to read and harder to write. It means that we need to know the type
of container before we can print the values. If we rewrite the loop in terms of
iterators, then the same loop works for both types of container:
// auto tells the compiler to figure out what type the curr and end variables should be
// Thing* for MyVector / LinkedListIterator for LinkedList
for(auto curr = myContainer.begin(), end = myContainer.end();
curr != end;
++curr){
Thing& val = *curr; // Thing&

cout << val << endl;

}

We now have one for loop that can handle both types of container – if we
decided to swap between Vectors or Linked Lists or any other containers we
wouldn’t need to adjust our printing code. This pattern was so common that it
was officially added into the language as range-based for loops6 which were
introduced in C++11 and extended in C++20. The compiler will translate the
range-based for loop below into the code above before compiling.
for(Thing& val : myContainer){
cout << val << endl;
}

4.6 Doubly Linked Lists

https://www.youtube.com/watch?v=99cNf17MEAc
In the previous sections, we discussed ‘Singly Linked Lists’ which correspond
6 https://en.cppreference.com/w/cpp/language/range-for
52 CHAPTER 4. LINKED LISTS

to the forward_list<T> container in the STL.7 The links/nodes only contain

pointers to the next item in the list and the list itself only contains a pointer to
the head. There is no tail pointer and it does not keep track of its size.

If we would like to be able to access the last link in 𝑂(1) time, then we could
also keep track of a tail pointer which we update whenever necessary. Consider
how this affects the implementation and complexity of all the functions above.
There is no container in STL that corresponds to a forward_list with a tail
pointer.

In contrast to the ideas above, it might be useful to be able to traverse the

container backwards as well. In this case, each link should store a next pointer
as well as a prev pointer. These pointers allow us to traverse forwards and
backwards respectively. This corresponds to the list<T> container in the STL.8
This structure stores both head (first link) and tail (last link) pointers as well
as the number of links in the list.9

Consider how all of the functions and analysis in the previous sections would
need to be adjusted for a doubly-linked list. Doubly linked lists will be exam-
inable.

4.7 Other Linked List Structures

There are other types of linked lists, such as Circularly Linked Lists and skip
lists as well.

• A Circularly Linked List is a forward_list where the last link’s next

pointer points to the first link.
• A Circular Doubly Linked List is similar, except that there are both next
and prev pointers. These are sometimes used when implementing certain
types of Heaps, which we will study later on in this course.
• A Skip List is a linked list where we can jump much further ahead in
the list through an express lane. These structures are very clever and
can give us 𝑂(𝑙𝑜𝑔𝑛) access times rather than linear time. Examining the
complexity of a skip list involves probabilistic complexity analysis which
you will learn in Honours.

7 http://www.cplusplus.com/reference/forward_list/forward_list/
8 http://www.cplusplus.com/reference/list/list
9 Interestingly, storing the size was only required in C++11. In C++98 the complexity

requirement of the size function was ‘up to linear’. This means that the compilers could
implement it using either approach. When the complexity requirements became 𝑂(1) in
C++11, the compilers were forced to keep track of the size.
4.8. DRAWBACKS OF LINKED STRUCTURES 53

4.8 Drawbacks of Linked Structures

4.8.1 Linear Searches
One of the significant drawbacks of a linked list is that you usually have to
perform a linear search to get to the link that you want to access. Even worse,
if you actually had a sorted list, you still wouldn’t be able to do a binary search
because you would need to traverse to the centre node each time, which is 𝑂(𝑛)
and entirely defeats the point of the 𝑂(𝑙𝑜𝑔𝑛) binary search.

4.8.2 Locality of Reference – Caching

In modern computers, there is usually a small amount of cache memory on the
CPU. When you access an item in memory, the cache remembers its value so
that if you access it again, then the second call is faster – the number is already
saved in the faster cache memory, so we don’t need to fetch it from RAM. This
is called Temporal Locality.
When we have lots of data we usually place the data in contiguous blocks of
memory (like in an array/vector) or in a class where the data members are
usually next to each other. This means that if we access data at address 𝑖 it is
likely that we’ll access data at address 𝑖 + 1. Because this is so common, the
cache will load the content of neighbouring memory blocks when we ask for the
content at 𝑖. If we now ask for content at 𝑖 + 1 it is already in the cache and
the value is returned faster than if we had to fetch it from RAM. This is called
Spatial Locality.
When we ask for a value, it is a cache hit if it is already in the cache. If it is not
in the cache and we need to fetch it from RAM, then it is a cache miss. Because
the memory is contiguous when using arrays, we usually have lots of cache hits.
In practice, this means that arrays are often faster than linked lists even when
you don’t expect them to be.10

4.8.3 Be Careful
In general, you should be aware that linked structures can be more inefficient
than we expect, with traversals and caching/locality both playing a role. This
translates into other languages as well, such as Lists in Java/Python/JavaScript
etc. These structures have their place, but ensure that the actual behaviour of
the structure on your hardware is as you expect.
Here is a great talk by the creator of C++, Bjarne Stroustrup, where he
compares the run times of Vectors and Linked Lists with surprising results:
https://www.youtube.com/watch?v=YQs6IC-vgmo
10 Remember that we noted earlier that 𝑂(⋅) hides the constants associated with the different

operations, but also assumes that the operations themselves take the same amount of time –
e.g. assignment always takes the same amount of time. Caching breaks this assumption and
in some cases, the memory access patterns may be more important than we’d otherwise think.
54 CHAPTER 4. LINKED LISTS

Here is a more recent video by Computerphile, where they run several experi-
ments to investigate the efficiency of the different structures. https://www.yo
utube.com/watch?v=DyG9S9nAlUM

4.9 Lab
https://www.youtube.com/watch?v=pMcYt5fHvdw
In the next lab, you need to implement your version of a forward_list along
with additional copy and reverse functions. Relevant unit tests and function
descriptions will be provided.
class Thing;

class Link{
public:
Link *next = nullptr;
Thing value;
};

class LinkedListIterator{
public:
Link* ptr = nullptr;

Thing& operator*();
LinkedListIterator& operator++();
};

class LinkedList{
public:
Link* head = nullptr;

LinkedList();
~LinkedList();

void push_front(Thing t);

void pop_front();

void push_back(Thing t);

void pop_back();

size_t size();

Thing& front();
Thing& back();
4.10. ADDITIONAL READING 55

Link* get_link(int i);

Thing& at(int i);

LinkedListIterator begin();
LinkedListIterator end();

LinkedList* copy();
void reverse();
};

4.10 Additional Reading

1. https://www.geeksforgeeks.org/data-structures/linked-list/
2. Chapter 3.2 (Singly Linked Lists), 3.3 (Doubly Linked Lists), 3.4 (Circu-
larly Linked Lists & Reversals) – Goodrich et al. (2011)
3. Chapter 3.2, 3.3, 3.5 – Weiss (2014)
4. http://www.cplusplus.com/reference/forward_list/forward_list/
5. http://www.cplusplus.com/reference/list/list/
56 CHAPTER 4. LINKED LISTS
Chapter 5

Stacks

5.1 Introduction
https://www.youtube.com/watch?v=0hHsu_llV-0
Often we would like to keep track of objects or events in a way that allows
us to access the newest/most recent one first. For example, we have seen the
Call Stack which keeps track of functions and makes sure that the functions are
always ordered from the most recent call (i.e. the function that we’re currently
in) to the oldest call (i.e. the main function). When we call a new function,
its stack frame (memory for automatic variables, program counter/line number
etc.) gets added to this structure and when the function returns, then that
frame is removed from the structure. We are always working on the same end of
the structure: adding and removing items that are the most recent. This type of
structure follows a Last In First Out (LIFO) structure,1 because the last thing
that we added, is the first one that can be removed. This type of structure is
called a Stack and is illustrated in Figure 5.1.
When a new pancake has been cooked we always place the new pancake on
top of the stack. When we remove a pancake,2 we always remove the pancake
which is on top – this means that the pancake we remove is always the one that
was cooked most recently. The last pancake placed onto the stack is the first
pancake we remove from the stack and devour. Beyond this, we can add and
remove pancakes arbitrarily: you’re cooking, I’m eating… You place p1 onto the
stack [p1], then you place p2 onto the stack [p1, p2], then you turn around
and I remove p2 and eat it [p1], you come back and place p3 onto the stack
[p1, p3], then you place p4 onto the stack [p1, p3, p4], then you place p5
onto the stack [p1, p3, p4, p5], then I eat p5 [p1, p3, p4], then p4 [p1,
p3], then p3 [p1]… Then you eat p1, which is probably cold by now anyway.
1 Or equivalently, First In Last Out (FILO)
2 And remember that we only remove 1 pancake at a time because we’re not a glutton.

57
58 CHAPTER 5. STACKS

Figure 5.1: A Stack of Pancakes

https://www.youtube.com/watch?v=ya-E2aYI3WQ
Stacks are very useful structures whenever we want to be able to retrace our
last steps. Think of the undo button in any computer program. As you perform
different operations, the program stores each action on a stack. The most recent
thing that you did is on top of the stack and the most recent thing after that is
underneath it. If you hit undo, it will remove the last action that you did from
the top of the stack and do the opposite action. If you hit undo again, it will
remove the second last action from the stack and reverse that action. As you
perform an action it is added to the top of the stack, as you hit undo, the action
on top of the stack is removed and then reversed in the program. Go to your
favourite word processor and play around with the undo button. Think about
what the stack would look like at each point.
https://www.youtube.com/watch?v=NzIfJW2WeGM
There are plenty of other examples of stacks that you use every day. Think
about how the examples below form a stack and how objects would be added
or removed.
1. The back button in your browser.
2. The forward button in your browser. When do pages get added to this
stack?
3. Views/activities/pages in a mobile application (imagine navigating for-
ward and backwards through the settings page of an app).
4. Recursive function calls in a C++ program.
5. Retracing your steps after hitting a dead-end in a maze.
5.2. OPERATIONS 59

You can see in the examples above, we often use stacks to keep track of decisions
that we have made, and then use the stack to retrace our steps if we decide that
we have made a mistake. This is how we can implement a class of algorithms
called backtracking algorithms. You came across this idea previously in IAP
when you discussed how to solve a Sudoku by using a recursive function. That
algorithm used the call stack to keep track of your actions when you realised
you’d made a mistake, the function returned false and the previous function
resumed after undoing the changes you’d made – Figure 5.2. Later on in this
chapter, we’re doing to talk about how to implement a backtracking algorithm
without recursion, by managing the stack ourselves.
There are lots of other problems that can be solved with backtracking algorithms.
Some of these are discussed further here https://www.geeksforgeeks.org/back
tracking-algorithms/.
Before we move on to how we can use stacks, let’s first talk about the interface
of the Stack ADT (Section 5.2) followed by some implementations (Section 5.3).

5.2 Operations
A Stack is a fairly simple ADT. It has only 4 important functions. Note that
there is no operator[] or at function because we are only ever allowed to
access the item on top of the stack. The only way to access other items would
be to pop off items until the one we wanted was at the top. In general, if you
need “random access” to access arbitrary items in the container, then a stack
is probably the wrong data structure and you should consider using something
else.
Assume that T is the type of object stored in the list, e.g. int.
1. void push(T value)
• Add value to the top of the stack.
2. void pop()
• Remove the item from the top of the stack.
3. T& top() or sometimes T& peek()
• Return a reference to the top item.
4. size_t size()
• Return the number of items in the stack.
https://www.youtube.com/watch?v=x9y0I_Horjk

5.3 Implementations
There are two main implementations for a stack, one is based on contiguous
memory, the other is based on a linked list.
https://www.youtube.com/watch?v=WWP5AoBAR60
60 CHAPTER 5. STACKS

5.3.1 Vector Implementation

https://www.youtube.com/watch?v=fJvAQk_UDeU

5.3.2 Linked List Implementation

https://www.youtube.com/watch?v=dOswfRwwXZI

5.4 std::stack<T, C>

The C++ Standard Template Library provides the std::stack template class
– http://www.cplusplus.com/reference/stack/stack/. This class uses an
underlying container such as a vector or list but can use any container that
provides the empty, size, back, push_back and pop_back functions. By default
it uses a double-ended queue (deque) as the underlying container – we’ll discuss
this structure later on in the course – this is a sensible default and is usually
the right choice.
https://www.youtube.com/watch?v=ZyLA0W9c42Y
You can create a std::stack in the following ways:
#include <stack>

using std::stack;
class Thing;

// Stack of Things, underlying container: deque<Thing>

stack<Thing> s0;
// Stack of Things, underlying container: deque<Thing>
stack<Thing, deque<Thing>> s1;
// Stack of Things, underlying container: vector<Thing>
stack<Thing, vector<Thing>> s2;
// Stack of Things, underlying container: list<Thing>
stack<Thing, list<Thing>> s3;

5.5 Applications
5.5.1 Postfix Notation
When we’re doing arithmetic, we use infix notation to represent the operators
and operands of a formula. This means that the operator (+ - x ÷) acts on the
operands which are on either side of it – the operator is in the middle, e.g. a +
b.
In the 1920s a Polish mathematician, Jan Łukasiewicz, invented Polish Notation.
He showed that by writing the operators in front of the operands you no longer
5.5. APPLICATIONS 61

need brackets to disambiguate the order of operations, e.g. + a b. Reverse Pol-

ish Notation (RPN) was then proposed by Philosopher and Computer Scientist,
Charles Hamblin. In this approach, the operators come after the operands. The
benefit of this is that the operators all appear in the order that they will be
evaluated. This approach is also called postfix notation because the operators
are after the operands, e.g. a b +.

RPN was used in the instruction language of the English Electric computers
in the 1960s. Hewlett-Packard engineers found that by requiring the user to
enter instructions in RPN, the electronics inside their early calculators could be
dramatically simplified. This means that users needed to learn the new notation,
but that the number of components in and therefore the cost of the calculators
could be reduced. In 1968, the HP9100A became the first calculator to use RPN
and is widely considered to be the first desktop computer.
By using RPN, the machine does not need to parse the formula first and in-
termediate values do not need to be written down as brackets are completely
unnecessary. These days, machines are powerful enough that parsing or under-
standing the infix formulae does not cost much computational time. Similarly,
transistors are so small and cheap, the extra hardware required to do this does
not affect the price or size.
Several modern calculators like the HP12C still use this notation and if you take
the Wits Actuarial Science course you are likely using one!

To evaluate a postfix expression, we perform the following algorithm and make

use of a stack to store the intermediate results which form the operands. When
we read a number, we push it to the stack, when we read an operator we pop
as many operands as are required, perform the operation, and then push the
result back onto the stack.

INPUT: Tokens of the postfix expression

OUTPUT: Evaluation of the expression

Initialise empty stack s

for each token in the postfix expression:
if token is a number:
push it to the stack
else if is an operator:
pop k numbers off of the stack
perform the operation
push the result back onto the stack
There should be 1 number remaining on the stack
RETURN this number as the result of the expression

There is a straightforward algorithm that also uses a stack, to convert an infix

formula into a postfix one. If you were building your own calculator, you could
62 CHAPTER 5. STACKS

accept an infix expression (10+5*2), convert it into a postfix expression (10 5

2 * +) and then evaluate it using the postfix algorithm above.
This technique is used extensively by compilers as they convert your source code
into machine code.
https://www.youtube.com/watch?v=4dvHdUHpgWY

5.5.2 Depth First Search

Searching through a Maze
We mentioned earlier that Stacks are often used when we need to retrace our
steps or backtrack. When we have a search space (e.g. a maze), we can perform
a systematic search of the maze by doing a Depth First Search. This means
that we make a decision about which direction to take at the first junction and
then try every path from there. If we hit a dead end, we go back to the last
decision we made and change it. The idea here is that we go deep down a path
until we’re forced to turn back. 3
https://www.youtube.com/watch?v=TLC83mz9XS8

Solving Sudoku
THe kind of search explained above does not always have to happen in a maze
or other ‘physical space’. We can think of each position in a search space cor-
responding to a different state of the world as well. In the maze above, each
decision was one of four directions. When solving sudoku, each decision involves
setting the value of a cell to one of nine numbers. In the maze, we followed a
path until we hit a dead end and couldn’t make any valid turns. When solving
a sudoku, we can make a decision (i.e. place a number in an empty block) and
then check if the state of the board is valid. If so, then we can make that move
and try all boards that lead on from that state. If none of those boards are
solvable, then we must have made an incorrect move and we need to change
that decision (i.e. that number needs to be updated to a different number).
At each decision, we push our action onto the stack. If we later realise that
there are no valid boards from this decision onwards (i.e. we made a decision
that leads us to a dead-end), then we can pop that action off the stack, try the
next action, and then check those boards.
We will formalise this algorithm below, where we consider your first project.
In IAP you saw this code when learning about recursion:
This code is doing the same thing! This code is a recursive implementation of
a Depth First Search. It uses the call stack to keep track of decisions and, as
each function returns, the previous state of the sudoku can be restored.
3 The alternative is to keep track of many paths at the same time where we go wide and

we call this a Breadth-First Search, which we will cover in the next chapter.
5.6. LAB 63

Figure 5.2: Sudoku Pseudocode from IAP

5.6 Lab
You need to implement both types of stack: based on a vector and based on a
linked list.

Here is the interface for a stack:

class Thing;

class Stack{
public:
// Add t to the top of the stack
void push(Thing &t);
// Remove the top item from the stack
void pop();
// Return a reference to the top item in the stack
Thing& top();
// Return the number of items in the stack
size_t size() const;
// Return true/false based on whether the stack is empty
bool empty() const;
public:
vector<Thing> data; // list<Thing> data;
};

You should make use of the relevant functions from the vector (vector<Thing>)
64 CHAPTER 5. STACKS

and linked list (list<Thing>) structures from the Standard Template Library
(STL). Both implementations should look remarkably similar.

5.7 Project: Solving Sudokus

You need to write a sudoku solver using a Depth First Search. Your code must
output the correct solution for a given input. The size of the sudoku will vary
(4 × 4, 9 × 9, 16 × 16, 25 × 25). Part of your grade in this project will be
competitive – based on the amount of time it takes your submission to solve an
𝑛 × 𝑛 sudoku and how well it scales.
https://www.youtube.com/watch?v=X17Bt9muwkg
Grades will be awarded as follows:

Description Grades
Auxiliary Functions. 30%
Solves a 9 × 9 sudoku correctly. 30%
Solves a 16 × 16 sudoku correctly. 10%
Solves a 25 × 25 sudoku correctly. 5%
Time taken to solve a 9 × 9 sudoku. 10% [based on speed ranking]
Time taken to solve a 16 × 16 sudoku. 10% [based on speed ranking]
Time taken to solve a 25 × 25 sudoku. 5% [based on speed ranking]

More details, as well as the test cases, will be released soon.

5.8 Additional Reading

1. https://www.geeksforgeeks.org/stack-data-structure/
2. Chapter 5.1 (Stacks) – Goodrich et al. (2011)
3. Chapter 3.6 – Weiss (2014)
4. Chapter 5.1 and 5.2 – Dale et al. (2018)
5. http://www.cplusplus.com/reference/stack/stack/
6. https://ocw.mit.edu/courses/civil-and-environmental-engineering/1-
00-introduction-to-computers-and-engineering-problem-solving-spring-
2012/lecture-notes/MIT1_00S12_Lec_35.pdf
7. https://www.geeksforgeeks.org/backtracking-algorithms/
Chapter 6

Queues

6.1 Introduction
In the previous chapter, we discussed the idea of a stack that allowed us to access
the most recent item. This enables us to implement a class of algorithms called
backtracking algorithms because to undo the most recent action, we could check
the top of the stack. In many algorithms, we need to do a similar operation,
but we need to access the first item that was added, i.e. the one that arrived
first. This type of structure forms a Queue. Just like every queue you’ve ever
stood in, we add to the back and remove from the front. A queue is known as
a First In First Out (FIFO) structure.
We often use queues when we need to process objects in the order that they ar-
rive. For example, when you are typing on the keyboard the hardware generates
a keypress event which stores which key was pressed. The operating system
gets notified of the event through an interrupt and it adds it to an event queue
for our program to process. When our program is running, we can ask the OS
to give us each event to process. The events must be given to us in the same
order that they were generated, otherwise, we’d receive mixed up data.

Figure 6.1: Pizza queue at Zesty Lemonz during lunch.

https://www.youtube.com/watch?v=p5ByAjY0NZM

65
66 CHAPTER 6. QUEUES

This is such a common process that when writing games we often create an
event loop that looks something like the code below.1 In the code below, the
operating system will add SDL_Event objects to the event queue. When we
call SDL_PollEvent it will check whether there is an event in the queue, if there
is, it will remove it from the front and place it into e. We can then check what
type of event it is and update the state of our game (e.g. change the position
of the character). Once we have handled the event, our loop repeats and we
check whether there is anything else in the event queue. if there is nothing in
the queue, then we update the state of our game (e.g. did the character collect
treasure in this move?) and redraw the updated image to the screen. Then our
main loop repeats and we check for more input events from the user.
while(!quit){
// This object contains the event information
SDL_Event e;

// Ask for an event from the queue

// While there are events, remove from the queue and process
while(SDL_PollEvent(&e)){
if(e.type == SDL_QUIT){
// If the window was closed
quit = true;
}else if(e.type == SDL_KeyboardEvent){
// Handle a keyboard button
handle_keyboard_event(e);
}else if(e.type == SDL_MouseButtonEvent){
// Handle a mouse button
handle_mouse_event(e);
}
}

// Update the game state.

update_state();
// Draw to screen.
draw();
// Repeat
}

In the example above, the operating system added events to the back of the
queue and our program removed events from the front. With a stack, we could
only ever access the item at the top. With a queue, we can only ever access
the item at the front. If you need to access another item in the container, then
you’re using the wrong structure.

1 This is based on the SDL framework. If you’re using a high-level framework like Unity or

a language like Java, then the event loop and dispatch will usually be done automatically for
you.
6.2. OPERATIONS 67

Whenever you want to process data in the order that it arrives, then a queue is
the correct data structure to use. Some examples of queues include:
1. Event Queues.
2. Print Queues.
3. Wits in-person registration queues.
4. Asking Richard questions during tutorials.
5. A Breadth-First Search – Section 6.5
Again, just as with the stack, we can implement it using linear data structures
that we have already built: vectors and lists. Although we’ll see that using
vectors directly leads us to an inefficient implementation and in this case if
we want to use contiguous memory, then we should implement something new
called a Circular Array.

6.2 Operations
A Queue is a very simple ADT. It has only 4 important functions. Note that
there is no operator[] or at function because we are only ever allowed to access
the item at the front of the queue. The only way to access other items would
be to dequeue/pop off items until the one we wanted was at the front – except
then we wouldn’t be able to replace those items at the front as we can only add
at the back. In general, if you need “random access” to access arbitrary items
in the container, then a queue is probably the wrong data structure and you
should consider using something else.
Assume that T is the type of object stored in the queue, e.g. int.
1. void push(T value) or void enqueue(T value)
• Add value to the back of the queue.
2. void pop() or void dequeue()
• Remove the item from the front of the queue.
3. T& peek() or T& front()
• Return a reference to the front item.
4. size_t size()
• Return the number of items in the queue.
https://www.youtube.com/watch?v=xt34AwFIi-g

6.3 Implementations
We will consider two implementations of a queue, one is based on contiguous
memory, the other is based on a linked list.

6.3.1 Contiguous Implementation

https://www.youtube.com/watch?v=Z_vk_juVtuM
68 CHAPTER 6. QUEUES

6.3.2 Linked List Implementation

https://www.youtube.com/watch?v=w4cAPdqv-n8

6.4 std::queue<T, C>

The C++ Standard Template Library provides the std::queue template class
– http://www.cplusplus.com/reference/queue/queue/. This class uses an
underlying container such as a deque or list but can use any container that
provides the empty, size, front, back, push_back and pop_front functions.
By default it uses a double-ended queue (deque) as the underlying container.
This is a sensible default and is usually the right choice as a deque contains
pop_front and push_back functions that are both 𝑂(1) time.
You can create a std::queue in the following ways:
#include <queue>

using std::queue;
class Thing;

//Good:
// Queue of Things, underlying container: deque<Thing>
queue<Thing> q0;
// Queue of Things, underlying container: deque<Thing>
queue<Thing, deque<Thing>> q1;
// Queue of Things, underlying container: list<Thing>
queue<Thing, list<Thing>> q2;

//Bad:
// Queue of Things, underlying container: vector<Thing>
// This is a compile error because vector does not have a pop_front
queue<Thing, vector<Thing>> q3;
// Queue of Things, underlying container: forward_list<Thing>
// This is a compile error because forward_list does not have a push_back
queue<Thing, forward_list<Thing>> q4;

6.5 Project – The Shortest Path in a Maze

(BFS)
6.5.1 Breadth First Search (BFS)
The problem of finding the shortest path occurs frequently in applications such
as computer games, satellite navigation, and network routing. For GPS maps
with routing such as Waze and Google Maps, this is their primary function.
6.5. PROJECT – THE SHORTEST PATH IN A MAZE (BFS) 69

These systems work on a structure called a graph, which you’ll learn more
about later in COMS2.
In this project, you will need to calculate a path through a maze using a Breadth-
First Search. This will be useful on the snake game for example, where you may
need to find the shortest path from the head of a snake to the apple so that
you can get there first. Another example is if you were implementing Artificial
Intelligence for the ghosts in Pacman. In this case, the source may be the ghost’s
current position, and the goal would be Pacman’s current position.2 You will
implement the BFS algorithm in a new program that will be submitted to
Moodle for automatic marking.
https://www.youtube.com/watch?v=3QYk3vKuXVY

6.5.2 Algorithm
Because each step in the path towards the goal costs the same (uses the same
amount of energy/takes the same amount of time/etc), we can use a standard
breadth-first search to find the shortest path. The first path found that starts
at the source and ends at the goal will be the shortest path.3 Starting at the
source, the algorithm proceeds as follows:
1. Starting at the source, find all new cells that are reachable at distance
1, i.e. all paths that are just 1 unit in length, and mark them with that
length.
2. Using the distance 1 cells, find all new cells which are reachable at distance
2.
3. Using all cells at distance 2 from the source, find all cells with distance 3.
4. Repeat until the target is found. This expansion creates a wavefront of
paths that search broadly from the source cell until the target cell is hit.
5. From the target cell, select the shortest path back to the source and mark
the cells along the path.
This ‘wavefront’ is called the fringe – the edge of what we’ve seen so far. At each
iteration, we take a cell from the fringe and look at its undiscovered neighbours.
Note that if it takes 𝑛 steps to get to an item in the fringe, it then takes
𝑛 + 1 steps to get to any of its undiscovered neighbours. By checking all paths
of length 𝑛 first, we can be sure that there is no quicker way to get to an
undiscovered neighbour.4 The fringe can be represented using a queue, this
2 Technically, in Pacman the ghosts (Blinky, Pinky, Inky and Clyde) have different goals.

Blinky aims directly at Pacman, Pinky aims two blocks ahead of Pacman, Inky aims 2 blocks
ahead of Pacman but with the distance doubled based on the distance between the ghost and
Pacman. Finally, Clyde will chase Pacman just like Blinky, unless he is fewer than 8 tiles
away, in which case Clyde will retreat to the bottom left corner of the map. In each case, a
BFS could be used to find the shortest path to the goal.
3 This would not be the case if different steps cost different amounts. In that case, you’d

need to use a priority queue in the BFS, which leads you to an implementation of Dijkstra’s
algorithm. You will be doing this next year.
4 See if you can prove this, try a proof by induction and/or contradiction.
70 CHAPTER 6. QUEUES

means that in iteration 𝑖, dequeue a cell from the fringe and enqueue all of its
unvisited neighbours, which will have a path length of 𝑖 + 1. Because the fringe
is FIFO, we will dequeue all cells at level 𝑖 before we dequeue any cells at level
𝑖 + 1. It turns out that this is a simplified, special case of Dijkstra’s algorithm
for finding the shortest path in a graph. You’ll learn more about this next year.

Figure 6.2: BFS Wavefront

6.5.3 Examples
The figures below show how the wavefront propagates through the maze and
around obstacles. The red blocks indicate the cells in the fringe (wavefront).
The green blocks indicate the start and endpoints. The numbers show how
many steps we must make to get from the start point to the relevant block.

6.5.4 Pseudocode
When running on a grid where each step costs the same, the shortest path
algorithm reduces to a normal breadth-first search. In the algorithm that follows,
we make use of a queue to keep track of the fringe. We use a parent array to
keep track of the row/column indices of the cell through which we travelled on
the way to the current cell. The distance array keeps track of how long the path
is to get from the source to the current cell. When we have found a path to
the goal, we follow the parent array back to the source and reverse it to get the
shortest path from the source to the goal.
Note: While it doesn’t affect the correctness of your algorithm in general, for
the marker it is important to visit neighbours of the current cell in the correct
order: down, left, up, right.

6.5.5 Sample Input/Output

You will receive the following input format on stdin:
6.5. PROJECT – THE SHORTEST PATH IN A MAZE (BFS) 71

Figure 6.3: BFS Examples

72 CHAPTER 6. QUEUES

Figure 6.4: BFS Examples

6.5. PROJECT – THE SHORTEST PATH IN A MAZE (BFS) 73

1. The first line will contain 2 integers, m and n, separated by a space. These
numbers represent the number of rows and columns in the grid respec-
tively.
2. There will then be m lines each with n columns that represent the maze.
• A space represents an open block in the world. You may travel
through this block.
• An x represents an obstacle. You may not travel through this block.
• An S represents the start.
• A G represents the goal.
3. The output should be the maze with * characters along the shortest path
from the start to the goal. 1 If there is no path between the start and
goal, then the output should say No Path.

maze1.txt maze2.txt maze3.txt

14 17 14 17 14 17
xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx
x x x x x x x x
x x x xxxx x x x xxxx x x
x S x x xxxxx S x x xxxxx S x
x x x x xxxx x x x xxxx x
x x x xxx xxxxx x x xxx xxxxx x
x x xxxxxx x xxxx xxxxxx x xxxx
x x x x x x x x
x xxxxxxxxx x x xxxxxxxxxxxx x xxxxxxxxxxxxxxx x
x x x x x x x x x x
x x xxxx x x x Gx xxxx x xxxx Gx xxxx x xxxx
x x Gx x x x x x x x x
x x x x x x x x
xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx

Output1: Output2: Output3:

xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx No Path
x x x******x*** x
x x x*xxxx***x* x
x S x x* xxxxx***S x
x * x x******x xxxx x
x * x x xxx*xxxxx x
x * x xxxxxx* x xxxx
x * x x ***** x x
x xxxxxxxxx * x x *xxxxxxxxxxxx x
x x * x x * x x
x x xxxx x * x x Gx xxxx x xxxx
x x Gx * x x x x x
x x **** x x x x
xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx
74 CHAPTER 6. QUEUES

6.5.6 Submission & Grading

Submit a single cpp file to Moodle. Moodle will attempt to compile and run
your file with the following command:
g++ -g -std=c++11 source.cpp -o bfs
./bfs < maze.txt

You may use any built-in C++11 STL types that you think are useful.
There are many test cases on Moodle that handle various mazes with and with-
out valid paths and that will test several edge cases in your code.

6.6 Additional Reading

1. https://www.geeksforgeeks.org/queue-data-structure/
2. Chapter 5.2 (Queues) – Goodrich et al. (2011)
3. Chapter 5.3 (Double-Ended Queues) – Goodrich et al. (2011)
4. Chapter 3.7 – Weiss (2014)
5. Chapter 5.3 and 5.4 – Dale et al. (2018)
6. http://www.cplusplus.com/reference/queue/queue/
7. https://ocw.mit.edu/courses/electrical-engineering-and-computer-scie
nce/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-
13-breadth-first-search-bfs/ or https://www.youtube.com/watch?v=s-
CYnVz-uh4
8. https://towardsdatascience.com/graph-theory-bfs-shortest-path-proble
m-on-a-grid-1437d5cb4023
9. https://medium.com/analytics-vidhya/part-i-breadth-first-search-using-
grid-dc41a5f41663
Chapter 7

Binary Search Trees

7.1 Trees
https://www.youtube.com/watch?v=AMESParVjOA

Up to this point we have dealt with linear data structures. In some sense, the
items were always stored one after the other. There was always some kind
of linear arrangement to the way that the data was stored and there was the
concept of the next item in the structure. From here onwards, we will focus on
data structures that are non-linear. We will consider various types of trees and
the algorithms associated with them.

Trees allow us to model hierarchical relationships between data where there is

a parent and a child. For example, a filesystem has directories that can contain
other subdirectories and files. A directory is the parent of all the items inside
it and the items inside the directory are the children.

Another reason to use a tree is when we have large amounts of data and the ac-
cess and search times associated with lists become too expensive. By organising
data in a tree, we can achieve search times of 𝑂(𝑙𝑜𝑔𝑛) in comparison to 𝑂(𝑛)
that we would usually get when searching through a vector or linked list. This
change might not seem substantial, but note that a running time of 𝑂(𝑙𝑜𝑔𝑛) is
exponentially faster than 𝑂(𝑛).1 If there are 1 million items in a vector, then
a linear search would perform 1 million comparisons in the worst case. With
a balanced binary tree, we could search the entire list for a number under 20
comparisons. In fact, this is how database systems work – they build an index
using some kind of balanced binary tree (usually a B-Tree) which allows for
exceptionally fast lookups even when there is a very large amount of data to
search through.
1 Literally, exponential speedup in the mathematical sense: 2𝑙𝑜𝑔2 𝑛 = 𝑛

75
76 CHAPTER 7. BINARY SEARCH TREES

We represent a tree as a set of vertices and edges. Each vertex represents a

value that is stored in the tree and each edge represents the connection between
a parent and a child. Every vertex has exactly 1 parent, except for the root
which does not have a parent.
“A tree is a collection of nodes. The collection can be empty; other-
wise, a tree consists of a distinguished node, r, called the root, and
zero or more nonempty (sub)trees 𝑇1 , 𝑇2 , … , 𝑇𝑘 each of whose roots
are connected by a directed edge from r.”
— Weiss (2014)
A tree then has 𝑛 − 1 edges. A path from node 𝑛𝑗 to 𝑛𝑘 is a sequence of nodes
such that there is an edge between any two consecutive nodes in the sequence.
The length of the path is the number of edges that would be traversed moving
from 𝑛𝑗 to 𝑛𝑘 .
A node can have any number of children. Nodes that share the same parent are
called siblings. A node is called an internal node if it has one or more children.
A node that has no children is called a leaf. The depth of a node is the length
of the path from the root to that node. The height of the tree is the length of
the longest path from the root to any leaf.
If we speak of a subtree that is rooted at 𝑛𝑘 , this means we are speaking of the
node 𝑛𝑘 and all of the edges and vertices that are descendants of that node.

7.2 Binary Trees

https://www.youtube.com/watch?v=xq5Vyf2ejiM
A tree where every node has a maximum of two children is called a Binary Tree
and in this case, we can speak of the left and right subtrees. We can speak of
the level of a node, the root has level 1, its children are on level 2 etc. A child’s
level is the parent’s level +1. A binary tree of height ℎ will have ℎ + 1 levels. A
binary tree with 2𝑘 nodes in level 𝑘 is called a perfect binary tree. A binary tree
where each node has zero or two children is called full or proper. A tree that is
perfect up to level ℎ and then fills up from the left in level ℎ + 1 is called a
complete binary tree.
https://www.youtube.com/watch?v=5fxFqU_5zzQ
Let 𝑛 denote the number of nodes, 𝑛𝑙 denote the number of leaves, 𝑛𝑖 denote
the number of internal nodes and ℎ is the height of the tree. Then the following
relationships hold:
1. 𝑙𝑜𝑔2 (𝑛 + 1) − 1 ≤ ℎ ≤ 𝑛 − 1
2. ℎ + 1 ≤ 𝑛 ≤ 2ℎ+1 − 1
3. 𝑛𝑙 = 𝑛 𝑖 + 1
4. 𝑛 = 2𝑛𝑖 + 1
7.3. BINARY SEARCH TREE 77

5. 𝑛𝑖 = (𝑛 − 1)/2
6. 𝑛𝑙 = (𝑛 + 1)/2
7. 𝑛 = 2𝑛𝑙 − 1
8. 𝑛𝑖 = 𝑛𝑙 − 1

The first relationship is significant and gives us bounds on several algorithms

that run from the root down a path until it reaches a leaf.

7.3 Binary Search Tree

An ordered binary tree is known as a Binary Search Tree (BST). A BST is a
binary tree with the added constraint that all values stored in the left subtree
of node 𝑛𝑘 must be less than the value stored in 𝑛𝑘 and all the values stored in
the right subtree must be greater than or equal to the value stored in 𝑛𝑘 . The
order property must hold for every node in the entire tree.

https://www.youtube.com/watch?v=d7sxjBXEFFc

7.3.1 Insertion
https://www.youtube.com/watch?v=aBZwcZW3Nl8

Inserting a value into a BST requires that we start at the root and compare
the value to be inserted with the value at the current node. If the value to be
inserted is less than the current node’s value, then we should recursively insert
the value into the left subtree, otherwise, we should recursively insert the value
into the right subtree. When we find an empty space in the tree (e.g. we need
to insert into the left subtree and there is no left child) then we create a node
with the new value and insert that node into the space.

In the worst case, our algorithm needs to traverse the tree along the longest
path from the root to a leaf before inserting. In this case, we traverse ℎ nodes
before we can perform the insert. So in the worst case, the amount of work done
is proportional to the height of the tree.

From the relationships in Section 7.2 above, this means that the amount of work
we need to do will depend on the structure of the tree. In the best case, the
height of the tree will be 𝑙𝑜𝑔2 (𝑛 + 1) − 1 and in the worst case, the height of the
tree will be 𝑛 − 1. In Big-O notation, we are interested in the shape of these
functions and so we say that the height is 𝑂(𝑙𝑜𝑔𝑛) or 𝑂(𝑛) respectively.

When the height of the tree is 𝑂(𝑛) we say that the tree is degenerate, and it
has basically become a linked list. In later chapters we will consider algorithms
that help make sure that the tree is always balanced and therefore has a height
that is 𝑂(𝑙𝑜𝑔𝑛).
78 CHAPTER 7. BINARY SEARCH TREES

7.3.2 Searching
https://www.youtube.com/watch?v=iKYzYwaEW2I
If we would like to search for a value, 𝑥, we follow a similar approach. Again we
start at the root and compare 𝑥 with the value of the current node. If it is equal
then we have found the value, if 𝑥 is less than the current node’s value, then
we should recursively search the left subtree, otherwise, we should recursively
search the right subtree. If the subtree being searched is ever empty, then it
means that 𝑥 is not present in the BST.
In the worst case, the number is not in the tree and the path we follow corre-
sponds to the longest path from the root to a leaf. In this case, we traverse ℎ
times, so the amount of work done is proportional to the height of the tree. Just
as in the case of insertion, this means that we will do either 𝑂(𝑙𝑜𝑔𝑛) or 𝑂(𝑛)
depending on the structure of the tree. In the best case, the search key (𝑥) is
the value stored in the root and we do 𝑂(1) amount of work.

7.3.3 Min & Max

https://www.youtube.com/watch?v=HTfr8SZSNOI
The minimum or maximum values in a BST can be found by repeatedly travers-
ing to the left or right.
To find the minimum value, we start at the root and repeatedly traverse left
(curr = curr->left) until we encounter a node that does not have a left child.
This is then the minimum value in the tree. Similarly, by repeatedly traversing
to the right, we will find the maximum value.

7.3.4 Delete
https://www.youtube.com/watch?v=BFoeIkPAa2s
To remove a value from the tree we need to consider what happens to that
node’s children. There are three different cases to consider.
When the node has no children, then we can simply delete the node, and set
the parent’s child pointer to nullptr. This process resembles deleting the last
link in a linked list.
When the node has one child, then we need to set the parent’s child pointer
to point to the current node’s child. After that is done then we can delete the
current node.
Finally, when the node has two children, then we need to replace the value
inside the current node with the successor. This means we need to find the next
largest value in the tree and move it to the current node. We can then delete
that value from the relevant subtree. The next largest value in the BST will
be the minimum value in the right subtree. So we traverse to the right subtree
7.4. TREE TRAVERSALS 79

and then traverse as far left as possible. This value can simply replace the value
that was being deleted, and then we recursively delete that new value from the
right subtree. We are guaranteed that in that case, then it will have zero or one
child and the deletion can take place using the strategies above.
Using the proof techniques from DCS, how do you think you could prove that
the successor does not have a left child?

7.4 Tree Traversals

7.4.1 Depth First Traversals
https://www.youtube.com/watch?v=CY3DMMt3DAM
Sometimes we would like to traverse over the entire tree, visiting each node in
a specified order. We can do this by performing a Depth First Search. At each
step, we can process/print the current value, process all the values in the left
subtree, and process all the values in the right subtree. The order in which we
do this creates three different traversals:
1. Pre-Order Traversal
• Value, Left, Right
2. In-Order Traversal
• Left, Value, Right
3. Post-Order Traversal
• Left, Right, Value
Each of these traversals achieves a different task. The in-order traversal will
give us all of the values in order. This means that we could sort a list by
constructing a BST and then performing an in-order traversal. The pre-order
traversal can be used to serialise the tree. If we perform a pre-order traversal,
we will get a list of numbers that, if used with the standard insertion algorithm,
will recreate the tree. If we perform a post-order traversal, then we can use the
tree to construct postfix expressions as seen in Section 5.5.1.
All of these traversals have elegant recursive implementations:
void BST::in_order_traversal(Node* curr){
if(curr == nullptr) return;

in_order_traversal(curr->left);
cout << curr->value << " ";
in_order_traversal(curr->right);
}

7.4.2 Breadth-First or Level Traversals

https://www.youtube.com/watch?v=gbxvra7q6NM
80 CHAPTER 7. BINARY SEARCH TREES

We could perform a breadth-first search where we visit the nodes in the tree
level by level. We first consider the root (at level 0), then we consider all nodes
at level 1, then all nodes at level 2 and continue in this way until we have visited
all nodes.

7.5 Lab: Binary Search Trees

For this lab, you need to implement your own Binary Search Tree. The code
will be graded using IO marking on Moodle. As such, you can structure your
code in any way you see fit. However, I have provided a skeleton that you can
adapt if you find that easier.
You should read from stdin. There will be one number per line and you should
incrementally insert them into your binary search tree. You should keep insert-
ing numbers until you read a -1.
https://www.youtube.com/watch?v=iCZZHRTLJjA

7.5.1 Submission 1
Construct a binary search tree based on the numbers given on stdin. Then print
out the pre-order, in-order, and post-order traversals each on their own lines.
You should print out the numbers separated by spaces and it is acceptable to
have a space at the end of each line.
Sample Input:
50
30
35
61
24
58
62
32
-1
Sample Output:
50 30 24 35 32 61 58 62
24 30 32 35 50 58 61 62
24 32 35 30 58 62 61 50

7.5.2 Submission 2
Construct a binary search tree based on the numbers given on stdin. Then print
out the minimum number and maximum numbers each on their own line.
Sample Input:
7.5. LAB: BINARY SEARCH TREES 81

50
30
35
61
24
58
62
32
-1
Sample Output:
24
62

7.5.3 Submission 3
Construct a binary search tree based on the numbers given on stdin. Then read
another number from stdin and search for it in the tree. You should print out
true or false depending on whether you can find the number or not. Your
program should exit when it encounters another -1.
Sample Input:
50
30
35
61
24
58
62
32
-1
-5
50
64
59
66
99
24
-1
Sample Output:
false
true
false
false
false
82 CHAPTER 7. BINARY SEARCH TREES

false
true

7.5.4 Submission 4
Finally, you should construct a binary search tree based on the numbers given on
stdin. You should then continue to read numbers from stdin until you encounter
a -1 again. After reading each number, you should delete it from the tree, and
then give the pre-order, in-order and post-order traversals (just as in Submission
1) followed by a blank line. For each number, you delete you should print all
three traversals.
Sample Input 1:
50
30
35
61
24
58
62
32
-1
30
24
32
-1
Sample Output 1:
50 32 24 35 61 58 62
24 32 35 50 58 61 62
24 35 32 58 62 61 50

50 32 35 61 58 62
32 35 50 58 61 62
35 32 58 62 61 50

50 35 61 58 62
35 50 58 61 62
35 58 62 61 50
Sample Input 2:
50
30
35
61
24
7.5. LAB: BINARY SEARCH TREES 83

58
62
32
33
-1
30
24
32
-1
Sample Output 2:
50 32 24 35 33 61 58 62
24 32 33 35 50 58 61 62
24 33 35 32 58 62 61 50

50 32 35 33 61 58 62
32 33 35 50 58 61 62
33 35 32 58 62 61 50

50 35 33 61 58 62
33 35 50 58 61 62
33 35 58 62 61 50

7.5.5 Recommend Structure

Here is a recommended structure for your code:
class TreeNode{
public:
// Pointer to the left child
TreeNode* left = nullptr;
// Pointer to the right child
TreeNode* right = nullptr;
// Value in the node
int value;

// Constructor, sets the value

TreeNode(int v) : value(v) {}
// Destructor
~TreeNode() {}
};

class Tree{
private:
TreeNode* root = nullptr;
// These functions do the actual work
84 CHAPTER 7. BINARY SEARCH TREES

void insert(int v, TreeNode* &subtree){

if(subtree == nullptr){
subtree = new TreeNode(v);
}else if(v < subtree->value){
insert(v, subtree->left);
}else{
insert(v, subtree->right);
}
}

void preOrderTraversal(TreeNode* subtree) const {/* TODO */ }

void inOrderTraversal(TreeNode* subtree) const {/* TODO */ }
void postOrderTraversal(TreeNode* subtree) const {/* TODO */ }

int min(TreeNode* subtree) const {/* TODO */ }

int max(TreeNode* subtree) const {/* TODO */ }
bool contains(int value, TreeNode* subtree) const {/* TODO */ }
void remove(int value, TreeNode* &subtree) {/* TODO */ }

public:
// Public interface to the recursive functions above
void insert(int value){
insert(value, root);
}

// Submission 1
void preOrderTraversal(){
preOrderTraversal(root);
cout << endl;
}
void inOrderTraversal(){
inOrderTraversal(root);
cout << endl;
}
void postOrderTraversal(){
postOrderTraversal(root);
cout << endl;
}
// Submission 2
int min(){
return min(root);
}
int max(){
return max(root);
}
7.6. ADDITIONAL READING 85

// Submission 3
bool contains(int value){
return contains(value, root);
}
// Submission 4
void remove(int value){
remove(value, root);
}
~Tree(){
// Here you should recursively delete all the nodes in the tree
// This is not tested by the Moodle marker, but see if you can
// figure out how to implement this.
}
};

7.6 Additional Reading

1. Great BST Visualisation: https://www.cs.usfca.edu/~galles/visualizati
on/BST.html
2. Geeks for Geeks - Binary Trees: https://www.geeksforgeeks.org/binary-
tree-data-structure
3. Geeks for Geeks - Binary Search Trees: https://www.geeksforgeeks.org/
binary-search-tree-data-structure
4. Chapter 4 – Weiss (2014)
5. Chapter 7 – Goodrich et al. (2011)
6. Chapter 8 – Dale et al. (2018)
7. MIT OpenCourseware, Binary Search Trees: https://ocw.mit.edu/course
s/electrical-engineering-and-computer-science/6-006-introduction-to-al
gorithms-fall-2011/lecture-videos/lecture-5-binary-search-trees-bst-sort/
86 CHAPTER 7. BINARY SEARCH TREES
Chapter 8

Balanced Trees

8.1 AVL Trees

https://www.youtube.com/watch?v=qsE5_m_IAJI

87
88 CHAPTER 8. BALANCED TREES
Chapter 9

Binary Heaps

https://www.youtube.com/watch?v=rdRRWifomVw

9.1 Lab: Binary Heaps

9.1.1 Instructions
For this lab, you need to implement your own Max Binary Heap. The code will
be graded using IO marking on Moodle. As such, you can structure your code
in any way you see fit. However, I have provided a skeleton that you can adapt
if you find that easier.
The underlying storage for your binary heap should be a vector.
You should read from stdin.
• If you read a number, then you should insert that number into the binary
heap and then print out the state of the underlying vector.
• If you read a p then you pop the max number from the heap and print
out the state of the underlying vector.
• If you read an x then your program should exit.
When printing out the state of the underlying storage you should print each
number separated by a space. At the end of the line it is acceptable to have a
space before the newline character. Presentation errors will get 100%.
If the two children of a node have the same value and that node’s value needs
to be swapped with one of them, then you should swap with the left child.

9.1.2 Sample IO
Sample Input 1:

89
90 CHAPTER 9. BINARY HEAPS

6
5
32
10
42
x
Sample Output 1:
6
6 5
32 5 6
32 10 6 5
42 32 6 5 10
Sample Input 2:
8
12
3
5
10
p
9
12
6
x
Sample Output 2:
8
12 8
12 8 3
12 8 3 5
12 10 3 5 8
10 8 3 5
10 9 3 5 8
12 9 10 5 8 3
12 9 10 5 8 3 6

9.1.3 Recommend Structure

Here is a recommended structure for your code:
#include <iostream>
#include <vector>
using namespace std;

class BinaryHeap{
9.1. LAB: BINARY HEAPS 91

public:
vector<int> data;

int parent(int idx){

int left_child(int idx){

int right_child(int idx){

int num_children(int idx){

void push(int value){

void pop(){

void print(){
for(auto &v : data){
cout << v << " ";
}
cout << endl;
}
};

int main()
{
BinaryHeap bh;
string line;
while(getline(cin, line) && line[0] != 'x'){
if(line[0] == 'p'){
bh.pop();
}else{
bh.push(stoi(line));
}
92 CHAPTER 9. BINARY HEAPS

bh.print();
}

return 0;
}
Chapter 10

Sorting

https://www.youtube.com/watch?v=FUzu-qypGuw

93
94 CHAPTER 10. SORTING
Bibliography

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction
to algorithms. MIT press.
Dale, N. B., Weems, C., and Richards, T. (2018). C++ plus data structures.
Jones & Bartlett Learning, 6th edition.
Goodrich, M. T., Tamassia, R., and Mount, D. M. (2011). Data structures and
algorithms in C++. John Wiley & Sons, 2nd edition.
Stroustrup, B. (2014). Programming: principles and practice using C++. Pear-
son Education.
Weiss, M. A. (2014). Data structures & algorithm analysis in C++. Pearson
Education, 4th edition.

95