Classification of Data Structures

A data structure is a method of organizing and storing data in a

computer so that it can be accessed and processed efficiently. Data
structures are classified based on the way data is organized and stored.
Data structures are mainly classified into:
1. Primitive Data Structures
2. Non-Primitive Data Structures

Primitive Data Structures

Primitive data structures are the basic built-in data types provided by
programming languages.

Non-Primitive Data Structures

Non-primitive data structures are derived from primitive data

structures. They can store multiple values and relationships among
data.

Performance Analysis of an Algorithm

Performance analysis means evaluating how efficiently an algorithm
works.
It mainly depends on:
1. Time Complexity
2. Space Complexity
Time Complexity
 Time complexity is the amount of time an algorithm takes to execute as
the input size increases.
How fast the algorithm works
Why is Time Complexity Important?
• Helps compare algorithms
• Identifies faster algorithms
• Useful for large data processing
Eg : for(i = 0; i < n; i++) If element is at the end, loop runs n times.
Space Complexity
Space complexity is the amount of memory required by an algorithm
during execution. How much memory the algorithm uses
It includes:
• Variables
• Arrays
• Dynamic memory
Why is Space Complexity Important?
• Helps manage memory efficiently
• Important in large applications
• Reduces memory wastage
Eg : int A[100]; Array requires memory for 100 integers. So memory
usage increases with input size.
Types of Space Used
1. Fixed Space
2. Variable Space

Algorithm
An algorithm is a step-by-step procedure used to solve a problem or
perform a task in a finite amount of time. It consists of a sequence of
well-defined instructions.
 Example

Algorithm to add two numbers:

1. Start
2. Read two numbers
3. Add the numbers
4. Display the result
5. Stop

Characteristics of a Good Algorithm

1. Input

An algorithm should accept zero or more inputs.

2. Output

An algorithm should produce at least one output.

3. Definiteness

Each step should be clear and unambiguous.

5. Effectiveness

Each step should be simple and executable in a practical amount of

time.

6. Correctness

The algorithm should produce accurate results for all valid inputs.

Abstract Data Type (ADT)

An Abstract Data Type (ADT) is a logical model of a data structure that
defines:

• What operations can be performed

• How data is organized

ADT specifies what to do, not how to do it.

Example: Stack ADT

 Top

30

20

10

The implementation details are hidden from the user.

An ADT mainly consists of:

1. Data : The values stored in the structure.
2. Operations : Functions that can be performed on the data.

Linear queue and circular queue.

LINEAR CIRCULAR

A queue in which insertion A queue in which the last

and deletion occur in a position is connected to the
linear manner first position
Linear structure Circular structure
Poor memory utilization, Poor memory utilization,
Wastage of Space No Wastage of Space

Explain how circular queues overcome the limitation of

linear queues.
A linear queue follows the FIFO (First In First Out) principle where:
• Insertion is done at the rear
• Deletion is done at the front
In a linear queue, once the rear reaches the last position of the array,
no more insertions are possible even if there are empty spaces at the
front. This leads to:Memory wastage
 A circular queue connects the last position of the queue back to the first
position. The queue behaves like a circle. When rear reaches the last
position and free space exists at the beginning, rear moves back to the
front position. Thus, empty spaces are reused efficiently.

What is the difference between static and dynamic data

structures?
STATIC DYNAMIC
Size is fixed before Size can change during
execution execution
Memory allocated at Memory allocated at run
compile time time
Size cannot be modified Size can be increased or
decreased
Simple to implement More complex
Eg : Array Eg : Linked List, Tree, Graph

Explain the divide-and-conquer strategy using Merge

Sort as an illustration.
Divide-and-Conquer is a problem-solving strategy in which a problem
is divided into smaller subproblems, solved independently, and then
combined to get the final solution.
It mainly involves three steps:
1. Divide
2. Conquer
3. Combine

Merge Sort is a sorting algorithm based on the Divide-and-Conquer

technique. It divides the array into two halves repeatedly until single
elements remain, then merges them in sorted order. ( Write an example
for merge sort).

Binary Search
 Binary search is a searching technique used to find an element in a
sorted array by repeatedly dividing the search interval into two halves.
Instead of checking each element one by one, binary search compares
the target element with the middle element of the array. Binary search
can be applied only if the array is sorted.

Linked List
A singly linked list is a linear data structure made up of a collection of
nodes, where each node contains:
1. Data
2. Address (pointer) of the next node
Each node is connected to the next node in a sequential manner. Last
node points to NULL indicating the end of the list.

Characteristics of Singly Linked List

• Sequential Access
• Efficient Insertion and Deletion
Node in a Linked List
A node is the basic building block of a linked list.
Each node contains:
1. Data field
2. Link field (pointer)
The link field stores the address of the next node.

Polynomial Representation using Linked List

 A polynomial can be represented using a linked list where each node
