Data Structures and Algorithms (2014)

Validated with: Computer Science and Technology

Studios

Author: Mohammed Nebil

@Mohammed_Nebil
+251913828882
I
 Table of Contents
Preface ...............................................................................................................................................................III
Chapter 1: Introduction to Data Structures and Algorithms ............................................................1
1.1 Data Structures and Algorithms ....................................................................................................1
1.1.1 Data Structures ......................................................................................................................... 1
1.1.2 Algorithms .................................................................................................................................. 2
1.1.3 Computer Program Design Goals ........................................................................................2
1.1.4 Efficiency ..................................................................................................................................... 2
1.1.5 Abstract Data Types (ADT) ................................................................................................... 4
1.2 Data Structure and File Structure .......................................................................................................5
1.3 Problems, Algorithms and Programs ................................................................................................. 5
1.4 Algorithm Design ......................................................................................................................................5
1.5 Properties of Algorithm ......................................................................................................................... 6
1.6 Programs ......................................................................................................................................................7
Chapter 2: Algorithms and Algorithm Analysis .....................................................................................8
2.1 Algorithms ............................................................................................................................................ 8
2.1.1 Algorithm Analysis ...................................................................................................................9
2.2 Computation of Run-time Algorithms ......................................................................................12
2.3 Types of Algorithm Complexity Analysis ................................................................................ 13
2.4 Order of Growth and Asymptotic Analysis .............................................................................13
2.5 Asymptotic Analysis Theorems .................................................................................................. 14
2.5.1 No Uniqueness ........................................................................................................................ 16
2.5.2 Order of Common Functions ..............................................................................................16
2.5.3 Common Properties of Big-Oh Notations ......................................................................16
2.5.4 Implication of Big-Oh Notations .......................................................................................17
Chapter 3: Arrays .......................................................................................................................................... 17
3.1 Introduction to Arrays ................................................................................................................... 17
3.2 Searching Algorithms ..................................................................................................................... 18
3.2.1 Linear/Sequential Search .................................................................................................... 19
3.2.2 Ordered and Unordered List in Searching Algorithms .............................................. 20
3.2.3 Binary Search ...........................................................................................................................20
3.2.4 Efficiency .................................................................................................................................. 22
3.3 Sorting Algorithms .......................................................................................................................... 22
3.3.1 Common Sort Algorithms ....................................................................................................22
3.3.2 Bubble Sort ...............................................................................................................................23
3.3.3 Insertion Sort ...........................................................................................................................26
3.3.4 Selection Sort .......................................................................................................................... 28
Chapter 4: Linked Lists ................................................................................................................................ 31
4.1 Introduction to Linked Lists ......................................................................................................... 31
4.2 Review on Structures ..................................................................................................................... 31
4.2.1 Accessing Members of Structure Variables ..................................................................32
4.2.2 Self-Referential Structures .................................................................................................32
II
 4.2.3 Common operations of the List of data structures .....................................................33
4.2.4 Implementation of an ADT ................................................................................................. 33
4.2.5 Operations on Linked Lists ................................................................................................. 36
Chapter 5: Stack and Queue ......................................................................................................................67
5.1 Stacks ................................................................................................................................................... 67
5.2 Implementation of Stacks .............................................................................................................68
5.2.1 Array Implementation of Stacks .......................................................................................68
5.2.2 Stack Attributes and Operations ......................................................................................68
5.2.3 Linked List Implementation of Stacks .............................................................................75
5.3 Application of Stack Data Structure ......................................................................................... 76
5.4 Expression Evaluations ..................................................................................................................76
5.4.1 Algorithm for Infix to Postfix .............................................................................................77
5.5 Queues .................................................................................................................................................79
5.5.1 Implementation of Queues .................................................................................................79
5.5.2 Empty or Full? ..........................................................................................................................79
5.5.3 Queue Attributes and Operations ................................................................................... 80
Chapter 6: Trees ............................................................................................................................................ 88
6.1 Trees .....................................................................................................................................................88
6.2 Example of Trees ..............................................................................................................................89
6.3 Tree Representation .......................................................................................................................90
6.3.1 Binary Tree ...............................................................................................................................90
6.3.2 Data Structures for Binary Trees ......................................................................................91
6.4 Tree Traversal ................................................................................................................................... 96
6.5 Binary Search Trees ........................................................................................................................ 97
6.5.1 findMin, findMax and delete ........................................................................................... 102

III
 Preface

Welcome to the world of data structures and algorithms! This book is designed to be your comprehensive guide to
understanding and implementing fundamental data structures and algorithms that are essential for solving complex
problems in computer science and software engineering.

In today's digital age, where vast amounts of data are generated and processed every second, the ability to efficiently
organize and manipulate data is crucial. Data structures provide the foundation for storing and managing data
effectively, while algorithms offer the means to perform various operations on that data with optimal efficiency.

Whether you are a student studying computer science, a software engineer looking to enhance your problem-solving
skills, or a curious individual interested in understanding the inner workings of computer programs, this book aims to
equip you with the necessary knowledge and skills to tackle real-world challenges.

Throughout this book, we will explore a wide range of data structures such as arrays, linked lists, stacks, queues, trees,
heaps, hash tables, and graphs. Each chapter will delve into the theoretical foundations of these data structures,
discussing their characteristics, advantages, and limitations.

Moreover, we will delve into the realm of algorithms, which are step-by-step procedures for solving specific problems.
We will cover various algorithmic paradigms, including searching, sorting, graph traversal, dynamic programming,
and divide-and-conquer. You will learn how to analyze the efficiency of algorithms using Big O notation, enabling you
to make informed decisions about algorithm selection and optimization.

To facilitate your learning experience, this book will provide numerous examples, illustrations, and pseudocode
implementations. You will have the opportunity to apply your knowledge through hands-on coding exercises and
programming challenges, allowing you to solidify your understanding and develop practical skills.

It is important to note that while this book covers a broad range of data structures and algorithms, it is by no means an
exhaustive resource. The field of data structures and algorithms is vast and constantly evolving. This book will serve as
a strong foundation upon which you can build your knowledge and explore more advanced topics in the future.

Let us embark on this journey together and unlock the power of data structures and algorithms. By mastering the
concepts and techniques presented in this book, you will develop the ability to design efficient and elegant solutions to
complex computational problems, opening doors to exciting opportunities in computer science and beyond.

IV
V
 Chapter 1: Introduction to Data Structures and Algorithms

1.1 Data Structures and Algorithms

Program is written in order to solve a problem

A solution to a problem actually consists of two things:

 A way to organize data (data structures)

 Sequence of steps needed to solve the problem (Algorithm)

A famous quote:
 Program = Algorithm + Data Structure.
A program prescribes "what" is to be done with "which" data.

#include <iostream>
using namespace std;
int main()
{
int i, j,sum;
cin >> i >> j;
sum=i+j;
cout <<sum << endl;
return 0;
}

Programming 1.1: Read the sum of the two integers

1.1.1 Data Structures

 Variables i and j are used to represent integers.

 They form the data structure.
 int data type is available as part of the C++ programming language.
 A data structure is also called a data type in a programming language.
 The data type of a variable defines its possible values and the operations that can be
performed on it.

1
1.1.2 Algorithms

 The main function defines the algorithm.

 This uses the built-in operation + for adding int variables.
 It also uses functions defined in the iostream library for reading and printing int
variables.
 Many commonly required data structures and algorithms are available as built-in
types or as part of libraries.

As we said, in this course, we will study:

 Algorithms: Sequence of steps the needs to be followed to solve problems
 Data structures: A means for efficiently storing, accessing, and modifying data
Specifically, you are going to learn
1. A collection of more commonly used data structures and algorithms-”programmers’
basic toolkit”
2. Trade-offs associated with data structures and algorithms preferred
 Usually, done by comparing space and time required by each data structures and
algorithms
3. How to measure quality of a given data structure and algorithms
 Allow you to judge the merits of new data structures that you or others might invent.

1.1.3 Computer Program Design Goals

 There are two basic design goals(sometimes conflicting):

1. To design algorithm that is easy to understand, code and debug
2. To design algorithm that makes efficient use of the computer's resources
 "Elegant program" satisfies both of the above goals
 The codes we write for this course needed to be elegant but our primary concern is
goal 2 (i.e. efficiency).
 Goal 1 is primarily the concern of software engineering.

1.1.4 Efficiency

 A solution is said to be efficient if it solves the problem within its resource constraints
or less cost
2
 Cost is the mount of resources that the solution consumes such as time
 Constraints:
 Space (typical for many programs )
 Time (specially for real time systems)
 Bandwidth
 However, that does not mean we always strive for the most efficient program.
 If the program works well within resource constraints, there is no benefit to making it
faster or smaller.

A philosophy of data structures

 Question: processor speed and memory size still continue to improve, will not today's
efficiency problem be solved by tomorrow's hardware?
 The answer is no, our history proved it.
 Reasons: as we develop more powerful computers, that addition is being used to
tackle more complex problems.
 More sophisticated user interface
 Bigger problem sizes
 New problems previously deemed unfeasible

Data structure

 A data structure is any data representation and its associated operations.

 Example int and float can be viewed as simple data structures
 Operations support similar operations +,*,/,% etc.

 Commonly, people use the term “data structure” to mean an organization or

structuring of collection of data items.
 Example, List of integers stored in array.

 Data can be represented in computer using different data structures.

 Example, list of integers can be represented using array or another data structure
called linked list.
 However, using the proper data structure can make the difference.

 There are different ways to organize data in computer

 In other words, Data structures are there is no ultimate data structure that fits to every
problem.
 Each data structure has associated costs and benefits(trade-offs).
 The choice to use a particular data structure depends on our requirements.
3
Steps to select data structure

1. Analyze your problem to determine the basic operations that must be supported.
 Inserting a data item into the data structure,
 Deleting a data item from the data structure,
 Finding a specified data item etc…
2. Quantify the resource constraints for each operation.
 Such as Time
3. Select the data structure that best meets these requirements.
 The "simplest" that meets requirements
 Note: Resource constraints on key operations such as search, insert and delete
drives the data structure selection.

Abstract Data Types Definitions

 A type is a collection of values.

Example: Boolean type consists of values true and false
 Simple type is a type/values that contains no sub parts
Example, int, float,…
 Aggregate/composite type: its value has subparts.
Example student type has parts like name, idno, gpa…
 A data item is a member of a type.
 A data type is a type together with a collection of operations to manipulate the type.
Example, int variable is a member of the integer data type and addition is example
operation on int data type

1.1.5 Abstract Data Types (ADT)

 Abstract Data Types(ADT) consists of data to be stored and operations supported on

them.
 ADT is a specification that describes a data set and the operation on that data.
 An ADT doesn’t specify how the data type is implemented
 Rather it only specifies a set of values and a set of operations on that data type
 Each ADT operation is implemented by a function/method.
 A data structure is the implementation of an ADT.
 In OOP languages, an ADT and its implementation together makes up a class.
 Each operation of ADT is implemented by the member methods.

4
Examples:

 Integer
Values are …., -3, -2, -1, 0, 1, 2, 3, …..
Operations are +, -, *, /, % …
 The abstract data type Integer is an infinite set.
 The built-in data structure int is a particular implementation of the abstract data
type Integer.
 Another built-in data structure long long int also implements the same abstract
type.

1.2 Data Structure and File Structure

 Data structure: usually refers to an organization for data in main memory.

 File structure: an organization for data on peripheral storage, such as a disk drive or
tape.

1.3 Problems, Algorithms and Programs

 Problem is a task to be performed.

 Best thought of as inputs and matching outputs.
 Example given id, find the detail of students
 Problem definition should include constraints on the resources that may be
consumed by any acceptable solution.
 Algorithms are steps that need to be followed to solve a problem.
 A recipe(a set of instructions for preparing a particular dish, including a list of the
ingredients required)
 An algorithm takes the input to a problem and transforms it to the output.
 A mapping of input to output.

1.4 Algorithm Design

 You have a problem to solve

 Analyze the problem and identify the requirements
 Design an efficient algorithm
