Amman Arab University

College of Information Technology

Data Structures

Course Name: Data Structures

Semester: Second (Spring)
 Course objectives

Course Overview
Course
Syllabus Grading criteria

Resources and references

Course objectives

• To provide knowledge of basic data structures and their

implementations.
• To recognize the role of abstraction in the design data
structures and algorithms, and algorithm analysis.
• To recognize the strength and weakness of different data
structures.
• To understand the importance of data structures in context
of writing efficient programs.
• To develop skills to apply appropriate data structures in
problem solving.
• To use the appropriate data structure in context of
solution of given problem.
• To develop programming skills which require to solve
given problem.
 Introduction to ADTs & C++ Review

Algorithm Analysis: Time Complexity & Big-O

Arrays: Unsorted & Sorted (Binary Search)

Course
Linked Lists: Unsorted & Sorted
Overview:
Stacks & Queues: Implementation & Applications
Data
Recursion: Tail & Standard Recursion
Structures
Trees: Binary Trees & Binary Search Trees (BST)

BST Operations & Traversals

Comparing BSTs to Linear Lists

Real-World Applications of Data Structures

 Assessment Expected Weight Assessment Expected Weight

Grading Tools
Midterm Exam
Due Date
8th week
(100%)
30%
Tools
Mid-Term Exam
Due Date
8th week
(100%)
20%

Criteria Activities (≥6)

Final Exam
Next lecture

16th or 17th
30%

40%
Activities (≥5)

Final Exam
Next lecture

16th or 17th
40%

40%
week week
 Recommended Textbooks

Online Learning Platforms (Coursera, edX,

Udacity)
Resources
Research Papers & Journals
and
References Official Documentation (C++, Python,
Data Structures)

University Lecture Notes & Slides

Additional Reading Materials & Blogs

 What are data
structures?
Introduction Importance in
to Data
Structures
computer science

Real-world
applications
 Ways to organize, store,
and manage data
efficiently.
What Are Provide structured
Data formats for handling
Structures? data.
Examples: Arrays, Linked
Lists, Stacks, Queues,
Trees, Graphs.
 Data structures are crucial because they:

Importance Improve efficiency – Faster data access

and modification.
in
Computer Optimize memory use – Reduce wasted
space and processing time.
Science
Enable complex problem-solving – Used
in algorithms for searching, sorting, etc.

Support software development – Key for

databases, AI, and networking.
 Real-World Applications

DATA STRUCTURES ARE DATABASES – ORGANIZING OPERATING SYSTEMS – WEB SEARCH ENGINES –
WIDELY USED IN: RECORDS EFFICIENTLY MANAGING PROCESSES STORING AND RETRIEVING
USING TREES AND HASH AND MEMORY WITH DATA QUICKLY USING
TABLES. QUEUES AND STACKS. TREES AND GRAPHS.

AI & MACHINE LEARNING – NETWORKING –

HANDLING LARGE MANAGING DATA PACKETS
DATASETS EFFICIENTLY. AND ROUTING USING
QUEUES AND GRAPHS.
 Abstract Data Types (ADT) & C++ Review

DEFINITION OF ADT ROLE OF ADTS IN C++ SYNTAX AND MEMORY

SOFTWARE DESIGN MANAGEMENT RECAP
Definition of Abstract Data Type (ADT)

An Abstract Data
Specifies what
Type (ADT) defines a
operations can be
data structure
performed, not how
conceptually,
they are
without specifying
implemented.
implementation.

Example: A Stack
ADT defines push
Examples: Stack, and pop operations
Queue, List, Set. but not the
implementation
(array or linked list).
 Role of ADTs in Software Design

ADTS ARE IMPORTANT IN ENCAPSULATE DATA – HIDES ENHANCE MODULARITY – IMPROVE REUSABILITY –
SOFTWARE DEVELOPMENT IMPLEMENTATION DETAILS, MAKES PROGRAMS EASIER PREDEFINED STRUCTURES
BECAUSE THEY: SIMPLIFYING COMPLEXITY. TO MAINTAIN AND UPDATE. CAN BE USED ACROSS
MULTIPLE PROJECTS.
C++ Syntax and Memory Management
Recap

Key concepts in C++ syntax and

memory management:

Variables, loops, conditions,

functions, and classes form the
core syntax.

Dynamic memory allocation:

Using `new` and `delete`.

Example: Allocating and

freeing memory dynamically in
C++.
 Code example of dynamic
memory allocation:
Example: C++
Memory
Management int* num = new int; // allocate
memory
*num = 5; // assign value
delete num; // free
memory
 Introduction to
templates

Template
Functions Benefits of
& Class reusable code

Templates
Examples of
function and class
templates
 Templates in C++ allow
writing generic code that
works with any data type.

Enable code reusability and

Introduction flexibility.

to
Templates Avoid writing separate
functions for different
types.

Used for both functions and

classes.
 Why use templates?

Benefits Saves time – No need for

multiple versions of the
of same function/class.

Reusable
Increases flexibility – Works
Code with different data types.

Reduces errors – One

implementation avoids
redundancy.
 Function Template
Example
• Example of a generic function:
•
#include <iostream>
using namespace std;

template <typename T>

T add(T a, T b) {
return a + b;
}

int main() {
cout << add(5, 10) << endl; // Works with integers
cout << add(5.5, 2.5) << endl; // Works with floating points
return 0;
}
 • Example of a generic class:
•
template <class T>
class Box {
private:

Class T value;
public:
Box(T v) { value = v; }
void show() { cout << "Box contains: " <<

Template value << endl; }

};

int main() {

Example Box<int> intBox(10);

Box<string> strBox("Template");

intBox.show();
strBox.show();
}
 • Time complexity (Big-O
Algorithm notation)
• Logarithms and series
Analysis • Running time calculations
• Worst-case, best-case, and
average-case analysis
 Algorithm
Analysis

• Understanding how efficient an

algorithm is in terms of time and
space complexity.
• Helps compare different
algorithms.
• Measures performance for large
datasets.
• Uses mathematical tools like Big-
O notation and logarithms.
 Time Complexity
(Big-O Notation)

• Big-O notation describes how an

