Dsa Unit 1 & 2

DATA STRUCTURES AND ALGORITHMS
LECTURE NOTES
MCA I YEAR – I
SEM -I (IT 12)
PATTERN -2024
Adv. MohammadAli Shaikh
MohammadAli Shaikh DSA-IT12 1|Page

Unit Contents Weightage No of
No. in % Sessions
Arrays/List:
1.1 Introduction & Definition of an Array
1.2 Memory Allocation & Indexing
1 1.3 Operations on 1-D & 2D Arrays/Lists 15 4
1.4 Arrays and Their Applications
1.5 Sparse Matrices
1.6 String manipulation using arrays
*Mapping of Course Outcomes for Unit 1: CO1
Linked Lists:
2.1 Introduction
2.2 Definition of a Linked List
2 20 7
2.3 Memory Allocation in a Linked List
2.4 Types of Linked Lists
2.4.1 Singly Linked List
2.4.2 Operations on a Singly Linked List
2.4.3 Circular Linked Lists
2.4.4 Operations on a Circular Linked List
2.4.5 Doubly Linked List
Operations on a Doubly Linked List
Stacks and Queues
3.1 Introduction and Definition of a Stack
3.2 Implementation of a Stack
3.2.1 Implementation of Stacks Using Arrays
3.2.2 Implementation of Stacks Using Linked Lists
3.3 Applications of Stacks:
3.3.1 Conversion of an expression (Infix, Prefix, Postfix)
3 20 10
3.3.2 Evaluation of Expression
3.3.3 String Reversal
3.4 Introduction and Definition of a Queue
3.5 Implementation of a Queue
3.5.1 Implementation of Queues Using Arrays
3.5.2 Implementation of Queues Using Linked Lists
3.6 Applications of Queues
Tree & Graph
4.1 Tree Definition, representation
4.2 Binary Search Tree and its operations
4.2.1 Tree Traversal
4.2.2 Insertion
4.2.3 Deletion
4.2.4 Search
4.3 AVL Tree and its operations
4.3.1 Insertion
4 25 16
4.3.2 Deletion
4.3.3 Rotations
4.4 Directed and Undirected Graph
4.5 Graph Representations
4.5.1 Adjacency Matrix
4.5.2 Adjacency List
4.6 Graph Traversals
4.6.1 BFS
4.6.2 DFS
Searching and Sorting
5 5.1 Linear Search or Sequential Search 20 8
5.2 Binary Search
5.3 Interpolation Search
5.4 Introduction to Sorting
5.5.1 Merge Sort
5.5.2 Quick Sort
5.5.3 Bubble Sort
5.5 Heap
5.5.1 Min heap and Max heap
5.6 Hashing
5.6.1 Hash Table
5.6.2 Hash Functions
Unit 1 : Data Structures and Algorithms:
Introduction
We begin with a definition for “algorithm.”
Algorithm: A finite sequence of steps for accomplishing some computational task.

An algorithm must
• Have steps that are simple and definite enough to be done by a computer, and
• Terminate after finitely many steps.
Abstract data type (ADT): A set of values (the carrier set), and operations on
those values.
Built-in Data Type
Those data types for which a language has built-in support are known as
Built-in Data types. For example, most of the languages provide the following
built-in data types.
 Integers
 Boolean (true, false)
 Floating (Decimal numbers)
 Character and Strings
Derived Data Type
Those data types which are implementation independent as they can be implemented in one or the
other way are known as derived data types. These data types are normally built by the combination of
primary or built-in data types and associated operations on them. For example −
 List
 Array
 Stack
 Queue
Data Definition
Data Definition defines a particular data with the following characteristics.

Atomic − Definition should define a single concept.
Traceable − Definition should be able to be mapped to some data element.
Accurate − Definition should be unambiguous.
Clear and Concise − Definition should be understandable.
Data Object
Data Object represents an object having a data.
Data Type
Data type is a way to classify various types of data such as integer, string, etc.
which determines the values that can be used with the corresponding type of
data, the type of operations that can be performed on the corresponding type
of data. There are two data types −
 Built-in Data Type

 Derived Data Type
Basic Operations
The data in the data structures are processed by certain operations. The particular data structure
chosen largely depends on the frequency of the operation that needs to be performed on the data
structure.
 Traversing
 Searching
 Insertion
 Deletion
 Sorting
 Merging
Primitive Data Structures
Primitive Data Structures are the basic data structures that directly operate upon the machine
instructions. They have different representations on different computers. For example, integer,
character, and string are all primitive data types. Programmers can use these data types when creating
variables in their programs.
Non-primitive Data Structures
Non-primitive data structures are more complicated data structures and are derived from
primitive data structures.
Linear Data Structures
A data structure is called linear if all of its elements are arranged in the linear order. In
linear data structures, the elements are stored in non-hierarchical way where each
element has the successors and predecessors except the first and last element.
Types of Linear Data Structures are given below:
 Arrays: An array is a collection of similar type of data items and each data item is
called an element of the array. The data type of the element may be any valid data
type like char, int, float or double. The elements of array share the same variable
name but each one carries a different index number known as subscript. The array
can be one dimensional, two dimensional or multidimensional.
 Linked List: Linked list is a linear data structure which is used to maintain a list in
the memory. It can be seen as the collection of nodes stored at non-contiguous
memory locations. Each node of the list contains a pointer to its adjacent node.
 Stack: Stack is a linear list in which insertion and deletions are allowed only at
one end, called top. A stack is an abstract data type (ADT), can be implemented in
most of the programming languages. It is named as stack because it behaves like
a real world stack, for example: - piles of plates or deck of cards etc.
 Queue: Queue is a linear list in which elements can be inserted only at one end
called rear and deleted only at the other end called front. It is an abstract data
structure, similar to stack. Queue is opened at both end therefore it follows First-
In-First-Out (FIFO) methodology for storing the data items
Non Linear Data Structure
This data structure does not form a sequence i.e. each item or element is connected with
two or more other items in a non-linear arrangement.
The data elements are not arranged in sequential structure.

Types of Non Linear Data Structures are given below:
 Trees: Trees are multilevel data structures with a hierarchical relationship among
its elements known as nodes. The bottommost nodes in the hierarchy are called
leaf node while the topmost node is called root node. Tree data structure is based
on the parent-child relationship among the nodes. Each ode contains pointers that
points to the child node. Each node in the tree can have more than one children
except the leaf nodes whereas each node can have at most one parent except the
root node. Trees can be classified into many categories which will be discussed
later.
 Graphs: Graphs can be defined as the pictorial representation of the set of
elements (represented by vertices) connected by the links known as edges. A
graph is different from tree in the sense that a graph can have cycle while the tree
cannot have the one. Basically, primitive data types, as the name is self-
explanatory, are the data types that already come with the programming language
completely ready for the programmer’s use.
An algorithm is a procedure having well defined steps for solving a particular problem.
Algorithm is finite set of logic or instructions, written in order for accomplish the certain
predefined task. It is not the complete program or code, it is just a solution (logic) of a
problem, which can be represented either as an informal description using a Flowchart or
Pseudo code.
Characteristics of an Algorithm
An algorithm must follow the mentioned below characteristics:
 Input: An algorithm must have 0 or well defined inputs.

 Output: An algorithm must have 1 or well defined outputs, and should match with
the desired output.
 Feasibility: An algorithm must be terminated after the finite number of steps.
 Independent: An algorithm must have step-by-step directions which is independent
of any programming code.
 Unambiguous: An algorithm must be unambiguous and clear. Each of their steps
and input/outputs must be clear and lead to only one meaning.
From the data structure point of view, following are some important categories
of algorithms −
 Search − Algorithm to search an item in a data structure.

 Sort − Algorithm to sort items in a certain order.
 Insert − Algorithm to insert item in a data structure.
 Update − Algorithm to update an existing item in a data structure.
 Delete − Algorithm to delete an existing item from a data structure.
Introduction
A structured type of fundamental importance in almost every procedural programming
language is the array.
Array: A fixed length, ordered collection of values of the same type stored in contiguous
memory locations; the collection may be ordered in several dimensions. The values stored
in an array are called elements. (DEF1)
Array : Array is a container which can hold a fix number of items and these items should
be of the same type. Most of the data structures make use of arrays to implement their
algorithms. a segment of memory for element storage. Thereafter the array may shrink
or grow. If the array shrinks during execution, then only an initial portion of allocated
memory is used. But if the array grows beyond the space allocated for it, a more complex
reallocation procedure must occur, as follows:
 A new segment of memory large enough to store the elements of the expanded
 array is allocated.
 All elements of the original (unexpanded) array are copied into the new
 memory segment.
 The memory used initially to store array values is freed and the newly allocated
 memory is associated with the array variable or reference.
 This reallocation procedure is computationally expensive, so systems are usually