5
 Use good data structures
 Show that your algorithm works!
 Prove its correctness
 Study the efficiency of your algorithm
 Run time
 Storage required
 For a problem given we might come up with different algorithms.
Example:

 Two algorithms for computing the Factorial

 Which one is better?

int factorial (int n)

{
if (n <= 1) return 1;
else
return n * factorial(n-1);
}

Programming 1.2

int factorial (int n)

{
if (n<=1) return 1;
else {
fact = 1;
for (k=2; k<=n; k++)
fact *= k;
return fact;
}

Programming 1.3

1.5 Properties of Algorithm

 Finiteness: Algorithm must complete after a finite number of steps.

6
 Definiteness: Each step must be clearly defined, having one and only one
interpretation. At each point in computation, one should be able to tell exactly what
happens next.
 Sequence: Each step must have a unique defined preceding and succeeding step. The
first step (start step) and last step (halt step) must be clearly noted.
 Feasibility: It must be possible to perform each instruction.
 Correctness: It must compute correct answer for all possible legal inputs.
 Language Independence: It must not depend on any one programming language.
 Completeness: It must solve the problem completely.
 Efficiency: It must solve with the least amount of computational resources such as
time and space.
 Generality: Algorithm should be valid on all possible inputs.
 Input/Output: There must be a specified number of input values, and one or more
result values.

1.6 Programs

 A computer program is an instance, or concrete representation, for an algorithm in

some programming language.
 We frequently interchange use of "algorithm" and "program" though they are actually
different concepts.

7
 Chapter 2: Algorithms and Algorithm Analysis

2.1 Algorithms

 An algorithm is a step-by-step procedure or a set of well-defined instructions

designed to solve a specific problem or accomplish a particular task. It is a precise
sequence of operations that can be followed to solve a problem, perform a
computation, or achieve a desired outcome.
 In essence, an algorithm is like a recipe or a road-map that guides you through a
series of logical steps to solve a problem. It may involve various operations, such as
arithmetic calculations, data manipulation, decision-making, and repetition of
certain steps.
 Here are a few key points to understand about algorithms:
1. Input: An algorithm typically takes one or more inputs, which are the initial data or
values provided to the algorithm before it begins its execution. The inputs can be
numbers, text, lists, or any other form of data.
2. Output: An algorithm produces an output, which is the result or solution obtained
after executing the steps defined by the algorithm. The output can be a single value, a
collection of values, or even a change in the state of a system.
3. Determinism: Algorithms are deterministic, meaning that given the same input, they
will always produce the same output. This property ensures repeatability and
predictability.
4. Correctness: An algorithm is considered correct if it solves the problem it was
designed for and produces the expected output for all valid inputs. Ensuring the
correctness of an algorithm is a crucial aspect of algorithm design.

8
5. Efficiency: Algorithms are also evaluated based on their efficiency, which refers to
the use of computational resources, such as time and memory. An efficient algorithm
solves a problem in the most optimal and resource-friendly manner.
 Algorithms are fundamental to computer science and play a vital role in various
applications, ranging from simple everyday tasks to complex computational problems.
They are used in software development, data analysis, artificial intelligence,
cryptography, optimization, and many other fields.
 By designing and analyzing algorithms, computer scientists aim to develop efficient
and effective solutions to problems, improve computational processes, and advance
our understanding of what can be computed.

2.1.1 Algorithm Analysis

 Studies computing resource requirements of different algorithms

- Computing Resources.
- Running time (Most precious).
- Memory usage.
- Communication bandwidth etc.

Why need algorithm analysis?

 Writing a working program is not good enough

 The program may be inefficient!
 If the program is run on a large data set, then the running time becomes an issue
 Goal is to pick up an efficient algorithm for the problem at hand
Reasons to perform analyze algorithms

It enables us to:
 Predict performance of algorithms
 Compare algorithms.
 Provide guarantees on running time/space of algorithms
 Understand theoretical basis.
 Primary practical reason: avoid performance bugs.
 Client gets poor performance because programmer did not understand performance
characteristics.

How to measure efficiency/performance?

9
 Two approaches to measure algorithms efficiency/performance:
 Empirical: Implement the algorithms and trying them on different instances of input
 Use/plot actual clock time to pick one.
 Theoretical/Asymptotic Analysis: Determine quantity of resource required
mathematically needed by each algorithms.

Drawbacks of Empirical Methods

 It is difficult to use actual clock because clock time varies based on:
 Specific processor speed
 Current processor load
 Specific data for a particular run of the program
 Input size
 Input properties
 Programming language (C++, java, python …)
 The programmer (You, Me, Bill gate …)
 Operating environment/platform (PC, sun, smartphone etc)
 Therefore, it is quite machine dependent.

Machine Independent Analysis

 Critical resources:
 Time, Space (disk, RAM), Programmer’s effort, Ease of use (user’s effort).
 Factors affecting running time:
 System dependent effects:
 Hardware: CPU, memory, cache, …
 Software: compiler, interpreter, garbage collector, …
 System: operating system, network, other apps, …
 System independent effects:
 Algorithm.
 Input data/ Problem size.
 For most algorithms, running time depends on "size" of the input.
 Size is often the number of inputs processed
 Example: in searching problem, size is the no of items to be sorted
 Running time is expressed as T(n) for some function T on input size n.

 Efficiency of an algorithm is measured in terms of the number of basic operations

it performs.
 Not based on actual time-clock
 We assume that every basic operation takes constant time.
10
 Arbitrary time
 Examples of Basic Operations:
 Single Arithmetic Operation (Addition, Subtraction, Multiplication)
 Assignment Operation
 Single Input/Output Operation
 Single Boolean Operation
 Function Return
 We do not distinguish between the basic operations.
 Examples of Non-basic Operations are
 Sorting, Searching.

Examples:

Count of Basic Operations (Time Units)

int count()
{
int k=0; - 1 is for the assignment statement; int k=0;
cout<< “Enter an integer”; - 1 is for the output statement.
cin>>n; - 1 is for the input statement.
- In the for loop:
for (i = 0;i < n;i++) - 1 assignment, n+1 tests, and n increments
k = k+1; - n loops of 2 units for assignment and addition.
return 0; - 1 is for return statement.
}
T(n) = 1+1+1+(1+n+1+n)+2n+1 = 4n+6

void func()
{
int x=0; - 1 is for first assignment statement.
int i=0; - 1 is for second assignment statement.
int j=1; - 1 is for third assignment statement.
cout<< “Enter an Integer value”; - 1 is for output statement
cin>>n; - 1 is for input statement
while (i<n){ - In the first while loop:
x++; - n+1 tests
11
i++; - n loops of 2 units for two increments.
}
while (j<n) - In the second while loop:
{ - n tests.
j++; - n-1 increments.
}
}
T(n) = 1+1+1+1+1+n+1+2n+n+n-1 = 5n+5

int sum (int n)

{
int partial_sum= 0; - 1 for the assignment.
for (int i = 1; i <= n; i++) - 1 assignment, n+1 tests, and n increments.
partial_sum= partial_sum+ (i * i * i); - n loops of 4 units for (=,+,*)
return partial_sum; - 1 is for return statement.
}

T(n) = 1+(1+n+1+n)+4n+1 = 6n+4

2.2 Computation of Run-time Algorithms

Examples: Suppose we have hardware capable of executing 106 instructions per second.
How long would it take to execute an algorithm whose complexity function was T(n) =
2�2 on an input size of n =108 ?

Solution: The total number of operations to be performed would be:

T(108 ) = 2 * (108 )2 = 2 * 1016
The required number of seconds would be given by:
T(108 )/106 => 2 * 1016 /106 = 2 * 1010

The number of seconds per day is 86,400 so this is about 231,480 days (634 years).

12
2.3 Types of Algorithm Complexity Analysis

 Best case:
 Lower bound on cost.
 Determined by “easiest” input.
 Provides a goal for all inputs.
 Worst case:
 Upper bound on cost.
 Determined by “most difficult” input.
 Provides a guarantee for all inputs.
 Average case:
 Expected cost for random input.
 Need a model for “random” input.
 Provides a way to predict performance.

Best, Worst, and Average Cases

 Not all inputs of a given size take the same time.

 Sequential search for K in an array of n integers:
 Begin at first element in array and look at each element in turn until K is found.
 Best Case: [Find at first position: 1 compare]
 Worst Case: [Find at last position: n compares]
 Average Case: [(n + 1)/2 compares]
 While average time seems to be the fairest measure, it may be difficult to determine.
 Depends on distribution. Assumption for above analysis: Equally likely at any
position.
 When is worst case time important?
 When the algorithms for time-critical systems.

2.4 Order of Growth and Asymptotic Analysis

 Suppose an algorithm for processing a retail store’s inventory takes:

 10,000 milliseconds to read the initial inventory from disk, and then
 10 milliseconds to process each transaction (items acquired or sold).
 Processing n transactions takes (10,000 + 10 n) milliseconds.
 Even though 10,000 >> 10, the "10 n" term will be more important if the number of
transactions is very large.

13
 We also know that these coefficients will change if we buy a faster computer or disk
drive, or use a different language or compiler.
 We want to ignore constant factors (which get smaller and smaller as technology
improves)
 In fact, we will not worry about the exact values, but will look at “broad classes" of
values.

Growth Rates

 The growth rate for an algorithm is the rate at which the cost of the algorithm grows
as the size of its input grows.

Figure 2.1: Growth Rates

2.5 Asymptotic Analysis Theorems

 Refers to the study of an algorithm as the input size "gets big" or reaches a limit.
 To compare two algorithms with running times f(n) and g(n), we need a rough
measure that characterizes how fast each function growsgrowth rate.
 Ignore constants [especially when input size very large]
 But constants may have impact on small input size
 Several notations are used to describe the running-time equation for an algorithm.
 Big-Oh (O), Little-Oh (o)
 Big-Omega (Ω), Little-Omega(w)
 Theta Notation(θ)

Big-Oh Notation
14
 Definition:
 For f(n) a non-negatively valued function, f(n) is in set O(g(n)) if there exist two
positive constants c and �0 such that f(n)≤cg(n)for all n>�0 .
 Usage: The algorithm is in O(�2 ) in [best ,average, worst] case.
 Meaning: For all data sets big enough (i.e., n > �0 ), the algorithm always executes in
less than cg (n) steps [in best, average or worst case].

Big-Oh Visualization

 O(g(n)) is the set of functions with smaller or same order of growth as f(n)
 Wish tightest upper bound:
 While T(n) = 3�2 is in O(�3 ), we prefer O(�2 ).
 Because, it provides more information to say O(�2 ) than O(�3 ).

Big-Oh

 Demonstrating that a function f(n) is in big-O of a function g(n) requires that we find
specific constants c and no for which the inequality holds.
 The following points are facts that you can use for Big-Oh problems:
 1<= n for all n >= 1
 n <= �2 for all n >= 1
 2n <= n! for all n >= 4
 log2 � <= n for all n >= 2
 n <= n log2 � for all n >= 2

Example:

f(n) = 10n + 5 and g(n) = n. Show that f(n) is in O(g(n)).

To show that f(n) is O(g(n)) we must show constants c and no such that
f(n) <= c.g(n) for all n >= �0 .
10n + 5 <= c.n for all n >= �0 .
Try c = 15. Then we need to show that 10n + 5 <= 15n
Solving for n we get: 5 < 5n or 1 <= n.
So f(n) =10n + 5 <= 15.g(n) for all n >= 1.
(c = 15, �0 = 1).

15
2.5.1 No Uniqueness

 There is no unique set of values for �0 and c in proving the asymptotic bounds
Prove that 100n + 5 = O(�2 )
100n + 5 ≤ 100n + n = 101n ≤ 101�2 for all n ≥ 5
�0 = 5 and c = 101 is a solution
100n + 5 ≤ 100n + 5n = 105n ≤ 105�2 for all n ≥ 1
�0 = 1 and c = 105 is also a solution
 Must find SOME constants c and �0 that satisfy the asymptotic notation relation.

2.5.2 Order of Common Functions

Table 2.1: Growth Rate Order of Common Functions

Notation Name Example

O(1) Constant Adding two numbers, c=a+b
O(log n) Logarithmic Finding an item in a sorted array with a binary search
or a search tree (best case)
O(n) Linear Finding an item in an unsorted list or a malformed tree
(worst case); adding two n-digit numbers
O(n log n) Linearithmic Performing a Fast Fourier transform; heap sort, quick
sort (best case), or merge sort
O(�� ) Quadratic Multiplying two n-digit numbers by a simple algorithm;
adding two n×n matrices; bubble sort (worst case or
naive implementation), shell sort, quick sort (worst
case), or insertion sort

2.5.3 Common Properties of Big-Oh Notations

 Constant factors are may be ignored

 For all k>0, kf is O(f)
 The growth rate of a sum of terms is the growth rate of its fastest growing term.
 Example, ��3 + bn2 is O(�3 ).
 The growth rate of a polynomial is given by the growth rate of its leading term
 If f is a polynomial of degree d, then f is O(�� ).

16
2.5.4 Implication of Big-Oh Notations

 We use Big-Oh notation to say how slowly code might run as its input grows.
 Suppose we know that our algorithm uses at most O(f(n)) basic steps for any n inputs,
and n is sufficiently large, then we know that our algorithm will terminate after
executing at most constant times f(n) basic steps.
 We know that a basic step takes a constant time in a machine.
 Hence, our algorithm will terminate in a constant times f(n) units of time, for all large
n.

Chapter 3: Arrays

3.1 Introduction to Arrays

 Arrays are fundamental data structures in computer science and programming. They
consist of a collection of elements, each identified by at least one array index or key.

 These elements are typically of the same data type, stored in contiguous memory
locations, and accessed by their position within the array.

 Here's a breakdown of key aspects regarding arrays in data structures and algorithms:

1. Ordered Collection: Arrays maintain the order of elements they contain. Each
element has a unique index or position within the array, starting from 0 to n-1 for an
array of size n.
2. Fixed Size: In most programming languages, arrays have a fixed size determined at
the time of declaration. This fixed size imposes constraints on the number of elements
that can be stored in the array.

17
3. Random Access: Arrays support constant-time access to elements based on their
index. This means accessing any element within the array takes the same amount of time,
regardless of its position.
4. Homogeneous Elements: Arrays typically store elements of the same data type. This
homogeneity allows for efficient memory allocation and retrieval.
5. Memory Efficiency: Arrays offer efficient memory allocation because they store
elements in contiguous memory locations. This property facilitates faster access
compared to other data structures like linked lists.
6. Insertion and Deletion: Insertion and deletion operations in arrays can be costly,
especially if they involve shifting elements to maintain order or resizing the array. In
some cases, appending elements at the end of the array (if space is available) can be done
relatively efficiently.
7. Dynamic Arrays: Some programming languages provide dynamic array
implementations (e.g., ArrayList in Java, vector in C++), which automatically resize
themselves as needed to accommodate additional elements. This dynamic resizing
mitigates the limitations of fixed-size arrays.
8. Multidimensional Arrays: Arrays can have multiple dimensions, forming matrices or
higher-dimensional structures. Accessing elements in multidimensional arrays requires
specifying indices for each dimension.
9. Common Operations: Arrays support common operations such as traversal (iterating
through elements), searching (finding a specific element), sorting (rearranging elements
in a specified order), and slicing (extracting a portion of the array).
10. Applications: Arrays are widely used in various algorithms and applications,
including sorting algorithms (e.g., quicksort, mergesort), searching algorithms (e.g.,
binary search), dynamic programming, representing matrices and images, implementing
hash tables, and more.

 Understanding arrays and their properties is crucial for developing efficient

algorithms and writing optimized code in various programming scenarios.

 There are some very common problems that we use computers to solve:
Searching: Looking for specific data item/record from list of data items or set of records.
Sorting: placing records/items in order.

3.2 Searching Algorithms

 In general, the faster the algorithm is, the more complex it is.
 You don’t always need to use or should use the fastest algorithm.
 The list to be searched can either be ordered or unordered list.
18
3.2.1 Linear/Sequential Search

Basic algorithm:
Get the search criterion (key)
Get the first record from the file
While ( (record != key) and (still more records) )
Get the next record
End_while

Linear search implementation in C++:

#include <iostream>
using namespace std;

// Function to perform linear search on an array

int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; ++i) {
if (arr[i] == key) {
return i; // Return the index of the element if found
}
}
return -1; // Return -1 if the element is not found
}