algorithm's runtime grows with
input size.
• O(1): Constant time (e.g.,
accessing an element in an
array).
• O(n): Linear time (e.g., searching
in an unsorted list).
• O(log n): Logarithmic time (e.g.,
binary search).
• O(n²): Quadratic time (e.g.,
bubble sort).
 Logarithms and
Series

• Logarithms help analyze efficient

algorithms like binary search.
• Used to understand growth
patterns in algorithms.
• Common in sorting and searching
problems.
• Example: Binary search runs in
O(log n) time.
 Running Time
Calculations

• Calculating how long an

algorithm takes based on
operations performed.
• Helps optimize performance for
large datasets.
• Involves counting basic
operations like comparisons and
swaps.
• Example: Sorting an array using
different algorithms.
 Worst-
Different scenarios for analyzing
case, algorithm performance.

Best- Worst-case: Slowest execution time (e.g.,

searching for a non-existent element).
case, and Best-case: Fastest execution time (e.g.,
Average- finding the first element).

Average-case: Expected performance for

case random inputs.

Analysis
 Unsorted List
(Array) –
Introduction

• Definition and characteristics

• Use cases and limitations
 A collection of elements stored
sequentially in memory without a
specific order.

Unsorted Elements are stored as they are added.

List (Array) –
Introduction Searching takes O(n) time (linear
search).

Insertion is fast (O(1)), but deletion

may require shifting (O(n)).
 Where and when to use unsorted arrays.

Use Cases:

Temporary storage (e.g., buffering data before sorting).

Simple data collection where ordering is not required.

Use Cases
Fast insertion scenarios such as appending logs.
and
Limitations:
Limitations
Searching is slow compared to sorted structures.

Deletion requires shifting elements, making it inefficient.

Fixed size in static arrays unless dynamic arrays are used.

 Adding and deleting
elements
Unsorted List
(Array) –
Implementation

Accessing and modifying

data
Unsorted List
(Array) –
Implementation
How to add, delete, access, and modify
elements in an unsorted array.
 Adding and Deleting
Elements
• Adding (Insertion):
• New elements are added at the next available index.
• Time Complexity: O(1) (fast insertion).
• Deleting an Element:
• Find the element and shift remaining elements.
• Time Complexity: O(n) (slow, since shifting is needed).
 •
#include <iostream>
using namespace std;

int main() {
C++ Example: int arr[5] = {10, 20, 30, 40, 50};
int n = 5;
Deleting an // Delete element at index 2 (30)
Element for(int i = 2; i < n-1; i++) {
arr[i] = arr[i+1];
}
n--;

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

cout << arr[i] << " ";
}
}
 Accessing an element:
Done using the index
(arr[i]).
Accessing
and Modifying an element:
Assign a new value
Modifying (arr[i] = newValue).
Data
Time Complexity: O(1)
(direct access via index).
 C++ Example: Access
& Modify Data
•
#include <iostream>
using namespace std;

int main() {
int arr[5] = {10, 20, 30, 40, 50};

cout << "Element at index 2: " << arr[2] << endl;

// Modify value
arr[2] = 99;
cout << "Modified element at index 2: " << arr[2] << endl;
}
 Unsorted List (Array)
– Implementation
(Cont’d)

• Optimizing performance
• Code examples and exercises
Unsorted List (Array)
– Implementation
(Cont’d)
Further improvements for performance
optimization.
 • Efficient Insertion:
• Insert at the end of the array (O(1)
time complexity).
• Fast Deletion (Lazy Deletion):
Optimizing • Instead of shifting elements, mark
deleted items to improve efficiency.
Performance • Resizing the Array (Dynamic
Arrays):
• Use dynamic arrays (e.g., vector in
C++) to automatically resize when
needed.
 C++ Example: Using
Dynamic Array (Vector)
•
#include <iostream>
#include <vector>
using namespace std;

int main() {
vector<int> arr = {10, 20, 30, 40, 50};
arr.push_back(60); // Efficient insertion at end (O(1))

cout << "Last element: " << arr.back() << endl;

return 0;
}
 Exercise 1: Implement an unsorted list using an array with
functions for:
Implement - Insert an element
- Delete an element
- Search for an element

Code
Examples
and Modify Exercise 2: Modify your deletion function to use lazy deletion
instead of shifting.

Exercises

Exercise 3: Convert the array-based implementation into a

Convert dynamic array (vector).
Sorted List (Array) – Introduction

Comparison
Why use
with
sorted lists?
unsorted lists
Sorted List (Array) – Introduction
• A sorted list stores elements in a specific
order (ascending/descending).
• Improves search efficiency.
• Allows binary search (O(log n) time
complexity).
• Useful in databases and search engines.
 Why Use Sorted
Lists?
• Faster Searching – Binary search works in O(log n)
compared to O(n) in unsorted lists.
• Better Organization – Data is structured and easier
to retrieve.
• Easier Merging – Combining multiple sorted lists is
more efficient.
Feature Sorted List (Array) Unsorted List
(Array) Comparison:
Insertion Slow (O(n)) -
maintains order
Fast (O(1)) - added
at the end
Sorted vs.
Search Fast (O(log n) with Slow (O(n), Linear
Unsorted
Binary Search) Search)
Lists
Deletion Requires shifting Requires shifting
(O(n)) (O(n))

Use Case Good for search- Good for frequent

heavy applications insertions
 When to Use Sorted
Lists?
• When fast searching is required.
• When elements need to be accessed in order.
• Used in databases, search engines, and ranking
systems.
 Sorted List (Array) –
Implementation
• Methods for inserting and maintaining order
• Complexity analysis
 Sorted List
(Array) –
Implementation
How to insert elements while
maintaining order in a sorted list.
Methods for Inserting
and Maintaining Order
Method 1: Find the Correct Position and Insert
• Traverse the list and shift elements to the right.
• Time Complexity: O(n) (worst case, shifting all elements).
Method 2: Using Binary Search for Faster Insertion
• Find the correct position in O(log n).
• But shifting elements still takes O(n), so overall
complexity remains O(n).
 C++ •
#include <iostream>
using namespace std;

Example: void insertSorted(int arr[], int &n, int value) {

int i;
for (i = n - 1; (i >= 0 && arr[i] > value); i--) {
arr[i + 1] = arr[i]; // Shift elements

Insert in }
}
arr[i + 1] = value; // Insert element
n++;

