Data Structures Course Details (with

Examples)
1. Course Overview
Attribute Value
Course Title Data Structures
Credit Hours 4(3,1)
Contact Hours 3,3
Pre-requisites Programming Fundamentals

2. Course Introduction
The course is meticulously designed to equip students with a profound understanding
of fundamental data structures and algorithmic schemes. The primary objective is to
enable programmers to efficiently manipulate, store, and retrieve data, which are
critical operations in software development. Throughout the course, students will be
exposed to the intricate concepts of time and space complexity of computer
programs, fostering an ability to write optimized and efficient code. This foundational
knowledge is essential for developing robust and scalable software solutions across
various domains.

3. Course Learning Outcomes (CLOs)

Upon successful completion of this course, students will be able to:
 CLO Course Learning Outcome Bloom
No. Taxonomy
CLO-1 Implement various data structures and their algorithms and apply
them in implementing simple applications. C3 (Apply)
CLO-2 Analyze simple algorithms and determine their complexities. C5 (Analyze)
CLO-3 Apply the knowledge of data structure to other application
domains. C3 (Apply)
CLO-4 Design new data structures and algorithms to solve problems. C6 (Design)

4. Course Outline
This section provides a detailed breakdown of the topics covered in the Data
Structures course. Each topic will be explored in depth, focusing on theoretical
concepts, practical implementations, and real-world applications.
4.1. Abstract Data Types (ADTs)
An Abstract Data Type (ADT) is a mathematical model for data types, where a data
type is defined by its behavior from the point of view of a user of the data, specifically
in terms of possible values, possible operations on data of this type, and the behavior
of these operations. ADTs are crucial for understanding the conceptual foundation of
data structures, allowing for a clear separation between the logical properties of a data
type and its concrete implementation. They specify what an operation does, but not
how it does it. This abstraction allows for flexibility in implementation and promotes
modularity in software design.
Example: Stack ADT
A Stack ADT defines operations like push , pop , peek (or top ), isEmpty , and size .
It doesn’t specify whether the stack is implemented using an array or a linked list; it
only defines the behavior.
 class StackADT:
def push(self, item): # Adds an item to the top of the stack
raise NotImplementedError

def pop(self): # Removes and returns the item from the top of the stack
raise NotImplementedError

def peek(self): # Returns the item from the top of the stack without
removing it
raise NotImplementedError

def isEmpty(self): # Checks if the stack is empty

raise NotImplementedError

def size(self): # Returns the number of items in the stack

raise NotImplementedError

4.2. Complexity Analysis and Big Oh Notation

Complexity analysis is a critical aspect of algorithm design, focusing on estimating
the resources (time and space) an algorithm requires. It helps in predicting the
performance of an algorithm as the input size grows. Big Oh notation (O-notation) is a
mathematical notation that describes the limiting behavior of a function when the
argument tends towards a particular value or infinity. It provides an upper bound on
the growth rate of an algorithm’s running time or space requirements, allowing for
comparison of efficiency between different algorithms. Topics include best-case,
worst-case, and average-case complexities, and the analysis of common growth
functions such as O(1), O(log n), O(n), O(n log n), O(n^2), and O(2n).
Time Complexity refers to the amount of time an algorithm takes to run as a function
of the input size (n). Space Complexity refers to the amount of memory an algorithm
uses as a function of the input size (n).
Common Time Complexities:
O(1) - Constant Time: The execution time is independent of the input size.
Example: Accessing an element in an array by its index.
 def get_first_element(arr):
return arr[0]

O(log n) - Logarithmic Time: The execution time grows logarithmically with the
input size. This often occurs in algorithms that divide the problem space in half
with each step. Example: Binary search.

def binary_search(arr, target):

low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1

O(n) - Linear Time: The execution time grows linearly with the input size.
Example: Traversing a list.

def find_max(arr):
max_val = arr[0]
for i in range(1, len(arr)):
if arr[i] > max_val:
max_val = arr[i]
return max_val

O(n log n) - Linearithmic Time: Often seen in efficient sorting algorithms.

Example: Merge Sort, Quick Sort.
O(n^2) - Quadratic Time: The execution time is proportional to the square of the
input size. Example: Nested loops, such as in Bubble Sort or Insertion Sort.
 def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr

O(2^n) - Exponential Time: The execution time doubles with each addition to
the input size. Example: Recursive calculation of Fibonacci numbers without
memoization.

def fibonacci_recursive(n):
if n <= 1:
return n
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

4.3. Stacks
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle.
This means the last element added to the stack is the first one to be removed. Think of
a stack of plates: you can only add a new plate to the top, and you can only take a plate
from the top. Operations include push (adding an element to the top) and pop
(removing an element from the top). Other common operations include peek (or
top ) to view the top element without removing it, and isEmpty to check if the stack
contains any elements. Stacks can be implemented using both linked lists and arrays.
Array-based Implementation Example (Python List):
 class ArrayStack:
def __init__(self):
[Link] = []

def push(self, item):

[Link](item)

def pop(self):
if not [Link]():
return [Link]()
else:
return "Stack is empty"

def peek(self):
if not [Link]():
return [Link][-1]
else:
return "Stack is empty"

def isEmpty(self):
return len([Link]) == 0

def size(self):
return len([Link])

# Example Usage:
my_stack = ArrayStack()
my_stack.push(10)
my_stack.push(20)
my_stack.push(30)
print(f"Stack: {my_stack.items}") # Output: Stack: [10, 20, 30]
print(f"Top element: {my_stack.peek()}") # Output: Top element: 30
print(f"Popped element: {my_stack.pop()}") # Output: Popped element: 30
print(f"Stack after pop: {my_stack.items}") # Output: Stack after pop: [10,
20]