int main() {
int arr[] = {45, 56, 78, 99, 112, 135};
int n = sizeof(arr) / sizeof(arr[0]); // Calculate the size
of the array
int key;

cout << "Enter the number to search: ";

cin >> key;

int index = linearSearch(arr, n, key);

if (index != -1) {
cout << "Element found at index: " << index << endl;
19
 } else {
cout << "Element not found" << endl;
}

return 0;
}

 This program defines a function linearSearch that takes an array arr, its size n,
and a key to search for.
 It iterates through the array elements sequentially and returns the index of the key if
found, or -1 if not found.
 In the main function, an array [45, 56, 78, 99, 112, 135] is defined, and the user is
prompted to enter a number to search for.
 The linearSearch function is called with the array, its size, and the key to search
for, and the result is printed accordingly.

Time complexity O(n):

 Unsuccessful search --- n times
 Successful search (worst) --- n times
 Successful search (best) --- 1 time
 Successful search (average) --- n/2 times

3.2.2 Ordered and Unordered List in Searching Algorithms

 Observation: the search is faster on an ordered list only when the item being searched
for is not in the list.
 Also, keep in mind that the list has to first be placed in order for the ordered search.
 Conclusion: the efficiency of these algorithms is roughly the same.
 So, if we need a faster search, on sorted list we need a completely different algorithm.

3.2.3 Binary Search

 Sequential search is not efficient for large lists because, on average, the sequential
search searches half the list.
 If we have an ordered list and we know how many things are in the list, we can use a
different strategy.

20
 The binary search gets its name because the algorithm continually divides the list into
two parts.
 Uses the divide-and-conquer technique to search the list.

Binary search implementation in C++:

#include <iostream>
using namespace std;

// Function to perform binary search on a sorted array

int binarySearch(int arr[], int low, int high, int key) {
while (low <= high) {
int mid = low + (high - low) / 2;

if (arr[mid] == key) {
return mid; // Return the index of the key if found
} else if (arr[mid] < key) {
low = mid + 1; // If key is greater, search in the
right half
} else {
high = mid - 1; // If key is smaller, search in the
left half
}
}
return -1; // Return -1 if the key is not found
}

int main() {
int arr[] = {27, 31, 45, 67, 88, 98, 111, 122, 147};
int n = sizeof(arr) / sizeof(arr[0]); // Calculate the size
of the array
int key;

cout << "Enter the number to search: ";

cin >> key;

int index = binarySearch(arr, 0, n - 1, key);

if (index != -1) {
cout << "Element found at index: " << index << endl;
21
 } else {
cout << "Element not found" << endl;
}

return 0;
}

 This program defines a function binarySearch that takes a sorted array arr, the
lower bound low, the upper bound high, and the key to search for.
 It repeatedly divides the search interval in half until the key is found or the interval
becomes empty.
 In the main function, an array [27, 31, 45, 67, 88, 98, 111, 122, 147] is defined, and
the user is prompted to enter a number to search for.
 The binarySearch function is called with the array, its lower and upper bounds,
and the key to search for, and the result is printed accordingly.

3.2.4 Efficiency

 Binary search is one of the fastest Algorithms

 The computational time for this algorithm is proportional to ���� � .
 Therefore, the time complexity is O(��� �).

3.3 Sorting Algorithms

 The binary search is a very fast search algorithm.

 But, the list has to be sorted before we can search it with binary search.
 To be really efficient, we also need a fast sort algorithm.

 There are many known sorting algorithms: Bubble Sort, Heap Sort, Selection Sort,
Merge Sort, Insertion Sort, Quick Sort.

3.3.1 Common Sort Algorithms

 Bubble sort is the slowest, running in �� time.

 Quick sort is the fastest, running in � ��� � time.
 As with searching, the faster the sorting algorithm, the more complex it tends to be.
22
 We will examine three sorting algorithms: Bubble sort, Insertion sort, Selection
sort.

3.3.2 Bubble Sort

 Suppose we have an array of data which is unsorted:

 Starting at the front, traverse the array, find the largest item, and move (or bubble) it
to the top.
 With each subsequent iteration, find the next largest item and bubble it up towards the
top of the array
 Bubble sort is a simple algorithm with:
 A memorable name, and a simple idea
 It is an O(�� ) algorithm and usually called “the generic bad algorithm”.
 Starting with the first item, assume that it is the largest
 Compare it with the second item:
 If the first is larger, swap the two,
 Otherwise, assume that the second item is the largest
 After one pass, the largest item must be the last in the list
 Start at the front again:
 The second pass will bring the second largest element into the second last position
 Repeat n – 1 times, after which, all entries will be in place

Bubble sort implementation in C++:

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<int>& arr) {

int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
23
 }
}

int main() {
vector<int> arr = { 67, 89, 34, 21, 58, 79, 88 };

cout << "Original array: ";

for (int num : arr) {
cout << num << " ";
}
cout << endl;

bubbleSort(arr);

cout << "Sorted array: ";

for (int num : arr) {
cout << num << " ";
}
cout << endl;

return 0;
}

 This code defines a function bubbleSort that implements the bubble sort algorithm
and sorts the given vector of integers.
 In the main function, we create the array [67, 89, 34, 21, 58, 79, 88], print it, sort it
using bubbleSort, and then print the sorted array.

24
Figure 3.1: Example of Bubble sort by using sorting algorithms

25
3.3.3 Insertion Sort

 Consider the following observations:

 A list with one element is sorted
 In general, if we have a sorted list of k items, we can insert a new item to create a
sorted list of size k + 1.
 Insertion sort works the same way as arranging your hand when playing cards.
 Out of the pile of unsorted cards that were dealt to you, you pick up a card and place
it in your hand in the correct position relative to the cards you’re already holding.

Basic Idea is:

 Find the location for an element and move all others up, and insert the element.

Steps:
1. The left most value can be said to be sorted relative to itself. Thus, we don’t need to do
anything.
2. Check to see if the second value is smaller than the first one.
- If it is swap these two values.
- The first two values are now relatively sorted.
3. Next, we need to insert the third value in to the relatively sorted portion
- So that after insertion, the portion will still be relatively sorted.
4. Now the first three are relatively sorted.
5. Do the same for the remaining items in the list.

Insertion sort implementation in C++:

#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector<int> &arr) {

int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;

// Move elements of arr[0..i-1], that are greater than

key,
// to one position ahead of their current position
26
 while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

int main() {
vector<int> arr = {43, 33, 19, 56, 65, 74};

cout << "Array before sorting: ";

for (int num : arr) {
cout << num << " ";
}
cout << endl;

insertionSort(arr);

cout << "Array after sorting: ";

for (int num : arr) {
cout << num << " ";
}
cout << endl;

return 0;
}

 This code defines a function insertionSort that performs the insertion sort
algorithm on a vector of integers.
 Then, in the main function, an array is initialized, displayed, sorted using insertion
sort, and then displayed again to show the sorted result.

27
 Figure 3.2: Example of Insertion sort by using sorting algorithms

3.3.4 Selection Sort

Basic Idea:
 Loop through the array from i = 0 to n - 1.
 Select the smallest element in the array from i to n
 Swap this value with value at position i.

Selection sort implementation in C++:

#include <iostream>
#include <vector>
using namespace std;

void selectionSort(vector<int> &arr) {

int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the minimum element with the current element
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}

int main() {
vector<int> arr = {76, 45, 54, 70, 23, 46};

cout << "Array before sorting: ";

for (int num : arr) {
cout << num << " ";
28
 }
cout << endl;

selectionSort(arr);

cout << "Array after sorting: ";

for (int num : arr) {
cout << num << " ";
}
cout << endl;

return 0;
}

 This code defines a function selectionSort that implements the Selection Sort
