Data Structure Final Preparation.

Data Structure Algorithm

1. Array 1. Linear Search
2. Ordered Array 2. Binary Search
3. Linked list 3. Bubble sort
4. Stack 4. Selection sort
5. Queue 5. Delete
6. Hash table 6. Inorder Traversal (left → root → right)
7. Binary search Tree 7. Preorder Traversal (root → left → right)
8. Red Black Tree 8. Postorder Traversal (left → right → root)
9. Hepa 9. Tree Rotations (Left & Right) (RBT)
10. Graph 10. Balancing Rules (Insertion)(RBT)
11. Wieght graph 11. Heap Insertion (Max-Heap / Min-Heap)
12. Recurion 12. Heap Deletion (Remove Max / Min)
13. Depth-First Search (DFS)
14. Breadth-First Search (BFS)
15. Dijkstra’s Algorithm (Shortest Path)
16. Kruskal’s Algorithm (Minimum Spanning Tree)
17. Topological Sort
18.

Exam format
I. MCQ 40 mark
II. Fill in the blank 20 Marks
III. Short answer
IV. Pseudocode
V. Real-world scenario
 I. Array
An array is a collection of items of the same variable type that are stored linearly in memory
locations. It is one of the most popular and simple data structures used in programming.
In Java, Data of a primitive type is a value type. All objects are references.
Basic terminology of arrays. Array index, length, element.
Declaration in array: int arr[];
TYPE OF ARRAY

Unordered array: The typical array in which elements do not need to be maintained in order.
Ordered array: An Array in which the element is ordered.
ASYMPTOTIC NOTATION refers to mathematical notation used for asymptotic analysis.
Big O Notation is used to describe the worst-case scenario of how many operations an algorithm
will perform as the data size grows.
What is O(1)?
For typical operations (comparison, calculation, etc.), it is considered constant time: c. Big O
Notation: O(1).
What is O(n)?
For loops, the operations will take n times as we have to go through all the elements. Big O
Notation: O(n).
What is O(n^m)?
Nested loops will be n^m in which n will be the number of elements, m is the number of loops.
(Eg, 2 nested loops would be n^2). Big O Notation: O(n^m).
What is the time complexity of loops followed by another loop?
Loops followed by another loop = n + n, so it is still n. Big O Notation: O(n).
What is O(log n)?
Splitting problems in half (Binary search) would result in log n. Big O Notation: O(log n).

OPERATING IN ARRAY

SEARCHING ALGORITHMs-BINARY SEARCH

 • Split the array into two equal parts.
• Start from the middle element.
• If the search value is smaller, search the lower half.
• If the search value is higher, search the upper half.
SORTING Algorithms.
Bubble sort is a simple comparison-based algorithm where each pair of adjacent elements is
compared and swapped if they are in the wrong order. This process repeats until the list is sorted.
Simply put: FROM RIGHT TO LEFT, the left is the largest after the first operation.

HOW IT WORK:

• Start from index 0.

• Find the minimum element in the unsorted section.
• Swap it with the first unsorted element.
• Move the boundary of sorted section one step to the right.
• Repeat until all elements are sorted.
Selection sort is a comparison-based sorting algorithm. It repeatedly selects the smallest element
from the unsorted part and moves it to the end of the sorted part.
HOW IT WORK

• Start from index 0.

• Find the minimum element in the unsorted section.
• Swap it with the first unsorted element.
• Move the boundary of sorted section one step to the right.
• Repeat until all elements are sorted.

Insertion sort is a simple sorting algorithm that works by iteratively inserting each element of
an unsorted list into its correct position in a sorted portion of the list. It removes one element
from the unsorted list, finds the location it belongs in the sorted list, and inserts it there.
HOW IT WORK.

• Begin with the second element of the array (the first element is considered sorted).
• Compare this element with the elements in the sorted part on its left.
• Insert the element into the correct position.
• Shift the other sorted elements to the right if needed.
• Repeat this for each element from the third to the last until the whole array is sorted.
INVARIANT OF EACH SORTING
Bubble sort: After each full pass, the largest unsorted element is placed in its correct position at
the end of the array.

Selection sort: After each pass, the subarray on the right (sorted part) contains the smallest
elements in correct order.
Insertion sort: At the start of each iteration, the subarray to the left of the current index is
already sorted.
Time complexity comparison:

Algorithm\Case Best case Average worst

Bubble sort O(n) O(n²) O(n²)
Selection sort O(n²) O(n²) O(n²)
Insertion sort O(n) O(n²) O(n²)
Binary Search O log(n) O log(n) O log(n)

LINKED LIST
A linked list is a fundamental data structure in computer science. It mainly allows efficient
insertion and deletion operations compared to arrays.
Data structure concept:

A Linked List is a linear data structure where each element (called a node) contains:

• Data
• A reference (or pointer) to the next node in the list.
• HEAD: the first
• Tail : the last
• Each items in the linked list are called Link/Node
•

Singly Linked List:

A singly linked list is a collection of nodes where each node contains data and a pointer to the
next node.

Each link consists of:

• The data itself

• A reference to the next link in the list, which is null for the last item
How does a singly linked list differ from an array?

• Singly linked list stores elements in nodes linked by pointers.

• Arrays store elements contiguously in memory.
• Linked lists allow easy insertion/deletion but no direct access by index.

Doubly linked list

A doubly linked list is a type of linked list where each node contains three parts:

• The data
• A pointer/reference to the next node
• A pointer/reference to the previous node

Key Characteristics:

• You can traverse forward and backward

• The first node’s prev is null, and the last node’s next is null
• Allows faster deletion from both ends and easier navigation

Circular Linked list:

A circular linked list is a variation where the last node points back to the first node, forming
a circle.
It can be singly or doubly linked.

• Singly Circular List: Only has next pointer, and last node’s next points to the head.
• Doubly Circular List: Has both next and prev pointers, and it loops in both
directions.

Key Characteristics:

• No node has null as a pointer.

• You can loop through the list endlessly (careful when searching/traversing).
 • Useful in applications where looping is needed, e.g., round-robin schedulers or
playlists.

SORTED LINKED LIST

Linked list where the data is maintained in sorted order.

Where is a Sorted Linked List useful?

• In the same applications where you use a sorted array.
• Insertion is faster than in a sorted array.
• Memory is used more efficiently.
Stack and Queue
A Stack is a linear data structure that follows a particular order in which the operations are
performed. The order may be LIFO (Last In First Out) or FILO(First In Last
Out). LIFO implies that the element that is inserted last comes out first, and FILO implies
that the element that is inserted first comes out last.
STACK is A LIFO (Last In, First Out) data structure where elements are added and removed
from the top of the stack.
Stack is a linear data structure that follows LIFO (Last In First Out) Principle, the last element
inserted is the first to be popped out. It means both insertion and deletion operations happen at
one end only.
Stack Operations (All are O(1)):

• Push: Add element to the top of the stack.

• Pop: Remove the top element from the stack.
 • Peek: View the top element without removing it.
• isEmpty: Check if the stack is empty.
• isFull: Check if the stack is full (mainly for fixed-size stacks).

Queue
Queue – A FIFO (First In, First Out) data structure where elements are added to back (or rear)
and removed from the front.

Operation Description Time Complexity

enqueue() Add element to the rear (back) O(1) ✅
dequeue() Remove element from the front O(1) ✅
peek() View the front element O(1) ✅
isEmpty() Check if the queue is empty O(1)
isFull() Check if queue is full (array-based) O(1)

Postfix and infix

Recursion
Recursion is a programming technique where a function calls itself to solve smaller instances of
the same problem. Its used in factorial, Hanoi tower, Fibonacci, Merge sort.
How do we solve recursive problem ?

Separate the problem into:

• A base case which you know to be true

• A recursive step, which represents the answer to a larger problem in terms of a smaller
one

When to Use Recursion:

Use recursion when:

• The problem is naturally recursive (e.g., trees, graphs, backtracking)

• You need cleaner, simpler code
• The input size is small or bounded

Avoid recursion when:

• You need maximum performance

• The input size is very large
• An iterative solution is faster and simpler
What are the downsides of Recursion?
Often slower because of:

• Function call overhead

• Redundant recursive calls (like in Fibonacci)

Uses more memory:

• Each recursive call stores data from previous calls.

What is a Tree ?

A tree is a non-linear, hierarchical data structure that consists of nodes connected by edges.
It’s used to represent relationships where data is organized in levels, like a family tree or file
system.

Unlike graphs, trees do not contain cycles.

What is a binary tree?

A Binary Tree is a type of tree data structure where each node has at most two children:

• Left child
• Right child

Key terms

• Path: Sequence of nodes connected by edges.

• Root: The node at the top of the tree. Only one.
• Parent: The node above.
• Child: The node below.
• Leaf: A node at the bottom with no children.
• Subtree: some parts of the tree.
• Traverse: iterating through the tree nodes.
• Levels: Number of generations a node is from the root.

Binary Search Tree

A Binary Search Tree (BST) is a special type of binary tree where:

• The left child is always smaller than its parent.

• The right child is always larger than its parent.
• All nodes in the right subtree are bigger than all nodes in the left subtree.
What is the difference between BST and Ordered Array?
Search time:

• Ordered Array: O(log n)

• Binary Search Tree: O(l), where l is the level of the tree.
o For balanced BST, l = log n
o For unbalanced BST, l can be up to n
Insertion and Deletion:

• BST: O(l)
• Ordered Array: O(n)
Space Complexity:

• Both use O(n)

• BST is dynamic (can grow/shrink), Ordered Array is fixed-size.
What are the types of Tree Traversal?
Inorder (most common):

• Visit nodes in this order: left -> root -> right.

• Produces sorted elements in ascending order.
Preorder:

• Visit nodes in this order: root -> left -> right.

Postorder:

• Visit nodes in this order: left -> right -> root.

What is RED BLACK TREE
Red Black Trees are a type of balanced binary search tree that use a set of rules to maintain
balance, ensuring logarithmic time complexity for operations like insertion, deletion, and
searching, regardless of the initial shape of the tree.
Red Black Trees are self-balancing, using a simple color-coding scheme to adjust the tree after
each modification.
The four rules of RBT
What are the Four Rules of a Red-Black Tree?

1. All nodes are either red or black.

2. The root must be black.
3. A red node can only have black children.
4. All paths from a node to its leaves or null nodes must have the same
number of black nodes.

What is Rotation in Red-Black Tree?

Rotation involves three nodes: a parent and its two children.
• Right rotation: The node’s left child becomes its parent.
• Left rotation: The opposite of right rotation.
What are Rotations in Trees?
Rotations raise some nodes and lower others to help balance the tree.
They ensure the rules of a Binary Search Tree are not broken:
• All nodes to the left must still be smaller.
• All nodes to the right must still be larger.

When is an Unbalanced Binary Search Tree better?

• If your data is fairly random.

• For insertion and deletion, it can be faster.
• It does not need extra space for storing colors (important if memory is
• limited).
When is a Red-Black Tree better?

• If your data is fairly sorted.

• It keeps the tree balanced for better performance.

Hash Table
Definition:
A Hash Table is a key-value data structure that uses a hash function applied to the key for fast
search and insertion.

Important Terms

• Hashing / Hash function:

Converts keys into array indices for O(1) access.
Example: Using modulo of the key with the array size.
• Collision:
Occurs when multiple keys map to the same index.
• Probe / Probing:
Process to find the next available position in the hash table after a collision.
Collision Handling Methods

• Open Addressing:
Move the collided element to the next available spot.
o Linear Probing: Move 1 position at a time (may cause clustering).
o Quadratic Probing: Move positions by a quadratic function.
o Double Hashing (best): Use two hash functions—one for the key, one for
probing.
• Separate Chaining:
Each index points to a linked list storing all collided elements.

Heap
Definition:
A heap is a complete binary tree where each row is fully filled from left to right except possibly
the last row.

Key Points

• Used to implement a priority queue.

• Types:
o Min-Heap: Smallest value at the root.
o Max-Heap: Largest value at the root.
• Different from a Binary Search Tree (BST); heaps are loosely ordered.

Supported Operations

• Deletion of the maximum element (max-heap).

• Insertion of a new element.

Implementation

• Using a tree structure (tree heap).

• Using an array.

Graphs
Definition:
A graph represents relationships between entities.

Components

• Vertices (nodes): Represent entities.

 • Edges: Represent relationships between entities.

Concepts

• Adjacency: Two vertices are adjacent (neighbors) if connected by an edge.

• Path: A sequence of vertices connected by edges.
• Connected Graph: A graph where every pair of vertices has at least one path connecting
them.
• Directed Graph: Edges have directions (shown by arrows).

Graph Search Algorithms

• Depth First Search (DFS): USE STACK

Explore as far down one path as possible before backtracking (goes deep).

Algorithms
ALGORITHM DFS(Graph, startVertex)
Create a Stack and push startVertex onto it
Mark startVertex as visited

WHILE Stack is not empty DO

current = Stack.peek()
IF current has an unvisited neighbor THEN
pick one unvisited neighbor
mark neighbor as visited
push neighbor onto Stack
ELSE
pop current from Stack
END WHILE
END ALGORITHM

• Breadth First Search (BFS): queue.

Visit all nodes at the current level before moving to the next level (goes wide).

BFS Algorithm Step-by-Step

1. Start at the source vertex (e.g., A)
2. Mark it as visited
3. Add it to the queue
4. Repeat while the queue is not empty:
o Remove a vertex from the front of the queue (current)
o For every unvisited neighbor of current:
§ Mark it as visited
§ Add it to the queue

BFS Psuedocode

ALGORITHM bfs(Graph graph, Vertex start)

Create a queue Q
Create a visited[] array, initialize to false

Mark start as visited

Enqueue start into Q

WHILE Q is not empty DO

Vertex current = Q.dequeue()
PRINT current

FOR each neighbor in graph.getNeighbors(current) DO

IF neighbor is not visited THEN
Mark neighbor as visited
Enqueue neighbor into Q
END IF
END FOR
END WHILE
END ALGORITHM