Applications of Stacks:
Function Call Management (Call Stack): When a function is called, its execution
context (local variables, return address) is pushed onto the call stack. When the
function returns, its context is popped.
Expression Evaluation: Used to convert infix expressions to postfix/prefix and
evaluate them.
 Backtracking Algorithms: Used to remember previous states to backtrack when
a dead end is reached (e.g., solving mazes, N-Queens problem).
Undo/Redo Functionality: Storing operations in a stack allows for easy undoing
and redoing.
Browser History: Navigating back and forth in web pages.
4.4. Recursion and Analyzing Recursive Algorithms
Recursion is a programming technique where a function calls itself to solve a problem.
A recursive function must have one or more base cases (stopping conditions) to
prevent infinite recursion, and a recursive step where the function calls itself with a
modified input that moves closer to the base case. Understanding recursion involves
identifying these components. Analyzing recursive algorithms often involves setting
up and solving recurrence relations to determine their time complexity. This section
will cover direct and indirect recursion, tail recursion, and the advantages and
disadvantages of using recursion.
Example: Factorial Calculation
The factorial of a non-negative integer n , denoted n! , is the product of all positive
integers less than or equal to n . The base case is 0! = 1 .
def factorial(n):
if n == 0: # Base case
return 1
else: # Recursive step
return n * factorial(n - 1)

# Example Usage:
print(f"Factorial of 5: {factorial(5)}") # Output: Factorial of 5: 120

Analyzing Recursive Algorithms (Recurrence Relations):

For the factorial function, the recurrence relation for time complexity T(n) is: T(n)
= T(n-1) + O(1) (for the multiplication and subtraction operations) T(0) = O(1)
(base case)
Solving this recurrence relation yields T(n) = O(n) .
Types of Recursion:
Direct Recursion: A function calls itself directly.
Indirect Recursion: A function calls another function, which in turn calls the first
function.
Tail Recursion: A recursive call is the last operation in the function. Some
compilers can optimize tail recursion into iteration, avoiding stack overflow
issues.
Advantages of Recursion:
Elegant and concise code for problems that are inherently recursive (e.g., tree
traversals, fractal generation).
Reduces the need for complex nested loops.
Disadvantages of Recursion:
Can be less efficient due to function call overhead (stack frames).
Risk of stack overflow for deep recursion without tail call optimization.
Can be harder to debug and understand for beginners.
4.5. Divide and Conquer Algorithms
Divide and Conquer is an algorithmic paradigm that involves breaking a problem into
smaller subproblems of the same type, solving them independently, and then
combining their solutions to solve the original problem. This technique is often
applied to problems that can be naturally split into smaller, more manageable pieces.
The three main steps are:
1. Divide: Break the problem into several subproblems that are smaller instances of
the same problem.
2. Conquer: Solve the subproblems recursively. If the subproblems are small
enough, solve them directly (base case).
3. Combine: Combine the solutions to the subproblems to obtain the solution to
the original problem.
Example: Merge Sort
Merge Sort is a classic example of a divide and conquer algorithm for sorting. It divides
the unsorted list into n sublists, each containing one element (a list of one element is
considered sorted). Then, it repeatedly merges sublists to produce new sorted sublists
until there is only one sorted list remaining.
def merge_sort(arr):
if len(arr) <= 1:
return arr

mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]

left_half = merge_sort(left_half) # Divide and Conquer (left)

right_half = merge_sort(right_half) # Divide and Conquer (right)

return merge(left_half, right_half) # Combine

def merge(left, right):

merged = []
left_idx, right_idx = 0, 0

while left_idx < len(left) and right_idx < len(right):

if left[left_idx] < right[right_idx]:
[Link](left[left_idx])
left_idx += 1
else:
[Link](right[right_idx])
right_idx += 1

[Link](left[left_idx:])
[Link](right[right_idx:])
return merged

# Example Usage:
unsorted_list = [38, 27, 43, 3, 9, 82, 10]
sorted_list = merge_sort(unsorted_list)
print(f"Sorted list: {sorted_list}") # Output: Sorted list: [3, 9, 10, 27,
38, 43, 82]

Analysis of Merge Sort:

Time Complexity: O(n log n) in all cases (best, average, worst).
 Space Complexity: O(n) due to the temporary arrays created during merging.
4.6. Sorting Algorithms
Sorting is the process of arranging elements in a specific order (ascending or
descending). This section will cover a variety of sorting algorithms, analyzing their
time and space complexities, stability, and practical applications.
4.6.1. Selection Sort
Selection Sort is a simple, in-place comparison-based sorting algorithm. It works by
repeatedly finding the minimum element from the unsorted part of the array and
putting it at the beginning. The algorithm maintains two subarrays in a given array:
1. The subarray which is already sorted.
2. The remaining subarray which is unsorted.
In every iteration of selection sort, the minimum element from the unsorted subarray
is picked and moved to the sorted subarray.
Example:
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i] # Swap the found minimum
element with the first element
return arr

# Example Usage:
unsorted_list = [64, 25, 12, 22, 11]
print(f"Sorted list (Selection Sort): {selection_sort(unsorted_list)}") #
Output: Sorted list (Selection Sort): [11, 12, 22, 25, 64]

Analysis of Selection Sort:

 Time Complexity: O(n^2) in all cases (best, average, worst) because of the