algorithm.
 It iterates through the array and selects the minimum element in the unsorted portion
of the array and swaps it with the first unsorted element.
 The main function initializes an array, displays it before sorting, sorts it using the
selection sort algorithm, and displays it again after sorting.

Figure 3.3: Example of Selection sort by using sorting algorithms

29
Best-case, Average-case and Worst-case for Searching and Sorting
Algorithms

A. Searching Algorithms:

1. Linear Search:
Best-case: O(1) - The element being searched for is the first element in the array.
Average-case: O(n) - On average, the element will be found in the middle of the array.
Worst-case: O(n) - The element is the last one in the array or not present at all.

2. Binary Search:
Best-case: O(1) - The element is found at the first mid-point check.
Average-case: O(log n) - The element is found after several mid-point checks.
Worst-case: O(log n) - The element is not present, and the array is completely divided.

B. Sorting Algorithms:

1. Selection Sort:

Best-case: O(n²) - Selection sort always performs n(n−1)/2 comparisons, regardless of

the input.
Average-case: O(n²) - The number of comparisons and swaps remains consistent.
Worst-case: O(n²) - Similar to the average case; performance does not change with
input.

2. Bubble Sort:

Best-case: O(n) - The array is already sorted, so only one pass is needed to confirm it.
Average-case: O(n²) - On average, it requires n(n−1)/2 comparisons and swaps.
Worst-case: O(n²) - The array is in reverse order, requiring the maximum number of
swaps.

3. Insertion Sort:

Best-case: O(n) - The array is already sorted, so only n−1 comparisons are needed.
Average-case: O(n²) - On average, elements are inserted in the middle.
Worst-case: O(n²) - The array is in reverse order, requiring maximum shifts for each
insertion.
30
 Chapter 4: Linked Lists

4.1 Introduction to Linked Lists

Linked lists are a fundamental data structure in computer science, used to store
collections of elements in a linear order. Unlike arrays, linked lists store elements in
nodes that contain data and a reference (or pointer) to the next node in the sequence.

Node: The basic unit of a linked list is a node. Each node contains two parts:
Data: The value or data the node holds.
Pointer (Next): A reference to the next node in the list.
Head: The head is the first node in a linked list. It serves as the entry point to the list.
Tail: The tail is the last node in a linked list. In some implementations, the tail node’s
next pointer is set to null (or None in Python) to indicate the end of the list.

4.2 Review on Structures

 Structures are aggregate data types built using elements of primitive data types.
 Structure is defined using the struct keyword:
Example: struct Time {
int hour;
int minute;
int second;
};
 The struct keyword creates a new user defined data type that is used to declare
variables of an aggregate data type.
 Structure variables are declared like variables of other types.
Syntax: struct<structure tag> <variable name>;
31
Example: struct Time timeObject,
struct Time *timeptr

4.2.1 Accessing Members of Structure Variables

 The Dot operator (.): to access data members of structure variables.

 The Arrow operator (->): to access data members of pointer variables pointing to
the structure.
Example, Print member hour of time Object and timeptr.
cout << timeObject.hour; or
cout << timeptr->hour;

 Note: timeptr->hour is the same as (*timeptr).hour

 The parentheses is required since (*) has lower precedence than (.)

4.2.2 Self-Referential Structures

 Structures can hold pointers to instances of themselves.

struct list {
char name[10];
int count;
struct list *next;
};
 However, structures cannot contain instances of themselves.

The List ADT

 A list data structure is sequence of zero or more elements: A1, A2, A3, … AN
N: length of the list
A1: first element
AN: last element
Ai: element at position i
 If N=0, then empty list
Linearly ordered:
Ai precedes Ai+1
Ai follows Ai-1
32
4.2.3 Common operations of the List of data structures

 printList: print the list

 makeEmpty: create an empty list
 find: locate the position of an object in a list
 list: 34,12, 52, 16, 12
 find(52) = 3
 insert: insert an object to a list
 insert(x,3) = 34, 12, 52, x, 16, 12
 remove: delete an element from the list
 remove(52) = 34, 12, x, 16, 12
 findKth: retrieve the element at a certain position

4.2.4 Implementation of an ADT

 Each operation associated with the ADT is implemented by one or more

subroutines(functions)
 Two standard implementations for the list ADT: Array-based and Linked list.

4.2.4.1 Array Implementation

 Need to know the maximum number of elements in the list at the start of the program.
- Difficult
- Wastes space if the guess is bad
 Adding/Deleting an element can take O(n) operations if the list has n elements.
- As it requires shifting of elements
 Accessing/changing an element anywhere takes O(1) operations independent of n.
- Random access
 Elements are stored in contiguous array positions.

Adding an element

 Normally first position (A[0]) stores the current size of the list
 Actual number of elements currsize+1
 Adding at the beginning: Move all elements one position up/behind
33
 Add at position 1;
 Increment the current size by 1
for (j = A[0]+1; j > 1; j--)
A[j] = A[j-1];
A[1] = new element;
A[0]=A[0]+1;

=> Complexity: O(n)

 Adding at the end: Add the element at the end

 Increment current size by 1;
A[A[0]+1] = new element;
A[0]=A[0]+1;

=> Complexity: O(1)

 Adding at kth position: Move all elements one position behind, kth position onwards;
 Add the element at the kth position
 Increment current size by 1;
for (j = A[0]+1; j > k; j--)
A[j] = A[j-1];
A[k] = new element;
A[0]=A[0]+1;

=> Complexity: O(n-k)

 Deleting at the beginning: Move all elements one position ahead;

 Decrement the current size by 1.
for (j = 1; j < A[0] ; j++)
A[j] = A[j+1];
A[0]=A[0]-1;

=> Complexity: O(n)

 Deleting at the End: Delete the element at the end

 Decrement current size by 1;
A[0]=A[0]-1;

=> Complexity: O(1)

34
 Deleting at the kth position: Move all elements down one position ahead, k+1th
position onwards;
 Decrement the current size by 1;
for (j = k; j < A[0]+1; j++)
A[j] = A[j+1];
A[0]=A[0]-1;

=> Complexity: O(n-k)

4.2.4.2 Linked Lists Implementation

 A linked list is a series of connected nodes

 Each node contains at least
 A piece of data (any type)
 Pointer to the next node in the list
 Head: pointer to the first node
 The last node points to NULL.

Table 4.1: Comparison between Arrays and Linked Lists

Arrays Linked Lists

Physically Contiguous Logically Contiguous only
Fixed Length Changeable Length
Access Elements by Index Access Elements by Traversal
Insertion/Removal is Costly Insertion/Removal is Efficient

Defining the data structure for a linked list

 The key part of a linked list is a structure, which holds the data for each node.
 Example: name, address, age or whatever for the items in the list and, most
importantly, a pointer to the next node.

struct node {
char name[20]; // Name of up to 20 letters
int age;
float height; // In metres
node *next; // Pointer to next node
};

35
struct node *head= NULL;

4.2.5 Operations on Linked Lists

 Inserting a node: At the beginning, At the end, At kth position.

 Removing Elements: From front, From end, From kth position.
 Traversing the list.

1. Inserting elements at the beginning:

struct Node {
int data;
Node* next;

// Constructor to initialize a node

Node(int val) {
data = val;
next = nullptr;
}
};

This defines the structure of a node in the linked list. Each node contains an integer data
and a pointer next to the next node.
The constructor initializes the data and sets next to nullptr.

class LinkedList {
private:
Node* head;

public:
// Constructor to initialize an empty linked list
LinkedList() {
head = nullptr;
}

// Function to insert a new node at the beginning

void insertAtBeginning(int val) {
// Create a new node
36
 Node* newNode = new Node(val);

// Point new node's next to the current head

newNode->next = head;

// Update head to the new node

head = newNode;
}

// Function to display the linked list

void display() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "null" << endl;
}

// Destructor to free allocated memory

~LinkedList() {
Node* current = head;
while (current != nullptr) {
Node* nextNode = current->next;
delete current;
current = nextNode;
}
}
};

The LinkedList class manages the linked list operations and contains a pointer head to
the first node.
The constructor initializes head to nullptr, indicating an empty list.

void insertAtBeginning(int val) {

Node* newNode = new Node(val); // Create a new node with the
given value
37
 newNode->next = head; // Link the new node to the
current head
head = newNode; // Update the head to point to
the new node
}

- This function creates a new node with the given value.

- It sets the new node’s next pointer to the current head.
- Finally, it updates the head to the new node.

void display() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "null" << endl;
}

- This function traverses the linked list starting from the head.
- It prints each node’s data followed by an arrow until it reaches the end of the list
(nullptr).

~LinkedList() {
Node* current = head;
while (current != nullptr) {
Node* nextNode = current->next;
delete current;
current = nextNode;
}
}

The destructor ensures that all dynamically allocated memory for the nodes is properly
freed when the LinkedList object is destroyed.

38
int main() {
LinkedList list;

// Insert elements at the beginning

list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);
list.insertAtBeginning(40);
list.insertAtBeginning(50);
list.insertAtBeginning(60);

// Display the linked list

list.display();

return 0;
}

- The main function demonstrates the usage of the LinkedList class.

- It creates a LinkedList object and inserts elements at the beginning.
- Finally, it displays the linked list.

2. Inserting elements at the end

struct Node {
int data;
Node* next;

// Constructor to initialize a node

Node(int val) {
data = val;
next = nullptr;
}
};

This defines the structure of a node in the linked list. Each node contains an integer data
and a pointer next to the next node.
The constructor initializes the data and sets next to nullptr.
39
class LinkedList {
private:
Node* head;

public:
// Constructor to initialize an empty linked list
LinkedList() {
head = nullptr;
}

// Function to insert a new node at the end

void insertAtEnd(int val) {
// Create a new node
Node* newNode = new Node(val);

// If the list is empty, set the new node as the head

if (head == nullptr) {
head = newNode;
return;
}

// Traverse to the last node

Node* current = head;
while (current->next != nullptr) {
current = current->next;
}

// Set the next of the last node to the new node

current->next = newNode;
}

// Function to display the linked list

void display() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "null" << endl;
40
 }

// Destructor to free allocated memory

~LinkedList() {
Node* current = head;
while (current != nullptr) {
Node* nextNode = current->next;
delete current;
current = nextNode;
}
}
};

The destructor ensures that all dynamically allocated memory for the nodes is properly
freed when the LinkedList object is destroyed.

int main() {
LinkedList list;

// Insert elements at the end

list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
list.insertAtEnd(40);
list.insertAtEnd(50);
list.insertAtEnd(60);

// Display the linked list

list.display();

return 0;
}

- The main function demonstrates the usage of the LinkedList class.

- It creates a LinkedList object and inserts elements at the end.
- Finally, it displays the linked list.

41
This implementation provides a basic understanding of how to create a linked list, insert
elements at the end, and display the list using C++.

3. Inserting elements at kth position

struct Node {
int data;
Node* next;

// Constructor to initialize a node

Node(int val) {
data = val;
next = nullptr;
}
};

- This defines the structure of a node in the linked list. Each node contains an integer data
and a pointer next to the next node.
- The constructor initializes the data and sets next to nullptr.

class LinkedList {
private:
Node* head;

public:
// Constructor to initialize an empty linked list
LinkedList() {
head = nullptr;
}

// Function to insert a new node at the k-th position

void insertAtPosition(int val, int position) {
Node* newNode = new Node(val); // Create a new node with
the given value

if (position == 0) { // If inserting at the

beginning
newNode->next = head; // Set the new node's next
to the current head
42
 head = newNode; // Update the head to the
new node
return;
}

Node* current = head;

for (int i = 0; current != nullptr && i < position - 1;
++i) {
current = current->next;
}

if (current == nullptr) { // If the position is out

of bounds
cout << "Position out of bounds" << endl;
delete newNode; // Free the newly
allocated node
return;
}

newNode->next = current->next; // Set the new node's next

to the current node's next
current->next = newNode; // Update the current
node's next to the new node
}

// Function to display the linked list

void display() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "null" << endl;
}

// Destructor to free allocated memory

