ASHA COACHING

ASHA COACHING CENTRE

Subject – COMPUTER APPLICATION & COMS
Chapter – DATA STRUCTURE
CLASS – XI
SEMESTER - II
Topic – Data Structure Introduction
Teacher – Aniruddha Sir
DATA STRUCTURE
DATA STRUCTURE
Definition: A Data Structure is a special method or arrangement for organizing, processing, and storing
data or information in a well-structured manner in a computer's memory. It is a logical or mathematical
model through which data is arranged so that it is easy to use, access, and manipulate effectively.

Simply put, a Data Structure is a technique for storing and arranging data.
Types of Data Structure
Data Structures are mainly of two types:
1. Linear Data Structure:
•Definition: This is a Data Structure where data elements are arranged in
a sequential or consecutive manner and each element is connected to its
immediate previous and next element.
•The data elements exist at a single level in this structure.
•It's possible to traverse all elements in a single run.

•Examples: Array, Stack, Queue, Linked List

2. Non-Linear Data Structure:

•Definition: This is a Data Structure where data elements are not
arranged sequentially or consecutively. Instead, the data is connected in
multiple levels or a hierarchical manner.
•In this structure, multiple elements can be connected to a single
element.
•This type of data structure cannot be traversed completely in a single
pass.

•Examples: Tree, Graph

Advantages of Data Structure
The main advantages of using a Data Structure are:
•Efficiency: Choosing the right Data Structure allows a program to
process data faster and using less memory. This is especially
important when dealing with a huge dataset.

•Reusability: Various data structures can be defined as common code

components, which can be easily reused in other programs or
modules. This reduces development time and effort.

•Improved Performance: An appropriate Data Structure can

significantly improve the performance of algorithms. When data is
well-organized, operations like searching , insertion , and deletion
become faster.

•Scalability: The correct Data Structure helps applications manage

larger and more complex data more easily, making the application
extensible.

•Simplicity of Code: Data Structures organize data in a logical way,

making the code easier to understand and debug.
Array
An Array is a fundamental concept in Data Structures, which stores data items of the same type
sequentially (contiguous memory locations) in memory.
•It is a Linear Data Structure.
•Data in an Array can be accessed quickly using an index (or subscript), where the index usually
starts from 0 (zero).
•Arrays are mainly of three types:
•One-Dimensional (1D)
•Two-Dimensional (2D)
Characteristics of Array
The main characteristics of an Array are:
•Collection of Homogeneous Elements: An Array can only store multiple elements of the
same data type (e.g., only integers or only characters).

•Fixed Size: The size of an Array must be specified when it is created. Once the size is
determined, it usually cannot be changed at run-time.

•Contiguous Memory Locations: All elements of an Array are stored in sequential or

adjacent (contiguous) memory locations. This is the main reason for the fast access of
Arrays.

•Indexing: Every element of an Array is accessed by its positional index. In most

programming languages, the index starts from 0 (zero).

•Linear Data Structure: An Array is a linear data structure where elements are arranged in
a sequential order.
Advantages of Array
The main advantages of using an Array in a Data Structure are:
•Fast Access: Since elements are stored sequentially in memory and their index is known, any
element can be accessed directly.

•Easy Implementation: Array is a simple Data Structure, which is comparatively easy to

understand and implement in programming.

•Efficient Memory Utilization: Data in an Array is stored in contiguous memory blocks and
does not require additional pointers or references like a Linked List, thus allowing for efficient
memory utilization.

•Foundation for Other Data Structures: Arrays are used as the foundation for implementing
many complex data structures like Stack, Queue, Hash Table, etc..

•Matrix Representation: Mathematical Matrices can be easily represented and processed

using a Two-Dimensional Array.
1. One-Dimensional Array (1D Array)
•A One-Dimensional Array is a simple or single list of data.
•Data in this Array is arranged in a single row or line, and only one index is required to
access each data item.
•Definition: An Array whose elements are accessed using a single subscript or index is
called a One-Dimensional Array.
•Example: Suppose you want to store the marks obtained by 5 students.
•Syntax in C: int student_marks[5];
•Value Storage:
•First student's mark: student_marks[0] = 85;
•Second student's mark: student_marks[2] = 92;