nested loops.
Space Complexity: O(1) as it is an in-place sorting algorithm.
Stability: Not stable.
4.6.2. Insertion Sort
Insertion Sort is a simple sorting algorithm that builds the final sorted array (or list)
one item at a time. It is much less efficient on large lists than more advanced
algorithms such as quicksort, heapsort, or merge sort. However, it has some
advantages:
Efficient for small data sets or data sets that are already substantially sorted.
Simple to implement.
Stable.
In-place.
The algorithm works by iterating through the input array and at each iteration, it
removes one element from the input data, finds the location it belongs within the
sorted list, and inserts it there. It repeats until no input elements remain.
Example:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr

# Example Usage:
unsorted_list = [12, 11, 13, 5, 6]
print(f"Sorted list (Insertion Sort): {insertion_sort(unsorted_list)}") #
Output: Sorted list (Insertion Sort): [5, 6, 11, 12, 13]

Analysis of Insertion Sort:

 Time Complexity:
Best Case: O(n) (when the array is already sorted).
Average and Worst Case: O(n^2) (when the array is sorted in reverse
order).
Space Complexity: O(1).
Stability: Stable.
4.6.3. Merge Sort
(Already covered in Divide and Conquer section - see 4.5)
4.6.4. Quick Sort
Quick Sort is an efficient, in-place, comparison-based, divide and conquer sorting
algorithm. It picks an element as a pivot and partitions the given array around the
picked pivot. The key process in quicksort is partition() . The goal of partitions is,
given an array and an element x of array as pivot, put x at its correct position in
sorted array and put all smaller elements (smaller than x ) before x , and put all
greater elements (greater than x ) after x . All this should be done in linear time.
Example:
 def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
return arr

def partition(arr, low, high):

pivot = arr[high] # Choose the last element as pivot
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1

# Example Usage:
unsorted_list = [10, 7, 8, 9, 1, 5]
n = len(unsorted_list)
print(f"Sorted list (Quick Sort): {quick_sort(unsorted_list, 0, n - 1)}") #
Output: Sorted list (Quick Sort): [1, 5, 7, 8, 9, 10]

Analysis of Quick Sort:

Time Complexity:
Best and Average Case: O(n log n).
Worst Case: O(n^2) (when the pivot selection consistently leads to highly
unbalanced partitions, e.g., already sorted array and pivot is always the
first/last element).
Space Complexity: O(log n) on average (due to recursion stack), O(n) in worst
case.
Stability: Not stable.
4.6.5. Bubble Sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list,
compares adjacent elements and swaps them if they are in the wrong order. The pass
through the list is repeated until no swaps are needed, which indicates that the list is
sorted. It is named for the way smaller or larger elements bubble to their correct
positions.
Example:
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
# Last i elements are already in place
for j in range(0, n - i - 1):
# Traverse the array from 0 to n-i-1
# Swap if the element found is greater
# than the next element
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr

# Example Usage:
unsorted_list = [5, 1, 4, 2, 8]
print(f"Sorted list (Bubble Sort): {bubble_sort(unsorted_list)}") # Output:
Sorted list (Bubble Sort): [1, 2, 4, 5, 8]

Analysis of Bubble Sort:

Time Complexity: O(n^2) in all cases (best, average, worst).
Space Complexity: O(1).
Stability: Stable.
4.6.6. Heap Sort
Heap Sort is a comparison-based sorting technique based on the Binary Heap data
structure. It is similar to selection sort where we first find the maximum element and
place it at the end. We repeat the same process for the remaining elements. A Binary
Heap is a complete binary tree that satisfies the heap property: for a max-heap, the
value of each node is greater than or equal to the value of its children; for a min-heap,
the value of each node is less than or equal to the value of its children.
Example (Max-Heap based Heap Sort):
 def heapify(arr, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left child
r = 2 * i + 2 # right child

# See if left child of root exists and is greater than root

if l < n and arr[largest] < arr[l]:
largest = l

# See if right child of root exists and is greater than root

if r < n and arr[largest] < arr[r]:
largest = r

# Change root, if needed

if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # swap
heapify(arr, n, largest)

def heap_sort(arr):
n = len(arr)

# Build a maxheap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)

# One by one extract elements

for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
return arr

# Example Usage:
unsorted_list = [12, 11, 13, 5, 6, 7]
print(f"Sorted list (Heap Sort): {heap_sort(unsorted_list)}") # Output:
Sorted list (Heap Sort): [5, 6, 7, 11, 12, 13]

Analysis of Heap Sort:

Time Complexity: O(n log n) in all cases.
Space Complexity: O(1).
Stability: Not stable.
4.6.7. Shell Sort
Shell Sort is an in-place comparison sort that can be seen as a generalization of
insertion sort. It sorts elements that are far apart from each other and then
successively reduces the gap between elements to be compared. The interval between
the elements (gap) is reduced based on some sequence (e.g., Knuth’s sequence: 1, 4,
13, 40, …). The main idea is to move elements to their correct positions faster than
insertion sort.
Example:
def shell_sort(arr):
n = len(arr)
gap = n // 2

while gap > 0:

for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2
return arr

# Example Usage:
unsorted_list = [12, 34, 54, 2, 3]
print(f"Sorted list (Shell Sort): {shell_sort(unsorted_list)}") # Output:
Sorted list (Shell Sort): [2, 3, 12, 34, 54]

Analysis of Shell Sort:

Time Complexity: Depends on the gap sequence. Worst-case can be O(n^2), but
with optimal gap sequences, it can approach O(n log^2 n) or O(n^(3⁄2)).
Space Complexity: O(1).
Stability: Not stable.
4.6.8. Radix Sort
Radix Sort is a non-comparative integer sorting algorithm that sorts data with integer
keys by grouping keys by individual digits which share the same significant position
and value. It works by processing digits from least significant to most significant (LSD
Radix Sort) or vice versa (MSD Radix Sort). It requires a stable sorting algorithm (like
Counting Sort) as a subroutine.
Example (LSD Radix Sort using Counting Sort):
def counting_sort_for_radix(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10

# Store count of occurrences in count[]

for i in range(n):
index = arr[i] // exp
count[index % 10] += 1

# Change count[i] so that count[i] now contains actual

# position of this digit in output array
for i in range(1, 10):
count[i] += count[i - 1]

# Build the output array

i = n - 1
while i >= 0:
index = arr[i] // exp
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1

# Copying the output array to arr[], so that arr now

# contains sorted numbers according to current digit
for i in range(n):
arr[i] = output[i]

def radix_sort(arr):
# Find the maximum number to know number of digits
max1 = max(arr)

# Do counting sort for every digit. Note that instead of passing digit
number,
# exp is passed. exp is 10^i where i is current digit number
exp = 1
while max1 // exp > 0:
counting_sort_for_radix(arr, exp)
exp *= 10
return arr

# Example Usage:
unsorted_list = [170, 45, 75, 90, 802, 24, 2, 66]
 print(f"Sorted list (Radix Sort): {radix_sort(unsorted_list)}") # Output:
Sorted list (Radix Sort): [2, 24, 45, 66, 75, 90, 170, 802]

Analysis of Radix Sort:

Time Complexity: O(nk) where n is the number of elements and k is the number
of digits (or maximum number of bits) in the largest number. If k is small and
constant, it can be faster than comparison sorts.
Space Complexity: O(n + k).
Stability: Stable (if the underlying counting sort is stable).
4.6.9. Bucket Sort
Bucket Sort (or bin sort) is a non-comparative sorting algorithm that works by
distributing elements into a number of buckets. Each bucket is then sorted
individually, either using a different sorting algorithm, or by recursively applying the
bucket sort algorithm. It is a distribution sort, and is effective for uniformly distributed
data.
Example:
 def bucket_sort(arr):
# Assume input is uniformly distributed between 0 and 1
num_buckets = 10
buckets = [[] for _ in range(num_buckets)]

# Distribute elements into buckets

for num in arr:
bucket_index = int(num * num_buckets)
buckets[bucket_index].append(num)

# Sort each bucket and concatenate the results

sorted_arr = []
for bucket in buckets:
[Link]() # Use insertion sort or any other stable sort
sorted_arr.extend(bucket)
return sorted_arr

# Example Usage (numbers between 0 and 1):

unsorted_list = [0.897, 0.565, 0.656, 0.123, 0.665, 0.343]
print(f"Sorted list (Bucket Sort): {bucket_sort(unsorted_list)}") # Output:
Sorted list (Bucket Sort): [0.123, 0.343, 0.565, 0.656, 0.665, 0.897]

Analysis of Bucket Sort:

Time Complexity: O(n + k) on average, where n is the number of elements and k
is the number of buckets. Worst-case can be O(n^2) if all elements fall into a
single bucket.
Space Complexity: O(n + k).
Stability: Stable (if the underlying sorting algorithm for buckets is stable).
4.7. Queues and Priority Queues
A queue is a linear data structure that follows the First In, First Out (FIFO) principle.
This means the first element added to the queue is the first one to be removed. Think
of a line at a ticket counter: the first person in line is the first to be served. Operations
include enqueue (adding an element to the rear) and dequeue (removing an element
from the front). Queues can be implemented using linked lists and arrays.
Array-based Implementation Example (Python [Link] for efficiency):
 from collections import deque

class ArrayQueue:
def __init__(self):
[Link] = deque()

def enqueue(self, item):

[Link](item)

def dequeue(self):
if not [Link]():
return [Link]()
else:
return "Queue is empty"

def peek(self):
if not [Link]():
return [Link][0]
else:
return "Queue is empty"

def isEmpty(self):
return len([Link]) == 0

def size(self):
return len([Link])

# Example Usage:
my_queue = ArrayQueue()
my_queue.enqueue(10)
my_queue.enqueue(20)
my_queue.enqueue(30)
print(f"Queue: {list(my_queue.items)}") # Output: Queue: [10, 20, 30]
print(f"Front element: {my_queue.peek()}") # Output: Front element: 10
print(f"Dequeued element: {my_queue.dequeue()}") # Output: Dequeued element:
10
print(f"Queue after dequeue: {list(my_queue.items)}") # Output: Queue after
dequeue: [20, 30]

Applications of Queues:
Operating Systems: CPU scheduling, disk scheduling.
Network Buffering: Handling data packets.
 Printer Spooling: Managing print jobs.
Breadth-First Search (BFS): Graph traversal algorithm.
A Dequeuer (Double-Ended Queue or Deque) is a linear data structure that allows
insertion and deletion from both ends (front and rear). It can be used as both a stack
and a queue.
from collections import deque

my_deque = deque()
my_deque.append(1) # Add to right (rear)
my_deque.appendleft(2) # Add to left (front)
print(f"Deque: {list(my_deque)}") # Output: Deque: [2, 1]
print(f"Pop from right: {my_deque.pop()}") # Output: Pop from right: 1
print(f"Pop from left: {my_deque.popleft()}") # Output: Pop from left: 2

A priority queue is an abstract data type similar to a regular queue or stack, but where
each element has a priority associated with it. Elements with higher priority are served
before elements with lower priority. If two elements have the same priority, their order
in the queue is determined by their order of arrival. Implementations often involve
heaps (specifically min-heaps or max-heaps) to efficiently retrieve the highest/lowest
priority element.
Example (Min-Heap based Priority Queue using heapq module):
 import heapq

class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0

def push(self, item, priority):

# Items are tuples (priority, index, item) to handle equal
priorities
[Link](self._queue, (priority, self._index, item))
self._index += 1

def pop(self):
if not [Link]():
return [Link](self._queue)[-1] # Return the item
else:
return "Priority Queue is empty"

def isEmpty(self):
return len(self._queue) == 0

# Example Usage:
my_pq = PriorityQueue()
my_pq.push("Task A", 3)
my_pq.push("Task B", 1)
my_pq.push("Task C", 2)

print(f"Popped (highest priority): {my_pq.pop()}") # Output: Popped (highest

priority): Task B
print(f"Popped (next highest priority): {my_pq.pop()}") # Output: Popped
(next highest priority): Task C

Applications of Priority Queues:

Dijkstra’s Algorithm: For finding the shortest path in graphs.
Prim’s Algorithm: For finding minimum spanning trees.
Event Simulation: Managing events based on their occurrence time.
Operating Systems: Process scheduling.
4.8. Linked Lists and Their Various Types
A linked list is a linear data structure where elements are not stored at contiguous
memory locations. Instead, each element (node) consists of two parts: data and a
reference (or link/pointer) to the next node in the sequence. This non-contiguous
storage allows for efficient insertions and deletions without shifting elements, unlike
arrays. However, it sacrifices direct access (random access) to elements, requiring
traversal from the beginning.
Basic Node Structure:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None # Pointer to the next node

4.8.1. Singly Linked List

A singly linked list is the simplest type of linked list, where each node points only to
the next node in the sequence. Traversal is unidirectional.
Example: Singly Linked List Implementation
 class SinglyLinkedList:
def __init__(self):
[Link] = None

def append(self, data):

new_node = Node(data)
if [Link] is None:
[Link] = new_node
return
last = [Link]
while [Link]:
last = [Link]
[Link] = new_node

def display(self):
elements = []
current = [Link]
while current:
[Link]([Link])
current = [Link]
print(" -> ".join(map(str, elements)))

# Example Usage:
my_sll = SinglyLinkedList()
my_sll.append(1)
my_sll.append(2)
my_sll.append(3)
print("Singly Linked List:", end=" ")
my_sll.display() # Output: Singly Linked List: 1 -> 2 -> 3

4.8.2. Doubly Linked List

A doubly linked list is a more complex type of linked list where each node has
pointers to both the next and previous nodes in the sequence. This allows for
bidirectional traversal, making some operations (like deleting a given node) more
efficient.
Example: Doubly Linked List Node Structure
 class DoublyNode:
def __init__(self, data):
[Link] = data
[Link] = None # Pointer to next node
[Link] = None # Pointer to previous node

4.8.3. Circular Linked List

A circular linked list is a linked list where the last node points back to the first node,
forming a circle. This can be a singly or doubly linked list. Circular linked lists are useful
for implementing circular buffers or for situations where you need to cycle through a
list continuously.
Example: Singly Circular Linked List (Conceptual)
In a singly circular linked list, the next pointer of the last node points to the head
node.
4.8.4. Sorted Linked List
A sorted linked list is a linked list where the elements are maintained in a specific
sorted order (ascending or descending). When inserting a new element, it is placed in
its correct sorted position to maintain the order. This makes searching potentially
faster than in an unsorted linked list, but still requires traversal.
4.9. Searching
Searching algorithms are used to find a specific element (or key) within a data
structure. The efficiency of a search algorithm depends heavily on the data structure
and whether the data is sorted.
4.9.1. Searching an Unsorted Array (Linear Search)
Linear Search (or sequential search) is the simplest searching algorithm. It
sequentially checks each element of the list until a match is found or the whole list has
been searched. It is suitable for unsorted arrays or lists.
Example:
 def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # Return the index if found
return -1 # Return -1 if not found

# Example Usage:
my_list = [5, 2, 8, 12, 1]
print(f"Target 8 found at index: {linear_search(my_list, 8)}") # Output:
Target 8 found at index: 2
print(f"Target 10 found at index: {linear_search(my_list, 10)}") # Output:
Target 10 found at index: -1

Analysis of Linear Search:

Time Complexity:
Best Case: O(1) (target is the first element).
Average and Worst Case: O(n) (target is at the end or not present).
Space Complexity: O(1).
4.9.2. Binary Search for Sorted Arrays
Binary Search is an efficient search algorithm for finding an item from a sorted list of
items. It works by repeatedly dividing the search interval in half. If the value of the
search key is less than the item in the middle of the interval, narrow the interval to the
lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is
found or the interval is empty.
Example:
 def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1

# Example Usage:
sorted_list = [1, 5, 8, 12, 15, 20]
print(f"Target 12 found at index: {binary_search(sorted_list, 12)}") #
Output: Target 12 found at index: 3
print(f"Target 10 found at index: {binary_search(sorted_list, 10)}") #
Output: Target 10 found at index: -1

Analysis of Binary Search:

Time Complexity: O(log n) in all cases.
Space Complexity: O(1) (iterative) or O(log n) (recursive due to call stack).
4.10. Hashing and Indexing
Hashing is a technique used to uniquely identify a specific object from a group of
similar objects. It involves mapping data of arbitrary size (keys) to fixed-size values
(hash values or hash codes). The primary goal of hashing is to enable efficient data
retrieval, insertion, and deletion operations, ideally in O(1) average time complexity. A
hash table (or hash map) is a data structure that implements an associative array
abstract data type, a structure that can map keys to values.
Key Concepts:
Hash Function: An algorithm that takes an input (or ‘key’) and returns a fixed-
size string of bytes, which is typically a hash value. A good hash function should
be fast to compute, minimize collisions, and distribute keys uniformly across the
hash table.
 Hash Table: An array where each index (or ‘bucket’) corresponds to a hash value.
Data is stored at the index computed by the hash function.
4.10.1. Collision Resolution
A collision occurs when two different keys hash to the same index in the hash table.
Effective collision resolution strategies are crucial for maintaining the efficiency of
hash tables.
Open Addressing: When a collision occurs, the system probes for another open
location in the hash table. Common techniques include:
Linear Probing: If a slot is occupied, it checks the next slot, and so on,
linearly.
Quadratic Probing: If a slot is occupied, it checks slots at quadratic
intervals (e.g., hash(key) + 1^2 , hash(key) + 2^2 , etc.).
Double Hashing: Uses a second hash function to determine the step size
for probing.
Chaining: Each slot in the hash table is a pointer to a linked list (or another data
structure). When a collision occurs, the new element is simply added to the
linked list at that slot.
Example: Hashing with Chaining (Conceptual Python Dictionary)
Python’s dictionary ( dict ) uses a hash table internally, and handles collisions
efficiently. While not a direct implementation of chaining, it demonstrates the concept
of mapping keys to values using hashing.
 my_hash_table = {}

# Insert operations
my_hash_table["apple"] = 10
my_hash_table["banana"] = 20
my_hash_table["cherry"] = 30

# Retrieve operations
print(f"Value for apple: {my_hash_table["apple"]}") # Output: Value for
apple: 10

# If a collision were to occur, Python's dict handles it internally,

# potentially by storing multiple key-value pairs at the same hash index
# and resolving with further comparisons.

4.10.2. Indexing
Indexing is a data structuring technique used to optimize the speed of data retrieval
operations on a database table or file. An index is a small, fast lookup table that
contains a key and a pointer to the record (or row) where that key’s value is stored.
Just like an index in a book helps you quickly find information, database indexes help
the database management system (DBMS) find data rows quickly without having to
scan the entire table.
Types of Indexes:
Primary Index: An index on a primary key, which uniquely identifies each record.
Secondary Index: An index on a non-primary key field, which may not be
unique.
Clustered Index: Reorders the physical storage of the table to match the index
order. A table can have only one clustered index.
Non-Clustered Index: Does not alter the physical order of the table. Instead, it
creates a separate structure that contains the index key and a pointer to the
actual data row.
Applications of Indexing:
Database Management Systems (DBMS): Crucial for speeding up SELECT
queries.
 File Systems: Used to quickly locate files and directories.
4.11. Trees and Tree Traversals
A tree is a non-linear data structure that simulates a hierarchical tree structure, with a
root value and subtrees of children with a parent node, represented as a set of linked
nodes. Unlike linear data structures (arrays, linked lists, stacks, queues), trees are used
to represent data with a hierarchical relationship. Key terminology includes root,
node, parent, child, sibling, leaf, edge, path, height, and depth.
4.11.1. Binary Trees
A binary tree is a tree data structure in which each node has at most two children,
which are referred to as the left child and the right child. Binary trees are fundamental
and widely used.
Example: Binary Tree Node Structure
class TreeNode:
def __init__(self, data):
[Link] = data
[Link] = None # Pointer to the left child
[Link] = None # Pointer to the right child

4.11.2. Tree Traversals

Tree traversal refers to the process of visiting each node in a tree data structure
exactly once. There are three common methods for traversing binary trees:
In-order Traversal (Left -> Root -> Right): Visits the left subtree, then the root
node, then the right subtree. For a Binary Search Tree, in-order traversal yields
elements in sorted order.
 def inorder_traversal(node):
if node:
inorder_traversal([Link])
print([Link], end=" ")
inorder_traversal([Link])

Pre-order Traversal (Root -> Left -> Right): Visits the root node, then the left
subtree, then the right subtree. Useful for creating a copy of the tree or for
expressing hierarchical structure.

def preorder_traversal(node):
if node:
print([Link], end=" ")
preorder_traversal([Link])
preorder_traversal([Link])

Post-order Traversal (Left -> Right -> Root): Visits the left subtree, then the
right subtree, then the root node. Useful for deleting a tree or for evaluating
expressions.

def postorder_traversal(node):
if node:
postorder_traversal([Link])
postorder_traversal([Link])
print([Link], end=" ")

Example Tree and Traversals:

Consider a simple binary tree:
 1
/ \
2 3
/ \
4 5

root = TreeNode(1)
[Link] = TreeNode(2)
[Link] = TreeNode(3)
[Link] = TreeNode(4)
[Link] = TreeNode(5)

print("In-order Traversal:", end=" ")

inorder_traversal(root) # Output: 4 2 5 1 3
print("\nPre-order Traversal:", end=" ")
preorder_traversal(root) # Output: 1 2 4 5 3
print("\nPost-order Traversal:", end=" ")
postorder_traversal(root) # Output: 4 5 2 3 1
print()

4.11.3. Binary Search Trees (BSTs)

A Binary Search Tree (BST) is a special type of binary tree where the value of each
node is greater than or equal to any value in its left subtree and less than or equal to
any value in its right subtree. This property allows for efficient searching, insertion,
and deletion operations, with an average time complexity of O(log n).
Example: BST Insertion and Search
 class BSTNode:
def __init__(self, key):
[Link] = key
[Link] = None
[Link] = None

def insert_bst(root, key):

if root is None:
return BSTNode(key)
if key < [Link]:
[Link] = insert_bst([Link], key)
else:
[Link] = insert_bst([Link], key)
return root

def search_bst(root, key):

if root is None or [Link] == key:
return root
if key < [Link]:
return search_bst([Link], key)
return search_bst([Link], key)

# Example Usage:
bst_root = None
bst_root = insert_bst(bst_root, 50)
bst_root = insert_bst(bst_root, 30)
bst_root = insert_bst(bst_root, 20)
bst_root = insert_bst(bst_root, 40)
bst_root = insert_bst(bst_root, 70)
bst_root = insert_bst(bst_root, 60)
bst_root = insert_bst(bst_root, 80)

print(f"Search for 40: {search_bst(bst_root, 40).key if search_bst(bst_root,

40) else 'Not Found'}") # Output: Search for 40: 40
print(f"Search for 90: {search_bst(bst_root, 90).key if search_bst(bst_root,
90) else 'Not Found'}") # Output: Search for 90: Not Found