designed to minimize its frequency of use. For example, when an array expands
beyond its memory allocation, its memory allocation might be doubled even if
space for only a single additional element is needed. The hope is that providing a
lot of extra space will avoid many expensive reallocation procedures if the array
expands slowly over time.
 Dynamic arrays are convenient for programmers because they can never be too
small—
 whenever more space is needed in a dynamic array, it can simply be expanded.
One drawback of dynamic arrays is that implementing language support for them
is more work for the compiler or interpreter writer. A potentially more serious
drawback is that the expansion procedure is expensive, so there are circumstances
when using a dynamic array can be dangerous. For example, if an application must
respond in real time to events in its environment, and a dynamic array must be
expanded when the application is in the midst of a response, then the response
may be delayed too long, causing problems
Following are the important terms to understand the concept of Array.

 Element − Each item stored in an array is called an element.
 Index − Each location of an element in an array has a numerical index, which is
used to identify the element.
Basic Operations
Following are the basic operations supported by an array.
 Traverse − print all the array elements one by one.

 Insertion − Adds an element at the given index.
 Deletion − Deletes an element at the given index
 Search − Searches an element using the given index or by the value
 Update − Updates an element at the given index.
Varieties of Arrays
In some languages, the size of an array must be established once and for all at program
design time and cannot change during execution. Such arrays are called static arrays. A
chunk of memory big enough to hold all the values in the array is allocated when the array
is created, and thereafter elements are accessed using the fixed base location of the array.
Static arrays are the fundamental array type in older procedural languages, such as
Fortran, Basic, and C, and in many newer object-oriented languages as well, such as
Java. Some languages provide arrays whose sizes are established at run-time and can
change during execution. These dynamic arrays have an initial size used as the basis for
allocating
An array is a data structure that contains a group of elements. Typically these elements
are all of the same data type, such as an integer, float, character or string. Arrays are
commonly used in computer programs to organize data so that a related set of values can
be easily sorted or searched.
int no [3]={10,20,30};
float no [3]={1.5,2.7,8.9};
Definition
An array is a collection of elements of the same type placed in contiguous
memory locations that can be individually referenced by using an index to
a unique identifier.
Initialization
An array can be initialized in two ways.
 By declaring and initializing it simultaneously. int arr [] = { 10, 20, 30, 40 }

 By declaring it first and initializing it later during run time.
Characteristics
 An array holds elements that have the same data type

 Array elements are stored in subsequent memory locations
 Two-dimensional array elements are stored row by row in subsequent memory
locations
 Array name represents the address of the starting element
 Array size should be mentioned in the declaration.
 Array size must be a constant expression and not a variable.
Types of ARRAY :
 One dimensional (1-D) arrays or Linear arrays.

 Multi-dimensional arrays.
o Two dimensional (2-D) arrays or Matrix arrays.
o Three dimensional arrays
Multi-Dimensional Arrays
Multi-dimensional arrays can be described as ‘arrays of arrays’. A multi-dimensional array

of dimension n is a collection of elements, which are accessed with the help of n subscript
values. Most of the high-level languages, including C, support arrays with more than one
dimension. However, the maximum limit of an array dimension is compiler dependent.
Two dimensional Arrays
A two-dimensional array is one in which two subscript values are used to access an array
element. They are useful when the elements being processed are to be arranged in rows
and columns (matrix form).
The syntax of declaring a two-dimensional array in C is as follows:
data_type array_name [row_size][column_size];
For example, in the statement int a[3][3], an integer array of three rows and three columns
is declared. Once a compiler reads a two-dimensional array declaration, it allocates a
specific amount of memory for this array.
Array is a linear data structure that is a collection of similar data types. Arrays are stored
in contiguous memory locations. It is a static data structure with a fixed size. It combines
data of similar types.
ARRAY
Applications of Array Data Structure:
Below are some applications of arrays.

 Storing and accessing data: Arrays are used to store and retrieve data in a
specific order. For example, an array can be used to store the scores of a group of
students, or the temperatures recorded by a weather station.
 Sorting: Arrays can be used to sort data in ascending or descending order. Sorting
algorithms such as bubble sort, merge sort, and quicksort rely heavily on arrays.
 Searching: Arrays can be searched for specific elements using algorithms such as
linear search and binary search.
 Matrices: Arrays are used to represent matrices in mathematical computations
such as matrix multiplication, linear algebra, and image processing.
 Stacks and queues: Arrays are used as the underlying data structure for
implementing stacks and queues, which are commonly used in algorithms and data
structures.
 Graphs: Arrays can be used to represent graphs in computer science. Each
element in the array represents a node in the graph, and the relationships between
the nodes are represented by the values stored in the array.
 Dynamic programming: Dynamic programming algorithms often use arrays to
store intermediate results of subproblems in order to solve a larger problem.
Real-Time Applications of Array:
Below are some real-time applications of arrays.

 Signal Processing: Arrays are used in signal processing to represent a set of
samples that are collected over time. This can be used in applications such as
speech recognition, image processing, and radar systems.
 Multimedia Applications: Arrays are used in multimedia applications such as
video and audio processing, where they are used to store the pixel or audio
samples. For example, an array can be used to store the RGB values of an image.
 Data Mining: Arrays are used in data mining applications to represent large
datasets. This allows for efficient data access and processing, which is important
in real-time applications.
 Robotics: Arrays are used in robotics to represent the position and orientation of
objects in 3D space. This can be used in applications such as motion planning and
object recognition.
 Real-time Monitoring and Control Systems: Arrays are used in real-time
monitoring and control systems to store sensor data and control signals. This
allows for real-time processing and decision-making, which is important in
applications such as industrial automation and aerospace systems.
 Financial Analysis: Arrays are used in financial analysis to store historical stock
prices and other financial data. This allows for efficient data access and analysis,
which is important in real-time trading systems.
 Scientific Computing: Arrays are used in scientific computing to represent
numerical data, such as measurements from experiments and simulations. This
allows for efficient data processing and visualization, which is important in real-time
scientific analysis and experimentation.
Applications of Array in C/C++:
 Arrays are used to implement vectors, and lists in C++ STL.
 Arrays are used as the base of all sorting algorithms.
 Arrays are used to implement other DS like a stack, queue, etc.

 Used for implementing matrices.
 Data structures like trees also sometimes use the array implementation since
arrays are easier to handle than pointers. For example, a segment tree uses array
implementation.
 Binary search trees and balanced binary trees are used in data structures such as
a heap, map, and set, which can be built using arrays.
 Graphs are also implemented as arrays in the form of an adjacency matrix.

Applications of Array in Java:
 Storing collections of data: Arrays are often used to store collections of data of
the same type. For example, an array of integers can be used to store a set of
numerical values.
 Implementing matrices and tables: Arrays can be used to implement matrices
and tables. For example, a two-dimensional array can be used to store a matrix of
numerical values.
 Sorting and searching: Arrays are often used for sorting and searching data. For
example, the Arrays class in Java provides methods like sort() and binarySearch()
to sort and search elements in an array.
 Implementing data structures: Arrays are used as the underlying data structure
for several other data structures like stacks, queues, and heaps. For example, an
array-based implementation of a stack can be used to store elements in the stack.
 Image processing: Arrays are commonly used to store the pixel values of an
image. For example, a two-dimensional array can be used to store the RGB values
of an image.
Applications of Array in C#:
 Implementing dynamic programming algorithms: Dynamic programming

algorithms often use arrays to store intermediate results. For example, in the
famous Fibonacci series algorithm, an array is used to store the values of Fibonacci
series.
 Database programming: Arrays can be used to store the results of database
queries. For example, an array can be used to store the results of a SELECT query.
 Parallel programming: Arrays are used in parallel programming to distribute
workloads among multiple threads. For example, an array can be divided into
multiple parts, and each part can be processed by a different thread.
Advantages of array data structure:
 Efficient access to elements: Arrays provide direct and efficient access to any
element in the collection. Accessing an element in an array is an O(1) operation,
meaning that the time required to access an element is constant and does not
depend on the size of the array.
 Fast data retrieval: Arrays allow for fast data retrieval because the data is stored
in contiguous memory locations. This means that the data can be accessed quickly
and efficiently without the need for complex data structures or algorithms.
 Memory efficiency: Arrays are a memory-efficient way of storing data. Because
the elements of an array are stored in contiguous memory locations, the size of the
array is known at compile time. This means that memory can be allocated for the
entire array in one block, reducing memory fragmentation.
 Versatility: Arrays can be used to store a wide range of data types, including
integers, floating-point numbers, characters, and even complex data structures
such as objects and pointers.
 Easy to implement: Arrays are easy to implement and understand, making them