2. Two-Dimensional Array (2D Array)

•A Two-Dimensional Array is an Array where data is stored in the form of Rows and Columns.
•It creates a structure like a Matrix or a Table.
•Definition: An Array whose elements are accessed using two subscripts or indices (one for the
row and one for the column) is called a Two-Dimensional Array.
•Example: Suppose you want to store the marks of 2 subjects for 3 students. This is a 3x2 Matrix.
•Syntax in C: int marks [3] [2]; (3 rows, 2 columns)
•Value Storage:
•First student's first subject mark: marks[0][0] = 75, 80;
•Second student's second subject mark: marks [1] [1] = 88, 83;
Linked List
The Linked List is a Dynamic Data Structure. Its main advantage is that its size can be increased
or decreased as needed at run-time, and adding or removing data (Insertion and Deletion) in the
middle is much easier compared to an Array.

Node: Each element of a Linked List is called a Node. Each Node is divided into two main parts:
[Link]: This is the actual information or value you want to store.
[Link]/Link (Next): This holds the memory address of the next node. Nodes are connected to
each other through this pointer. The Pointer of the last node contains a NULL value, which
indicates the end of the list.

Head and Tail:

•Head: The address of the first node in the list is stored in a special pointer (usually known as
'Head'). The entire list cannot be accessed without this Head.
•Tail: The last node of the list.
Linked Lists are mainly of three types:

1. Singly Linked List

•Structure: This is the most common type. Each node has a Data part and a Pointer for the next (Next)
node.
•Traversal: In this list, traversal can only be done Forward (one-way). You can go from one node to the
next, but cannot easily go back to the previous node.
•End: The Pointer of the last node contains a NULL value, which indicates the end of the list.
2. Doubly Linked List
•Structure: Each node in this list has three parts: Data, a Pointer for the next (Next) node, and a
Pointer for the previous (Previous/Prev) node.
•Traversal: Due to the presence of both Next and Prev pointers, this list can be traversed Forward
and Backward (two-way).
•Start/End: The Prev pointer of the first node and the Next pointer of the last node have a NULL
value.
3. Circular Linked List
•Concept: This can be either Singly or Doubly. The specialty of this list is that the Pointer of the
last node does not contain NULL, but points back to the first node (Head).
•Traversal: The list creates a Circular structure, so there is no start or end. Unless you track the
starting node, you can traverse infinitely.
•Usage: It is used in various algorithms, including Round-Robin Scheduling.
 Feature Array Linked List
Data exists in separate Nodes and is stored
Data elements are stored in contiguous
Storage Method in non-contiguous memory locations.
(sequential/adjacent) memory locations.
Nodes are connected using pointers.
Typically Fixed. The size must be
Dynamic. The size can be easily increased
Size specified at Compile-Time and generally
or decreased at Run-time as needed.
cannot be changed later.
Random Access [O(1) time]. Any element Sequential Access [O(n) time]. Elements
Element Access can be accessed directly using its index must be traversed one by one starting from
(subscript). the head node.
Relatively slow [O(n)]. Inserting or Relatively fast [O(1) in the best case, O(n)
Insertion/Deletion deleting an element requires shifting the for search]. Only requires changing the
remaining elements in memory. pointer addresses, no shifting is needed.
More memory is used as each node
Less memory is used as no extra space is requires additional space to store the
Memory Usage
required to store pointers for each element. memory address (pointer) of the next
node.
Usually allocated statically on the stack or
Allocated dynamically on the heap
Memory Allocation in the data segment (unless it's a dynamic
memory at run-time.
array).
Cache-friendly due to contiguous memory Not cache-friendly due to scattered
Cache Friendliness
storage, leading to better performance. memory locations.
A Stack is a fundamental Linear Data Structure that follows a specific order or principle for operations: LIFO (Last-
In, First-Out).
Imagine a stack of plates: you can only add a new plate to the top, and you can only remove a plate from the top. The last
plate you put on is the first one you take off.