Analysis of BST Operations:

Time Complexity (Average Case): O(log n) for search, insertion, deletion.
Time Complexity (Worst Case): O(n) (when the tree becomes skewed,
resembling a linked list).
4.11.4. Heaps
A heap is a specialized tree-based data structure that satisfies the heap property. It is
typically implemented as an array. Heaps are commonly used to implement priority
queues.
Max-Heap: For any given node C, if P is a parent node of C, then the key (value) of
P is greater than or equal to the key of C. The largest element is at the root.
Min-Heap: For any given node C, if P is a parent node of C, then the key (value) of
P is less than or equal to the key of C. The smallest element is at the root.
Example: Min-Heap (Conceptual with heapq )
import heapq

min_heap = []
[Link](min_heap, 3)
[Link](min_heap, 1)
[Link](min_heap, 4)
[Link](min_heap, 1)

print(f"Min-Heap: {min_heap}") # Output: Min-Heap: [1, 1, 4, 3] (internal

array representation)
print(f"Smallest element: {[Link](min_heap)}") # Output: Smallest
element: 1
print(f"Min-Heap after pop: {min_heap}") # Output: Min-Heap after pop: [1,
3, 4]

Applications of Heaps:
Priority Queues: Efficiently retrieve the highest/lowest priority item.
Heap Sort: An efficient sorting algorithm.
Graph Algorithms: Dijkstra’s and Prim’s algorithms use priority queues, often
implemented with heaps.
4.11.5. M-way Trees
An M-way tree (or multi-way tree) is a tree in which each node can have more than
two children (up to M children). These trees are generalizations of binary trees and are
often used in database systems and file systems to store large amounts of data on disk,
as they can reduce the height of the tree, thereby reducing the number of disk I/O
operations required to access data.
Example: B-Trees (a type of M-way tree)
B-trees are self-balancing M-way trees commonly used in databases and file systems.
They are designed to work well on disk-based storage systems. Each node can have
many children, and the number of children is typically determined by the block size of
the disk.
4.11.6. Balanced Trees
Balanced trees are self-balancing binary search trees that automatically keep their
height small in the face of arbitrary insertions and deletions. This ensures that
operations like search, insertion, and deletion maintain a logarithmic time complexity
(O(log n)) even in the worst case, preventing the tree from degenerating into a linked
list. Examples include:
AVL Trees: The first self-balancing binary search tree. It maintains a height
balance factor (difference between heights of left and right subtrees) of -1, 0, or 1
for every node.
Red-Black Trees: A more complex but widely used self-balancing BST. They
maintain balance by enforcing five specific properties related to the coloring of
nodes (red or black).
Applications of Balanced Trees:
Database Indexing: Efficiently store and retrieve data.
Associative Arrays: Implementing maps and dictionaries.
File Systems: Managing file structures.
4.12. Graphs
A graph is a non-linear data structure consisting of a finite set of vertices (or nodes)
and a set of edges connecting pairs of vertices. Graphs are used to model many real-
world systems, such as social networks, road networks, and computer networks. Key
terminology includes vertex, edge, degree, path, cycle, connected graph, directed
graph, and undirected graph.
4.12.1. Graph Representations
There are two common ways to represent a graph:
Adjacency Matrix: A 2D array where matrix[i][j] is 1 if there is an edge
between vertex i and vertex j , and 0 otherwise. For weighted graphs, it stores
the weight of the edge. It is suitable for dense graphs (many edges).