~LinkedList() {
Node* current = head;
while (current != nullptr) {
43
 Node* nextNode = current->next;
delete current;
current = nextNode;
}
}
};

- The LinkedList class manages the linked list operations and contains a pointer head
to the first node.
- The constructor initializes head to nullptr, indicating an empty list.

void insertAtPosition(int val, int position) {

Node* newNode = new Node(val); // Create a new node with the
given value

if (position == 0) { // If inserting at the

beginning
newNode->next = head; // Set the new node's next to
the current head
head = newNode; // Update the head to the new
node
return;
}

Node* current = head;

for (int i = 0; current != nullptr && i < position - 1; ++i)
{
current = current->next;
}

if (current == nullptr) { // If the position is out of

bounds
cout << "Position out of bounds" << endl;
delete newNode; // Free the newly allocated
node
return;
}
44
 newNode->next = current->next; // Set the new node's next to
the current node's next
current->next = newNode; // Update the current node's
next to the new node
}

- This function creates a new node with the given value.

- If the position is 0, it inserts the new node at the beginning and updates the head.
- Otherwise, it traverses the list to find the node just before the desired position.
- If the position is out of bounds, it prints an error message and frees the allocated node.
- It inserts the new node by updating the pointers accordingly.

void display() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "null" << endl;
}

- This function traverses the linked list starting from the head.
- It prints each node’s data followed by an arrow until it reaches the end of the list
(nullptr).

~LinkedList() {
Node* current = head;
while (current != nullptr) {
Node* nextNode = current->next;
delete current;
current = nextNode;
}
}

45
The destructor ensures that all dynamically allocated memory for the nodes is properly
freed when the LinkedList object is destroyed.

int main() {
LinkedList list;

// Insert elements at specific positions

list.insertAtPosition(10, 0); // Insert 10 at position 0
list.insertAtPosition(20, 1); // Insert 20 at position 1
list.insertAtPosition(30, 1); // Insert 30 at position 1
list.insertAtPosition(40, 2); // Insert 40 at position 2
list.insertAtPosition(50, 0); // Insert 50 at position 0

// Display the linked list

list.display();

return 0;
}

- The main function demonstrates the usage of the LinkedList class.

- It creates a LinkedList object and inserts elements at various positions.
- Finally, it displays the linked list.

4. Removing the elements from the front

struct Node {
int data;
Node* next;

// Constructor to initialize a node

Node(int val) {
data = val;
next = nullptr;
}
};

46
- This defines the structure of a node in the linked list. Each node contains an integer data
and a pointer next to the next node.
- The constructor initializes the data and sets next to nullptr.

class LinkedList {
private:
Node* head;

public:
// Constructor to initialize an empty linked list
LinkedList() {
head = nullptr;
}

// Function to insert a new node at the end

void insertAtEnd(int val) {
Node* newNode = new Node(val);

if (head == nullptr) {
head = newNode;
return;
}

Node* current = head;

while (current->next != nullptr) {
current = current->next;
}

current->next = newNode;
}

// Function to remove a node from the front

void removeFromFront() {
if (head == nullptr) {
cout << "List is empty. Nothing to remove." << endl;
return;
}

47
 Node* temp = head;
head = head->next;
delete temp;
}

// Function to display the linked list

void display() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "null" << endl;
}

// Destructor to free allocated memory

~LinkedList() {
Node* current = head;
while (current != nullptr) {
Node* nextNode = current->next;
delete current;
current = nextNode;
}
}
};

- The LinkedList class manages the linked list operations and contains a pointer head
to the first node.
- The constructor initializes head to nullptr, indicating an empty list.

void insertAtEnd(int val) {

Node* newNode = new Node(val);

if (head == nullptr) {
head = newNode;
return;
}

48
 Node* current = head;
while (current->next != nullptr) {
current = current->next;
}

current->next = newNode;
}

- This function creates a new node with the given value.

- If the list is empty, it sets the new node as the head.
- Otherwise, it traverses to the last node and sets its next pointer to the new node.

void removeFromFront() {
if (head == nullptr) {
cout << "List is empty. Nothing to remove." << endl;
return;
}

Node* temp = head; // Store the current head in a temporary

variable
head = head->next; // Update the head to point to the next
node
delete temp; // Delete the old head node to free
memory
}

- This function removes the node at the front (head) of the linked list.
- If the list is empty (head == nullptr), it prints a message and returns.
- Otherwise, it stores the current head in a temporary variable, updates the head to point
to the next node, and deletes the old head node to free memory.

void display() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
49
 }
cout << "null" << endl;
}

- This function traverses the linked list starting from the head.
- It prints each node’s data followed by an arrow until it reaches the end of the list
(nullptr).

~LinkedList() {
Node* current = head;
while (current != nullptr) {
Node* nextNode = current->next;
delete current;
current = nextNode;
}
}

The destructor ensures that all dynamically allocated memory for the nodes is properly
freed when the LinkedList object is destroyed.

int main() {
LinkedList list;

// Insert elements at the end

list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
list.insertAtEnd(40);
list.insertAtEnd(50);
list.insertAtEnd(60);

// Display the linked list

cout << "Linked list before removal: ";
list.display();

// Remove elements from the front

50
 list.removeFromFront();
cout << "Linked list after removing one element: ";
list.display();

list.removeFromFront();
cout << "Linked list after removing another element: ";
list.display();

list.removeFromFront();
cout << "Linked list after removing the last element: ";
list.display();

list.removeFromFront(); // Trying to remove from an empty

list

return 0;
}

- The main function demonstrates the usage of the LinkedList class.

- It creates a LinkedList object and inserts elements at the end.
- It then displays the linked list, removes elements from the front, and displays the list
after each removal.

5. Removing the elements from the end

struct Node {
int data;
Node* next;

// Constructor to initialize a node

Node(int val) {
data = val;
next = nullptr;
}
};

- This defines the structure of a node in the linked list. Each node contains an integer data
and a pointer next to the next node.
51
- The constructor initializes the data and sets next to nullptr.

class LinkedList {
private:
Node* head;

public:
// Constructor to initialize an empty linked list
LinkedList() {
head = nullptr;
}

// Function to insert a new node at the end

void insertAtEnd(int val) {
Node* newNode = new Node(val);

if (head == nullptr) {
head = newNode;
return;
}

Node* current = head;

while (current->next != nullptr) {
current = current->next;
}

current->next = newNode;
}

// Function to remove a node from the end

void removeFromEnd() {
if (head == nullptr) {
cout << "List is empty. Nothing to remove." << endl;
return;
}

// If there is only one node in the list

if (head->next == nullptr) {
52
 delete head;
head = nullptr;
return;
}

// Traverse to the second last node

Node* current = head;
while (current->next->next != nullptr) {
current = current->next;
}

// Delete the last node and update the second last node's
next to nullptr
delete current->next;
current->next = nullptr;
}

// Function to display the linked list

void display() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "null" << endl;
}

// Destructor to free allocated memory

~LinkedList() {
Node* current = head;
while (current != nullptr) {
Node* nextNode = current->next;
delete current;
current = nextNode;
}
}
};

53
- The LinkedList class manages the linked list operations and contains a pointer head
to the first node.
- The constructor initializes head to nullptr, indicating an empty list.

void insertAtEnd(int val) {

Node* newNode = new Node(val);

if (head == nullptr) {
head = newNode;
return;
}

Node* current = head;

while (current->next != nullptr) {
current = current->next;
}

current->next = newNode;
}

- This function creates a new node with the given value.

- If the list is empty, it sets the new node as the head.
- Otherwise, it traverses to the last node and sets its next pointer to the new node.

void removeFromEnd() {
if (head == nullptr) {
cout << "List is empty. Nothing to remove." << endl;
return;
}

// If there is only one node in the list

if (head->next == nullptr) {
delete head;
head = nullptr;
return;
}

54
 // Traverse to the second last node
Node* current = head;
while (current->next->next != nullptr) {
current = current->next;
}

// Delete the last node and update the second last node's
next to nullptr
delete current->next;
current->next = nullptr;
}

- This function removes the node at the end of the linked list.
- If the list is empty (head == nullptr), it prints a message and returns.
- If there is only one node in the list, it deletes the head and sets head to nullptr.
- Otherwise, it traverses the list to find the second last node, deletes the last node, and
updates the second last node's next pointer to nullptr.

void display() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "null" << endl;
}

- This function traverses the linked list starting from the head.
- It prints each node’s data followed by an arrow until it reaches the end of the list
(nullptr).

~LinkedList() {
Node* current = head;
while (current != nullptr) {
Node* nextNode = current->next;
delete current;
55
 current = nextNode;
}
}

The destructor ensures that all dynamically allocated memory for the nodes is properly
freed when the LinkedList object is destroyed.

int main() {
LinkedList list;

// Insert elements at the end

list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
list.insertAtEnd(40);
list.insertAtEnd(50);
list.insertAtEnd(60);

// Display the linked list

cout << "Linked list before removal: ";
list.display();

// Remove elements from the end

list.removeFromEnd();
cout << "Linked list after removing one element: ";
list.display();

list.removeFromEnd();
cout << "Linked list after removing another element: ";
list.display();

list.removeFromEnd();
cout << "Linked list after removing the last element: ";
list.display();

list.removeFromEnd(); // Trying to remove from an empty list

56
 return 0;
}

- The main function demonstrates the usage of the LinkedList class.

- It creates a LinkedList object and inserts elements at the end.
- It then displays the linked list, removes elements from the end, and displays the list
after each removal.

6. Removing the elements from kth position

struct Node {
int data;
Node* next;

// Constructor to initialize a node

Node(int val) {
data = val;
next = nullptr;
}
};

- This defines the structure of a node in the linked list. Each node contains an integer data
and a pointer next to the next node.
- The constructor initializes the data and sets next to nullptr.

class LinkedList {
private:
Node* head;

public:
// Constructor to initialize an empty linked list
LinkedList() {
head = nullptr;
}

// Function to insert a new node at the end

void insertAtEnd(int val) {
57
 Node* newNode = new Node(val);

if (head == nullptr) {
head = newNode;
return;
}

Node* current = head;

while (current->next != nullptr) {
current = current->next;
}

current->next = newNode;
}

// Function to remove a node from the k-th position (0-

indexed)
void removeFromKthPosition(int k) {
if (head == nullptr) {
cout << "List is empty. Nothing to remove." << endl;
return;
}

// If the head is to be removed

if (k == 0) {
Node* temp = head;
head = head->next;
delete temp;
return;
}

// Find the (k-1)-th node

Node* current = head;
for (int i = 0; current != nullptr && i < k - 1; i++) {
current = current->next;
}

// If k is out of bounds
if (current == nullptr || current->next == nullptr) {
58
 cout << "Position is out of bounds." << endl;
return;
}

// current points to (k-1)-th node, current->next is the

k-th node
Node* temp = current->next;
current->next = current->next->next;
delete temp;
}

// Function to display the linked list

void display() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "null" << endl;
}

// Destructor to free allocated memory

~LinkedList() {
Node* current = head;
while (current != nullptr) {
Node* nextNode = current->next;
delete current;
current = nextNode;
}
}
};

- The LinkedList class manages the linked list operations and contains a pointer head
to the first node.
- The constructor initializes head to nullptr, indicating an empty list.

void insertAtEnd(int val) {

59
 Node* newNode = new Node(val);

if (head == nullptr) {
head = newNode;
return;
}

Node* current = head;

while (current->next != nullptr) {
current = current->next;
}

current->next = newNode;
}

- This function creates a new node with the given value.

- If the list is empty, it sets the new node as the head.
- Otherwise, it traverses to the last node and sets its next pointer to the new node.

void removeFromKthPosition(int k) {
if (head == nullptr) {
cout << "List is empty. Nothing to remove." << endl;
return;
}

// If the head is to be removed

if (k == 0) {
Node* temp = head;
head = head->next;
delete temp;
return;
}

// Find the (k-1)-th node

Node* current = head;
for (int i = 0; current != nullptr && i < k - 1; i++) {
current = current->next;
}
60
 // If k is out of bounds
if (current == nullptr || current->next == nullptr) {
cout << "Position is out of bounds." << endl;
return;
}

// current points to (k-1)-th node, current->next is the k-th

node
Node* temp = current->next;
current->next = current->next->next;
delete temp;
}