Key Characteristics
•LIFO (Last-In, First-Out): The element that was added most recently is the element that will be removed first.
•Single End Access: All insertions and deletions are done from only one end, called the Top.
•Linear Data Structure: Elements are arranged in a sequential manner.

Operations on a Stack
A stack primarily supports two main operations:
[Link] (Insertion):
1. Adds an element to the top of the stack.
2. If the stack is already full, it results in a condition called Stack Overflow.
[Link] (Deletion):
1. Removes the element from the top of the stack.
2. If the stack is already empty, it results in a condition called Stack Underflow.
Auxiliary Operations
•Peek/Top: Returns the top element of the stack without removing it.
•isEmpty: Checks if the stack is empty.
•isFull: Checks if the stack is full (especially when implemented using an Array).
Applications
Stacks are widely used in computer science for:
•Function Calls/Recursion: The Call Stack manages function calls by storing return addresses and
local variables (LIFO is essential here).
•Expression Evaluation: Used to convert and evaluate arithmetic expressions (Infix to Postfix/Prefix,
and Postfix evaluation).
•Backtracking: Used in algorithms like depth-first search (DFS) to remember the path to return to.
•Browser History: The "Back" button functionality is typically implemented using a stack.

A Queue is a fundamental Linear Data Structure that follows a specific order for operations: FIFO (First-In,
First-Out).
It operates much like a real-world queue or waiting line, such as people waiting to buy tickets or cars waiting at a
traffic light. The element that gets added first is the one that is served and removed first.

Key Characteristics
•FIFO (First-In, First-Out): The element that was added earliest is the element that will be removed first.
•Dual-End Access: Operations occur at two different ends:
• Front (or Head): Where elements are deleted (dequeue).
• Rear (or Tail): Where elements are inserted (enqueue).
•Linear Data Structure: Elements are arranged in a sequential manner.
Operations on a Queue
A queue primarily supports two main operations:
[Link] (Insertion):
1. Adds a new element to the Rear end of the queue.
2. If the queue is full, it results in a Queue Overflow.
[Link] (Deletion):
1. Removes the element from the Front end of the queue.
2. If the queue is empty, it results in a Queue Underflow.
Auxiliary Operations
•Peek/Front: Returns the element at the Front of the queue without removing it.
•Rear: Returns the element at the Rear of the queue without removing it.
•isEmpty: Checks if the queue contains any elements.
•isFull: Checks if the queue has reached its maximum capacity (when array-implemented).

Applications
Queues are essential in operating systems and networking for managing processes and data flow:
•Operating Systems: Managing processes for the CPU (Job Scheduling), handling I/O operations
(print queues), and buffering data.
•Networking: Handling data packets in routers and switches.
•Simulation: Modeling real-world scenarios, like waiting times at a counter.
•Breadth-First Search (BFS): A graph traversal algorithm uses a queue to explore nodes level by
level.
 Feature Stack Queue
Principle LIFO (Last-In, First-Out) FIFO (First-In, First-Out)
The last element added is the The first element added is the
Definition
first one to be removed. first one to be removed.
Operation Name for
Push (Insertion) Enqueue (Insertion)
Insertion
Operation Name for
Pop (Deletion) Dequeue (Deletion)
Deletion
Access occurs at two ends: Rear
Access occurs at only one end,
Access Ends (for insertion) and Front (for
called the Top.
deletion).
Elements are added at the Rear
Insertion Location Elements are added at the Top.
(or Tail).
Elements are removed from the Elements are removed from the
Deletion Location
Top. Front (or Head).
A stack of plates or an 'Undo' A waiting line of people or a
Analogy
history. print queue.
Job scheduling in Operating
Function call management (Call
Common Systems (CPU scheduling), and
Stack), expression evaluation,
Application the Breadth-First Search (BFS)
and backtracking algorithms.
algorithm.
1. Simple Queue (or Linear Queue)
•Structure: Elements are inserted at the rear and deleted from the front.
•Order: FIFO (First In, First Out)
•Limitation: When elements are deleted, the freed space at the front can’t be reused
easily.
Example:
Front → [10, 20, 30, 40] ← Rear
After deleting 10 → [20, 30, 40], but front moves forward — not reusable in a static
array.
Use case: Simple task scheduling where reusability of space is not a concern.