an ideal choice for beginners learning computer programming.
 Compatibility with hardware: The array data structure is compatible with most
hardware architectures, making it a versatile tool for programming in a wide range
of environments.
Disadvantages of array data structure:
 Fixed size: Arrays have a fixed size that is determined at the time of creation. This
means that if the size of the array needs to be increased, a new array must be
created and the data must be copied from the old array to the new array, which can
be time-consuming and memory-intensive.
 Memory allocation issues: Allocating a large array can be problematic,
particularly in systems with limited memory. If the size of the array is too large, the
system may run out of memory, which can cause the program to crash.
 Insertion and deletion issues: Inserting or deleting an element from an array can
be inefficient and time-consuming because all the elements after the insertion or
deletion point must be shifted to accommodate the change.
 Wasted space: If an array is not fully populated, there can be wasted space in the
memory allocated for the array. This can be a concern if memory is limited.
 Limited data type support: Arrays have limited support for complex data types
such as objects and structures, as the elements of an array must all be of the same
data type.
 Lack of flexibility: The fixed size and limited support for complex data types can
make arrays inflexible compared to other data structures such as linked lists and
trees.
Advantages of Structure over Array:
 The structure can store different types of data whereas an array can only store
similar data types.
 Structure does not have limited size like an array.
 Structure elements may or may not be stored in contiguous locations but array
elements are stored in contiguous locations.
 In structures, object instantiation is possible whereas in arrays objects are not

possible.
Sparse Matrix and its representations

A matrix is a two-dimensional data object made of m rows and n columns, therefore
having total m x n values. If most of the elements of the matrix have 0 value, then it is
called a sparse matrix.
Why to use Sparse Matrix instead of simple matrix ?
 Storage: There are lesser non-zero elements than zeros and thus lesser memory
can be used to store only those elements.
 Computing time: Computing time can be saved by logically designing a data
structure traversing only non-zero elements.
Example:
0 0 3 0 4
0 0 5 7 0
0 0 0 0 0
02600
Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes

in the matrix are of no use in most of the cases. So, instead of storing zeroes with non-
zero elements, we only store non-zero elements. This means storing non-zero elements
with triples- (Row, Column, value).
Sparse Matrix Representations can be done in many ways following are two common
representations:
1. Array representation
2. Linked list representation

Method 1: Using Arrays:
2D array is used to represent a sparse matrix in which there are three rows named as
 Row: Index of row, where non-zero element is located
 Column: Index of column, where non-zero element is located
 Value: Value of the non zero element located at index – (row,column)

# Python program for Sparse Matrix Representation
# using arrays
# assume a sparse matrix of order 4*5
# let assume another matrix compactMatrix

# now store the value,row,column of arr1 in sparse matrix compactMatrix
sparseMatrix = [[0,0,3,0,4],[0,0,5,7,0],[0,0,0,0,0],[0,2,6,0,0]]
# initialize size as 0
size = 0
for i in range(4):
for j in range(5):
if (sparseMatrix[i][j] != 0):
size += 1
# number of columns in compactMatrix(size) should
# be equal to number of non-zero elements in sparseMatrix

rows, cols = (3, size)
compactMatrix = [[0 for i in range(cols)] for j in range(rows)]
k=0
for i in range(4):
for j in range(5):
if (sparseMatrix[i][j] != 0):
compactMatrix[0][k] = i
compactMatrix[1][k] = j
compactMatrix[2][k] = sparseMatrix[i][j]
k += 1
for i in compactMatrix:
print(i)
# This code is contributed by MRINALWALIA
Output
001133
242312
345726
Time Complexity: O(NM), where N is the number of rows in the sparse matrix, and M is
the number of columns in the sparse matrix.
Auxiliary Space: O(NM), where N is the number of rows in the sparse matrix, and M is
the number of columns in the sparse matrix.
Method 2: Using Linked Lists
In linked list, each node has four fields. These four fields are defined as:
 Row: Index of row, where non-zero element is located
 Column: Index of column, where non-zero element is located
 Value: Value of the non zero element located at index – (row,column)
 Next node: Address of the next node
// C++ program for sparse matrix representation.
// Using Link list
#include<iostream>
using namespace std;
// Node class to represent link list

class Node
{
public:
int row;
int col;
int data;
Node *next;
};
// Function to create new node