stores:
1. Coefficient
2. Exponent
3. Address of next node

Polynomial Addition
To add two polynomials:
• Compare exponents of both polynomials
• If exponents are same:
▪ Add coefficients
• Otherwise:
▪ Copy the term with larger exponent
Example :
Polynomial 1 : 5x³ + 4x² + 2x
Polynomial 2 : 3x³ + 6x + 1
Final Polynomial : 8x³ + 4x² + 8x + 1
Algorithm :
PolyAdd(P1, P2)
1. Create a new list P3
2. While P1 != NULL and P2 != NULL
3. If [Link] == [Link]
Add coefficients
Insert result into P3
Move P1 and P2 forward
4. Else if [Link] > [Link]
Copy P1 node into P3
Move P1 forward
5. Else
Copy P2 node into P3
Move P2 forward
6. Copy remaining nodes of P1 if any
7. Copy remaining nodes of P2 if any
8. Return P3
 Difference Between Singly Linked List, Doubly Linked
List, and Circular Linked List
Singly Linked List Doubly Linked List Circular Linked List
Each node contains Each node contains Last node links back to first
data and one link to data, previous link, node
next node and next link
One link Two links One or two links arranged
circularly
Only forward traversal Forward and Circular traversal possible
backward traversal
Last Node Points to Last Node Next Last node points to first
NULL pointer points to node
NULL

Binary Tree and Binary Search Tree (BST)

BINARY TREE BINARY SEARCH TREE
A tree in which each node A binary tree that follows a
has at most two children specific ordering property
No specific order Left subtree < Root < Right
subtree
Nodes can be arranged in Nodes are arranged in
any order sorted manner
Searching Speed slower Searching Speed faster

Degree of a Node
The degree of a node is the number of children that the node has.
Leaf Nodes
Leaf nodes are nodes that do not have any children.
Internal Nodes
 Internal nodes are nodes that have at least one child. They are non-leaf
nodes.

Difference Between Adjacency Matrix and Adjacency

List
Adjacency Matrix Adjacency List

Graph represented using a Graph represented using

2D matrix linked lists
Uses rows and columns Uses list of connected
vertices
Requires more memory Requires less memory
Implementation simple Implementation slightly
complex

Traversing a binary tree

The standard approaches for traversing a binary tree are:
1. Inorder Traversal
2. Preorder Traversal
3. Postorder Traversal
Inorder Traversal (LNR)
Left → Root → Right
Steps
1. Traverse left subtree
2. Visit root
3. Traverse right subtree
Preorder Traversal (NLR)
Root → Left → Right
 Steps
1. Visit root
2. Traverse left subtree
3. Traverse right subtree
Postorder Traversal (LRN)
Left → Right → Root
Steps
1. Traverse left subtree
2. Traverse right subtree
3. Visit root

Binary Tree and Its Classifications

A binary tree is a hierarchical data structure in which each node can
have at most two children.
These children are called:
• Left child
• Right child
Classifications of Binary Trees
• Binary trees are classified into:
• Full Binary Tree
• Complete Binary Tree
• Skewed Binary Tree
1. Full Binary Tree
A full binary tree is a binary tree in which every node has either:
• 0 children, or 2 children
 No node has only one child.
2. Complete Binary Tree
A complete binary tree is a binary tree in which:
• All levels are completely filled except possibly the last level
• Last level nodes are filled from left to right
[Link] Binary Tree
A skewed binary tree is a binary tree in which every node has only one
child.
It behaves like a linked list.

Hashing and collision

Hashing is a technique used to store and retrieve data quickly using a
hash function. A hash function converts a key into an index or address
in a hash table.
Collision occurs when two or more keys produce the same hash index.
Why Collision Resolution is Required
When collision occurs:
• Multiple elements try to occupy the same location
• Data may be overwritten
• Searching becomes incorrect
Therefore, collision resolution techniques are required to store all
elements properly and ensure efficient searching.
To handle collisions, two important techniques are used:
1. Open Hashing
2. Closed Hashing
Open hashing is a collision resolution technique in which multiple
elements that hash to the same index are stored using a linked list.
Closed hashing is a collision resolution technique in which all elements
are stored inside the hash table itself. If collision occurs, another empty
location is searched.

Linear Search and Binary Search Algorithms with Time

Complexity Analysis
Linear Search
Linear search is a searching technique in which each element of the
list is checked one by one until the required element is found. It is also
known as sequential search.
LinearSearch(A, n, key)
1. Start
2. Repeat for i = 0 to n-1
If A[i] == key
Print "Element Found"
Stop
3. Print "Element Not Found"
4. Stop

Binary Search
 Binary search is a searching technique that repeatedly divides the
search space into two halves. It works only on sorted array.
BinarySearch(A, low, high, key)
1. While low <= high
2. Find mid = (low + high)/2
3. If A[mid] == key
Print "Element Found"
4. Else if key < A[mid]
high = mid - 1
5. Else
low = mid + 1
6. If not found
Print "Element Not Found"