# Example: Adjacency Matrix for an undirected graph with 3 vertices

# (0)--(1)
# | /
# | /
# (2)
adj_matrix = [
[0, 1, 1],
[1, 0, 1],
[1, 1, 0]
]

Adjacency List: An array of linked lists (or lists in Python) where the i -th
element in the array contains a list of vertices adjacent to vertex i . It is suitable
for sparse graphs (few edges).

# Example: Adjacency List for the same graph

adj_list = {
0: [1, 2],
1: [0, 2],
2: [0, 1]
}

4.12.2. Graph Traversals

Graph traversal refers to the process of visiting (checking and/or updating) each
vertex in a graph. Two common algorithms are:
Breadth-First Search (BFS): Traverses a graph level by level. It starts at a source
node and explores all its immediate neighbors (level 1 nodes) before moving to
their neighbors (level 2 nodes), and so on. BFS typically uses a queue.
 from collections import deque

def bfs(graph, start_node):

visited = set()
queue = deque([start_node])
[Link](start_node)

while queue:
current_node = [Link]()
print(current_node, end=" ")

for neighbor in graph[current_node]:

if neighbor not in visited:
[Link](neighbor)
[Link](neighbor)

# Example Usage (using adj_list from above)

graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1]
}
print("BFS Traversal (starting from 0):")
bfs(graph, 0) # Output: 0 1 2
print()