void create_new_node(Node **p, int row_index,
int col_index, int x)
{
Node *temp = *p;
Node *r;
// If link list is empty then
// create first node and assign value.

if (temp == NULL)
{
temp = new Node();
temp->row = row_index;
temp->col = col_index;
temp->data = x;
temp->next = NULL;
*p = temp;
// If link list is already created
// then append newly created node

else
{
while (temp->next != NULL)
temp = temp->next;
r = new Node();
r->row = row_index;
r->col = col_index;
r->data = x;
r->next = NULL;
temp->next = r;
// Function prints contents of linked list
// starting from start

void printList(Node *start)
Node *ptr = start;
cout << "row_position:";

while (ptr != NULL)
cout << ptr->row << " ";
ptr = ptr->next;
}
cout << endl;
cout << "column_position:";

ptr = start;
while (ptr != NULL)
cout << ptr->col << " ";
ptr = ptr->next;
cout << endl;

cout << "Value:";
ptr = start;
while (ptr != NULL)
cout << ptr->data << " ";
ptr = ptr->next;
// Driver Code
int main()
// 4x5 sparse matrix

int sparseMatrix[4][5] = { { 0 , 0 , 3 , 0 , 4 },
{ 0 , 0 , 5 , 7 , 0 },
{ 0 , 0 , 0 , 0 , 0 },
{ 0 , 2 , 6 , 0 , 0 } };
// Creating head/first node of list as NULL
Node *first = NULL;

for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 5; j++)
// Pass only those values which
// are non - zero

if (sparseMatrix[i][j] != 0)
create_new_node(&first, i, j,
sparseMatrix[i][j]);
printList(first);
return 0;
// This code is contributed by ronaksuba
Output
row_position:0 0 1 1 3 3
column_position:2 4 2 3 1 2
Value:3 4 5 7 2 6
Time Complexity: O(N*M), where N is the number of rows in the sparse matrix, and M
is the number of columns in the sparse matrix.
Auxiliary Space: O(K), where K is the number of non-zero elements in the array.
Other representations:
As a Dictionary where row and column numbers are used as keys and values are matrix
entries. This method saves space but sequential access of items is costly.
As a list of list. The idea is to make a list of rows and every item of list contains values.
We can keep list items sorted by column numbers.
Python String Data Type
Strings are a collection of Unicode characters that are used specifically in Python. A string
is the language or text we use to communicate. However, machines can only read binary,
they cannot comprehend text. As a result, ASCII numbers are initially generated from
characters before being transformed to binary representation. However, ASCII is
exclusively used for the English language, and when programming languages are used in
other nations, they are translated to 16-bit characters known as Unicode.
Creating Strings
Python offers several methods for creating strings, including single, double, and triple
quotes. When constructing a string, if the string contains any kind of quote, you should
use a separate kind of quote in the declaration to prevent an error. Try the example below
in any Python IDE or code editor for a better understanding.
4
5
10
s = 'Good Morning'
#single quotes
s = 'It'
s been a great day ' #syntax error (It confuses where string starts and ends)
s = "It's been a great day"
#correct way
s = ''
'Good Morning'
''
#multi - line strings
When declaring or referencing a lengthy paragraph use triple quotes. Any other data type
can be declared as a string or converted using an internal function.
a = 99 #int
print(str(a)) #int to str

Accessing Substring from String
To address a specific use case, it may occasionally be essential to access portions of a

string. We shall discuss indexing and slicing, which enable us to extract a specific section
of the text as output.
Indexing
Indexing a string with zeros is the same as indexing an array. Simply put, the zero indexes
in a string represent the first character, and as the index rises, the string advances.
Positive and negative indexing are the two categories of indexing in Python.
Positive Indexing
Positive indexing is moving from zero to the end length of a string. It is also known as
zero-based indexing.
4
5
s = 'GoodMorning'
print(s[0])
print(s[2])
print(s[4])
print(s[len(s) - 1])
print(len(s))
output:
1
2
11
Note: If access s(11), program returns a Index error
Negative Indexing
Accessing string elements using a negative index means going backward in time. It
usually takes a long time to access the last character in a string if we use positive indexing
since we have to calculate the length of the string and then take one off of it. In this
situation, we can just use the negative indexing.
1
s = 'GoodMorning'
print(s[-1])
print(s[-2])
output:
n
Slicing
The concept of slicing, which is accomplished using the colon operator, comes into play
when we have long strings, such as sentences or paragraphs, and we want to access
specific pieces, like whole words, but we cannot do so merely using indexing. To ensure
that the output is a portion of the string from a start index to an end index less one, we
must specify the starting index and end index in square brackets that are separated by
colons.
1
2
s = 'Good Morning'
print(s[1: 4])
output:
1
ood
Start with the first index in the example above and retrieve the character all the way to the
third index. Now that there are various slicing variations, let’s examine them practically
using the code sample below.
6
s = 'GoodMorning'
print(s[1: ])
print(s[: 4])
print(s[: ])
print(s[0: 8: 3])
print(s[::-1])
output:
3
4
oodMorning #It will print the entire string starting from index 1
Good #It will print the entire string starting from index 0 to 3
GoodMorning #It will print the entire string
Gdr #It will print zero index and skip two index and take third index till eighth index
gninroMdooG #It will print the string in reverse order
Editing and Deleting Python Strings
Since strings in Python are immutable data types, attempting to change one will result in
a type error. The existing string cannot be changed or added to, but it can be assigned to
a separate variable to produce a new string. Let’s examine the practical effects of deleting
and altering strings to see whether we experience any errors.
Since strings are immutable, we cannot directly reassign the value of the particular string
in the below snippet.
s = 'GoodMorning'
s[0] = "M"
#This operation is not allowed and it will
return not support Item assignment error
Instead, the below combination will work
s = 'GoodMorning'
a = "M" + s[1: ]
print(a)
output:
MoodMorning
Deleting the strings won’t work well and the below statements will generate errors saying
we can’t delete the string.
del s[0]
del s[: 3: 2]
It is crucial to comprehend that strings cannot be changed; nothing can be added or

removed from an existing string.
Operations on Python String
Arithmetic Operations
Addition(+)
Concatenation, as it is also known, allows us to link any amount of strings by using the
addition operator.
s = "Good" + "-" + "Morning"

print(s)
output:
Good - Morning
Multiplication(*)
To repeat a certain string before the multiplication operator any number of times is known
as string repetition. When we want a pattern, we use it.
s = "Good"
print(s * 3)
output:
GoodGoodGood
Relational Operations
Relational operators display the relationship between two terms and determine whether a
particular condition is true or false, producing a boolean result.
2
print("Hello" == "World")
print("Hello" != "World")
output:
False
True
When we apply the larger than and less than operators the situation becomes more
intriguing.
1
2
print("Mumbai" > "Pune")
print("Goa" < "Indore")

output:
False
True
You might be wondering how it compares two strings. As a result, it lexicographically

compares a string. As P follows M in the alphabetical order in the first case, the statement
is false. Lowercase characters are placed after uppercase because occasionally people
mistake the two case types.
Logical Operations
When you use the AND, OR, and NOT logical operators on strings, Python returns false
for empty strings and true for non-empty strings.
5
6
print("Hello"
and "World") #True and True - > True(O / P - > World)
print(""
and "World") #False and True - > False(O / P - > "")
print(""
or "World") #False OR True - > True(O / P - > "World")

print(not "Hello") #opposite of True - > False
print(not "") #True

Loops
Slicing allows us to loop over strings starting at any index. To access distinct characters
or create a pattern in a string, we can use both a where and a for loop.
1
s = 'GoodMorning'
for i in s:
print(i)
output:
8
9
10
11
M
o
Membership Operators
Python’s in and NOT in membership operators are used to determine whether any
element is present in any sequence data structure.
s = 'GoodMorning'
if 'M' in s:
print('true')
output:
true
Python String Functions
The most important parts of a string are string functions which you use everywhere
whenever you build any project. Now we will study all-important string functions which are
frequently used.
Common Functions:
These are the same functions that are available for all other iterator data types, including
list, tuple, set, and string.
1. length - It provides the string’s length.
2. minimum - This function returns the smallest character in a string, as determined

by ASCII.
3. maximum - The largest character found in the string, as determined by ASCII, is

provided by the third option, maximum.
4. sorted - The string is sorted in either ascending or descending order using the
ASCII character sequence. This function always returns a list of characters as its
result.
s = 'GoodMorning'
print(len(s))
print(min(s))
print(max(s))
print(sorted(s))
print(sorted(s, reverse = True))

output:
3
4
11
['G', 'M', 'd', 'g', 'i', 'n', 'n', 'o', 'o', 'o', 'r']
['r', 'o', 'o', 'o', 'n', 'n', 'i', 'g', 'd', 'M', 'G']
Some Specific Purpose Functions in Strings
The functions we’ll look at here only work with strings.

Title or capitalize
The title function capitalizes the first letter of each word, whereas the capitalize function
capitalizes the first letter of a string.
2
3
s = "its raining outside"
print(s.capitalize()) #O / P - > Its raining outside
print(s.title()) #O / P - > Its Raining Outside

Upper / lower / swap case
In string each character is converted in the upper function to lowercase characters. Swap
case changes an upper to a lower case character, and vice versa.
3
4
s = "Its Raining Outside"
print(s.upper()) #O / P - > ITS RAINING OUTSIDE
print(s.lower()) #O / P - > its raining outside

print(s.swapcase()) #O / P - > iTS rAINING oUTSIDE
Count
It provides the number of any substrings that are present in a string. It outputs 0 if the
substring is missing from the string. It is used to determine how often a given substring
occurs in a string.
print(s.count("i")) #3
print(s.count("ing")) # 1
Find / Index
Both functions operate in exactly the same manner. Both locate the position of a substring
within a string. The sole distinction between the two functions is that while index gives an
error when the substring is absent, string find produces a negative value when this occurs.
print(s.find("ing")) #8
print(s.index("ing")) # 8
print(s.find("down")) # - 1
print(s.index("down")) #error
Unit 2 : Linked List
2.1 Introduction :
A list or sequence is an abstract data type that represents a countable number of ordered
values, where the same value may occur more than once. A linked list is a sequence of data
structures, which are held together by links. A Linked List is a sequence of links which
contains items. Each link contains a connection to another link. A Linked list is the second
most-used data structure after an array.
2.2 Definition of a Linked List

A linked list is a linear collection of homogeneous elements called nodes. Successive nodes
of a linked list need not occupy adjacent memory locations. The linear order between nodes
is maintained by means of pointers. In linked lists, insertion or deletion of nodes do not
require shifting of existing nodes as in the case of arrays; they can be inserted or deleted
merely by adjusting the pointers or links.
Or
A linked list is a sequence of data structures, which are connected together via links.
Linked List is a sequence of links which contains items. Each link contains a connection to
another link. Linked list is the second most-used data structure after array. Following are the
important terms to understand the concept of Linked List.
Linked List
Link − Each link of a linked list can store a data called an element.
Next − Each link of a linked list contains a link to the next link called Next.
LinkedList − A Linked List contains the connection link to the first link called First.
Linked List Representation

Linked list can be visualized as a chain of nodes, where every node points to the next node.
As per the above illustration, following are the important points to be considered.
Linked List contains a link element called first.
Each link carries a data field(s) and a link field called next.
Each link is linked with its next link using its next link.
Last link carries a link as null to mark the end of the list.
2.3 Memory Allocation in a Linked List
Node Creation
When creating a new node in a linked list, memory is allocated dynamically using heap memory. This
allocation process involves reserving a continuous block of memory in heap that is large enough to store
two key components:
1. The data element of the node
2. A pointer to the next node
For example, if we’re creating a linked list of alphabets/characters, each node would typically require
memory for:
 An ASCII character value (usually 4 bytes)
 A pointer to the next node (usually 4 or 8 bytes, depending on the system architecture. Let’s assume that
this is a 32 bit system and 4 bits are required for storing pointer/reference address to the next node).
When a new node is created, the system allocates this continuous block of memory (in this case, 8 bytes or
two slots of memory) on the heap. Initially, the address of the next node is set to null. In memory
terms, null is represented by an invalid memory address (often 0x0 or 0), indicating that the current node is
not pointing to any other node yet. Below is how the newly created node looks like in memory:
# Node class to store data and link to the next node
class Node:
def __init__(self, data):
# Initialize the node with given data
self.data = data
# Set the next pointer to None initially
self.next = None
# We need to create the nodes first before linking them

node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")
Linking Nodes
In the previous step, we looked at how we can allocate and fill memory required for each node. Now we
can start connecting them to form a linked list. This process involves setting the “next” pointer of each node
to the memory address of the subsequent node in the list. Let’s first connect node As next pointer to node Bs
address by using the expression node1.next = address of node2:
Now, address of A (103) is stored as the head node of the linked list. Using this address we can access all
the linked list nodes and perform all linked list operations. In the memory layout, although the sequence of
linked list nodes is D, A, B, C, since we start from head node address (103), the sequence depends on how
each node is linked, irrespective of how those nodes are arranged in the memory slots.
Below is how we programmatically link linked list nodes:
node1.next = node2 # A->B
node2.next = node3 # B->C
node3.next = node4 # C->A
# node1 is the head node in the linked list

head = node1 # Node A
Types of Linked List

Following are the various types of linked list.
Simple Linked List − Item navigation is forward only.
Doubly Linked List − Items can be navigated forward and backward.
Circular Linked List − Last item contains link of the first element as
next and the first element has a link to the last element as previous.
Basic Operations
Following are the basic operations supported by a list
Insertion − Adds an element at the beginning of the list.
Deletion − Deletes an element at the beginning of the list.
Display − Displays the complete list.
Search − Searches an element using the given key
Delete − Deletes an element using the given key.
2.4 Types of Linked Lists

Depending on the number of pointers in a node or the purpose for which the pointers are
maintained, a linked list can be classified into various types such as
 singly-linked list
 circular-linked list
 doubly-linked list
2.5 What is Linked List in Python

A linked list is a type of linear data structure similar to arrays. It is a collection of nodes that
are linked with each other. A node contains two things first is data and second is a link that
connects it with another node. Below is an example of a linked list with four nodes and each
node contains character dataand a link to another node. Our first node is where head points
and we can access all the elements of the linked list using the head.
Creating a linked list in Python

In this LinkedList session, we will use the Node class to create a linked list. In thisclass, we
have an __init__ method that initializes the linked list with an empty head. Next, we have
created an insertAtBegin() method to insert a node at the beginning of the linked list, an
insertAtIndex() method to insert a node at the given index of the linked list, and
insertAtEnd() method inserts a node at the end of the linked list. After that, we have the
remove_node() method which takes the data as an argument to delete that
node. In the remove_node() method we traverse the linked list if a node is present equal
to data then we delete that node from the linked list. Then we havethe sizeOfLL() method
to get the current size of the linked list and the last method of the LinkedList class is printLL()
which traverses the linked list and prints the data of each node.
Creating a Node Class

We have created a Node class in which we have defined a __init__ function to initialize the
node with the data passed as an argument and a reference with None because if we have only
one node then there is nothing in its reference.
class Node:
def init (self, data):

self.data = data
self.next = None
Insertion in Linked List

Insertion at Beginning in Linked List
This method inserts the node at the beginning of the linked list. In this method,we create a
new_node with the given data and check if the head is an emptynode or not if the
head is empty then we make the new_node as head and return else we
insert the head at the next new_node and make the head equal to new_node.
def insertAtBegin(self, data):

new_node = Node(data)
if self.head is None:
self.head = new_node
return
else:
new_node.next = self.head
Insert a Node at a Specific Position in a Linked List

This method inserts the node at the given index in the linked list. In this method, we create a
new_node with given data , a current_node that equals to the head, and a counter ‘position’
initializes with 0. Now, if the index is equalto zero it means the node is to be inserted
at begin so we called insertAtBegin() method else we run a while loop
until the current_node is not equal to None or (position+1) is not equal to the index we have
to at the one position back to insert at a given position to make the linking of nodes and in each
iteration, we increment the position by 1 and make the current_node next of it. When the loop
breaks and if current_node is not equal to None we insert new_node
at after tothe current_node. If current_node is
equal to None it means that the index is not present in the list and we print “Index not present”.
# Indexing starts from 0.
def insertAtIndex(self, data, index):

current_node = self.head
position = 0
if position == index:
self.insertAtBegin(data)
else:
while(current_node != None and position+1 != index):
position = position+1
current_node = current_node.next
if current_node != None:
new_node.next = current_node.next
current_node.next = new_node
else:
print("Index not present")
Insertion in Linked List at End

This method inserts the node at the end of the linked list. In this method, we create a new_node
with the given data and check if the head is an empty nodeor not if the head is
empty then we make the new_node as head and return else we make a
current_node equal to the head traverse to the last node of the linked list and when we get
None after the current_node the while loop breaks and insert the new_node in the next of
current_node which is the last node of linked list.
def inserAtEnd(self, data):
return
while(current_node.next):
current_node.next = new_node
Update the Node of a Linked List

This code defines a method called updateNode in a linked list class. It is used to update the value
of a node at a given position in the linked list
# Update node of a linked list

# at given position
def updateNode(self, val, index):

position = 0
current_node.data = val
else:
while(current_node != None and position != index):
current_node.data = val
else:
Delete Node in a Linked List
Remove First Node from Linked List
This method removes the first node of the linked list simply by making thesecond node head
of the linked list.
def remove_first_node(self):
if(self.head == None):
return
self.head = self.head.next
Remove Last Node from Linked List

In this method, we will delete the last node. First, we traverse to the second last node using
the while loop, and then we make the next of that
node None and last node will be removed.
def remove_last_node(self):
return
while(current_node.next.next):
Deletecurrent_node.next = None
a Linked List Node at a given Position
In this method, we will remove the node at the given index, this method is similar to the
insert_at_inded() method. In this method, if the head is None we simply return else
We initializea current_node with self.head and position with 0. If the position is equal to the
index we called the remove_first_node() method else we traverse to the one node before that
we want to remove using the while loop. After that whenwe out of the while loop we check
that current_node is equal to None if not then we make the next of current_node equal to the
next of node that we wantto remove else we print the message “Index not
present” because current_node is equal to None. if not
then we make the next of current_node equal to the next of node that we wantto remove
else we print the message “Index not present” because current_node is equal
to None.
# Method to remove at given index
def remove_at_index(self, index):
if self.head == None:
return
position = 0
self.remove_first_node()
else:
while(current_node != None and position+1 != index):
Delete a Linkedcurrent_node.next
List Node of a given Data
= current_node.next.next
else:
This method removes the node with the given data from the linked list. In this method, firstly we
made a current_node equal to the head
print("Index and run a while loop to
not present") traverse the linked
list. This while loop breaks when current_node becomes None or the data next to the
current node is equal to the data given in the argument. Now, After coming out of the loop if the
current_node is equal to None it means that the node is not present in the data and we just return,
and if the data next to the current_node is equal to the data given then we remove that node by
making next of that removed_node to the next of current_node. And this is implemented using the
if else condition.
def remove_node(self, data):
while(current_node != None and current_node.next.data != data):

if current_node == None:
return
else:
current_node.next = current_node.next.next
Linked List Traversal in Python
This method traverses the linked list and prints the data of each node. In this
method, we made a current_node equal to the head and iterate through the
linked list using a while loop until the current_node become None and print
the data of current_node in each iteration and make the current_node next
toit.
def printLL(self):
while(current_node):
print(current_node.data)
Get Length of a Linked List in Python

This method returns the size of the linked list. In this method, we have initialized a counter ‘size’
with 0, and then if the head is not equal to None wetraverse the linked list using a while loop and
increment the size with 1 in each iteration and return the size when current_node becomes None
else wereturn 0.
def sizeOfLL(self):
size = 0
if(self.head):
size = size+1
return size
else:
return 0
Example of the Linked list in Python
In this example, After defining the Node and LinkedList class we have created a linked list named
“llist” using the linked list class and then insert four nodeswith character data ‘a’, ‘b’, ‘c’, ‘d’ and
‘g’ in the linked list then we print the linked list using printLL() method linked list class after that
we have removed some nodes using remove methods and then print the linked list again and wecan
see in the output that node is deleted successfully. After that, we also print the size of the linked list.
Python3
# Create a Node class to create a node

class Node:
def init (self, data):
self.data = data
self.next = None
# Create a LinkedList class
class LinkedList:
def init (self):

self.head = None
# Method to add a node at begin of LL

def insertAtBegin(self, data):
return
else:
# Method to add a node at any index

# Indexing starts from 0.
def insertAtIndex(self, data, index):

position = 0
if position == index: self.insertAtBegin(data)
else:
while(current_node != None and position+1 !=
index):position = position+1
if current_node != None: new_node.next =

current_node.nextcurrent_node.next =
new_node
else:
print("Index not present") # Method to add a
node at the end of LL
def insertAtEnd(self, data):new_node = Node(data)
if self.head is None: self.head = new_nodereturn
while(current_node.next): current_node =
current_node.next
current_node.next = new_node# Update node of a
linked list
# at given position
def updateNode(self, val, index):current_node =
self.head position = 0
if position == index: current_node.data = val
else:
while(current_node != None and position !=
if current_node != None: current_node.data = val
else:
# Method to remove first node of linked list
def remove_first_node(self):
return
self.head = self.head.next
# Method to remove last node of linked list

def remove_last_node(self):
return
while(current_node.next.next): current_node =
current_node.next
current_node.next = None
# Method to remove at given index

def remove_at_index(self, index):
return
current_node = self.headposition = 0
if position == index: self.remove_first_node()
else:
while(current_node != None and position+1 !=
else:
# Method to remove a node from linked list

def remove_node(self, data):current_node = self.head
while(current_node != None and

current_node.next.data != data):current_node =
current_node.next
if current_node == None:
returnelse:
# Print the size of linked list

def sizeOfLL(self):size = 0 if(self.head):
while(current_node):size = size+1
return size
else:
return 0
# print method for the linked list

def printLL(self): current_node = self.head
print(current_node.data) current_node =
current_node.next
# create a new linked list llist = LinkedList()
# add nodes to the linked list llist.insertAtEnd('a')

llist.insertAtEnd('b') llist.insertAtBegin('c')
llist.insertAtEnd('d') llist.insertAtIndex('g', 2)
# print the linked list print("Node Data") llist.printLL()

# remove a nodes from the linked list print("\nRemove First
Node") llist.remove_first_node() print("Remove Last Node")
llist.remove_last_node() print("Remove Node at Index 1")
llist.remove_at_index(1)
# print the linked list again

print("\nLinked list after removing a node:")
llist.printLL()
print("\nUpdate node Value")

llist.updateNode('z', 0)
llist.printLL()
print("\nSize of linked list :", end=" ")

Output:
print(llist.sizeOfLL())
Node Data
c
a
g
b
d
Remove First Node

Remove Last Node
Remove Node at Index 1
Linked list after removing a node:

a
Update node Value

z
b
Size of linked list : 2
What is Circular Linked List?
A circular linked list is a type of data structure where each node points to the next node, and the last
node points back to the first, forming a circle.
This setup allows for an endless cycle of node traversal, which can be particularly useful in
applications where the end of the list naturally reconnects to the beginning.
For example, in computer applications that manage resources in a loop or in creating playlists where
the last song leads back to the first song, a circular linked list offers a seamless way to cycle through
items without the need for complex logic to manage the end of the list.
Structure of Circular Linked List

A circular linked list in data structure is a variation of the linked list where the last node points back to
the first node, making the list circular:
1. Node
Each element in the list is contained in a "node." The structure of a node in a circular linked list
includes:
 Data: This field holds the actual value that the node represents. This could be any type of data,
such as an integer, a string, or even a complex object.
 Next Pointer: Unlike in a singly linked list where the last node's next pointer is null, in a
circular linked list, the last node's next pointer points back to the first node, creating a loop.
2. Head
The head is a pointer or reference to the first node in the list. It serves as the entry point for any
traversal or modification operation on the list. In a circular linked list, even if you traverse all the way
through, you will end up at the head again if you continue to follow each node’s next pointer.
Circular Linked List in Python

class Node:
def __init__(self, value):
self.value = value # Data stored in the node
self.next = self # Initially pointing to itself
# Example of creating a new node
new_node = Node(10)
In each of these examples, the node is initially set to point to itself, which is a characteristic setup for
circular linked lists, especially when the list starts with a single node. This self-referencing setup
makes it simpler to expand the list by adjusting the next pointers as new nodes are added.
Types of Circular Linked List

Circular linked lists can be categorized primarily into two types based on how nodes are linked:
1. Singly Circular Linked List
2. Doubly Circular Linked List
Doubly circular linked list
Circular Linked List

A circular linked list is a type of linked list in which the first and the last nodes are also connected to
each other to form a circle.
There are basically two types of circular linked list:
1. Circular Singly Linked List
Here, the address of the last node consists of the address of the first node.
In a singly circular linked list, each node contains a single pointer that points to the next node in the
sequence. The unique aspect of this structure is that the last node in the list points back to the first
node, forming a circle. This setup allows for continuous, end-to-end traversal of the list.
Circular Linked List Representation

Advantages: Simple to implement, uses less memory per node (one pointer).
Use Cases: Suitable for applications where the list needs to be traversed in only one direction, such as
implementing a round-robin scheduler or a cyclic queue where entries are processed in a continuous
loop.
2. Circular Doubly Linked List

Here, in addition to the last node storing the address of the first node, the first node will also store the
address of the last node.
Doubly circular linked lists enhance the singly circular linked list by adding an additional pointer in
each node. This second pointer links each node to its previous node, as well as to its next node,
forming a two-way link.
Circular Doubly Linked List Representation
Here, both the head and the tail are interconnected, creating a seamless circular navigation system.
Advantages: Allows both forward and backward traversal, making it easier to navigate and modify the
list. Useful for more complex data structures where nodes might need to be removed or added
frequently and from different positions.
Use Cases: Ideal for applications requiring bidirectional traversal, such as a playlist that allows
playing the next or previous media file, or implementing advanced navigation systems in software
applications.
Representation of Circular Linked List

Let's see how we can represent a circular linked list on an algorithm/code. Suppose we have a linked
list:
Insertion on a Circular Linked List

We can insert elements at 3 different positions of a circular linked list:
1. Insertion at the beginning
2. Insertion in-between nodes
3. Insertion at the end
Suppose we have a circular linked list with elements 1, 2, and 3.
Initial circular linked list

Let's add a node with value 6 at different positions of the circular linked list we made above. The first
step is to create a new node.
 allocate memory for newNode
 assign the data to newNode
New node
1. Insertion at the Beginning

 store the address of the current first node in the newNode (i.e. pointing the newNode to the
current first node)
 point the last node to newNode (i.e making newNode as head)
Insert at the beginning
2. Insertion in between two nodes

Let's insert newNode after the first node.
 travel to the node given (let this node be p)
 point the next of newNode to the node next to p
 store the address of newNode at next of p
Insertion at a node
3. Insertion at the end

 store the address of the head node to next of newNode (making newNode the last node)
 point the current last node to newNode
 make newNode as the last node
Insert at the end
Deletion on a Circular Linked List

Suppose we have a double-linked list with elements 1, 2, and 3.
Initial circular linked list
1. If the node to be deleted is the only node

 free the memory occupied by the node
 store NULL in last
2. If last node is to be deleted
 find the node before the last node (let it be temp)
 store the address of the node next to the last node in temp
 free the memory of last
 make temp as the last node
Delete the last node

3. If any other nodes are to be deleted
 travel to the node to be deleted (here we are deleting node 2)
 let the node before node 2 be temp
 store the address of the node next to 2 in temp
 free the memory of 2
Delete a specific node
Circular Linked List Implementation in Python

class Node:
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def append(self, data):
if not self.head:
self.head = Node(data)
self.head.next = self.head
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
def print_list(self):
current = self.head
while current:
print(current.data, end=" ")
if current == self.head:
break
print()
# Example usage
cllist = CircularLinkedList()
cllist.append(1)
cllist.append(2)
cllist.append(3)
cllist.print_list() # Output: 1 2 3
Circular Linked List Code in Python
Class: Circular Linked List
We will use nodes created by the previous class to implement a circular linked list. It will contain one
head node, one count member, and multiple methods for specific tasks.
class CLL:
def __init__(self):
self.head = None
self.count = 0
def __repr__(self):
string = ""
string += "Circular Linked List Empty"
return string
string += f"Circular Linked List:\n{self.head.data}"

temp = self.head.next
while(temp != self.head):
string += f" -> {temp.data}"
temp = temp.next
return string

self.insert(data, self.count)
return
def insert(self, data, index):

if (index > self.count) | (index < 0):
raise ValueError(f"Index out of range: {index}, size: {self.count}")
self.head = Node(data)
self.count += 1
return
temp = self.head
for _ in range(self.count - 1 if index - 1 == -1 else index - 1):
temp = temp.next
aftertemp = temp.next #New node goes between temp and aftertemp

temp.next = Node(data)
temp.next.next = aftertemp
if(index == 0):
self.head = temp.next
self.count += 1
return
def remove(self, index):
if (index >= self.count) | (index < 0):
raise ValueError(f"Index out of range: {index}, size: {self.count}")
if self.count == 1:
self.head = None
self.count = 0
return
before = self.head
for _ in range(self.count - 1 if index - 1 == -1 else index - 1):
before = before.next
after = before.next.next
before.next = after
if(index == 0):
self.head = after
self.count -= 1
return
def index(self, data):

temp = self.head
for i in range(self.count):
if(temp.data == data):
return i
temp = temp.next
return None
def size(self):
return self.count
def display(self):
print(self)
Advantages of Circular Linked Lists:

1. Efficient Operations: Circular linked lists can provide efficient operations for certain
scenarios. Insertion and deletion at the beginning and end of the list can be done in constant
time O(1) since there is no need to traverse the entire list.
2. Circular Structure: The circular structure allows for easy traversal from the end of the list to
the beginning, making it useful in applications where circular behavior is required, such as
round-robin scheduling or cyclic buffer implementations.
3. Memory Efficiency: Circular linked lists can be memory-efficient compared to other data
structures like arrays, as they can dynamically allocate memory for each element without
needing contiguous memory blocks.
4. Infinite Looping: Circular linked lists can be used to create infinite loops or cyclic patterns,
where the last node’s next pointer points back to the first node. This property can be
leveraged in certain algorithms and applications.
5. The NULL assignment is not required because a node always points to another node.
6. The starting point can be set to any node.
7. Traversal from the first node to the last node is quick.
Disadvantages of Circular Linked Lists:

1. Doubly linked lists consume more memory compared to singly linked lists, as they require an
additional pointer (previous) per node.
2. The implementation of doubly linked lists is more complex than that of singly linked lists,
which may lead to increased development time and potential bugs.
3. Traversing the list in both directions requires additional memory accesses and comparisons,
which may result in a slightly slower performance compared to singly linked lists for certain
operations.
4. The overhead of maintaining the previous pointers adds complexity and additional memory
usage to the operations, especially during insertion and deletion.
Applications:
Circular linked lists find applications in various scenarios, including:
1. Implementing a playlist in media players.
2. Managing processes in operating systems.
3. Simulation of round-robin scheduling algorithms.
4. Computer Networking: Circular linked lists are used in networking, particularly in
implementing algorithms for token ring networks where each computer on a network is given
a chance to transmit data in a pre-defined, circular order.
5. Operating Systems: Many operating systems use circular linked lists for various
management tasks, including scheduling algorithms like round-robin scheduling. This method
cycles through processes, allocating CPU time one by one in a fair and cyclic manner.
6. Multiplayer Games: In games that involve multiple players, circular linked lists can manage
player turns in a loop. After the last player takes a turn, the system automatically goes back to
the first player.
7. Music Players: Media players often use circular linked lists to manage playlists, especially in
'repeat' mode. When the playlist reaches the end, it loops back to the beginning seamlessly.
8. User Interface: Circular linked lists are used in applications with a circular carousel of items,
such as image sliders or navigation menus that loop back to the beginning after reaching the
end.
9. Resource Allocation: They are also used in managing resources in an environment where the
resources need to be used cyclically, such as allocating CPU or memory resources in a
circular manner to various processes.
Doubly Linked List
A doubly linked list is a type of data structure where each element, known as a node, holds data and
two references: one pointing to the next node and one pointing to the previous node. This two-way
linking allows for movement in both directions through the list, making it more versatile than a singly
linked list which only allows movement in one direction.
The importance of doubly linked lists in data structures and algorithms (DSA) lies in their ability to
facilitate quicker and more flexible modifications—such as insertions and deletions—not just at the
ends of the list, but also in the middle.
Example of Doubly Linked List
The doubly linked list in data structure is particularly beneficial in applications where the ability to
navigate backwards is as necessary as moving forwards.
For example, in navigation systems like web browsers, a doubly linked list can manage the user's
history, allowing easy forward (redo) and backward (undo) movements through previously visited
pages.
This example illustrates how doubly linked lists support complex sequence data management in
practical software solutions, enhancing user interface responsiveness and functionality.
Structure of a Doubly Linked List
Node:
Each node in a doubly linked list includes:
 Data: The actual information held within the node, which could be numbers, strings, or any
other data type.
 Next Pointer: A reference to the next node in the list, which helps in traversing the list forward.
 Prev Pointer: A reference to the previous node in the list, which facilitates backward traversal.
How It Works?
 Head and Tail: The list has two special nodes, the head and the tail. The head points to the first
element of the list, while the tail points to the last element. These pointers enhance operations
such as adding or removing elements at the ends of the list.
 Traversal: You can start from the head to move forward through the list or from the tail to move
backward, making it versatile for various operations that require scanning the list in either
direction.
 Insertions and Deletions: Adding or removing nodes can be done efficiently at any point in the
list. When inserting or deleting a node, pointers from adjacent nodes are updated to maintain
the list’s integrity without needing to shift elements as in contiguous data structures
like array
class Node:
self.item = data
self.next = None
self.prev = None
The item variable will store the actual element of the node. The next stores the address to the
next node, while prev stores the address to the previous node in the doubly linked list.
In the next step, we will create a doublyLinkedList class, that contains different functions to
insert, delete and display elements of doubly linked list.
class doublyLinkedList:
def __init__(self):
self.start_node = None
Difference Between Singly and Doubly Linked List

Let’s know about the difference between singly linked list and doubly linked list:
Feature Singly Linked List Doubly Linked List
Only forwards. You can Both forwards and backwards. You can
Direction of Traversal traverse from the head to the traverse from the head to the tail and vice
end of the list. versa.
Less memory per node (one More memory per node (two pointers per
Memory Usage
pointer per node). node).
Efficient at the beginning; Efficient at both the beginning and the

Insertions/Deletions requires traversal from the end; easier insertions and deletions in the
head for other positions. middle without full traversal.
Simpler and requires less code More complex due to additional pointers,
Complexity to manage compared to doubly requiring more management and care in
linked lists. code.
Suitable when memory is a Preferred when frequent operations

Use Case concern and only forward require elements to be accessed from both
traversal is needed. ends.
Typically slower for
Faster for operations involving the end of
Operations operations that involve
the list due to the tail pointer.
elements at the end of the list.
Both head and tail pointers are used,

Head and Tail
Only head pointer is used. providing immediate access to both ends
Management
of the list.
Advantages of Doubly Linked Lists

 Bidirectional Navigation: Allows traversal in both forward and backward directions,
facilitating easier and more flexible data manipulation.
 Easier Insertion and Deletion: Nodes can be added or removed from both ends and the middle
of the list without needing to traverse the entire list, especially if the tail pointer is maintained.
 Efficient Operations at Both Ends: Adding or removing elements at the beginning and the end
is efficient because both head and tail pointers provide direct access to the endpoints of the
list.
 Dynamic Size: The size of the list can increase or decrease dynamically, which is efficient for
memory usage since it allocates space only as needed.
Disadvantages of Doubly Linked Lists
 Increased Memory Usage: Each node requires extra memory for an additional pointer
(previous pointer), which can be significant in memory-constrained environments.
 Complexity: Managing two pointers (next and prev) per node increases the complexity of the
operations, making the code more prone to errors such as memory leaks and pointer
corruption.
 Slower Individual Operations: The overhead of maintaining an extra pointer can slightly slow
down operations compared to singly linked lists, as more pointer operations are required.
 Overhead in Memory Management: More complex memory management is needed,
especially in languages that do not handle garbage collection automatically, due to the
additional pointers that need to be correctly handled during insertions and deletions
Uses and Applications of Doubly Linked List
Doubly linked lists find a wide range of applications in software development and system design due
to their ability to efficiently add, remove, and access elements from both ends:
 Navigation Systems: Doubly linked lists are ideal for applications where users need to navigate
both forward and backward, such as web browsers or document viewers.
 Music Players: In media playback software, doubly linked lists can manage playlists where
users might want to go to the next or previous track. This allows for seamless navigation
through the playlist.
 Undo Functionality in Applications: Many applications like text editors or graphic design
software use doubly linked lists to implement undo and redo functionalities. Each node in the
list could represent a state of the work, and navigating through the nodes allows users to undo
or redo changes in their projects.
 Gaming: In gaming, doubly linked lists can be used to manage various game states or the
inventory of items that players can cycle through both forward and backward.
 Implementing Other Data Structures: Doubly linked lists are also used to implement more
complex data structures like deque (double-ended queue) which requires adding and
removing items from both ends efficiently.
 Memory Management: In systems programming, doubly linked lists can be used to keep track
of free memory blocks or resources. This allows the system to efficiently allocate and
deallocate resources by adjusting pointers rather than moving memory blocks.
Doubly Linked List Operations

Operations on doubly linked lists in data structures are more versatile compared to singly linked
lists due to their two-way linking of nodes:
1. Insertion
Inserting nodes into a doubly linked list can be done in several ways, each using the ability to access
nodes from both directions:
 At the Beginning: Add a new node at the start of the list. Set the new node's next pointer to the
current head of the list, and update the prev pointer of the existing head to point back to the
new node. Update the head pointer to the new node.
 At the End: Add a new node at the end. Traverse to the last node, set the next pointer of the last
node to the new node, and set the prev pointer of the new node to the last node. Update the
tail pointer if maintained.
 After a Given Node: To insert a node after a given node,adjust the next pointer of the new node
to the next pointer of the given node, update the next pointer of the given node to the new
node, and set the prev pointer of the node that follows the new node (if any) to the new node.
1. Inserting Items to Empty List
2. Inserting Items at the End
Inserting Items to Empty List
The most permissive way to insert an element in a doubly linked list is to insert the element in
the empty list. The following piece of code enters an element at the origin of the doubly linked
list:
def InsertToEmptyList(self, data):
if self.start_node is None:
self.start_node = new_node
else:
print("The list is empty")
Inserting Items at the End

Inserting an element at the end of the doubly linked list is slightly alike to inserting an element at
the start of the list. Before entering the elements, we need to verify and check if the doubly
linked list is empty. If the list is empty then we can easily use the function InsertToEmptyList()
method to insert the element to the list. If the list already has added element, we iterate through
the list till the address to the next node reaches NULL. When the next node address becomes
NULL, it denotes that the current node is the last node.
The previous reference for the new node is set to the last node, and the next address for the last
node is assigned to the newly inserted node. The function for inserting an item at the last node is
as follows:
# Insert element at the end
def InsertToEnd(self, data):
# Check if the list is empty
return
n = self.start_node
# Iterate till the next reaches NULL
while n.next is not None:
n = n.next
n.next = new_node
new_node.prev = n
2. Deletion
Removing nodes requires adjustment of pointers from both the preceding and succeeding nodes:
 From the Beginning: Remove the head node by updating the head to the second node and
setting the prev pointer of the new head to null.
 From the End: Remove the tail node by setting the next pointer of the second last node to null
and updating the tail to this second last node.
 A Specific Node: Disconnect the node by adjusting the next pointer of the preceding node to
point to the node after the target node, and adjust the prev pointer of the succeeding node
likewise.
3. Deleting Elements from the Start

4. Deleting Elements from the End
Deleting Elements from the Start
The most natural way to delete an element from a doubly linked list is deleting from the start of
the list. In order to achieve this, we will assign the value of the start node to the next node and
then assign the previous address of the start node to NULL. But before doing this, we need to
check two things. First, we need to check if the list is empty. And then we have to verify if the
list has only one node or not. If the list has only one element then we can easily assign the start
node to NULL. The following code can be utilised to delete node from the start of the doubly
linked list.
# Delete the elements from the start

def DeleteAtStart(self):
print("The Linked list is empty, no element to delete")
return
if self.start_node.next is None:
return
self.start_node = self.start_node.next
self.start_prev = None;
Deleting Elements from the End

To remove the element from the end, we have to again verify if the list is empty or if the list has
a single element. If the list has a single element, we will assign the start node to NULL. If the
doubly linked list has more than one element, we traverse through the list until the last node
reaches NULL. Once we reach the last node, we assign the next address of the node previous to
the last node, to NULL which actually deletes the last node. The following function can be used
to delete the element from the end of the list.
# Delete the elements from the end

def delete_at_end(self):
# Check if the List is empty
return
return
n = self.start_node
n = n.next
n.prev.next = None
3. Search
Searching involves traversing through the list either from the head or the tail, depending on proximity
and potentially the direction of traversal that may optimize the search:
 Search by Value: Start from the head (or tail) and traverse through the next (or prev) pointers to
find the node containing the desired value.
4. Traversal
Traversal can be performed in both directions, which is a significant advantage of doubly linked lists:
 Forward Traversal: Start from the head and move through each node using the next pointers.
 Backward Traversal: Start from the tail (if available) and move through each node using the
prev pointers.
Traversing the Linked List
Display the elements in the doubly linked list, while iterating through each element.
# Traversing and Displaying each element of the list

def Display(self):
return
else:
n = self.start_node
while n is not None:
print("Element is: ", n.item)
n = n.next
print("\n")
5. Update
Updating the value of a node can be performed directly once the node is accessed, without any
specific need for traversal if the node reference is already known.
Complete python code of Doubly Linked List
# Initialise the Node

class Node:
self.item = data
self.next = None
self.prev = None
# Class for doubly Linked List
class doublyLinkedList:
def __init__(self):
# Insert Element to Empty list
def InsertToEmptyList(self, data):
else:
# Insert element at the end
def InsertToEnd(self, data):
# Check if the list is empty
return
n = self.start_node
# Iterate till the next reaches NULL
n = n.next
n.next = new_node
new_node.prev = n
# Delete the elements from the start
def DeleteAtStart(self):
return
return
self.start_node = self.start_node.next
self.start_prev = None;
# Delete the elements from the end
def delete_at_end(self):
# Check if the List is empty
return
return
n = self.start_node
n = n.next
n.prev.next = None
# Traversing and Displaying each element of the list
def Display(self):
return
else:
n = self.start_node
while n is not None:
print("Element is: ", n.item)
n = n.next
print("\n")
# Create a new Doubly Linked List
NewDoublyLinkedList = doublyLinkedList()
# Insert the element to empty list
NewDoublyLinkedList.InsertToEmptyList(10)
# Insert the element at the end
NewDoublyLinkedList.InsertToEnd(20)
# Display Data
NewDoublyLinkedList.Display()
# Delete elements from start
NewDoublyLinkedList.DeleteAtStart()
# Delete elements from end
NewDoublyLinkedList.DeleteAtStart()
# Display Data
NewDoublyLinkedList.Display()
Implement Doubly Linked List in Python

class Node:
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
if not self.head:
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
new_node.prev = last_node
def print_list(self):
current = self.head
while current:
print(current.data, end=" ")
print()
# Example Usage
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)
dll.print_list() # Output: 10 20 30
Applications
 A music player that has next and previous buttons, like the concept of doubly linked list you’ll
have functionality to go back and the next element. .
 Undo Redo operations that we discussed at the beginning of the article.
 The browser cache functionality in common web browsers like Chrome, Microsoft edge, which
allows us to move front and back within pages is also a great application of a doubly linked
list.
 LRU cache, also Most Recently Used is also an instance of DLL.
 A deck of cards in a game is a perfect example of the applicability of DLL. It is additionally
utilized to store the state of the game during play.

Dsa Unit 1 & 2

Uploaded by

Copyright:

Available Formats

Dsa Unit 1 & 2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Dsa Unit 1 & 2

Uploaded by

Copyright:

Available Formats

DATA STRUCTURES AND ALGORITHMS

SEM -I (IT 12)

Adv. MohammadAli Shaikh

MohammadAli Shaikh DSA-IT12 1|Page

Algorithm: A finite sequence of steps for accomplishing some computational task.

• Terminate after finitely many steps.

built-in data types.

Derived Data Type

Data Definition defines a particular data with the following characteristics.

Traceable − Definition should be able to be mapped to some data element.

Accurate − Definition should be unambiguous.

Clear and Concise − Definition should be understandable.

Data Object represents an object having a data.

of data. There are two data types −

 Built-in Data Type

Non Linear Data Structure

The data elements are not arranged in sequential structure.

An algorithm must follow the mentioned below characteristics:

 Input: An algorithm must have 0 or well defined inputs.

 Search − Algorithm to search an item in a data structure.

Following are the important terms to understand the concept of Array.

 Traverse − print all the array elements one by one.

An array is a collection of elements of the same type placed in contiguous

memory locations that can be individually referenced by using an index to

An array can be initialized in two ways.

 By declaring and initializing it simultaneously. int arr [] = { 10, 20, 30, 40 }

 An array holds elements that have the same data type

 One dimensional (1-D) arrays or Linear arrays.

Multi-dimensional arrays can be described as ‘arrays of arrays’. A multi-dimensional array

Two dimensional Arrays

The syntax of declaring a two-dimensional array in C is as follows:

data_type array_name [row_size][column_size];

Below are some applications of arrays.

Below are some real-time applications of arrays.

 Arrays are used to implement vectors, and lists in C++ STL.

 Arrays are used as the base of all sorting algorithms.

 Arrays are used to implement other DS like a stack, queue, etc.

 Graphs are also implemented as arrays in the form of an adjacency matrix.

 Implementing dynamic programming algorithms: Dynamic programming

 In structures, object instantiation is possible whereas in arrays objects are not

Sparse Matrix and its representations

Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes

2. Linked list representation

 Column: Index of column, where non-zero element is located

 Value: Value of the non zero element located at index – (row,column)

# assume a sparse matrix of order 4*5

# let assume another matrix compactMatrix

# number of columns in compactMatrix(size) should

# be equal to number of non-zero elements in sparseMatrix

compactMatrix = [[0 for i in range(cols)] for j in range(rows)]

# This code is contributed by MRINALWALIA

 Column: Index of column, where non-zero element is located

 Value: Value of the non zero element located at index – (row,column)

 Next node: Address of the next node

// C++ program for sparse matrix representation.

// Using Link list

// Node class to represent link list

// Function to create new node

int col_index, int x)