2. Circular Queue
•Improvement over Linear Queue
•The last position is connected to the first to form a circle.
•Advantage: Avoids wasted space — can reuse freed positions.
Example:
[10, 20, 30, 40]
Front = 0 → 10
Rear = 3 → 40
If we dequeue 10 and enqueue 50, 50 goes to position 0 (circularly)
Use case: Circular resource management (e.g., CPU scheduling).
3. Double-Ended Queue (Deque)
•Elements can be inserted or removed from both ends.
•Types:
• Input-restricted deque: Insertion allowed only at one end.
• Output-restricted deque: Deletion allowed only at one end.
Example:
Front ⇄ [10, 20, 30, 40] ⇄ Rear
Use case: Implementing both stacks and queues; useful in algorithms like palindrome checking or
sliding window problems.

4. Priority Queue
•Each element is assigned a priority.
•Elements with higher priority are served first, regardless of insertion order.
•Can be implemented using a heap, array, or linked list.
Example:
[ (A, 2), (B, 1), (C, 3) ]
→ Dequeue order: C (3), A (2), B (1)
Use case: Operating systems (process scheduling), Dijkstra’s algorithm,
Huffman coding.
1. Tree Data Structure
A Tree is a hierarchical non-linear data structure that
consists of nodes connected by edges.

Term Meaning
Node Each element in the tree
Root The topmost node (starting point)
Parent A node that has child nodes
Child A node that descends from another node
Leaf A node with no children
Edge Connection between two nodes
Level Distance from the root node
Subtree A smaller tree within the main tree

➢ Structure Example
A •A → Root
/\ •B, C → Children of A
B C •D, E → Children of B
/ \ \ •F → Child of C
D E F •D, E, F → Leaf nodes
 Tree Type Description
General Tree No restriction on the number of children.
Binary Tree Each node has ≤ 2 children.
Binary Search Tree
Left < Parent < Right.
(BST)
AVL Tree Self-balancing BST.
Heap (Min/Max) Complete tree used for priority queues.
B-Tree / B+ Tree Multi-way search tree used in databases.
Trie (Prefix Tree) Used for string searching and auto-completion.

➢ Applications
•File systems (folders & subfolders)
•Hierarchical databases
•Binary search (BST)
•Expression evaluation (syntax trees)
•Huffman coding (data compression)
2. Graph Data Structure
A Graph is a non-linear data structure consisting of a set of
vertices (nodes) and edges (connections) between them.

Term Meaning
Vertex (Node) Represents an entity (like a city or person).
Edge Connection between two vertices.
Degree Number of edges incident on a vertex.
Path Sequence of vertices connected by edges.
Cycle Path that starts and ends at the same vertex.
Connected
Every vertex is reachable from another.
Graph

A --- B
| / | •Vertices: A, B, C, D
| / | •Edges: AB, AC, BC, BD, CD
C --- D
 Type Description

Undirected Graph Edges have no direction (A—B = B—A).

Directed Graph
Edges have direction (A → B).
(Digraph)
Weighted Graph Each edge has a weight (distance, cost).

Unweighted Graph All edges are equal.

Cyclic Graph Contains at least one cycle.

Acyclic Graph No cycles (e.g., tree).
DAG (Directed Directed graph with no cycles (used in
Acyclic Graph) scheduling).