Depth-First Search (DFS): Traverses a graph by going as deep as possible along

each branch before backtracking. It explores a path completely before exploring
other paths. DFS typically uses a stack (or recursion, which uses the call stack).
 def dfs(graph, start_node, visited=None):
if visited is None:
visited = set()
[Link](start_node)
print(start_node, end=" ")

for neighbor in graph[start_node]:

if neighbor not in visited:
dfs(graph, neighbor, visited)

# Example Usage (using adj_list from above)

graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1]
}
print("DFS Traversal (starting from 0):")
dfs(graph, 0) # Output: 0 1 2 (order might vary based on adjacency
list order)
print()

4.12.3. Topological Order

Topological sorting (or topological ordering) of a directed acyclic graph (DAG) is a
linear ordering of its vertices such that for every directed edge uv from vertex u to
vertex v , u comes before v in the ordering. Topological sorting is not possible on
graphs with cycles. It has many applications, especially in scheduling tasks with
dependencies.
Example: Task Scheduling
Consider tasks A, B, C, D, E with dependencies:
A must be done before B and C.
B must be done before D.
C must be done before E.
A topological sort would give a valid order of tasks, e.g., A -> B -> D -> C -> E or A -> C ->
E -> B -> D.
4.12.4. Shortest Path Algorithms
Shortest path algorithms are used to find a path between two vertices (or nodes) in a
graph such that the sum of the weights of its constituent edges is minimized. These
algorithms are fundamental in network routing, mapping applications, and resource
allocation.
Dijkstra’s Algorithm: Finds the shortest paths from a single source vertex to all
other vertices in a graph with non-negative edge weights. It uses a priority queue
to efficiently select the next vertex to visit.
Bellman-Ford Algorithm: Finds the shortest paths from a single source vertex to
all other vertices in a weighted graph. It can handle graphs with negative edge
weights, but it is slower than Dijkstra’s algorithm. It can also detect negative
cycles.
Example: Dijkstra’s Algorithm (Conceptual)
Imagine a road map where cities are vertices and roads are edges with distances as
weights. Dijkstra’s algorithm can find the shortest route from your starting city to all
other cities.
4.12.5. Adjacency Matrix and Adjacency List Implementations
(Already covered in Graph Representations - see 4.12.1)
4.13. Memory Management and Garbage Collection
Memory management is the process of controlling and coordinating computer
memory, assigning memory blocks to running programs, and optimizing overall
system performance. It involves allocating memory to programs when they request it
and deallocating it when they are no longer needed. Efficient memory management is
crucial for preventing memory leaks, improving program performance, and ensuring
system stability.
Key Concepts:
Dynamic Memory Allocation: Allocating memory at runtime (e.g., using
malloc / free in C/C++ or new / delete in C++). This allows programs to request
memory as needed, rather than allocating a fixed amount at compile time.
 Memory Leaks: Occur when a program allocates memory but fails to deallocate
