D a t a s t r u c t u r e s a n d a L g o r I t h m s Annotated Reference with Examples

---

DSA
D a t a S t r u c t u r e s a n d A l g o r i t h m s
Annotated Reference with Examples
Granville Barne!
Luca Del Tongo

---

Data Structures and Algorithms:
Annotated Reference with Examples
First Edition
Copyright c
° Granville Barnett, and Luca Del Tongo 2008.

---

This book is made exclusively available from DotNetSlackers
(http://dotnetslackers.com/) the place for .NET articles, and news from
some of the leading minds in the software industry.

---

Contents
1 Introduction
1
1.1 What this book is, and what it isn’t . . . . . . . . . . . . . . . .
1
1.2 Assumed knowledge . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2.1
Big Oh notation . . . . . . . . . . . . . . . . . . . . . . .
1
1.2.2
Imperative programming language . . . . . . . . . . . . .
3
1.2.3
Object oriented concepts . . . . . . . . . . . . . . . . . .
4
1.3 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.4 Tips for working through the examples . . . . . . . . . . . . . . .
6
1.5 Book outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.6 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.7 Where can I get the code? . . . . . . . . . . . . . . . . . . . . . .
7
1.8 Final messages . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
I
Data Structures
8
2 Linked Lists
9
2.1 Singly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.1.1
Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.1.2
Searching . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.1.3
Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.1.4
Traversing the list . . . . . . . . . . . . . . . . . . . . . .
12
2.1.5
Traversing the list in reverse order . . . . . . . . . . . . .
13
2.2 Doubly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.2.1
Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.2.2
Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.2.3
Reverse Traversal . . . . . . . . . . . . . . . . . . . . . . .
16
2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3 Binary Search Tree
19
3.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.3 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3.4 Finding the parent of a given node . . . . . . . . . . . . . . . . .
24
3.5 Attaining a reference to a node . . . . . . . . . . . . . . . . . . .
24
3.6 Finding the smallest and largest values in the binary search tree
25
3.7 Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3.7.1
Preorder . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
I

---

3.7.2
Postorder . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3.7.3
Inorder . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.7.4
Breadth First . . . . . . . . . . . . . . . . . . . . . . . . .
30
3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
4 Heap
32
4.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.2 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
4.3 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
4.4 Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
5 Sets
44
5.1 Unordered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
5.1.1
Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
5.2 Ordered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
6 Queues
48
6.1 A standard queue . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
6.2 Priority Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
6.3 Double Ended Queue . . . . . . . . . . . . . . . . . . . . . . . . .
49
6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
7 AVL Tree
54
7.1 Tree Rotations . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
7.2 Tree Rebalancing . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
7.3 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
7.4 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
II
Algorithms
62
8 Sorting
63
8.1 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
8.2 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
8.3 Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
8.4 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
8.5 Shell Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
8.6 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
8.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
9 Numeric
72
9.1 Primality Test . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
9.2 Base conversions . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
9.3 Attaining the greatest common denominator of two numbers . .
73
9.4 Computing the maximum value for a number of a specific base
consisting of N digits . . . . . . . . . . . . . . . . . . . . . . . . .
74
9.5 Factorial of a number . . . . . . . . . . . . . . . . . . . . . . . .
74
9.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
II

---

10 Searching
76
10.1 Sequential Search . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
10.2 Probability Search . . . . . . . . . . . . . . . . . . . . . . . . . .
76
10.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
11 Strings
79
11.1 Reversing the order of words in a sentence . . . . . . . . . . . . .
79
11.2 Detecting a palindrome . . . . . . . . . . . . . . . . . . . . . . .
80
11.3 Counting the number of words in a string . . . . . . . . . . . . .
81
11.4 Determining the number of repeated words within a string . . . .
83
11.5 Determining the first matching character between two strings . .
84
11.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
A Algorithm Walkthrough
86
A.1 Iterative algorithms . . . . . . . . . . . . . . . . . . . . . . . . .
86
A.2 Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . . . .
88
A.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
90
B Translation Walkthrough
91
B.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
C Recursive Vs. Iterative Solutions
93
C.1 Activation Records . . . . . . . . . . . . . . . . . . . . . . . . . .
94
C.2 Some problems are recursive in nature . . . . . . . . . . . . . . .
95
C.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95
D Testing
97
D.1 What constitutes a unit test? . . . . . . . . . . . . . . . . . . . .
97
D.2 When should I write my tests? . . . . . . . . . . . . . . . . . . .
98
D.3 How seriously should I view my test suite? . . . . . . . . . . . . .
99
D.4 The three A’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
D.5 The structuring of tests . . . . . . . . . . . . . . . . . . . . . . .
99
D.6 Code Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . .
100
D.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
100
E Symbol Definitions
101
III

---

Preface
Every book has a story as to how it came about and this one is no different,
although we would be lying if we said its development had not been somewhat
impromptu. Put simply this book is the result of a series of emails sent back
and forth between the two authors during the development of a library for
the .NET framework of the same name (with the omission of the subtitle of
course!). The conversation started off something like, “Why don’t we create
a more aesthetically pleasing way to present our pseudocode?” After a few
weeks this new presentation style had in fact grown into pseudocode listings
with chunks of text describing how the data structure or algorithm in question
works and various other things about it. At this point we thought, “What the
heck, let’s make this thing into a book!” And so, in the summer of 2008 we
began work on this book side by side with the actual library implementation.
When we started writing this book the only things that we were sure about
with respect to how the book should be structured were:
1.
always make explanations as simple as possible while maintaining a moder-
ately fine degree of precision to keep the more eager minded reader happy;
and
2.
inject diagrams to demystify problems that are even moderatly challenging
to visualise (. . . and so we could remember how our own algorithms worked
when looking back at them!); and finally
3.
present concise and self-explanatory pseudocode listings that can be ported
easily to most mainstream imperative programming languages like C++,
C#, and Java.
A key factor of this book and its associated implementations is that all
algorithms (unless otherwise stated) were designed by us, using the theory of
the algorithm in question as a guideline (for which we are eternally grateful to
their original creators). Therefore they may sometimes turn out to be worse
than the “normal” implementations—and sometimes not. We are two fellows
of the opinion that choice is a great thing. Read our book, read several others
on the same subject and use what you see fit from each (if anything) when
implementing your own version of the algorithms in question.
Through this book we hope that you will see the absolute necessity of under-
standing which data structure or algorithm to use for a certain scenario. In all
projects, especially those that are concerned with performance (here we apply
an even greater emphasis on real-time systems) the selection of the wrong data
structure or algorithm can be the cause of a great deal of performance pain.
IV

---

V
Therefore it is absolutely key that you think about the run time complexity and
space requirements of your selected approach. In this book we only explain the
theoretical implications to consider, but this is for a good reason: compilers are
very different in how they work. One C++ compiler may have some amazing
optimisation phases specifically targeted at recursion, another may not, for ex-
ample. Of course this is just an example but you would be surprised by how
many subtle differences there are between compilers. These differences which
may make a fast algorithm slow, and vice versa. We could also factor in the
same concerns about languages that target virtual machines, leaving all the
actual various implementation issues to you given that you will know your lan-
guage’s compiler much better than us...well in most cases. This has resulted in
a more concise book that focuses on what we think are the key issues.
One final note: never take the words of others as gospel; verify all that can
be feasibly verified and make up your own mind.
We hope you enjoy reading this book as much as we have enjoyed writing it.
Granville Barnett
Luca Del Tongo

---

Acknowledgements
Writing this short book has been a fun and rewarding experience. We would
like to thank, in no particular order the following people who have helped us
during the writing of this book.
Sonu Kapoor generously hosted our book which when we released the first
draft received over thirteen thousand downloads, without his generosity this
book would not have been able to reach so many people. Jon Skeet provided us
with an alarming number of suggestions throughout for which we are eternally
grateful. Jon also edited this book as well.
We would also like to thank those who provided the odd suggestion via email
to us. All feedback was listened to and you will no doubt see some content
influenced by your suggestions.
A special thank you also goes out to those who helped publicise this book
from Microsoft’s Channel 9 weekly show (thanks Dan!) to the many bloggers
who helped spread the word. You gave us an audience and for that we are
extremely grateful.
Thank you to all who contributed in some way to this book. The program-
ming community never ceases to amaze us in how willing its constituents are to
give time to projects such as this one. Thank you.
VI

---

About the Authors
Granville Barnett
Granville is currently a Ph.D candidate at Queensland University of Technology
(QUT) working on parallelism at the Microsoft QUT eResearch Centre
1
. He also
holds a degree in Computer Science, and is a Microsoft MVP. His main interests
are in programming languages and compilers. Granville can be contacted via
one of two places: either his personal website (http://gbarnett.org) or his
blog (http://msmvps.com/blogs/gbarnett).
Luca Del Tongo
Luca is currently studying for his masters degree in Computer Science at Flo-
rence. His main interests vary from web development to research fields such as
data mining and computer vision. Luca also maintains an Italian blog which
can be found at http://blogs.ugidotnet.org/wetblog/.
1
http://www.mquter.qut.edu.au/
VII

---

Page intentionally left blank.

---

Chapter 1
Introduction
1.1
What this book is, and what it isn’t
This book provides implementations of common and uncommon algorithms in
pseudocode which is language independent and provides for easy porting to most
imperative programming languages. It is not a definitive book on the theory of
data structures and algorithms.
For the most part this book presents implementations devised by the authors
themselves based on the concepts by which the respective algorithms are based
upon so it is more than possible that our implementations differ from those
considered the norm.
You should use this book alongside another on the same subject, but one
that contains formal proofs of the algorithms in question. In this book we use
the abstract big Oh notation to depict the run time complexity of algorithms
so that the book appeals to a larger audience.
1.2
Assumed knowledge
We have written this book with few assumptions of the reader, but some have
been necessary in order to keep the book as concise and approachable as possible.
We assume that the reader is familiar with the following:
1.
Big Oh notation
2.
An imperative programming language
3.
Object oriented concepts
1.2.1
Big Oh notation
For run time complexity analysis we use big Oh notation extensively so it is vital
that you are familiar with the general concepts to determine which is the best
algorithm for you in certain scenarios. We have chosen to use big Oh notation
for a few reasons, the most important of which is that it provides an abstract
measurement by which we can judge the performance of algorithms without
using mathematical proofs.
1

---