- This function removes the node at the k-th position (0-indexed) in the linked list.
- If the list is empty (head == nullptr), it prints a message and returns.
- If the node to be removed is the head (k == 0), it updates the head to the next node and
deletes the old head.
- Otherwise, it traverses the list to find the (k-1)-th node, checks if the k-th node exists,
and then removes the k-th node by updating the (k-1)-th node's next pointer and deleting
the k-th node.

void display() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "null" << endl;
}

- This function traverses the linked list starting from the head.
- It prints each node’s data followed by an arrow until it reaches the end of the list
(nullptr).

~LinkedList() {
Node* current = head;
61
 while (current != nullptr) {
Node* nextNode = current->next;
delete current;
current = nextNode;
}
}

The destructor ensures that all dynamically allocated memory for the nodes is properly
freed when the LinkedList object is destroyed.

int main() {
LinkedList list;

// Insert elements at the end

list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
list.insertAtEnd(40);
list.insertAtEnd(50);

// Display the linked list

cout << "Linked list before removal: ";
list.display();

// Remove element from the 2nd position (0-indexed)

list.removeFromKthPosition(2);
cout << "Linked list after removing from position 2: ";
list.display();

// Remove element from the 0th position (0-indexed)

list.removeFromKthPosition(0);
cout << "Linked list after removing from position 0: ";
list.display();

// Remove element from a position out of bounds

list.removeFromKthPosition(10);
cout << "Linked list after attempting to remove from out-of-
bounds position: ";
62
 list.display();

return 0;
}

- The main function demonstrates the usage of the LinkedList class.

- It creates a LinkedList object and inserts elements at the end.
- It then displays the linked list, removes elements from specific positions, and displays
the list after each removal.

7. Traversing the elements

struct Node {
int data;
Node* next;

// Constructor to initialize a node

Node(int val) {
data = val;
next = nullptr;
}
};

- This defines the structure of a node in the linked list. Each node contains an integer data
and a pointer next to the next node.
- The constructor initializes the data and sets next to nullptr.

class LinkedList {
private:
Node* head;

public:
// Constructor to initialize an empty linked list
LinkedList() {
head = nullptr;
63
 }

// Function to insert a new node at the end

void insertAtEnd(int val) {
Node* newNode = new Node(val);

if (head == nullptr) {
head = newNode;
return;
}

Node* current = head;

while (current->next != nullptr) {
current = current->next;
}

current->next = newNode;
}

// Function to traverse the linked list and print each

element
void traverse() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "null" << endl;
}

// Destructor to free allocated memory

~LinkedList() {
Node* current = head;
while (current != nullptr) {
Node* nextNode = current->next;
delete current;
current = nextNode;
}
}
64
};

- The LinkedList class manages the linked list operations and contains a pointer head
to the first node.
- The constructor initializes head to nullptr, indicating an empty list.

void insertAtEnd(int val) {

Node* newNode = new Node(val);

if (head == nullptr) {
head = newNode;
return;
}

Node* current = head;

while (current->next != nullptr) {
current = current->next;
}

current->next = newNode;
}

- This function creates a new node with the given value.

- If the list is empty, it sets the new node as the head.
- Otherwise, it traverses to the last node and sets its next pointer to the new node.

void traverse() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "null" << endl;
}

- This function traverses the linked list starting from the head.

65
- It prints each node’s data followed by an arrow until it reaches the end of the list
(nullptr).

~LinkedList() {
Node* current = head;
while (current != nullptr) {
Node* nextNode = current->next;
delete current;
current = nextNode;
}
}

The destructor ensures that all dynamically allocated memory for the nodes is properly
freed when the LinkedList object is destroyed.

int main() {
LinkedList list;

// Insert elements at the end

list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
list.insertAtEnd(40);
list.insertAtEnd(50);

// Traverse and display the linked list

cout << "Traversing the linked list: ";
list.traverse();

return 0;
}

- The main function demonstrates the usage of the LinkedList class.

- It creates a LinkedList object and inserts elements at the end.
- It then traverses and displays the linked list, printing each element followed by an
arrow.
66
 Chapter 5: Stack and Queue

5.1 Stacks

A stack is a list with the restriction

- Insertions and deletions can only be performed at the top of the list.
- The other end is called bottom.
- Stacks are less flexible.
- But are more efficient and easy to implement.
- Stacks are known as LIFO (Last In, First Out) lists.
- The last element inserted will be the first to be retrieved.

Fundamental operations:
- Push: Equivalent to an insert
Add an element to the top of the stack
- Pop: Equivalent to delete
Removes the most recently inserted element from the stack
In other words, removes the element at the top of the stack
67
- Top/peek: Examines the most recently inserted element.
Retrieves the top element from the stack.

5.2 Implementation of Stacks

Any list implementation could be used to implement a stack

- Arrays (static: the size of stack is given initially)
- Linked lists (dynamic: never become full)
We will explore implementations based on array and linked list
- Let’s see how to use an array to implement a stack first.

5.2.1 Array Implementation of Stacks

Need to declare an array size ahead of time

Associated with each stack is TopOfStack for an empty stack, set TopOfStack to -1
Push:
(1) Increment TopOfStack by 1.
(2) Set Stack[TopOfStack] = X
Pop:
(1) Set return value to Stack[TopOfStack]
(2) Decrement TopOfStack by 1
- These operations are performed in very fast constant time.

5.2.2 Stack Attributes and Operations

Attributes of Stack:
- maxTop: the max size of stack.
- top: the index of the top element of stack.
- values: element/point to an array which stores elements of stack.
Operations of Stack:
- IsEmpty: return true if stack is empty, return false otherwise.
- IsFull: return true if stack is full, return false otherwise.
- Top: return the element at the top of stack.
- Push: add an element to the top of stack.
- Pop: delete the element at the top of stack.
- DisplayStack: print all the data in the stack.
68
1. Pushing the elements into the stack

#include <iostream>
#include <stdexcept>
using namespace std;

class Stack {
private:
int* arr;
int top;
int capacity;

public:
// Constructor to initialize stack
Stack(int size) {
arr = new int[size];
capacity = size;
top = -1;
}

// Destructor to free memory allocated to the stack

~Stack() {
delete[] arr;
}

// Function to add an element to the stack

void push(int x) {
if (isFull()) {
throw overflow_error("Stack Overflow");
}
arr[++top] = x;
}

// Function to remove an element from the stack

int pop() {
if (isEmpty()) {
throw underflow_error("Stack Underflow");
}
69
 return arr[top--];
}

// Function to return the top element of the stack

int peek() {
if (isEmpty()) {
throw underflow_error("Stack Underflow");
}
return arr[top];
}

// Function to check if the stack is empty

bool isEmpty() const {
return top == -1;
}

// Function to check if the stack is full

bool isFull() const {
return top == capacity - 1;
}

// Function to get the current size of the stack

int size() const {
return top + 1;
}
};

int main() {
// Array to be pushed onto the stack
int elements[] = {9, 8, -7, 4, 11, 6};
int n = sizeof(elements) / sizeof(elements[0]);

// Create a stack with sufficient capacity

Stack stack(n);

// Push elements onto the stack

for (int i = 0; i < n; ++i) {
stack.push(elements[i]);
cout << "Pushed " << elements[i] << " onto the stack.\n";
70
 }

// Print stack elements by popping them

cout << "Stack elements are:\n";
while (!stack.isEmpty()) {
cout << stack.pop() << " ";
}
cout << endl;

return 0;
}

Output Console:

Figure 5.1: The output form of pushing elements into the stack
1. Class Definition: The Stack class includes private members for the array arr to hold
stack elements, the integer top to keep track of the top index, and the integer capacity to
store the stack's capacity.

2. Constructor and Destructor: The constructor initializes the stack with a given size and
sets top to -1. The destructor frees the allocated memory.

3. Push Function: The push method checks if the stack is full using isFull(). If not, it
increments top and assigns the value to arr[top].

4. Pop Function: The pop method checks if the stack is empty using isEmpty(). If not,
it returns the top element and decrements top.

5. Peek Function: The peek method returns the top element without modifying the stack.

71
6. isEmpty and isFull Functions: These methods check if the stack is empty or full
by comparing top with -1 or capacity -1.

7. Driver Code: In the main function, we create a stack, push the elements of the array
onto it, and then pop and print the elements to demonstrate the stack operations.

This code provides a simple implementation of a stack using an array and demonstrates
basic stack operations.

2. Popping the elements into the stack

#include <iostream>
#include <stdexcept>
using namespace std;

class Stack {
private:
int* arr;
int top;
int capacity;

public:
// Constructor to initialize stack
Stack(int size) {
arr = new int[size];
capacity = size;
top = -1;
}

// Destructor to free memory allocated to the stack

~Stack() {
delete[] arr;
}

// Function to add an element to the stack

void push(int x) {
if (isFull()) {
throw overflow_error("Stack Overflow");
}
arr[++top] = x;
72
 }

// Function to remove an element from the stack

int pop() {
if (isEmpty()) {
throw underflow_error("Stack Underflow");
}
return arr[top--];
}

// Function to return the top element of the stack

int peek() {
if (isEmpty()) {
throw underflow_error("Stack Underflow");
}
return arr[top];
}

// Function to check if the stack is empty

bool isEmpty() const {
return top == -1;
}

// Function to check if the stack is full

bool isFull() const {
return top == capacity - 1;
}

// Function to get the current size of the stack

int size() const {
return top + 1;
}
};

int main() {
// Array to be pushed onto the stack
int elements[] = {7, 11, -9, -10, -18, 2, -15};
int n = sizeof(elements) / sizeof(elements[0]);

73
 // Create a stack with sufficient capacity
Stack stack(n);

// Push elements onto the stack

for (int i = 0; i < n; ++i) {
stack.push(elements[i]);
cout << "Pushed " << elements[i] << " onto the stack.\n";
}

// Print stack elements by popping them

cout << "Popping elements from the stack:\n";
while (!stack.isEmpty()) {
cout << stack.pop() << " ";
}
cout << endl;

return 0;
}

Output Console:

Figure 5.2: The output form of popping elements into the stack

1. Class Definition: The Stack class includes private members for the array arr to hold
stack elements, the integer top to keep track of the top index, and the integer capacity to
store the stack's capacity.

2. Constructor and Destructor: The constructor initializes the stack with a given size and
sets top to -1. The destructor frees the allocated memory.

3. Push Function: The push method checks if the stack is full using isFull(). If not, it
increments top and assigns the value to arr[top].

74
4. Pop Function: The pop method checks if the stack is empty using isEmpty(). If not,
it returns the top element and decrements top.

5. Peek Function: The peek method returns the top element without modifying the stack.

6. isEmpty and isFull Functions: These methods check if the stack is empty or full
by comparing top with -1 or capacity -1.

7. Driver Code: In the main function, we create a stack, push the elements of the array
onto it, and then pop and print the elements to demonstrate the stack operations.

5.2.3 Linked List Implementation of Stacks

- Need not know the maximum size

- Add/Access/Delete in the beginning, O(1)
- Need several memory access, deletions.

The PUSH and POP operations in linked lists:

Algorithm for PUSH operations:

Step-1: Create the new node
Step-2: Check if the top of Stack is empty or not if so, go to step-3 else go to step-4
Step-3: Make your "topOfstack" pointer point to it and quit.
Step-4: Assign the topOfstackpointer to the newly attached element.

push(node *newnode)
{
cout << "Add data" <<endl;
cin >> newnode -> item;
newnode -> next = NULL;
if( topOfStack = = NULL){
topOfStack = newnode;
}
else {
newnode -> next = topOfStack;
topOfStack = newnode;
}
}

75
Algorithm for POP operations:
Step-1: If the Stack is empty then give an alert message "Stack Underflow" and quit; else
proceed.
Step-2: Make "target" point to topOfstack next pointer.
Step-3: Free the topOfstack node;
Step-4: Make the node pointed by "target" as your TOP most element.