➢ Applications
•Social networks (friends, followers)
•Google Maps (shortest path between cities)
•Computer networks (routing)
•Dependency resolution (e.g., build systems)
•Recommendation systems (graph-based relationships)
Recursion
Definition
Recursion is a programming technique in which a function calls itself directly or
indirectly to solve a problem.
In recursion, a problem is divided into smaller subproblems of the same type
until it reaches a simple base case, which can be solved directly.

➢ Structure of a Recursive Function

A recursive function generally has two main parts:
[Link] Case:
The condition under which the recursion stops (prevents infinite calls).
[Link] Case:
The part of the function that calls itself to solve smaller subproblems.

Example: Factorial using Recursion

int factorial(int n) {
if (n == 0) // Base case
return 1;
else
return n * factorial(n - 1); // Recursive case
}
 Advantage Explanation

Complex problems (like tree traversal,

1. Simplifies Code factorial, Fibonacci) can be expressed more
easily.
Examples Where Recursion Is Commonly Used
2. Reduces Code Recursive code is often shorter and easier to •Factorial calculation
Size read than iterative code. •Fibonacci sequence
•Tree traversals (preorder, inorder, postorder)
3. Natural Some problems (like Towers of Hanoi, •Tower of Hanoi problem
Representation directory traversal) are naturally recursive. •Searching in file directories
•Quick sort and Merge sort algorithms
4. Easier to Recursive solutions are often cleaner and
Maintain easier to debug conceptually.

Limitation Explanation
Each recursive call adds a new frame to the call
1. High Memory Usage
stack, consuming memory.
Too many recursive calls can exceed stack size and
2. Stack Overflow Risk
crash the program.
Function call overhead (saving and restoring stack
3. Slower Execution
frames) makes recursion slower than iteration.
➢ Searching Algorithms (Linear Search & Binary Search)
Searching algorithms are used to find the location (index) of a target value in a list or array.
Two of the most common searching techniques are:
[Link] Search
[Link] Search

1. Linear Search (Sequential Search)

Definition
Linear Search is the simplest searching technique.
It checks each element in the list one by one until the target
element is found.
Works on:
Unsorted arrays ➢ Example
Sorted arrays (but no advantage) Array: [4, 2, 7, 1, 9]
Search for: 1
❑ Algorithm (Step-by-Step) Steps:
[Link] from the first element of the array. •Compare 4 with 1 → not equal
[Link] the target value with each element. •Compare 2 with 1 → not equal
[Link] a match is found → return the index. •Compare 7 with 1 → not equal
[Link] the end of the array is reached → element not found. •Compare 1 with 1 → found at index 3
Pseudocode
LinearSearch(arr, n, key):
for i = 0 to n-1: Python Code (Linear Search)
if arr[i] == key:
return i def linear_search(arr, key):
return -1 for i in range(len(arr)):
if arr[i] == key:
Time Complexity
return i # return index if found
Case Complexity return -1 # return -1 if not found

Best Case O(1) (first element)

Worst Case O(n) # Example usage
Average Case O(n) arr = [4, 2, 7, 1, 9]
key = 7
➢ Advantages
•Simple to implement result = linear_search(arr, key)
•Works on unsorted lists if result != -1:
•No extra memory required print(f"Element found at index {result}")
➢ Disadvantages else:
•Slow for large data print("Element not found")
•Checks all elements → inefficient
2. Binary Search
Definition
Binary Search is an efficient search algorithm based on the
divide-and-conquer technique.
Works ONLY on sorted arrays (ascending or descending)
It repeatedly divides the array into halves to find the target.
❑ Algorithm (Step-by-Step)
[Link] low = 0, high = n-1
[Link] middle index:
mid = (low + high) / 2
➢ Example
3. Compare target with arr[mid] Sorted Array: [1, 2, 4, 7, 9, 12]
•If equal → element found Search for: 7
•If key < arr[mid] → search in left half Steps:
•If key > arr[mid] → search in right half [Link] = 0, high = 5 → mid = 2 → arr[mid] = 4
4. Continue until low > high → element not found 7 > 4 → search right half
[Link] = 3, high = 5 → mid = 4 → arr[mid] = 9
7 < 9 → search left half
[Link] = 3, high = 3 → mid = 3 → arr[mid] = 7
Found at index 3
Pseudocode Time Complexity
BinarySearch(arr, low, high, key):
while low <= high: Case Complexity
mid = (low + high) / 2 Best Case O(1)
if arr[mid] == key:
Worst Case O(log n)
return mid
else if key < arr[mid]: Average Case O(log n)
high = mid - 1
else:
low = mid + 1
return -1