it when it’s no longer needed, leading to a gradual reduction in available memory
and potential system slowdowns or crashes.
Fragmentation: Memory can become fragmented over time, where free memory
is broken into small, non-contiguous blocks, making it difficult to allocate large
contiguous blocks even if enough total free memory exists.
Garbage collection is a form of automatic memory management that attempts to
reclaim garbage, or memory occupied by objects that are no longer in use by the
program. Instead of manual deallocation, a garbage collector automatically identifies
and frees up memory that is no longer reachable or referenced by the program. This
simplifies programming by reducing the burden on developers to manage memory
explicitly.
Common Garbage Collection Algorithms:
Reference Counting: Each object maintains a count of references pointing to it.
When the count drops to zero, the object is considered garbage and its memory is
reclaimed. (e.g., CPython’s primary GC mechanism).
Mark-and-Sweep: The garbage collector first marks all reachable objects (from a
set of root objects) and then sweeps (deletes) all unmarked objects.
Copying Collectors: Divides memory into two halves. When one half is full, it
copies all live objects to the other half, compacting them in the process, and then
reclaims the entire first half.
Generational Collectors: Based on the observation that most objects die young.
It divides the heap into generations (e.g., young, old) and collects younger
generations more frequently.
Example: Python’s Automatic Garbage Collection
In Python, memory management is largely automatic. When an object is no longer
referenced, its memory is automatically reclaimed by the garbage collector. This is
primarily done through reference counting, with a cycle detector to handle circular
references.
 class MyObject:
def __init__(self, name):
[Link] = name
print(f"{[Link]} created")

def __del__(self):
print(f"{[Link]} destroyed")

# Object creation and deletion

obj1 = MyObject("Object 1")
obj2 = obj1 # obj2 now references the same object as obj1
del obj1 # Reference count of "Object 1" is still 1 (due to obj2)
del obj2 # Reference count drops to 0, __del__ is called

# Output:
# Object 1 created
# Object 1 destroyed

Advantages of Automatic Garbage Collection:

Reduces programming effort and complexity related to memory management.
Helps prevent memory leaks and dangling pointers.
Disadvantages of Automatic Garbage Collection:
Can introduce performance overhead due to the garbage collection process.
Unpredictable pauses (stop-the-world events) can occur during collection.
Less control over memory usage compared to manual management.

5. Reference Materials
This course draws upon several authoritative texts in the field of Data Structures and
Algorithms. Students are encouraged to consult these resources for further reading
and deeper understanding.
1. Data Structures and Algorithm Analysis in Java by Mark A. Weiss
2. Data Structures and Abstractions with Java by Frank M. Carrano & Timothy M.
Henry
 3. Data Structures and Algorithms in C++ by Adam Drozdek
4. Data Structures and Algorithm Analysis in C++ by Mark Allen Weiss
5. Java Software Structures: Designing and Using Data Structures by John Lewis
and Joseph Chase
Author: Manus AI Date: April 12, 2026