int pop( ) {
int pop_val= 0;
if(topOfStack = = NULL)
cout << "Stack Underflow";
else {
node *temp= topOfStack;
pop_val= temp->data;
topOfStack =topOfStack-> next;
delete temp;
}
return(pop_val);
}

5.3 Application of Stack Data Structure

Balancing Symbols: to check that every right brace, bracket, and parentheses must
correspond to its left counterpart
Example, [( )] is legal, but [( ] ) is illegal
Algorithm:
(1) Make an empty stack.
(2) Read characters until end of file:
I. If the character is an opening symbol, push it onto the stack
II. If it is a closing symbol, then if the stack is empty, report an error
III. Otherwise, pop the stack. If the symbol popped is not the corresponding opening
symbol, then report an error
(3) At end of file, if the stack is not empty, report an error

5.4 Expression Evaluations

There are three common notations to represent arithmetic expressions

76
Infix: operators are between operands. Example, A + B
Prefix (polish notation): operators are before their operands. Example, + A B
Postfix (Reverse notation): operators are after their operands. Example, A B +.

- Though infix notation is convenient for human beings, postfix notation is much
cheaper and easy for machines.
- Therefore, computers change the infix to postfix notation first
- Then, the post-fix expression is evaluated.

5.4.1 Algorithm for Infix to Postfix

Examine the next element in the input.

- If it is operand, output it.
- If it is opening parenthesis, push it on stack.
- If it is an operator, then
- If stack is empty, push operator on stack.
- If the top of stack is opening parenthesis, push operator on stack
- If it has higher priority than the top of stack, push operator on stack.
- Else pop the operator from the stack and output it, repeat the fourth step.
- If it is a closing parenthesis, pop operators from stack and output them until an opening
parenthesis is encountered. pop and discard the opening parenthesis.
- If there is more input go to first step.
- If there is no more input, pop the remaining operators to output.

Example: Suppose we want to see the infix notation: A + B * C, Convert to Prefix and
Postfix notation.

To convert an infix expression like A + B * C to its equivalent prefix and postfix

expressions, we can follow systematic procedures. These conversions involve
understanding the order of operations (precedence) and associativity of the operators.
Here is a step-by-step explanation of how to perform these conversions.

Step-by-Step Conversion from Infix to Prefix

Infix Expression: A + B * C

Step 1: Identify Operators and Operands

Operators: + and *
Operands: A, B, and C
77
Step 2: Understand Operator Precedence and Associativity

* (multiplication) has higher precedence than + (addition).

Both operators are left associative.
Step 3: Convert to Prefix (Polish Notation)

Start from the operator with the highest precedence (* in this case).
Write the operator before its operands (prefix form).
Move to the next operator with lower precedence (+).

Conversion Steps:

Identify the sub-expression with the highest precedence: B * C.

Convert B * C to prefix: * B C.
Now, handle the + operator with its operands, A and the result of * B C.
Result: + A * B C

Step-by-Step Conversion from Infix to Postfix

Infix Expression: A + B * C

Step 1: Identify Operators and Operands

Operators: + and *
Operands: A, B, and C
Step 2: Understand Operator Precedence and Associativity

* (multiplication) has higher precedence than + (addition).

Both operators are left associative.
Step 3: Convert to Postfix (Reverse Polish Notation)

Start from the operator with the highest precedence (* in this case).
Write the operands first, followed by the operator (postfix form).
Move to the next operator with lower precedence (+).
Conversion Steps:

Identify the sub-expression with the highest precedence: B * C.

Convert B * C to postfix: B C *.
Now, handle the + operator with its operands, A and the result of B C *.
Result: A B C * +

78
Summary:
Infix Expression: A + B * C
Prefix Expression: + A * B C
Postfix Expression: A B C * +

5.5 Queues

- Like a stack, a queue is also a list.

- However, with a queue, insertion is done at one end, while deletion is performed at the
other end.
- Accessing the elements of queues follows a First In, First Out (FIFO) order.
- Like customers standing in a check-out line in a shop, the first customer in is the first
customer served.

Basic operations:
enqueue: insert an element at the rear of the list.
dequeue: delete the element at the front of the list.

Like check-out lines in a store, a queue has a front and a rear.

5.5.1 Implementation of Queues

- Just as stacks can be implemented as arrays or linked lists, so with queues.

- Dynamic queues have the same advantages over static queues as dynamic stacks have
over static stacks.

- There are several different algorithms to implement Enqueue and Dequeue

- When enqueuing, the front index is always fixed and the rear index moves forward in
the array.
- When dequeuing, the element at the front of the queue is removed. Move all the
elements after it by one position.

5.5.2 Empty or Full?

Empty queue:
- back = front - 1
79
Full queue:
- We need to count to know if queue is full
Solutions:
- Use a boolean variable to say explicitly whether the queue is empty or not
- Make the array of size n+1 and only allow n elements to be stored
- Use a counter of the number of elements in the queue

5.5.3 Queue Attributes and Operations

Attributes of Queue:
- front/rear: front/rear index.
- counter: number of elements in the queue.
- maxSize: capacity of the queue.
- values: point to an array which stores elements of the queue.
Operations of Queue:
- IsEmpty: return true if queue is empty, return false otherwise.
- IsFull: return true if queue is full, return false otherwise.
- Enqueue: add an element to the rear of queue.
- Dequeue: delete the element at the front of queue.
- DisplayQueue: print all the data.

1. Implementation of C++ to enqueuing and dequeuing from the queue by using array

#include <iostream>
#include <stdexcept>
using namespace std;

class Queue {
private:
int* arr;
int front;
int rear;
int capacity;
int count;

public:
// Constructor to initialize the queue
80
Queue(int size) {
arr = new int[size];
capacity = size;
front = 0;
rear = -1;
count = 0;
}

// Destructor to free memory allocated to the queue

~Queue() {
delete[] arr;
}

// Function to add an element to the queue

void enqueue(int x) {
if (isFull()) {
throw overflow_error("Queue Overflow");
}
rear = (rear + 1) % capacity;
arr[rear] = x;
count++;
}

// Function to remove an element from the queue

int dequeue() {
if (isEmpty()) {
throw underflow_error("Queue Underflow");
}
int item = arr[front];
front = (front + 1) % capacity;
count--;
return item;
}

// Function to return the front element of the queue

int peek() {
if (isEmpty()) {
throw underflow_error("Queue Underflow");
}
81
 return arr[front];
}

// Function to check if the queue is empty

bool isEmpty() const {
return count == 0;
}

// Function to check if the queue is full

bool isFull() const {
return count == capacity;
}

// Function to get the current size of the queue

int size() const {
return count;
}
};

int main() {
// Array to be enqueued
int elements[] = {5, 7, 3, 4, 8, 11, 14, 17};
int n = sizeof(elements) / sizeof(elements[0]);

// Create a queue with sufficient capacity

Queue queue(n);

// Enqueue elements into the queue

for (int i = 0; i < n; ++i) {
queue.enqueue(elements[i]);
cout << "Enqueued " << elements[i] << " into the
queue.\n";
}

// Dequeue elements from the queue and print them

cout << "Dequeued elements from the queue:\n";
while (!queue.isEmpty()) {
cout << queue.dequeue() << " ";
}
82
 cout << endl;

return 0;
}

Output Console:

Figure 5.3: The output form of enqueuing and dequeuing elements into the queue by using array

1. Define the Node Structure: Create a structure that represents a node in the linked list,
including a data field and a pointer to the next node.

2. Define the Queue Class: Create a class that represents a queue, including member
variables for the front and rear pointers of the linked list.

3. Initialize the Queue: Provide a constructor to initialize the queue with front and rear
pointers set to nullptr.

4. Enqueue Operation: Implement a function to add elements to the rear of the queue.

5. Dequeue Operation: Implement a function to remove elements from the front of the
queue.

6. Front Operation: Implement a function to return the front element of the queue without
removing it.

7. isEmpty Operation: Implement a function to check if the queue is empty.

8. Driver Code: Use the queue class to enqueue and dequeue the array of integers and
demonstrate its functionality.

83
2. Implementation of C++ to enqueuing and dequeuing from the queue by using linked
list

#include <iostream>
#include <stdexcept>
using namespace std;

// Define the structure for a Node in the linked list

struct Node {
int data;
Node* next;

Node(int value) : data(value), next(nullptr) {}

};

// Define the Queue class

class Queue {
private:
Node* front;
Node* rear;

public:
// Constructor to initialize the queue
Queue() : front(nullptr), rear(nullptr) {}

// Destructor to free memory allocated to the queue

~Queue() {
while (!isEmpty()) {
dequeue();
}
}

// Function to add an element to the queue

void enqueue(int x) {
Node* newNode = new Node(x);
if (isEmpty()) {
front = rear = newNode;
84
 } else {
rear->next = newNode;
rear = newNode;
}
}

// Function to remove an element from the queue

int dequeue() {
if (isEmpty()) {
throw underflow_error("Queue Underflow");
}
Node* temp = front;
int data = temp->data;
front = front->next;
delete temp;
if (front == nullptr) {
rear = nullptr;
}
return data;
}

// Function to return the front element of the queue

int peek() const {
if (isEmpty()) {
throw underflow_error("Queue Underflow");
}
return front->data;
}

// Function to check if the queue is empty

bool isEmpty() const {
return front == nullptr;
}
};

int main() {
// Array to be enqueued
int elements[] = {5, 7, 3, 4, 8, 11, 14, 17};
int n = sizeof(elements) / sizeof(elements[0]);
85
 // Create a queue
Queue queue;

// Enqueue elements into the queue

for (int i = 0; i < n; ++i) {
queue.enqueue(elements[i]);
cout << "Enqueued " << elements[i] << " into the
queue.\n";
}

// Dequeue elements from the queue and print them

cout << "Dequeued elements from the queue:\n";
while (!queue.isEmpty()) {
cout << queue.dequeue() << " ";
}
cout << endl;

return 0;
}

Output Console:

Figure 5.4: The output form of enqueuing and dequeuing elements into the queue by using linked list

1. Node Structure: The Node structure represents a node in the linked list. Each node
contains an integer data field and a pointer to the next node.

2. Queue Class: The Queue class contains private member variables front and rear, which
are pointers to the front and rear nodes of the linked list, respectively.

86
3. Constructor and Destructor: The constructor initializes the front and rear pointers to
nullptr, indicating an empty queue. The destructor frees the allocated memory by
dequeuing all elements until the queue is empty.

4. Enqueue Function: The enqueue method creates a new node with the given data. If the
queue is empty, both front and rear point to the new node. Otherwise, the new node is
added to the end of the queue, and rear is updated to point to this new node.

5. Dequeue Function: The dequeue method checks if the queue is empty. If not, it
retrieves the data from the front node, updates front to point to the next node, and deletes
the old front node. If the queue becomes empty after the dequeue operation, rear is also
set to nullptr.

6. Peek Function: The peek method returns the data from the front node without
modifying the queue.

7. isEmpty Function: This method checks if the queue is empty by checking if front is
nullptr.

8. Driver Code: In the main function, we create a queue, enqueue the elements of the
array onto it, and then dequeue and print the elements to demonstrate the queue
operations.

87
 Chapter 6: Trees

6.1 Trees

- Linear access time of linked lists is expensive

- Requires O(N) running time for most of basic operations like search, insert and delete
- Does there exist any simple data structure for which the running time of most
operations (search, insert, delete) is O(log N)?
- The answer is yes
- Data structures like binary tree

- A tree is a collection of nodes

- The collection can be empty
- (The recursive definition) If not empty, a tree consists of a distinguished node r (the
root), and zero or more nonempty sub-trees T1, T2, ...., Tk, each of whose roots are
connected by an edge from r.

88
 Figure 6.1: Trees

SOME TERMINOLOGIES:

Child and parent: Every node except the root has one parent (J is a parent of P and Q)
A node can have an arbitrary number of children (A has 6 while D has 1)
Leaves/External Nodes: Nodes with no children (B, C, H, I, P, Q, K, L, M, N)
Sibling: nodes with same parent (P and Q)
Internal node: A node with at least one child (A,D,E,F,G,J)
Path: is a sequence of nodes from root to a node (arbitrary node in the tree).
Length: Number of edges on the path from node x to node y
Depth of a node: Number of edges from the root to that node (Depth of C =1).
Height of a node:
- Length of the longest path from that node to a leaf (E=2)
- All leaves are at height 0
- The height of a tree is equal to the height of the root.
Ancestor and descendant:
- The ancestors of a node are all the nodes along the path from the root to the node.
- Descendant node reachable by repeated proceeding from parent to child.

6.2 Example of Trees

 Tree is useful to represent hierarchical data

 One of its application a file system used by many systems
 The following is an example of UNIX file system

Figure 6.2: Examples of UNIX File System

89
 We use struct/class to abstract nodes

Generic methods:
- integer size()
- boolean isEmpty()
- displayElements()
Accessor methods:
- Object root()
- Object parent(p)
- displayChildren(p)
Query methods:
- boolean isInternal(p)
- boolean isExternal(p)
- boolean isRoot(p)
Update methods:
- swapElements(p, q)
- object replaceElement(p, o)

 Additional update methods may be defined by data structures implementing the Tree
ADT.

6.3 Tree Representation

A node is represented by an object storing

- Element
- Parent node
- Sequence of children nodes

6.3.1 Binary Tree

 A binary tree is a tree with the following properties:

 Each internal node has at most two children (degree of two)
 The children of a node are an ordered pair
 We call the children of an internal node left child and right child
 Alternative recursive definition: a binary tree is either a tree consisting of a single
node, OR a tree whose root has an ordered pair of children, each of which is a binary
tree.
90
 The Binary Tree ADT extends the Tree ADT, it inherits all the methods of the Tree
ADT.
Additional methods:
- position leftChild(p)
- position rightChild(p)
- position sibling(p)
 Update methods may be defined by data structures implementing the Binary Tree
ADT.

6.3.2 Data Structures for Binary Trees

A node is represented by an object storing

- Element
- Parent node
- Left child node
- Right child node

Implementation of Trees in C++:

#include <iostream>
#include <queue>
using namespace std;

// Define the structure for a Node in the tree

struct Node {
int data;
Node* left;
Node* right;

Node(int value) : data(value), left(nullptr), right(nullptr)

{}
};

// Define the BinaryTree class

class BinaryTree {
private:
Node* root;
91
 // Helper function for in-order traversal
void inOrder(Node* node) {
if (node == nullptr) return;
inOrder(node->left);
cout << node->data << " ";
inOrder(node->right);
}

// Helper function for pre-order traversal

void preOrder(Node* node) {
if (node == nullptr) return;
cout << node->data << " ";
preOrder(node->left);
preOrder(node->right);
}

// Helper function for post-order traversal

void postOrder(Node* node) {
if (node == nullptr) return;
postOrder(node->left);
postOrder(node->right);
cout << node->data << " ";
}

public:
// Constructor to initialize the tree
BinaryTree() : root(nullptr) {}

// Function to insert a node into the tree

void insert(int value) {
Node* newNode = new Node(value);
if (root == nullptr) {
root = newNode;
return;
}

queue<Node*> q;
q.push(root);
92
 while (!q.empty()) {
Node* temp = q.front();
q.pop();

if (temp->left == nullptr) {
temp->left = newNode;
return;
} else {
q.push(temp->left);
}

if (temp->right == nullptr) {
temp->right = newNode;
return;
} else {
q.push(temp->right);
}
}
}

// Function for in-order traversal

void inOrderTraversal() {
inOrder(root);
cout << endl;
}

// Function for pre-order traversal

void preOrderTraversal() {
preOrder(root);
cout << endl;
}

// Function for post-order traversal

void postOrderTraversal() {
postOrder(root);
cout << endl;
}

93
 // Function to search for a value in the tree
bool search(int value) {
if (root == nullptr) return false;

queue<Node*> q;
q.push(root);

while (!q.empty()) {
Node* temp = q.front();
q.pop();

if (temp->data == value) {
return true;
}

if (temp->left != nullptr) {
q.push(temp->left);
}

if (temp->right != nullptr) {
q.push(temp->right);
}
}

return false;
}
};

// Main function to demonstrate the BinaryTree class

int main() {
BinaryTree tree;

// Insert elements into the tree

int elements[] = {5, 7, 3, 4, 8, 11, 14, 17};
for (int value : elements) {
tree.insert(value);
}

// Perform tree traversals

94
 cout << "In-order Traversal: ";
tree.inOrderTraversal();

cout << "Pre-order Traversal: ";

tree.preOrderTraversal();

cout << "Post-order Traversal: ";

tree.postOrderTraversal();

// Search for elements in the tree

int searchValue = 8;
if (tree.search(searchValue)) {
cout << "Value " << searchValue << " found in the tree."
<< endl;
} else {
cout << "Value " << searchValue << " not found in the
tree." << endl;
}

searchValue = 10;
if (tree.search(searchValue)) {
cout << "Value " << searchValue << " found in the tree."
<< endl;
} else {
cout << "Value " << searchValue << " not found in the
tree." << endl;
}

return 0;
}

Output Console:

Figure 6.3: Output form of Trees & Traversal

95
1. Node Structure: The Node structure represents a node in the binary tree. Each node
contains an integer data field and pointers to the left and right child nodes.

2. BinaryTree Class: The BinaryTree class contains a private member root, which is
a pointer to the root node of the tree. The class includes methods for inserting nodes,
traversing the tree (in-order, pre-order, and post-order), and searching for a value in the
tree.

3. Insertion: The insert method creates a new node with the given value and inserts it into
the tree. If the tree is empty, the new node becomes the root. Otherwise, the method
performs a level-order traversal to find the appropriate position for the new node.

4. Traversal: The traversal methods (inOrder, preOrder, and postOrder) are

implemented as private helper functions. These methods recursively traverse the tree and
print the node values in the respective order.

5. Search: The search method performs a level-order traversal to find the node with the
specified value. If found, it returns true; otherwise, it returns false.

6. Driver Code: In the main function, we create a BinaryTree object, insert elements
into the tree, perform different traversals, and search for specific values to demonstrate
the tree operations.

6.4 Tree Traversal

Used to print out the data in a tree in a certain order

- Pre-order traversal
- Print the data at the root
- Recursively print out all data in the left subtree
- Recursively print out all data in the right subtree

1. Preorder traversal: node, left, right

It uses prefix expression.
2. Postorder traversal: left, right, node
It uses postfix expression.
3. Inorder traversal: left, node, right.
It uses infix expression.

96
6.5 Binary Search Trees

Stores keys in the nodes in a way so that searching, insertion and deletion can be done
efficiently.
Binary search tree property
- For every node X, all the keys in its left subtree are smaller than the key value in X, and
all the keys in its right subtree are larger than the key value in X.

Figure 6.4: Binary Search Trees

 Average depth of a node is O(log N); maximum depth of a node is O(N).

Implementation of Binary Search Tree (BST) in C++:

#include <iostream>
using namespace std;

// Define the structure for a Node in the BST

struct Node {
int data;
Node* left;
Node* right;

Node(int value) : data(value), left(nullptr), right(nullptr)

{}
};

97
// Define the BinarySearchTree class
class BinarySearchTree {
private:
Node* root;

// Helper function for in-order traversal

void inOrder(Node* node) {
if (node == nullptr) return;
inOrder(node->left);
cout << node->data << " ";
inOrder(node->right);
}

// Helper function for pre-order traversal

void preOrder(Node* node) {
if (node == nullptr) return;
cout << node->data << " ";
preOrder(node->left);
preOrder(node->right);
}

// Helper function for post-order traversal

void postOrder(Node* node) {
if (node == nullptr) return;
postOrder(node->left);
postOrder(node->right);
cout << node->data << " ";
}

// Helper function to insert a new node in the BST

Node* insert(Node* node, int value) {
if (node == nullptr) {
return new Node(value);
}

if (value < node->data) {

node->left = insert(node->left, value);
} else {
node->right = insert(node->right, value);
98
 }

return node;
}

// Helper function to search for a value in the BST

bool search(Node* node, int value) {
if (node == nullptr) return false;

if (node->data == value) return true;

if (value < node->data) {

return search(node->left, value);
} else {
return search(node->right, value);
}
}

public:
// Constructor to initialize the BST
BinarySearchTree() : root(nullptr) {}

// Function to insert a new value in the BST

void insert(int value) {
root = insert(root, value);
}

// Function to search for a value in the BST

bool search(int value) {
return search(root, value);
}

// Function for in-order traversal

void inOrderTraversal() {
inOrder(root);
cout << endl;
}

// Function for pre-order traversal

99
 void preOrderTraversal() {
preOrder(root);
cout << endl;
}

// Function for post-order traversal

void postOrderTraversal() {
postOrder(root);
cout << endl;
}
};

// Main function to demonstrate the BinarySearchTree class

int main() {
BinarySearchTree bst;

// Insert elements into the BST

int elements[] = {5, 6, 9, 10, -14};
for (int value : elements) {
bst.insert(value);
}

// Perform tree traversals

cout << "In-order Traversal: ";
bst.inOrderTraversal();

cout << "Pre-order Traversal: ";

bst.preOrderTraversal();

cout << "Post-order Traversal: ";

bst.postOrderTraversal();

// Search for elements in the BST

int searchValue = 8;
if (bst.search(searchValue)) {
cout << "Value " << searchValue << " found in the BST."
<< endl;
} else {

100
 cout << "Value " << searchValue << " not found in the
BST." << endl;
}

searchValue = 10;
if (bst.search(searchValue)) {
cout << "Value " << searchValue << " found in the BST."
<< endl;
} else {
cout << "Value " << searchValue << " not found in the
BST." << endl;
}

return 0;
}

Output Console:

Figure 6.5: Output forms of Binary Search Trees

1. Node Structure: The Node structure represents a node in the BST. Each node contains
an integer data field and pointers to the left and right child nodes.

2. BinarySearchTree Class: The BinarySearchTree class contains a private

member root, which is a pointer to the root node of the tree. The class includes methods
for inserting nodes, traversing the tree (in-order, pre-order, and post-order), and
searching for a value in the tree.

3. Insertion: The insert method is a recursive function that inserts a new value into the
BST while maintaining the BST property. If the tree is empty, the new node becomes the
root. Otherwise, the method recursively finds the correct position for the new node.

4. Traversal: The traversal methods (inOrder, preOrder, and postOrder) are

implemented as private helper functions. These methods recursively traverse the tree and
print the node values in the respective order.
101
5. Search: The search method is a recursive function that searches for a value in the BST.
If the value is found, it returns true; otherwise, it returns false.

7. Driver Code: In the main function, we create a BinarySearchTree object, insert

elements into the tree, perform different traversals, and search for specific values to
demonstrate the tree operations.

6.5.1 findMin, findMax and delete

findMin: Return the node containing the smallest element in the tree

Start at the root and go left as long as there is a left child. The stopping point is the
smallest element

Node*findMin(node*root)
{
If(root==NULL)
Return Null;
Else if(root->left==Null)
Return root
Else
Return(findMin(root->left)
}

Similarly for findMax, findMin

Time complexity = O(height of the tree)

findMax: Finds the maximum element in BST

Start at the root and go right as long as there is a right child. The stopping point is the
largest element

Node*findMin(node*root)
{
If(root==NULL)
Return Null;
Else if(root->right==Null)
Return root
102
Else
Return(findMin(root->right)
}

delete:When we delete a node, we need to consider how we take care of the children
of the deleted node.
When a node is deleted the definition of a BST should be maintained.
When a node is deleted four cases should be considered
Case 1: Deleting a leaf node (a node with no child)
Case 2: Deleting a node having only one child
Case 3: Deleting a node having two child
Case 4: Deleting a root node

 If BST has only one node, make root to point to nothing, Root=NULL
 Otherwise, copy the node containing the largest element in the left (or the smallest
element in the right)to the node to be deleted.
 Delete the copied node.

103