Sorted int main() {

int arr[10] = {10, 20, 30, 50};
int n = 4;

List }
insertSorted(arr, n, 40);
for (int i = 0; i < n; i++) cout << arr[i] << " ";
Operation Time Complexity
Insertion O(n) (due to shifting)
Complexity
Analysis
Search O(log n) (Binary Search)

Deletion O(n) (due to shifting)

 • Searching is fast (O(log
Key n)), but insertion/deletion
is slow (O(n)).
Takeaways • Best for read-heavy
applications like databases
and search engines.
 Sorted List (Array) –
Binary Search
• Binary search concept
• Implementation and efficiency
• Comparison with linear search
Sorted List (Array) – Binary
Search

Binary search is an efficient method

to find an element in a sorted list.
 • Works by repeatedly dividing the
search range in half.

Binary • Steps:
1. Find the middle element.
2. If it matches the target, return the
index.
Search 3. If the target is smaller, search the
left half.
4. If the target is larger, search the

Concept right half.

5. Repeat until found or the range is
empty.
• Time Complexity: O(log n) (much
faster than linear search O(n)).
 •
#include <iostream>
using namespace std;

int binarySearch(int arr[], int left, int right, int target) {

while (left <= right) {
int mid = left + (right - left) / 2;

C++ if (arr[mid] == target) return mid;

if (arr[mid] < target) left = mid + 1;
else right = mid - 1;

Implementation }
}
return -1;

of Binary Search int main() {

int arr[] = {10, 20, 30, 40, 50};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 30;

int result = binarySearch(arr, 0, size - 1, target);

(result != -1) ? cout << "Element found at index " << result
: cout << "Element not found";
}
Comparison: Binary Search
vs. Linear Search

Feature Binary Search Linear Search

Sorting Required? Yes (must be No (works on

sorted) any list)

Time Complexity O(log n) (Efficient) O(n) (Slow for large

lists)

Best Use Case Large sorted lists Small or unsorted

lists
 When to Use Binary
Search?
• When fast searching is needed in a sorted list.
• Used in applications like databases, dictionaries,
and search engines.
 Unsorted
• Definition and advantages
Linked List – over arrays
Introduction • Real-world use cases
Unsorted Linked List –
Introduction

A dynamic data structure consisting

of nodes linked together.
 Definition and
Advantages Over Arrays

• Dynamic Size: No fixed size; can grow or shrink as needed.

• Efficient Insertions & Deletions: No shifting required (O(1) for
insertion at the beginning).
• Flexible Memory Allocation: Uses memory only as needed,
reducing wastage.
• Slower Searching (O(n)) compared to arrays (O(1) for direct
access).
• Extra Memory Overhead (pointers require additional storage).
 C++
Representation
•
of a Linked List struct Node {
int data;
Node Node* next;
};
 • Used in dynamic applications
with frequent insertions/removals
(e.g., Undo functionality).
•
Real-World Use Memory-sensitive applications
where arrays might be inefficient.

Cases • Data structures like stacks,

queues, and graphs rely on linked
lists.
• Operating Systems use linked
lists for memory management and
task scheduling.
Unsorted Linked
List – • Node structure
•
Implementation •
Adding and deleting nodes
Traversal methods
Unsorted Linked
List – • Implementation of a linked list,
including node structure, insertion,
Implementation deletion, and traversal.
 • A linked list consists of nodes,
where each node contains:
•
Node Structure •
Data (stores the value)
Pointer (next) that points to
the next node
C++ Example:
Node
Structure

•
struct Node {
int data;
Node* next;
};
 Adding a Node
(At the
Beginning)

• Create a new node.

• Set its next pointer
to the current head.
• Update the head
to the new node.
 C++ Example:
Insert at
Beginning

•
void insertAtBeginning(Node*&
head, int value) {
Node* newNode = new
Node();
newNode->data = value;
newNode->next = head;
head = newNode;
}
 Deleting a Node

• Find the node to delete.

• Update the previous node's
next pointer.
• Free memory.
 C++ Example: Delete a Node
•
void deleteNode(Node*& head, int key) {
Node* temp = head, *prev = nullptr;
if (temp != nullptr && temp->data == key) {
head = temp->next;
delete temp;
return;
}
while (temp != nullptr && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == nullptr) return;
prev->next = temp->next;
delete temp;
}
 Traversal
Methods

• Iterative Traversal: Uses a

loop to visit each node.
• Recursive Traversal: Uses
recursion to visit each node.
• Time Complexity: O(n) (must
visit each node).
 C++ Example:
Traversal
Methods

•
void printList(Node* head) {
while (head != nullptr) {
cout << head->data << " ";
head = head->next;
}
}

void printListRecursive(Node* head) {

if (head == nullptr) return;
cout << head->data << " ";
printListRecursive(head->next);
}
Sorted Linked List
– Introduction

• Why use sorted linked lists?

• Implementation strategies
 Sorted Linked List –
Introduction

• A linked list where elements are

inserted in sorted order.
 Why Use Sorted Linked Lists?

• Faster Searches – Searching takes O(n), but elements remain sorted.

• Automatic Ordering – No need to sort later, elements are inserted in
order.
• Efficient for Priority-Based Applications – Used in priority queues &
scheduling.
• Slower Insertions (O(n)) – Finding the correct insertion point takes time.
• More Overhead – Additional logic needed to maintain order.
 Implementation
Strategies
• Method 1: Insert at the Correct Position
• Method 2: Maintain Sorted Order During
Deletion
• Time Complexity:
- Insertion: O(n) (must find the correct position)
- Search: O(n)
- Deletion: O(n)
 C++ •
void insertSorted(Node*& head, int value) {
Node* newNode = new Node();
newNode->data = value;

Example: if (!head || head->data >= value) {

newNode->next = head;
head = newNode;

Insert in }
return;

Node* current = head;

Sorted while (current->next && current->next->data < value) {

}
current = current->next;

Order }
newNode->next = current->next;
current->next = newNode;
 When data