Time complexity: O(|V| + |E|)

Minimum Spanning Tree

What is Minimum Spanning Tree (MST)?

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, undirected,

weighted graph that:
 1. Connects all the vertices together (i.e., forms a spanning tree).
2. Has no cycles.
3. Has the minimum possible total edge weight.

MST Algorithms:

Prim’s algorithm

• For a weighted graph, undirected graph

• Uses min-heaps
• Builds the MST by expanding from an initial vertex, adding the minimum-weight edge
connected to the MST at each step.

Pseudocode:

PrimMST(Graph G):
Create a priority queue Q
Create a set MST (for storing MST edges)
Pick a starting vertex s
For each vertex v in G:
key[v] = ∞
parent[v] = NULL
key[s] = 0
Insert all vertices into Q with their key values

while Q is not empty:

u = Extract-Min(Q)
for each neighbor v of u:
if v is in Q and weight(u, v) < key[v]:
key[v] = weight(u, v)
parent[v] = u

return parent[] // represents the MST

Kruskal’s algorithm

• For a weighted, undirected graph

• Greedy algorithm
• Sorts all edges first, then builds the MST by choosing the smallest available edge that
doesn’t create a cycle.

KruskalMST(Graph G):
MST = empty set
Sort all edges in G by increasing weight
For each vertex v in G:
Make-Set(v)

for each edge (u, v) in sorted edges:

if Find-Set(u) ≠ Find-Set(v):
Add edge (u, v) to MST
Union(u, v)
 return MST

Explain: To create a Minimum Spanning Tree (MST), I used Kruskal’s Algorithm. This
algorithm works by:

1. Sorting all edges by ascending weight.

2. Adding the smallest edge that doesn't form a cycle.
3. Repeating until all nodes are connected.

Topological Sort

Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that
for every directed edge u → v, vertex u comes before v in the ordering.

Key Conditions:

• ❗ Only works on DAGs (Directed Acyclic Graphs)

• ❌ If there's a cycle, topological sort is impossible

Real-Life Example:

Course prerequisites:

• You must take Course A before Course B → A → B

• A valid topological order would be: A, B

Algorithm Steps:

1. Find a vertex that has no successors (DFS)

o This means: the vertex has no outgoing edges.
o In a dependency graph, this vertex doesn't depend on anything else anymore.
o So, it can safely be placed last in the topological order.
2. Delete this vertex from the graph
o Remove the vertex and all incoming edges to it.
o This makes other vertices potentially become "no successor" nodes.
3. Insert its label at the beginning of a list
o Because it's a leaf (no outgoing edges), it comes last in the logical order.
o By putting it at the front of the list, we’re building the list backwards.
4. Repeat until every vertex is gone
o Each time, remove a vertex with no outgoing edges and put it at the beginning.
o Eventually, the list becomes a valid topological sort.
Pseudocode:

TOPOLOGICAL_SORT(Graph G):
L = empty list // This will store the final topological order
while G has vertices:
found = false
for each vertex v in G:
if v has no outgoing edges (no successors):
found = true
remove v from G
insert v at the beginning of list L
break
if not found:
print "Graph has a cycle. Topological sort not possible."
return None
return L

Dijkstra’s Algorithm for finding Shortest Paths

Dijkstra’s Algorithm is used to find the shortest path from a single source vertex to all other
vertices in a weighted graph with non-negative edge weights.

How It Works (Conceptually):

1. Start from the source node and assign distance 0 to it.

2. Assign infinity (∞) to all other nodes.
3. Visit the closest unvisited node, and:
o Update distances of its neighbors if a shorter path is found.
4. Mark this node as visited (we found the shortest path to it).
5. Repeat until all nodes have been visited.

Pseudocode:

DIJKSTRA(Graph G, Vertex source):

// Step 1: Initialize
for each vertex v in G:
distance[v] = ∞ // Unknown distance from source to v
previous[v] = null // No known path yet
distance[source] = 0 // Distance to source is 0

// Step 2: Create a priority queue Q (or use a simple set if no heap)

Q = set of all vertices in G

// Step 3: Process the graph

while Q is not empty:
u = vertex in Q with smallest distance[u]
remove u from Q

for each neighbor v of u:

alt = distance[u] + weight(u,v)//Tentative distance through u
if alt < distance[v]: // Found a shorter path
 distance[v] = alt
previous[v] = u

return distance[], previous[]

Weighted Graphs
Definition:
A graph where edges have weights indicating strength, cost, or distance of the connection.

Characteristics

• Can be directed or undirected.

• For undirected graphs, the adjacency matrix is symmetric (weights are duplicated).
• Adjacency Matrix:
Stores weights instead of 1 or 0; uses INF (infinity) to indicate no connection between
nodes.