Page 1
DATA STRUCTURES
MODULE 1: INTRODUCTION TO DATA STRUCTURES
Introduction: Definition, Need for Data Structures, Types of Data Structures. Linear Data
Structures: Arrays - Definition, Declaration, and storage of one and two-dimensional arrays.
Sparse matrices. Sorting: Introduction, Bubble sort, Insertion sort, Selection sort, Quick sort,
and Merge sort. Comparison of different sorting techniques.
Practicum:
1. Array
2. Bubble sort
3. Selection sort
4. Insertion sort
5. Quick sort
6. Merge sort
INTRODUCTION TO DATA STRUCTURES
[Link] is Data Structure?
A data structure is a particular way of organising data in a computer so that it can be
used effectively. The idea is to reduce the space and time complexities of different
tasks.
Example: array, list, stack, queue, tree, graph and many more.
An efficient data structure also uses minimum memory space and execution time to
process the structure.
It is also used for processing, retrieving, and storing data.
There are different basic and advanced types of data structures that are used in almost
every program or software system that has been developed. So we must have good
knowledge of data structures.
Need of Data Structure:
The structure of the data and the synthesis of the algorithm are relative to each other.
Data presentation must be easy to understand so the developer, as well as the user, can
make an efficient implementation of the operation.
Data structures provide an easy way of organising, retrieving, managing, and storing
data.
Here is a list of the needs for data.
Page 2
o Data structure modification is easy.
o It requires less time.
o Save storage memory space.
o Data representation is easy.
o Easy access to the large database
2. Explain the Classification or Types of Data Structures.
o Linear Data Structure
o Non-Linear Data Structure.
Linear Data Structure: Elements are arranged in one dimension, also known as
linear dimension. Example: lists, stack, queue, etc.
Non-Linear Data Structure: Elements are arranged in one-many, many-one and
many-many dimensions. Example: tree, graph, table, etc.
(i) Array:
An Array is a data structure used to collect multiple data elements of the same data
type into same data name (one variable).
An array is a collection of data items stored at contiguous memory locations. The idea
is to store multiple items of the same type together.
This makes it easier to calculate the position of each element by simply adding an
offset to a base value, i.e., the memory location of the first element of the array
(generally denoted by the name of the array).
Page 3
Array Data Structure
(ii) Linked Lists:
Linked List is a linear data structure.
Linked list elements are not stored at a contiguous location; the elements are linked
using pointers.
Linked Data Structure
(iii) Stack
Stack is a linear data structure which 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). In stack, all
insertion and deletion are permitted at only one end of the list.
Stack Operations:
push(): When this operation is performed, an element is inserted into the stack.
pop(): When this operation is performed, an element is removed from the top of the
stack and is returned.
Page 4
top(): This operation will return the last inserted element that is at the top without
removing it.
size(): This operation will return the size of the stack i.e. the total number of elements
present in the stack.
isEmpty(): This operation indicates whether the stack is empty or not.
(iv) Queue:
Queue is a linear structure which follows a particular order in which the operations
are performed.
The order is First In First Out (FIFO).
In the queue, items are inserted at one end and deleted from the other end.
A good example of the queue is any queue of consumers for a resource where the
consumer that came first is served first.
The difference between stacks and queues is in removing.
In a stack we remove the item the most recently added; in a queue, we remove the
item the least recently added.
Queue Operations:
Enqueue(): Adds (or stores) an element to the end of the queue..
Dequeue(): Removal of elements from the queue.
Peek() or front(): Acquires the data element available at the front node of the queue
without deleting it.
Page 5
rear(): This operation returns the element at the rear end without removing it.
isFull(): Validates if the queue is full.
isNull(): Checks if the queue is empty.
Queue Data Structure
(v) Linked Lists
A Linked List is a linear data structure used to store a collection of data elements
dynamically.
Data elements in this data structure are represented by the Nodes, connected using
links or pointers.
Each node contains two fields, the information field consists of the actual data, and
the pointer field consists of the address of the subsequent nodes in the list.
The pointer of the last node of the linked list consists of a null pointer, as it points to
nothing. Unlike the Arrays, the user can dynamically adjust the size of a Linked List
as per the requirements.
Linked Lists can be classified into different types:
Singly Linked List: A Singly Linked List is the most common type of Linked List.
Each node has data and a pointer field containing an address to the next node.
Doubly Linked List:
o A Doubly Linked List consists of an information field and two pointer fields.
The information field contains the data.
Page 6
o The first pointer field contains an address of the previous node, whereas
another pointer field contains a reference to the next node. Thus, we can go in
both directions (backward as well as forward).
Circular Linked List:
o The Circular Linked List is similar to the Singly Linked List.
o The only key difference is that the last node contains the address of the first
node, forming a circular loop in the Circular Linked List.
Non-Linear Data Structures
Non-Linear Data Structures are data structures where the data elements are not
arranged in sequential order.
Here, the insertion and removal of data are not possible in a linear manner. There
exists a hierarchical relationship between the individual data items.
Types of Non-Linear Data Structures
(i) Trees
A Tree is a Non-Linear Data Structure and a hierarchy containing a collection of
nodes such that each node of the tree stores a value and a list of references to other
nodes (the "children").
The Tree data structure is a specialized method to arrange and collect data in the
computer to be utilized more effectively.
It contains a central node, structural nodes, and sub-nodes connected via edges. We
can also say that the tree data structure consists of roots, branches, and leaves
connected.
Page 7
(ii) Graphs
A Graph is a Non-Linear Data Structure comprising a finite number of nodes or
vertices and the edges connecting them.
The Graphs are utilized to address problems of the real world in which it denotes the
problem area as a network such as social networks, circuit networks, and telephone
networks.
For instance, the nodes or vertices of a Graph can represent a single user in a
telephone network, while the edges represent the link between them via telephone.
The Graph data structure, G is considered a mathematical structure comprised of a set
of vertices, V and a set of edges, E as shown below: G = (V,E)
Page 8
ARRAY
An array is a collection of one or more values of the same data type stored in
contiguous memory locations.
The data type can be user-defined or even any other primitive data-type.
Elements of an array can be accessed with the same array name by specifying the
index number as the location in memory.
Array Index: The index of an element in an array identifies the element’s location.
The array index starts at 0.
Array element: Elements are the items contained in an array. The elements can be
found using the index.
Array Length: The size of an array is determined by the number of elements it can hold.
Array Declaration
Page 9
Data type can be of any type, and any name can be given to the array, just like naming
a random variable.
Syntax:
int Arr[5]; //arr is the array name of type integer, and 5 is the size of the array
Example of Array Declaration
// C Program to illustrate the array declaration
#include <stdio.h>
int main()
{ // declaring array of integers
int arr_int[5];
// declaring array of characters
char arr_char[5];
return 0;
}
Array Initialization
In static uninitialized arrays, all the elements initially contain garbage values, but we
can explicitly initialize them at their declaration.
Syntax:
<data_type> <arr_name> [arr_size]={value1, value2, value3,…};
Page 10
Example of Array Initialization in C
// C Program to demonstrate array initialization
#include <stdio.h>
int main()
{
// array initialization using initialier list
int arr[5] = { 10, 20, 30, 40, 50 };
// array initialization using initializer list without
// specifying size
int arr1[] = { 1, 2, 3, 4, 5 };
// array initialization using for loop
float arr2[5];
for (int i = 0; i < 5; i++) {
arr2[i] = (float)i * 2.1;
}
return 0;
}
Access Array Elements
Any element of an array can be accessed using the array subscript operator [ ] and the
index value i of the element.
array_name [index];
Indexing in the array always starts with 0, i.e., the first element is at index 0 and
the last element is at N – 1 where N is the number of elements in the array.
Page 11
Example of Accessing Array Elements using Array Subscript Operator
// C Program to illustrate element access using array subscript
#include <stdio.h>
int main()
{ // array declaration and initialization
int arr[5] = { 15, 25, 35, 45, 55 };
// accessing element at index 2 i.e 3rd element
printf("Element at arr[2]: %d\n", arr[2]);
// accessing element at index 4 i.e last element
printf("Element at arr[4]: %d\n", arr[4]);
// accessing element at index 0 i.e first element
printf("Element at arr[0]: %d", arr[0]);
return 0;
}
Output
Element at arr[2]: 35
Element at arr[4]: 55
Element at arr[0]: 15
Types of Arrays
The number of dimensions in an array determines the array type.
The number of indices or subscripts necessary to reach a single array element
determines the array’s dimensions.
The following are the different types of arrays:
o One-dimensional array
Page 12
o Multidimensional array
Two-dimensional array
Three-dimensional array
One Dimensional Array in C
o One-dimensional array is a single row to store the elements.
o All the elements are stored at contiguous memory locations
Syntax of 1D Array in C
array_name [size];
// C Program to illustrate strings
#include <stdio.h>
int main()
{ // creating array of character
char arr[6] = { 'G', 'e', 'e', 'k', 's', '\0' };
// printing string
int i = 0;
while (arr[i]) {
printf("%c", arr[i++]);
}
return 0;
}
Output
Geeks
Multidimensional Array in C
Multi-dimensional Arrays are those arrays that have more than one dimension.
Some of the popular multidimensional arrays are 2D arrays and 3D arrays.
Declare arrays with more dimensions than 3d arrays but they are avoided as they
get very complex and occupy a large amount of space.
A. Two-Dimensional Array in C
A Two-Dimensional array or 2D array is an array that has exactly two dimensions.
Page 13
They can be visualized in the form of rows and columns organized in a two-
dimensional plane.
Syntax of 2D Array in C
array_name[size1] [size2];
Here,
size1: Size of the first dimension.
size2: Size of the second dimension.
Example of 2D Array in C
// C Program to illustrate 2d array
#include <stdio.h>
int main()
{
// declaring and initializing 2d array
int arr[2][3] = { 10, 20, 30, 40, 50, 60 };
printf("2D Array:\n");
// printing 2d array
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 3; j++)
{
printf("%d ",arr[i][j]);
}
printf("\n");
}
return 0;
}
Output
Page 14
2D Array:
10 20 30
40 50 60
B. Three-Dimensional Array in C
Another popular form of a multi-dimensional array is Three Dimensional Array or 3D
Array.
A 3D array has exactly three dimensions.
It can be visualized as a collection of 2D arrays stacked on top of each other to create
the third dimension.
Syntax of 3D Array in C
array_name [size1] [size2] [size3];
Example of 3D Array
#include<stdio.h>
#include<conio.h>
int main()
{
int i, j, k;
int arr[3][4][2] = {
{ {2, 4}, {7, 8}, {3, 4}, {5, 6} },
{ {7, 6}, {3, 4}, {5, 3}, {2, 3} },
{ {8, 9}, {7, 2}, {3, 4}, {5, 1} }
};
for(i=0; i<3; i++)
Page 15
{
for(j=0; j<4; j++)
{
for(k=0; k<2; k++)
printf("arr[%d][%d][%d] = %d ", i, j, k, arr[i][j][k]);
printf("\n");
}
printf("\n");
}
getch();
return 0;
}
Output
SPARSE MATRIX IN DATA STRUCTURE
2-D array is the form of a matrix.
However, if a matrix has most of its elements equal to zero, then the matrix is known
as a sparse matrix.
In the case of a sparse matrix, we don’t store the zeros in the memory to reduce
memory usage and make it more efficient.
We only store the non-zero values of the sparse matrix inside the memory.
Page 16
For example, in the following 5*4 matrix, most of the numbers are zero.
Only a few elements are non-zero which makes it a sparse matrix.
Thus, a sparse matrix is a matrix in which the number of zeros is more than the
number of non-zero elements.
If we store this sparse matrix as it is, it will consume a lot of space.
Therefore, we store only non-zero values in the memory in a more efficient way.
There are mainly two reasons for using sparse matrices. These are:
1. Computation time: If we store the sparse matrix in a memory-efficient manner,
we can save a lot of computational time to perform operations on the matrix.
2. Storage: When we store only non-zero elements, we can save a lot of
memory/space that we can use for storing other data structures or performing other
operations.
Memory Representation of Sparse Matrix using Array representation
Arrays are used to store a sparse matrix.
The sparse matrix is stored in a 2-D array having three rows as follows:
o Row: It stores the index of the row, where we have a non-zero element in the
sparse matrix.
o Column: It stores the index of the column, where we have the non-zero
element in the sparse matrix.
o Value: This variable consists of the actual non-zero value being stored.
For example, the following diagram represent a sparse matrix with the help of an
array by storing only non-zero elements in the array along with their row number and
column number.
Page 17
SORTING: INTRODUCTION, BUBBLE SORT, INSERTION SORT, SELECTION
SORT, QUICK SORT, AND MERGE SORT
SORTING:
Arranging the elements in ascending order or in descending order is called Sorting.
Sorting techniques are broadly categorized into two.
o Internal Sorting and
o External Sorting.
Internal Sorting: All the records that are to be sorted are in main memory.
External Sorting: Some sorts that cannot be performed in main memory and must be
done on disk or tape. This type of sorting is known as External Sorting.
Efficiency:
o One of the major issues in the sorting algorithms is its efficiency.
o The efficiency of sorting algorithm is denoted in terms of time complexity.
o The time complexities are given in terms of big-oh notation.
Commonly there are O(n2) and O(n log n ) time complexities for various algorithms.
Quick sort is the fastest algorithm and bubble sort is the slowest one.
Sorting Method — — — — — — — — — — — — — - Efficiency
Bubble sort/Selection sort/Insertion sort — — — —— — 0(n2)
Quick / Merge — — — — — — — — — — — — —— 0(n log n)
Insertion Sort Algorithm:
Algorithm
The simple steps of achieving the insertion sort are listed as follows -
Page 18
Step 1 - If the element is the first element, assume that it is already sorted. Return 1.
Step2 - Pick the next element, and store it separately in a key.
Step3 - Now, compare the key with all elements in the sorted array.
Step 4 - If the element in the sorted array is smaller than the current element, then
move to the next element. Else, shift greater elements in the array towards the right.
Step 5 - Insert the value.
Step 6 - Repeat until the array is sorted.
Selection Sort Algorithm:
Selection sort in C
Page 19
Selection sort in C to sort numbers of an array in ascending order. With a
little modification, it arranges numbers in descending order.
Selection sort algorithm (for ascending
order)
1. Find the minimum element in the array and swap it with the
element in the 1st position.
2. Find the minimum element again in the remaining array[2, n] and
swap it with the element at 2nd position, now we have two elements at
their correct positions.
3. We have to do this n-1 times to sort the array.
Selection sort program in C
#include <stdio.h>
int main()
{
int array[100], n, c, d, position, t;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
for (c = 0; c < (n - 1); c++) // finding minimum
element (n-1) times
{
position = c;
for (d = c + 1; d < n; d++)
{
if (array[position] > array[d])
position = d;
}
if (position != c)
{
t = array[c];
array[c] = array[position];
array[position] = t;
Page 20
}
}
printf("Sorted list in ascending order:\n");
for (c = 0; c < n; c++)
printf("%d\n", array[c]);
return 0;
}
Output of program:
Bubble Sort Algorithm:
Bubble sort algorithm
1. Start at index zero, compare the element with the next one (a[0] &
a[1] (a is the name of the array)), and swap if a[0] > a[1]. Now compare
a[1] & a[2] and swap if a[1] > a[2]. Repeat this process until the end of
the array. After doing this, the largest element is present at the end. This
whole thing is known as a pass. In the first pass, we process array
elements from [0,n-1].
Page 21
2. Repeat step one but process array elements [0, n-2] because the
last one, i.e., a[n-1], is present at its correct position. After this step, the
largest two elements are present at the end.
3. Repeat this process n-1 times.
Bubble sort program in C
/* Bubble sort code */
#include <stdio.h>
int main()
{
int array[100], n, c, d, swap;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
for (c = 0 ; c < n - 1; c++)
{
for (d = 0 ; d < n - c - 1; d++)
{
if (array[d] > array[d+1]) /* For decreasing
order use '<' instead of '>' */
{
swap = array[d];
array[d] = array[d+1];
array[d+1] = swap;
}
}
}
printf("Sorted list in ascending order:\n");
for (c = 0; c < n; c++)
printf("%d\n", array[c]);
return 0;
}
Page 22
Output of program:
Merge sort
Merge sort is one of the most efficient sorting algorithms. It works on the principle
of Divide and Conquer based on the idea of breaking down a list into several sub-
lists until each sublist consists of a single element and merging those sublists in a
manner that results into a sorted list.
Merge Sort Working Rule
The concept of Divide and Conquer involves three steps:
1. Divide the problem into multiple subproblems.
2. Solve the Sub Problems. The idea is to break down the problem into atomic
subproblems, where they are actually solved.
3. Combine the solutions of the subproblems to find the solution of the actual
problem.
So, the merge sort working rule involves the following steps:
1. Divide the unsorted array into subarray, each containing a single element.
2. Take adjacent pairs of two single-element array and merge them to form an
array of 2 elements.
3. Repeat the process till a single sorted array is obtained.
4. Array = {70,50,30,10,20,40,60}
Page 23