must stay sorted
automatically.
When to
Use a
Priority-based
Sorted applications like
task scheduling.
Linked
List?
Databases
where maintaining
order is crucial.
 Revision for
Midterm Exam

• Summary of key concepts

• Practice questions
Midterm Exam

• Exam instructions
• Time management tips
The Stack ADT

• Definition and
characteristics
• Representation methods
• Operations on stacks
(push, pop, peek)
 The Stack ADT

• A data structure that follows the

Last In, First Out (LIFO) principle.
Definition and
Characteristics
• LIFO Structure – Last element
added is the first to be removed.
• Restricted Access – Can only
add/remove elements from the
top.
• Used in Recursive Function
Calls, Undo Operations, and
Expression Evaluation.
 Representation
Methods

• Array-Based Stack –
Fixed size, fast operations.
• Linked List-Based
Stack – Allows dynamic
memory allocation, no
size limitation.
 Time
Operation Description Complexity
Push Adds an element
to the top of the
O(1) Operations
Pop
stack

Removes the top O(1)

on Stacks
element

Peek Returns the top O(1)

element without
removing it
 •
#include <iostream>
using namespace std;

#define MAX 5

class Stack {
int top;
int arr[MAX];

public:
Stack() { top = -1; }

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

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

C++ Example: void push(int value) {

if (isFull()) { cout << "Stack Overflow
"; return; }

Stack
arr[++top] = value;
}

void pop() {
if (isEmpty()) { cout << "Stack Underflow

Implementation "; return; }

}
top--;

int peek() {
if (!isEmpty()) return arr[top];
return -1;
}
};

int main() {
Stack s;
s.push(10);
s.push(20);
cout << "Top element: " << s.peek() << endl;
s.pop();
cout << "Top element after pop: " << s.peek() << endl;
}
 Undo/Redo in
text editors.

Applications Function call

management
of Stacks (recursion).

Expression
evaluation (postfix,
infix, prefix
conversion).
 Array
Implementation
of Stacks

• Static vs. dynamic arrays

• Memory allocation strategies
 Array
Implementation
of Stacks

• Using arrays to implement a

stack (either static or
dynamic).
 Static vs.
Dynamic Arrays

• Static Array Stack: Fixed

size, defined at compile time.
• Fast operations (O(1) for
push, pop, peek).
• Memory limitation: No
more elements can be added
when full.
• Dynamic Array Stack: Can
grow or shrink as needed.
• Uses dynamic memory
allocation (heap memory).
• Slightly slower due to
memory allocation overhead.
 •
#include <iostream>

C++
using namespace std;

#define MAX 5

class Stack {
int top;
int arr[MAX];

public:

Example:
Stack() { top = -1; }

void push(int value) {

if (top == MAX - 1) { cout << "Stack Overflow
"; return; }
arr[++top] = value;
}

void pop() {

Static
if (top == -1) { cout << "Stack Underflow
"; return; }
top--;
}

int peek() { return (top != -1) ? arr[top] : -1; }

};

int main() {

Stack
Stack s;
s.push(10);
s.push(20);
cout << "Top element: " << s.peek() << endl;
s.pop();
cout << "Top after pop: " << s.peek() << endl;
}
 • Static Allocation: Memory is
allocated at compile time (fixed-
size array).
Memory • Dynamic Allocation:
Memory is allocated at runtime
Allocation using `new` or `malloc()`.
Strategies • Static arrays are faster but
limited in size.
• Dynamic arrays provide
flexibility but require memory
management.
 •
#include <iostream>
using namespace std;

C++
class Stack {
int* arr;
int top, capacity;

public:
Stack(int size) {
capacity = size;
arr = new int[capacity];
top = -1;

Example:
}

~Stack() { delete[] arr; }

void push(int value) {

if (top == capacity - 1) { cout << "Stack Overflow
"; return; }
arr[++top] = value;
}

Dynamic void pop() {

if (top == -1) { cout << "Stack Underflow
"; return; }

}
top--;

int peek() { return (top != -1) ? arr[top] : -1; }

};

Stack int main() {

Stack s(5);
s.push(10);
s.push(20);
cout << "Top element: " << s.peek() << endl;
s.pop();
cout << "Top after pop: " << s.peek() << endl;
}
 • Static arrays are simple
and fast but limited in size.
• Dynamic arrays provide
Key flexibility but require extra
memory management.
Takeaways • Choose based on
application needs (e.g.,
embedded systems →
static, flexible applications
→ dynamic).
 Implementing Stacks Using
Dynamic Array Allocation

• Advantages of dynamic memory

• Code example
Implementing
Stacks Using Using dynamic

Dynamic memory for

flexible stack
implementation.
Array
Allocation
 • Flexibility – Can grow or
shrink as needed.
• Efficient Memory Usage –
Advantages Uses only necessary memory.
of Dynamic • No Fixed Size – Adjusts
dynamically instead of a fixed
Memory size at compile-time.
• Better for Large Data –
Works well when the number
of elements is unknown in
advance.
 •
#include <iostream>
using namespace std;

class Stack {
int* arr;
int top, capacity;

public:
Stack(int size) {
capacity = size;
arr = new int[capacity]; // Allocate memory dynamically
top = -1;
}

C++ Example: ~Stack() { delete[] arr; } // Free memory when object is destroyed

void push(int value) {

Dynamic Stack
if (top == capacity - 1) { cout << "Stack Overflow
"; return; }
arr[++top] = value;
}

Implementation void pop() {

if (top == -1) { cout << "Stack Underflow
"; return; }

}
top--;

int peek() { return (top != -1) ? arr[top] : -1; }

};

int main() {
Stack s(5);
s.push(10);
s.push(20);
cout << "Top element: " << s.peek() << endl;
s.pop();
cout << "Top after pop: " << s.peek() << endl;
}
 • Dynamic stacks provide
flexibility and efficient
memory management.
Key • Memory is allocated at
runtime, preventing
Takeaways wastage.
• Ideal for applications
where the maximum stack
size is unknown.
 Linked List • Benefits over array-based
Implementation stacks
of Stacks • Memory efficiency
considerations
Linked List
Implementation
of Stacks
Using linked lists to
implement dynamic stacks.
Benefits • Dynamic Size – No fixed size,
grows/shrinks dynamically.

Over •

•
Efficient Memory Usage –
Memory allocated only when needed.
No Overflow (Unless Memory is

Array- •
Full) – Unlike array stacks, no size
limit.
No Need for Resizing – Avoids
costly array resizing.
Based • Extra Memory Overhead –
Requires extra storage for pointers.
• Slower Access – Linked list
Stacks traversal is slower than array indexing.
 Memory Efficiency
Considerations
• Linked list stacks consume more memory due to
pointer storage.
• When to use linked list stacks?
• - When frequent insertions/deletions are needed.
• - When memory availability varies (allocates only what
is needed).
• - When the stack size is unpredictable.
 •
#include <iostream>
using namespace std;

struct Node {
int data;
Node* next;
};

class Stack {
private:
Node* top;

public:
Stack() { top = nullptr; }

void push(int value) {

Node* newNode = new Node();
newNode->data = value;

C++ }
newNode->next = top;
top = newNode;

Implementation:
void pop() {
if (top == nullptr) {
cout << "Stack Underflow
";
return;

Linked List Stack }

}
Node* temp = top;
top = top->next;
delete temp;

int peek() {
if (top != nullptr) return top->data;
return -1;
}

bool isEmpty() { return top == nullptr; }

};

int main() {
Stack s;
s.push(10);
s.push(20);
cout << "Top element: " << s.peek() << endl;
s.pop();
cout << "Top after pop: " << s.peek() << endl;
}
 • Linked lists are useful for
dynamic stacks where size
changes frequently.
Key • Extra memory overhead
exists due to storing pointers.
Takeaways • Use linked list stacks when
insertions and deletions are
more frequent than direct
access needs.
 • Parsing expressions
Applications
• Evaluating arithmetic
of Stacks expressions
• Other real-world uses
Applications
of Stacks
Common uses of stacks in programming
and real-world applications.
 • Stacks help in parsing
expressions in
programming languages
and compilers.
Parsing
• Used for syntax
Expressions checking (e.g., ensuring
balanced parentheses).
• Helps convert
expressions between infix,
postfix, and prefix notation.
 •

C++
#include <iostream>
#include <stack>
using namespace std;

Example: bool isBalanced(string expr) {

stack<char> s;
for (char ch : expr) {
if (ch == '(' || ch == '{' || ch == '[') s.push(ch);

Checking else if (ch == ')' && !s.empty() && s.top() == '(') s.pop();
else if (ch == '}' && !s.empty() && s.top() == '{') s.pop();
else if (ch == ']' && !s.empty() && s.top() == '[') s.pop();
else return false;

Balanced }
}
return s.empty();

Parentheses int main() {

}
string expr = "{[()]}";
cout << (isBalanced(expr) ? "Balanced" : "Not Balanced") << endl;
 Stacks are used in
evaluating mathematical
expressions.

Evaluating Postfix expressions

(Reverse Polish Notation -
Arithmetic RPN) can be evaluated using a
Expressions stack.

Used in calculators and

compilers.
 •
#include <iostream>
#include <stack>

C++ using namespace std;

int evaluatePostfix(string exp) {

stack<int> s;

Example:
for (char ch : exp) {
if (isdigit(ch)) s.push(ch - '0');
else {
int val2 = s.top(); s.pop();
int val1 = s.top(); s.pop();

Postfix switch (ch) {

case '+': s.push(val1 + val2); break;
case '-': s.push(val1 - val2); break;
case '*': s.push(val1 * val2); break;

Expression
case '/': s.push(val1 / val2); break;
}
}
}
return s.top();

Evaluation }

int main() {
string postfix = "23*5+";
cout << "Result: " << evaluatePostfix(postfix) << endl;
}
Other • Undo/Redo in text
editors.
Real- • Function call
management (Recursion).

World • Web browser

back/forward navigation.
• Memory management
Uses in Operating Systems.
 • Stacks are essential in
programming for expression
evaluation and syntax
checking.
Key • Used in everyday
applications like web
Takeaways browsing, text editors, and OS
memory management.
• A fundamental data
structure in recursion and
function call execution.
 The
• Definition and
Queue characteristics
• Types of queues (FIFO,

ADT circular, priority)

The
Queue
ADT
A data structure
that follows the
First In, First Out
(FIFO) principle.
 • FIFO Structure – The
first element inserted is the
first to be removed.
Definition and • Insertion (Enqueue)
happens at the rear, and
Characteristics removal (Dequeue)
happens from the front.
• Used in scheduling,
buffering, and task
management.
 • FIFO Queue (Standard
Queue) – Follows First In, First

Types of •
Out.
Circular Queue – The rear
connects to the front, making
Queues efficient use of memory.
• Priority Queue – Elements
are removed based on
priority, not order.
 C++ Implementation: Queue
•
#include <iostream>
using namespace std;

#define SIZE 5

class Queue {
int arr[SIZE], front, rear;

public:
Queue() { front = -1; rear = -1; }

bool isFull() { return (rear == SIZE - 1); }

bool isEmpty() { return (front == -1 || front > rear); }

void enqueue(int value) {

if (isFull()) { cout << "Queue Overflow
"; return; }
if (front == -1) front = 0;
arr[++rear] = value;
}

void dequeue() {
if (isEmpty()) { cout << "Queue Underflow
"; return; }
front++;
}

int peek() {
if (!isEmpty()) return arr[front];
return -1;
}
};

int main() {
Queue q;
q.enqueue(10);
q.enqueue(20);
cout << "Front element: " << q.peek() << endl;
q.dequeue();
cout << "Front after dequeue: " << q.peek() << endl;
}
 • Queues follow the FIFO
principle, making them useful
for scheduling and buffering.
Key • Different types of queues
exist for different applications
Takeaways (FIFO, circular, priority).
• Used in CPU scheduling,
network buffering, and real-
world task management.
 Array
• Enqueue and dequeue
Implementation
operations
of Queues
• Efficiency comparison
 Array
Implementation
of Queues
• Using arrays to implement
a queue with enqueue
and dequeue operations.
 Enqueue (Insertion at Rear): Adds a new element at
the rear of the queue.

Steps for Enqueue:

1. Check if the queue is full (Overflow condition).
2. If empty, set front = 0.
Enqueue and 3. Increment rear and insert the element.
Dequeue
Operations Dequeue (Removal from Front): Removes an
element from the front of the queue.

Steps for Dequeue:

1. Check if the queue is empty (Underflow condition).
2. Remove the element at the front.
3. Increment front.
 •
#include <iostream>

C++
using namespace std;

#define SIZE 5

class Queue {
int arr[SIZE], front, rear;

public:

Example:
Queue() { front = -1; rear = -1; }

bool isFull() { return (rear == SIZE - 1); }

bool isEmpty() { return (front == -1 || front > rear); }

void enqueue(int value) {

if (isFull()) { cout << "Queue Overflow
"; return; }

Queue
if (front == -1) front = 0;
arr[++rear] = value;
}

void dequeue() {
if (isEmpty()) { cout << "Queue Underflow
"; return; }
front++;

Using
}

int peek() {
if (!isEmpty()) return arr[front];
return -1;
}
};

Arrays
int main() {
Queue q;
q.enqueue(10);
q.enqueue(20);
cout << "Front element: " << q.peek() << endl;
q.dequeue();
cout << "Front after dequeue: " << q.peek() << endl;
}
Efficiency Comparison

Operation Array-Based Linked List-Based

Queue Queue
Enqueue O(1) O(1)
Dequeue O(1) (Circular) / O(1)
O(n) (Shifting)
Memory Fixed Size Dynamic (More
(Wasted Space Overhead)
Possible)
 Key Takeaways

ARRAY-BASED QUEUES ARE LINKED LIST QUEUES ARE CIRCULAR QUEUES

SIMPLE BUT FIXED IN SIZE. DYNAMIC BUT REQUIRE EXTRA PREVENT WASTED SPACE IN
MEMORY FOR POINTERS. ARRAYS.
 Linked List
Implementation
of Queues

• Memory management
benefits
• Handling dynamic
queues
 Linked List
Implementation
of Queues
• Using linked lists to
implement dynamic
queues with efficient
memory management.
 Memory Management Benefits

EFFICIENT MEMORY USAGE – NO MEMORY WASTAGE – NO OVERFLOW (UNLESS MEMORY

GROWS DYNAMICALLY AS NEEDED. ALLOCATES MEMORY ONLY WHEN IS FULL) – UNLIKE ARRAY QUEUES, IT
NEEDED. EXPANDS DYNAMICALLY.
Handling Dynamic Queues

• Linked list queues dynamically allocate and deallocate

nodes.
• Ideal when queue size is unpredictable.
• Best for applications with frequent insertions and
deletions.
• Operations:
• - Enqueue (Insertion at Rear): Adds a new node at the rear.
• - Dequeue (Removal from Front): Removes the node at the
front.
 •
#include <iostream>
using namespace std;

C++
struct Node {
int data;
Node* next;
};

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

Example: public:
Queue() { front = rear = nullptr; }

void enqueue(int value) {

Node* newNode = new Node();
newNode->data = value;
newNode->next = nullptr;

Queue
if (!rear) {
front = rear = newNode;
return;
}
rear->next = newNode;
rear = newNode;
}

Using
void dequeue() {
if (!front) {
cout << "Queue Underflow
";
return;
}
Node* temp = front;
front = front->next;

Linked
if (!front) rear = nullptr;
delete temp;
}

int peek() {
if (front) return front->data;
return -1;
}

List
};

int main() {
Queue q;
q.enqueue(10);
q.enqueue(20);
cout << "Front element: " << q.peek() << endl;
q.dequeue();
cout << "Front after dequeue: " << q.peek() << endl;
}
 • Linked list queues are
flexible and handle
dynamic memory
Key •
efficiently.
No fixed size, no
Takeaways wasted space, unlike
arrays.
• Best for applications
with frequent insertions
and deletions.
Applications • Process scheduling
of Queues • Networking (packet
processing)
 Applications of
Queues

• Common uses of queues in

operating systems and
networking.
 Process Scheduling (Operating
Systems)

• Queues are used in CPU scheduling to

manage tasks efficiently.
• Processes waiting for CPU time are stored
in a queue (Ready Queue).
• Round Robin Scheduling uses a queue
where processes wait their turn (FIFO).
• Priority Scheduling uses a priority queue
where higher-priority tasks execute first.
 •
#include <iostream>
#include <queue>
using namespace std;

C++ Example: int main() {

queue<string> processQueue;
Process processQueue.push("Process 1");
processQueue.push("Process 2");
Scheduling processQueue.push("Process 3");

while (!processQueue.empty()) {
cout << "Executing: " <<
processQueue.front() << endl;
processQueue.pop();
}
}
 Networking (Packet Processing)

Queues manage network Packets are processed in Routers and switches use
packet transmission and order (FIFO) before being queues to handle network
processing. sent to their destination. traffic efficiently.
 •
#include <iostream>
#include <queue>

C++ using namespace std;

int main() {

Example:
queue<int> packetQueue;

// Simulating packet arrivals

packetQueue.push(101);

Packet packetQueue.push(102);
packetQueue.push(103);

while (!packetQueue.empty()) {

Processing cout << "Processing packet: " << packetQueue.front()

<< endl;
packetQueue.pop();
}
}
 Queues ensure fair CPU
allocation in process
scheduling (Round Robin,
Priority Scheduling).
Used in network routing for
Key packet management (FIFO
processing).
Takeaways
Queues help in data
buffering, task scheduling,
and resource management.
Recursion • Definition and rules
• Tail recursion vs. standard
Concepts recursion
Recursion • Understanding recursion, its rules, and
the difference between tail recursion and
Concepts standard recursion.
 • Recursion is a technique where a
function calls itself to solve smaller
Definition subproblems.
• Used in mathematics, algorithms, and
and Rules data structures.
• Rules of Recursion:
of - Base Case: A condition where recursion
stops.

Recursion - Recursive Case: The function calls itself

with a smaller subproblem.
- Progress Toward Base Case: Each call must
get closer to termination.
 Standard
• The recursive call is NOT the last
Recursion •
operation in the function.
Function must retain previous states until
(Non-Tail •
all recursive calls complete.
Uses more memory (stack space) since
Recursion) each function call is stored.
 •

C++ #include <iostream>

using namespace std;

Example: int factorial(int n) {

if (n == 0) return 1; // Base case

Standard return n * factorial(n - 1); // Recursive

call
}
Recursion int main() {

(Factorial) cout << "Factorial of 5: " << factorial(5)

<< endl;
}
 The recursive call is the LAST
operation in the function.

Tail No need to store previous

states (stack frames are
Recursion reused).

More memory efficient and can

be optimized by the compiler
(Tail Call Optimization - TCO).
 C++ •
#include <iostream>
using namespace std;
Example: int tailFactorial(int n, int result = 1) {
Tail if (n == 0) return result; // Base case
return tailFactorial(n - 1, n * result);

Recursion // Tail-recursive call

}

(Optimized int main() {

cout << "Factorial of 5: " <<
Factorial) tailFactorial(5) << endl;
}
 Key Takeaways

Recursion is useful for solving Tail recursion is more memory- Used in algorithms like tree
problems that can be divided efficient than standard traversal, divide & conquer,
into smaller instances. recursion. and backtracking.
Designing
• Common recursive
Recursive patterns
Solutions • Recursion vs. iteration
Designing • Understanding recursive
Recursive patterns and when to use
recursion vs. iteration.
Solutions
 Direct Recursion – Function calls itself
directly (e.g., Factorial).

Indirect Recursion – Two or more

functions call each other.

Common Tail Recursion – Recursive call is the last

Recursive operation in the function (e.g.,
Optimized Factorial).
Patterns
Tree Recursion – Function makes
multiple recursive calls (e.g., Fibonacci,
tree traversal).

Backtracking – Used for problems with

multiple choices (e.g., Maze solving, N-
Queens).
 Aspect Recursion Iteration
Concept Function calls itself Uses loops (for,
while)

Memory Usage Uses stack memory Uses constant

Recursion (each call stored in memory
call stack)
vs. Performance Can be slower due to Generally faster
Iteration stack overhead for large loops

Readability Simpler, more elegant Better for

for problems like repetitive tasks
trees like looping over
an array
 •
When to Use Recursion:
- When the problem naturally breaks into smaller
Use subproblems.
- When dealing with trees, graphs, and
Recursion backtracking.
- When an iterative approach is more complex.
vs. Iteration • Use Iteration:
- When performance and memory usage are
concerns.
- When solving simple looping problems.
- When recursion depth is too large (stack overflow
risk).
 C++ •
#include <iostream>
using namespace std;
Example: int fibonacci(int n) {
Recursive if (n <= 1) return n;
return fibonacci(n - 1) +

vs. fibonacci(n - 2);

}

Iterative int main() {

cout << "Fibonacci(5): " <<

Fibonacci fibonacci(5) << endl;

}
 •
#include <iostream>
C++ using namespace std;

int fibonacciIterative(int n) {
Example: int a = 0, b = 1, next;
for (int i = 2; i <= n; i++) {
next = a + b;

Iterative }
a = b;
b = next;

Fibonacci }
return b;

(Efficient) int main() {

cout << "Fibonacci(5): " <<
fibonacciIterative(5) << endl;
}
 Key Takeaways

Use recursion when the problem naturally fits a

recursive approach (e.g., trees, divide and conquer).

Use iteration for performance-efficient solutions

when recursion adds unnecessary overhead.

Understanding recursive patterns helps in

designing efficient algorithms.
 Binary
Trees &
Binary • Tree structure and
properties
Search • Binary search tree
definition
Trees
(BSTs)
 Binary Trees &
Binary Search
Trees (BSTs)

• Understanding tree structures,

properties, and the definition of
BSTs.
 • A Binary Tree is a hierarchical
structure where each node has at
most two children.
Tree • Key Properties:
• - Root Node – The topmost node in
Structure •
the tree.
- Parent & Child Nodes – A node is
and •
connected to its children.
- Leaf Node – A node without
children.
Properties • - Depth – Number of edges from
root to a node.
• - Height – Depth of the deepest
node.
 Types • Full Binary Tree – Every
node has 0 or 2 children.
• Complete Binary Tree – All

of •
levels are filled except possibly
the last.
Perfect Binary Tree –

Binary Internal nodes have exactly 2

children, and all leaf nodes are
at the same level.
• Balanced Binary Tree –
Trees Difference in heights of left and
right subtrees is at most 1.
 Binary Search Tree
(BST) Definition
• A BST is a binary tree where:
• - Left child contains nodes with smaller values.
• - Right child contains nodes with larger values.
• - No duplicate values are allowed.
• Efficient for searching, inserting, and deleting elements.
• Average case time complexity: O(log n) for most operations.
• Used in databases, indexing, and searching applications.
 •
#include <iostream>
using namespace std;

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

Node* createNode(int value) {

Node* newNode = new Node();
newNode->data = value;
newNode->left = newNode->right = nullptr;
return newNode;

C++ Example: }

Node* insert(Node* root, int value) {

if (root == nullptr) return createNode(value);
if (value < root->data) root->left = insert(root->left, value);

Implementing
else root->right = insert(root->right, value);
return root;
}

void inorderTraversal(Node* root) {

a BST
if (root == nullptr) return;
inorderTraversal(root->left);
cout << root->data << " ";
inorderTraversal(root->right);
}

int main() {
Node* root = nullptr;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);

cout << "Inorder Traversal: ";

inorderTraversal(root);
}
 Key Takeaways

Binary trees organize data BSTs efficiently store and retrieve Used in search algorithms,
hierarchically with at most two ordered data using the left- databases, and file systems.
children per node. smaller, right-larger rule.
 Basic
• Insert, delete, search
Operations operations
on BSTs • Efficiency of BSTs
 Basic Operations on
BSTs
• Understanding insert, delete,
search operations, and
efficiency of BSTs.
 Insert, Delete, and
Search Operations
• Insert Operation:
• - If value < root, insert in left subtree.
• - If value > root, insert in right subtree.
• Search Operation:
• - If value matches node, return node.
• - If value is smaller, search left subtree.
• - If value is larger, search right subtree.
• Delete Operation Cases:
• - Leaf Node: Remove directly.
• - One Child: Replace node with child.
• - Two Children: Replace with inorder successor.
 Best Case
(Balanced Worst Case Efficiency
Operation BST) (Skewed BST)
Insertion O(log n) O(n) of BSTs
Search O(log n) O(n)

Deletion O(log n) O(n)

 •
#include <iostream>
using namespace std;

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

Node* createNode(int value) {

C++
return new Node{value, nullptr, nullptr};
}

Node* insert(Node* root, int value) {

if (!root) return createNode(value);
if (value < root->data) root->left = insert(root->left, value);
else root->right = insert(root->right, value);
return root;

Example:
}

Node* search(Node* root, int value) {

if (!root || root->data == value) return root;
return (value < root->data) ? search(root->left, value) : search(root->right, value);
}

Node* findMin(Node* root) {

Insert,
while (root->left) root = root->left;
return root;
}

Node* deleteNode(Node* root, int value) {

if (!root) return root;
if (value < root->data) root->left = deleteNode(root->left, value);
else if (value > root->data) root->right = deleteNode(root->right, value);

Search,
else {
if (!root->left) return root->right;
if (!root->right) return root->left;
Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;

Delete in
}

void inorderTraversal(Node* root) {

if (!root) return;
inorderTraversal(root->left);
cout << root->data << " ";
inorderTraversal(root->right);
}

BST int main() {

Node* root = nullptr;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);

cout << "Inorder Traversal: ";

inorderTraversal(root);

cout << "\nDeleting 50...\n";

root = deleteNode(root, 50);
inorderTraversal(root);
}
 • BST operations follow
the left-smaller, right-larger
rule.
• Balanced BSTs are
Key efficient with O(log n)
operations.
Takeaways • Skewed BSTs degrade to
O(n), reducing efficiency.
• Deletion requires
special handling (leaf, one
child, or two children
cases).
 BST Traversals
• In-order, pre-order, and post-order
• Use cases of each traversal type
 • Understanding In-Order,
BST Pre-Order, and Post-Order
Traversals and their use
Traversals cases.
In-Order Traversal (Left
→ Root → Right)
• Visits the left subtree, then the root, then the right
subtree.
• Retrieves elements in sorted order (ascending).
• Example output: 20 → 30 → 40 → 50 → 60 → 70 →
80
• Used in BSTs to extract elements in sorted order.
 Pre-Order Traversal
(Root → Left → Right)

• Visits the root first, then the left subtree, then

the right subtree.
• Used for tree copying and prefix expressions.
• Example output: 50 → 30 → 20 → 40 → 70 →
60 → 80
 Post-Order Traversal
(Left → Right → Root)

• Visits the left subtree, then the right subtree,

then the root.
• Used for memory deallocation and postfix
expressions.
• Example output: 20 → 40 → 30 → 60 → 80 →
70 → 50
 •
#include <iostream>
using namespace std;

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

Node* createNode(int value) {

return new Node{value, nullptr, nullptr};
}

C++
Node* insert(Node* root, int value) {
if (!root) return createNode(value);
if (value < root->data) root->left = insert(root->left, value);
else root->right = insert(root->right, value);
return root;
}

void inOrder(Node* root) {

Example:
if (!root) return;
inOrder(root->left);
cout << root->data << " ";
inOrder(root->right);
}

void preOrder(Node* root) {

if (!root) return;
cout << root->data << " ";

BST
preOrder(root->left);
preOrder(root->right);
}

void postOrder(Node* root) {

if (!root) return;
postOrder(root->left);
postOrder(root->right);
cout << root->data << " ";

Traversals
}

int main() {
Node* root = nullptr;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);

cout << "In-Order Traversal: ";

inOrder(root);
cout << "\nPre-Order Traversal: ";
preOrder(root);
cout << "\nPost-Order Traversal: ";
postOrder(root);
}
 • In-order traversal retrieves
elements in sorted order
(used in BSTs).
Key • Pre-order traversal is
useful for tree copying and
Takeaways prefix notation.
• Post-order traversal helps
with memory deallocation
and postfix expressions.
Comparing
BSTs to •
•
Advantages and disadvantages
When to use BSTs vs. arrays or linked lists
Linear Lists
Comparing
• Advantages, disadvantages, and when to
BSTs to use BSTs vs. arrays or linked lists.

Linear Lists
 BINARY SEARCH TREE LINEAR LISTS
FEATURE (BST) (ARRAY/LINKED LIST)

Search Time O(log n) (balanced) O(n) (linked list) /

Complexity O(log n) (sorted
array)
Insertion/Deletion O(log n) (balanced) O(1) for linked list
(beginning), O(n) for
Advantages array

and Sorting Elements always

sorted
Sorting takes O(n log
n)
Disadvantages Memory Usage Uses extra pointers Less overhead for
arrays

Random Access Not possible O(1) for arrays, O(n)

(traversal needed) for linked lists

Efficiency for Large Fast for dynamic Fast for static data
Datasets data
 • Use BSTs When:
• - Fast searching, insertion, and deletion
When to •
are required.
- Data is dynamic and frequently
updated.
Use BSTs • - Elements need to be kept sorted
automatically.
vs. Arrays •
•
Use Arrays When:
- Random access is needed (O(1) access
time).
or Linked • - The dataset is static and doesn't
change often.
Lists •
•
Use Linked Lists When:
- Frequent insertions and deletions are
required.
• - The structure needs flexibility in size.
 C++ •
// BST Search (Logarithmic Time)
Node* search(Node* root, int value) {
Example: if (!root || root->data == value) return
root;
return (value < root->data) ? search(root-
Comparing >left, value) : search(root->right, value);
}

BST vs. // Array Search (Linear Time)

int searchArray(int arr[], int size, int key) {

Array for (int i = 0; i < size; i++) {

}
if (arr[i] == key) return i;

Search }
return -1;
 Key Takeaways

BSTs are great for searching Arrays are better for fast Linked lists are best when
and maintaining sorted data random access and static insertions and deletions
but require balancing. datasets. occur frequently.
 More Applications of Data Structures

Data structures in databases AI and machine learning

applications
 Revision for the Final Exam

Key takeaways from the Problem-solving strategies

course
 Final Exam

Exam format and guidelines Final remarks