Advantages
•Much faster than Linear Search
•Efficient for large datasets
•Uses divide-and-conquer

Disadvantages
•Array must be sorted
•Not suitable for frequently updated lists (sorting cost)
Python Code

def binary_search(arr, key):

low = 0
high = len(arr) - 1
# Example usage
while low <= high: arr = [1, 2, 4, 7, 9, 12]
mid = (low + high) // 2 key = 7

if arr[mid] == key: result = binary_search(arr, key)

return mid if result != -1:
elif key < arr[mid]: print(f"Element found at index {result}")
high = mid - 1 else:
else: print("Element not found")
low = mid + 1

return -1
Bubble Sort Algorithm
➢ Definition
Bubble Sort is a simple comparison-based sorting algorithm.
It works by repeatedly swapping adjacent elements if they are in the wrong order.
Because the largest element “bubbles up” to the end in each pass, the algorithm is
called Bubble Sort.

➢ How Bubble Sort Works (Step-by-Step)

Given an array of n elements:
[Link] the first two adjacent elements.
[Link] the first is greater than the second → swap them.
[Link] to the next pair (index 1 & 2) and repeat.
[Link] the first pass, the largest element is at the last position.
[Link] the passes until all elements are sorted.

Optimization (Early Stop Flag)

If in any pass no elements are swapped, it means the array is already sorted.
We can stop early to save time.
Example
Bubble Sort Algorithm (Pseudocode)
Sort this array:
Version 1: Basic Bubble Sort
[5, 1, 4, 2, 8]
Pass 1
BubbleSort(arr, n):
Compare and swap when needed:
for i = 0 to n-1:
→ [1, 4, 2, 5, 8] (8 moves to end)
for j = 0 to n-i-1:
Pass 2
if arr[j] > arr[j+1]:
→ [1, 2, 4, 5, 8]
swap(arr[j], arr[j+1])
Pass 3
→ [1, 2, 4, 5, 8] (No swap — already sorted)
Pass 4 Time & Space Complexity
→ No swaps → algorithm stops.
Case Complexity
Best Case (already sorted) O(n) (optimized version)
Worst Case O(n²)
Average Case O(n²)
Space Complexity O(1) (in-place)
➢ Bubble Sort in Python & C #include <stdio.h>

void bubbleSort(int arr[], int n) {

def bubble_sort(arr):
int i, j, temp, swapped;
n = len(arr)
for (i = 0; i < n-1; i++) {
for i in range(n - 1):
swapped = 0;
swapped = False
int main() {
for (j = 0; j < n-i-1; j++) { int arr[] = {5, 1, 4, 2, 8};
for j in range(n - i - 1):
if (arr[j] > arr[j+1]) { int n = sizeof(arr)/sizeof(arr[0]);
if arr[j] > arr[j + 1]:
temp = arr[j];
arr[j], arr[j + 1] = arr[j + 1], arr[j]
arr[j] = arr[j+1]; bubbleSort(arr, n);
swapped = True
arr[j+1] = temp;
swapped = 1; printf("Sorted array: ");
if not swapped:
} for (int i = 0; i < n; i++)
break
} printf("%d ", arr[i]);

if (swapped == 0) return 0;
arr = [5, 1, 4, 2, 8]
break; }
bubble_sort(arr)
}
print("Sorted array:", arr)
}
To be continued…