Best-case, worst-case, and average-case time

complexities
Time complexity measures the amount of time required by an algorithm
to execute for a given input size.
The performance of an algorithm is analyzed in three cases:
1. Best Case
2. Worst Case
3. Average Case
• Best-case time complexity is the minimum time required by an
algorithm to execute.
• Worst-case time complexity is the maximum time required by an
algorithm to execute.
• Average-case time complexity is the average time taken by an
algorithm for all possible inputs.
• Example : Linear Search

Queue and Different Types of Queues

A queue is a linear data structure that follows the principle: FIFO (First
In First Out)
Types of Queues
There are mainly four types of queues:
1. Linear Queue
2. Circular Queue
3. Double Ended Queue (Deque)

1. Linear Queue
A linear queue is a queue in which insertion takes place at the rear and
deletion takes place at the front in a linear manner
Front → 10 20 30 40 ← Rear

Operations :
• Enqueue → Insert element
• Dequeue → Delete element
[Link] Queue
 A circular queue is a queue in which the last position is connected back
to the first position. The queue behaves like a circle.
Front
↓
10 20 30 40
↑ ↓
└───────┘
Rear
[Link] Ended Queue (Deque)
A deque is a queue in which insertion and deletion can be performed at
both ends.
Front ⇄ 10 20 30 40 ⇄ Rear
Operations
• InsertFront()
• InsertRear()
• DeleteFront()
• DeleteRear()

Bubble Sort
Bubble sort is a simple sorting algorithm that repeatedly compares
adjacent elements and swaps them if they are in the wrong order. The
largest element “bubbles up” to the correct position after each pass.
Working Principle
1. Compare adjacent elements
2. Swap if left element is greater than right element
3. Continue until the array becomes sorted
BubbleSort(A, n)
1. Repeat for i = 0 to n-1
 2. Repeat for j = 0 to n-i-1
3. If A[j] > A[j+1]
Swap A[j] and A[j+1]
4. Stop
( Write example for bubble sort )

Breadth-First Search
Breadth-First Search is a graph traversal technique that visits vertices
level by level. It first visits all neighboring vertices before moving to the
next level. It uses queue.
Working of BFS
1. Start from a source vertex
2. Visit the source vertex
3. Add neighboring vertices to the queue
4. Remove a vertex from queue and visit its neighbors
5. Continue until all vertices are visited
A
/ \
B C
/\
D E
BFS Traversal : A → B → C → D → E

Depth-First Search (DFS)

Depth-First Search is a graph traversal technique that explores a path
completely before backtracking. It uses Stack.
 Working of DFS
1. Start from source vertex
2. Visit the vertex
3. Move to an unvisited adjacent vertex
4. Continue deeply until no vertex remains
5. Backtrack and continue traversal
A
/ \
B C
/\
D E
DFS Traversal : A → B → D → E → C

Explain the process of removing a particular node from

a linked list and outline the corresponding algorithm.
Deletion in a linked list means removing a node from the list and
adjusting the links properly.
In a singly linked list, deletion can occur:
• At the beginning
• At the end
• At a particular position or specific node
Steps for Deleting a Particular Node
1. Locate the node to be deleted
2. Find the previous node
3. Change the link of previous node
4. Free the deleted node memory

Quick Sort
Quick Sort is a divide-and-conquer sorting algorithm that works by:
1. Selecting a pivot element
2. Partitioning the array into two parts
o Elements smaller than pivot
o Elements greater than pivot
3. Recursively sorting the subarrays
It is one of the fastest sorting algorithms.
Working Principle of Quick Sort
1. Choose a pivot element
2. Rearrange elements around the pivot
3. Place pivot in correct sorted position
4. Apply the same process to left and right subarrays
(Write example for quick sort)

Define asymptotic notations. Explain Big-O, Big-Ω and

Big-Θ with examples.
Asymptotic notations are mathematical tools used to describe the
performance and efficiency of algorithms as the input size becomes
very large.
They help in:
• Measuring time complexity
• Comparing algorithms
• Predicting algorithm growth rate
 Asymptotic notations mainly describe:
• Best-case performance
• Worst-case performance
• Average-case performance
The three important asymptotic notations are:
1. Big-O Notation (O)
2. Big-Omega Notation (Ω)
3. Big-Theta Notation (Θ)
1. Big-O Notation : Big-O notation represents the upper bound or worst-
case complexity of an algorithm. It describes the maximum time an
algorithm can take.
2. Big-Omega Notation : Big-Omega notation represents the lower bound
or best-case complexity of an algorithm. It describes the minimum time
required.
3. Big-Theta Notation : Big-Theta notation represents the tight bound of
an algorithm. It gives both: Upper bound and Lower bound