Chapter-16: Data Structure
Introduction
Data structures are ways to organize and store
data in a computer so that it can be accessed and modified efficiently. This
chapter will cover the definition and types of data structures, arrays, linked
lists, stacks, queues, recursion, and searching and sorting methods. We will
use simple explanations and examples relevant to India.
Definition and Types of Data Structures
Definition
A data structure is a particular way of
organizing data in a computer to utilize it efficiently.
Types of Data Structures
Data structures can be broadly classified into
two categories: linear and non-linear.
Linear Data Structures
In linear data structures, elements are arranged in a sequential manner.
1. Arrays
2. Linked Lists
3. Stacks
4. Queues
Non-Linear Data Structures
In non-linear data structures, elements are not arranged in a sequential manner.
1. Trees
2. Graphs
Examples
1. Linear Data Structure Example: A list of
students in a class arranged roll number wise.
2. Non-Linear Data Structure Example: A family
tree representing relationships.
Arrays:
1D, 2D and Their Applications
Definition
An array is a collection of elements, each identified by an array index.
1D Array
A one-dimensional array is a list of elements of
the same type stored in contiguous memory locations.
Example
In India, an array can be used to store the
marks of students in a class:
int marks[5] = {85, 90, 78, 88, 76};
2D Array
A two-dimensional array is an array of arrays,
where each element is identified by two indices.
Example
In India, a 2D array can be used to store the
marks of students in different subjects:
int marks[3][5] = {
{85,
90, 78, 88, 76},
{80,
85, 88, 92, 79},
{75,
80, 85, 90, 85}
};
Applications
1. 1D Array: Storing student marks,
temperatures, and prices of items.
2. 2D Array: Representing a matrix, storing
student marks in multiple subjects.
Linked
List: Basic Concepts of Single, Circular, and Double Linked List
Single Linked List
A single linked list is a collection of nodes
where each node contains data and a reference to the next node.
Example
A single linked list can be used to store a list
of books in a library:
struct Node {
int
data;
struct
Node next;
};
Circular Linked List
In a circular linked list, the last node points
to the first node, forming a circle.
Example
Circular linked lists can be used in round-robin
scheduling in operating systems.
Double Linked List
A double linked list contains nodes with
references to both the next and the previous nodes.
Example
Double linked lists can be used in web browsers
to implement the forward and backward navigation.
Stack
Stack Operations (Push and Pop)
A stack is a linear data structure that follows the Last In First Out (LIFO) principle.
1. Push: Add an element to the top of the stack.
2. Pop: Remove the top element from the stack.
Example
A stack can be used in the Undo feature in text
editors:
struct Stack {
int
data;
struct
Stack next;
};
Applications of Stack
1. Expression Evaluation
2. Backtracking
3. Undo Mechanism in Editors
Queue
Queue Operations
A queue is a linear data structure that follows the First In First Out (FIFO) principle.
1. Enqueue: Add an element to the end of the
queue.
2. Dequeue: Remove the front element from the
queue.
Example
A queue can be used in the ticket booking system
in Indian Railways:
struct Queue {
int
data;
struct
Queue next;
};
1. Scheduling in Operating Systems
2. Managing Print Jobs
3. Customer Service Management
Circular Queue
A circular queue is a queue where the last
position is connected back to the first position to make a circle.
Example
Circular queues can be used in the management of
the CPU scheduling in a time-sharing system.
Priority Queue
In a priority queue, each element is associated
with a priority, and elements are served based on their priority.
Example
Priority queues can be used in operating systems
for job scheduling based on priority.
Recursion
Definition
Recursion is a process where a function calls
itself directly or indirectly.
Advantages
1. Simplifies Code: Recursive solutions can be
more elegant and easier to understand.
2. Problem Solving: Suitable for problems that
can be divided into similar sub-problems.
Limitations
1. Memory Usage: Recursion can use more memory
due to function call stack.
2. Performance: Recursive solutions can be
slower for large inputs.
Example
Calculating factorial of a number using
recursion:
int factorial(int n) {
if (n
== 0) return 1;
else
return n factorial(n - 1);
}
Searching
and Sorting
Linear Search
Linear search involves checking each element of
the array until the desired element is found.
Example
Searching for a roll number in a list of
students:
int linearSearch(int arr[], int n, int x) {
for
(int i = 0; i < n; i++) {
if
(arr[i] == x) return i;
}
return
-1;
}
Binary Search
Binary search is a more efficient method that
requires the array to be sorted. It repeatedly divides the array in half to
find the element.
Example
int binarySearch(int arr[], int l, int r, int x)
{
while
(l <= r) {
int m = l + (r - l) / 2;
if
(arr[m] == x) return m;
if
(arr[m] < x) l = m + 1;
else r = m - 1;
}
return
-1;
}
Bubble Sort
Bubble sort repeatedly steps through the list,
compares adjacent elements, and swaps them if they are in the wrong order.
Example
Sorting an array of student marks:
void bubbleSort(int arr[], int n) {
for
(int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
Understanding data structures is fundamental for
efficient data management and algorithm development. This chapter provided an
overview of various data structures, their operations, and applications with
examples relevant to India.
References
1. Data Structures and Algorithms Made Easy by
Narasimha Karumanchi
2. Introduction to Algorithms by Thomas H.
Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
3. GeeksforGeeks: [Data
Structures](https://www.geeksforgeeks.org/data-structures/)
4. Wikipedia: [Data Structure](https://en.wikipedia.org/wiki/Data_structure)
x
Comments
Post a Comment