MALLA REDDY UNIVERSITY

L-T-P-C 3-0-1-4
MR22-1CS0105

Lecture Notes
Data Structures and Its Applications

UNIT – I
Data Structures: Introduction, Difference between data type and data structure, Need
of Data structure, Classification of Data structures, Linear vs. Non-linear Data
Structures.
Types of Data Structures in Python: Built-in and user-defined data structures.
Static Linear Data Structure: Arrays- Characteristics of an Array, Applications of Arrays.
Arrays vs.List.
Searching: Linear Search, Binary search. Sorting: Merge Sort, Bubble Sort, Selection
Sort and Quick Sort.

UNIT – II
Dynamic Linear Data Structure: Stacks, Stack operations, Characteristics of a Stacks,
Applications of Stacks.
Dynamic Linear Data Structure: Queues, Characteristics of a Queues, Circular Queues,
Applications of Queue.

UNIT - III
Dynamic Linear Data Structure: Linked List, Characteristics of a Linked List, Types of
Linked List:
Singly linked, doubly linked and circular. Applications of Linked List.
Implementation of stacks and queue using linked list.
UNIT – IV
Non-linear Data Structure: Trees, Tree Terminologies, Characteristics of a Trees,
Operations on Binary Trees and Binary Search Trees: find, insert and delete.
Tree traversal techniques: Inorder, Preorder, Postorder Traversal, Applications of Trees.

UNIT -V
Non-linear Data Structure: Graphs, Characteristics of a Graphs,
Graph Traversals: Breadth First Search, Depth First Search, Applications of Graphs.

REFERENCE BOOKS:

1. Data structures and algorithms in python by Michael t. Goodrich

2. Data Structures and Algorithmic Thinking with Python by Narasimha Karumanchi
3. Python for Data Analysis by William McKinney, Second Edition, O’Reilly Media Inc
4. Data Structures using Python by Dr Shriram K. Vasudevan, Mr Abhishek S.
Nagarajan, and Prof. Karthick Nanmaran
Data Structure:

Organizing, managing and storing data is important as it enables easier access

and efficient modifications. Data Structures allows you to organize your data in
such a way that enables you to store collections of data, relate them and perform
operations on them accordingly.

Data Types

A Data Type in a programming language is a set of data with predefined rules.

 Examples : Integer, Floating point, Character, String etc.,
A Data type reduces the coding effort. Python provides various standard data
types that define the storage method on each of them.
There are six standard data types in python.
 1 Numeric or Numbers (int, float, complex)
 2 Sequence (list, tuple, string, range)
 3 Boolean
 4 Set
 5 Dictionary - Mapping type
 6 Binary and None (Memory view, byte array, bites, None)

Numbers
Python supports three different numerical types
 1 Integer (signed integers)
 2 Float (floating point real variables)
 3 Complex (complex variables)
All integers in python are represented as long integers, hence no separate long
int data type in python.
Ex: a = 5, b = 25.5, c = 2+3i

Strings

Strings in Python are identified as a continuous set of characters represented in

quotation marks, either single, double or triple. In the case of string handling,
the operator + is used to concatenate two strings as the operation
Ex: "hello"+" python" returns "hello python".
The operator * is known as a repetition operator as the operation "Python" * 2
returns 'Python Python'.

Boolean
The Python Boolean type is one of Python's built-in data types. It is used to
represent the truth value of an expression - True or False. It is denoted by a class
'bool'. True can be represented by any non-zero value or 'True' whereas false can
be represented by the 0 or 'False'.

Ex: a = 5, b=10, c=5

print(a==b) # False
print(a==c) # True

Data Structure:
Once we have data in variables, we need some mechanism to manipulate that
data for solving our problems. Data Structure is a specific way of storing and
organizing data, so that it can be used more effectively. Data Structure is used,
in general, for organizing, processing, retrieving and storing of data.
General data structures includes arrays, files, linked lists, stacks, queues, trees,
graphs and so on.
Data structures are the building blocks of programming languages.

Need for Data Structure

We need data structures nowadays because things are becoming complex and
the amount of data is increasing at a high rate. To handle a large amount of data,
high-speed processors are needed. Sometimes processors fail while dealing with
huge amounts of data. With the increase of data on a daily basis it becomes
difficult to search and find the particular data from the huge amount of data.
Sometimes multiple users are finding the data on web-server which slows down
the server and the user does not get the result. To resolve such issues, data
structures are used.

Advantages of Data Structures

Data Structures enable the storage of information on hard disks. They help to
manage large data sets for example databases, internet indexing services, etc.
Data Structures play an important role when someone wants to design
algorithms. Data Structures secure the data and can't be lost. One can use the
stored data in multiple projects and programs. It processes the data easily. One
can access the data anytime anywhere from the connected machine, for example,
a computer, laptop, etc.

In other way, by using Data Structures, we have

Efficiency: in terms of time and space
Reusability: Multiple users can access the data at a time and any number of
times
Abstraction: It hides the data i.e., user can't see the data but he can handle it
through interface

In addition to using data structures, it is crucial to select the best data structure
for each activity. A bad data structure selection could lead to slow runtimes or
unresponsive code. There are five things to think about while choosing a data
structure.
 What kind of information will be stored?
 How will that information be used?
 Where should data persist, or be kept, after it is created?
 What is the best way to organize the data?
 What factors should be taken into account while managing Memory and
storage reservations?

Data Types vs Data Structures

 Computer programming entirely revolves around data. Every business
logic is implemented on data, and an application's or project's functionality
is dependent on the flow of data. Organizing and storing the data for its
optimal usage and performing effective programming with a strong data
model is hence crucial.
 From the surface, both data type and data structure appear to be the same
thing, as both deal with the nature and organizing of data, but there is a
big difference between the two. One describes the type and nature of data,
while the other represents the collections in which that data can be stored
 The data type describes the type of information or value that is sent to a
variable in programming. The data type is basically a classification of data.
In computer programming, the data type helps the compiler to select a
proper machine representation of data.
 The implementation of data type is referred to as "abstract
implementation". This means, different programming languages provide
the definition of a data type in different ways. The data type does not store
any value, but it defines that which type of value can be stored in a variable
 A Data Structure is the collection that holds data which can be
manipulated and used in programming so that operations and algorithms
can be more easily applied. Thus, a data structure is a group of data types.
It is a collection of data on which certain types of operations can be
executed.
 The implementation of data structure is known as "concrete
implementation". It is because, the definition of a data structure is already
defined by the programming language. Data structures have the ability to
hold different types of data within a single object.
 Data structures suffer from the problem of time complexity.
 The most significant difference between a data type and a data structure
is that a data type is the representation of nature and type of data, whereas
a data structure is a collection that holds different types of data which can
be manipulated and used in programming so that different programming
logic and operations can be applied in an efficient manner.
A data structure is classified into two categories:

 Linear data structure

 Non-linear data structure

Now let's have a brief look at both these data structures. What is the linear data
structure?
A linear data structure is a structure in which the elements are stored
sequentially, and the elements are connected to the previous and the next
element. As the elements are stored sequentially, so they can be traversed or
accessed in a single run. The implementation of linear data structures is easier
as the elements are sequentially organized in memory. The data elements in an
array are traversed one after another and can access only one element at a time.
The types of linear data structures are Array, Queue, Stack, Linked List.

 Array: An array consists of data elements of a same data type. For

example, if we want to store the roll numbers of 10 students, so instead of
creating 10 integer type variables, we will create an array having size 10.
Therefore, we can say that an array saves a lot of memory and reduces the
length of the code.
 Stack: It is linear data structure that uses the LIFO (Last In-First Out)
rule in which the data added last will be removed first. The addition of data
element in a stack is known as a push operation, and the deletion of data
element form the list is known as pop operation.
 Queue: It is a data structure that uses the FIFO rule (First In-First Out).
In this rule, the element which is added first will be removed first. There
are two terms used in the queue front end and rear The insertion
operation performed at the back end is known as enqueue, and the
deletion operation performed at the front end is known as dequeue.
 Linked list: It is a collection of nodes that are made up of two parts, i.e.,
data element and reference to the next node in the sequence.

What is a Non-linear data structure?

A non-linear data structure is also another type of data structure in which the
data elements are not arranged in a contiguous manner. As the arrangement is
nonsequential, so the data elements cannot be traversed or accessed in a single
run. In the case of linear data structure, element is connected to two elements
(previous and the next element), whereas, in the non-linear data structure, an
element can be connected to more than two elements.

Trees and Graphs are the types of non-linear data structure.

Linear Data structures are of two types. 1) Static Data Structures
2) Dynamic Data Structures

 Static data structure has a fixed memory size. It is easier to access the
elements in a static data structure. The content of the data structure can
be modified but without changing the memory space allocated to it.
Example: Arrays
 In dynamic data structure, the size is not fixed. It's size can be randomly
updated during the runtime i.e., during the operations performed on it,
which may be considered efficient concerning to the memory (space) and
as well time complexity of the code.
Example: Queue, Stack
Advantages of Static Linear Data Structures
Fast access time: Static data structures offer fast access time because memory
is allocated at compile-time and the size is fixed. It is easier to access the
elements in a static data structure.
Predictable memory usage: Since the memory allocation is fixed at compile-
time, the programmer can precisely predict how much memory will be used by
the program, which is an important factor in memory-constrained environments.
Ease of implementation and optimization: Static data structures may be
easier to implement and optimize since the structure and size are fixed, and
algorithms can be optimized for the specific data structure, which reduces cache
misses and can increase the overall performance of the program.
Efficient memory management: Static data structures allow for efficient
memory allocation and management. Since the size of the data structure is fixed
at compile-time, memory can be allocated and released efficiently, without the
need for frequent reallocations or memory copies
Simplified code: Since static data structures have a fixed size, they can simplify
code by removing the need for dynamic memory allocation and associated error
checking.
Reduced overhead: Static data structures typically have lower overhead than
dynamic data structures, since they do not require extra bookkeeping to manage
memory allocation and de-allocation.

Advantages of Dynamic Linear Data Structures

Flexibility: Dynamic data structures can grow or shrink at run-time as needed,

allowing them to adapt to changing data requirements. This flexibility makes
them well-suited for situations where the size of the data is not known in advance
or is likely to change over time.
Reduced memory waste: Since dynamic data structures can resize themselves,
they can help reduce memory waste. For example, if a dynamic array needs to
grow, it can allocate additional memory on the heap rather than reserving a large
fixed amount of memory that might not be used.
Improved performance for some operations: Dynamic data structures can be
more efficient than static data structures for certain operations. For example,
inserting or deleting elements in the middle of a dynamic list can be faster than
with a static array, since the remaining elements can be shifted over more
efficiently.
Simplified code: Dynamic data structures can simplify code by removing the
need for manual memory management. Dynamic data structures can also reduce
the complexity of code for data structures that need to be resized frequently.
Scalability: Dynamic data structures can be more scalable than static data
structures, as they can adapt to changing data requirements as the data grows.

Comprehensions:

List:
List comprehensions provide a concise way to create lists. Common applications
are to make new lists where each element is the result of some operations applied
to each member of another sequence or iterable, or to create a subsequence of
those elements that satisfy a certain condition.

For example, assume we want to create a list of squares, like:

>>> list1=[]
>>> for x in range(10):
list1.append(x**2)
>>> list1
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
(or)
This is also equivalent to
>>> list1=list(map(lambda x:x**2, range(10)))
>>> list1
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
(or)
Which is more concise and redable.
>>> list1=[x**2 for x in range(10)]
>>> list1
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Similarly some examples:

>>> x=[m for m in range(8)]

>>> print(x)
[0, 1, 2, 3, 4, 5, 6, 7]
>>> x=[z**2 for z in range(10) if z>4]
>>> print(x)
[25, 36, 49, 64, 81]
>>> x=[x ** 2 for x in range (1, 11) if x % 2 == 1]
>>> print(x)
[1, 9, 25, 49, 81]
>>> a=5
>>> table = [[a, b, a * b] for b in range(1, 11)]
>>> for i in table: print(i)
[5, 1, 5]
[5, 2, 10]
[5, 3, 15]
[5, 4, 20]
[5, 5, 25]
[5, 6, 30]
[5, 7, 35]
[5, 8, 40]
[5, 9, 45]
[5, 10, 50]

Tuple:
Tuple Comprehensions are special: The result of a tuple comprehension is
special. You might expect it to produce a tuple, but what it does is produce a
special "generator" object that we can iterate over.

For example:
>>> x = (i for i in 'abc') #tuple comprehension
>>> x
<generator object <genexpr> at 0x033EEC30>
>>> print(x)
<generator object <genexpr> at 0x033EEC30>

You might expect this to print as ('a', 'b', 'c') but it prints as <generator object
<genexpr> at 0x02AAD710> The result of a tuple comprehension is not a tuple:
it is actually a generator. The only thing that you need to know now about a
generator now is that you can iterate over it, but only once.

So, given the code

>>> x = (i for i in 'abc')
>>> for i in x: print(i)
abc

Create a list of 2-tuples like (number, square):

>>> z= [(x, x**2) for x in range (6)]
>>> z
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]

Set:
Similarly, to list comprehensions, set comprehensions are also supported:
>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
{'r', 'd'}
>>> x= {3*x for x in range(10) if x>5}
>>> x
{24, 18, 27, 21}

Dictionary:
Dictionary comprehensions can be used to create dictionaries from arbitrary
key and value expressions:
>>> z={x: x**2 for x in (2,4,6)}
>>> z
{2: 4, 4: 16, 6: 36}
>>> dict11 = {x: x*x for x in range(6)}
>>> dict11
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

Arrays
An array is a fundamental data structure available in most programming
languages. An array is a collection of items of the same variable type that are
stored at contiguous memory locations. It's one of the most popular and simple
data structures and is often used to implement other data structures. It allows
the processing of a large amount of data in a relatively short period.

Array Index: In an array, elements are identified by their indexes. Array index
starts with 0.
Array Element: Elements are items stored in an array and can be accessed by
their index.
Array Length: The length of an array is determined by the number of elements
it can contain. There are different operations possible in an array, like Searching,
Sorting, Inserting, Traversing, Reversing, and Deleting

Characteristics of Arrays
Arrays use an index-based data structure which helps to identify each of the
elements in an array easily using the index. If a user wants to store multiple
values of the same data type, then the array can be utilized efficiently. An array
can also handle complex data structures by storing data in a two-dimensional
array. An array is also used to implement other data structures like Stacks,
Queues, Heaps, Hash tables, etc.,
The search process in an array can be done very easily

Types of Arrays
One-dimensional array (1-D): You can imagine a 1d array as a row, where
elements are stored one after another.
Two-dimensional array (2-D): Multidimensional arrays can be considered as an
array of arrays or as a matrix consisting of rows and columns.
Three-dimensional array (3-D): A 3-D Multidimensional array contains three
dimensions, so it can be considered an array of two-dimensional arrays.

(a) One Dimensional Array

(b) Two Dimensional Array

(c) Three Dimensional Array

Operations on Arrays
Initialization: An array can be initialized with values at the time of declaration
or later using an assignment statement.
Accessing elements: Elements in an array can be accessed by their index, which
starts from 0 and goes up to the size of the array minus one.
Searching for elements: Arrays can be searched for a specific element using
linear search or binary search algorithms.
Sorting elements: Elements in an array can be sorted in ascending or
descending order using algorithms like bubble sort, selection sort, or quick sort.
Inserting elements: Elements can be inserted into an array at a specific
location, but this operation can be time-consuming because it requires shifting
existing elements in the array.
Deleting elements: Elements can be deleted from an array by shifting the
elements that come after it to fill the gap.
Updating elements: Elements in an array can be updated or modified by
assigning a new value to a specific index.
Traversing elements: The elements in an array can be traversed in order,
visiting each element once

Arrays vs List

Both list and array and list are used to store the data in Python. These data
structures allow us to indexing, slicing, and iterating. But they have little
dissimilarity with each other.
Python List
A list is a built-in, linear data structure of Python. It is used to store the data in
a sequence manner. We can perform several operations to list, such as indexing,
iterating, and slicing. The list comes with the following features.
 The list elements are enclosed with a square bracket, and each element is
separated by a comma (,).
 It is a mutable type which means we can modify the list items after their
creation.
 The lists are ordered, which means items are stored in a specific order. We
can use indexing to access the list element.
 We can store the items of different data types. We can combine strings,
integers, and objects in the same list.

Below is an example of a list.

Example 1
1. list = [31, 60, 19, 12]
2. print(list)
3. print(type(list))
Output:
[31, 60, 19, 12]
<class ‘list’>

Example 2
1. # creating a list containing elements
2. # belonging to different data types
3. list1 = [1,"Yash",['a','e']]
4. print(list1)

Output:
[1, 'Yash', ['a', 'e']

In the above list, the first element is an integer; the second is a string and third
is a list of characters.

Array in Python
An array is also a linear data structure that stores the data. It is also ordered,
mutable, and enclosed in square brackets. It can store the non-unique items.
But there are restrictions to store the different data type values.
To work with the Array in Python, we need to import either an array module or
a Numpy.
1. import array as arr
2. or
3. import numpy as np

Elements are allocated in contiguous memory location that allows us to easy

modification, addition, deletion, accessing of element. Moreover, we need to
specify the data type. Let's understand the following example.

Example - 1
1. Import array as arr
2. array_1 = arr.array("i", [31, 60,19, 12])
3. print(array_1)
4. print(type(array_1))

Output:
array('i', [31, 60, 19, 12])
<class 'array.array'>

Example - 2: Using Numpy array

1. import numpy as np
2. array_sample = np.array(["str", 'sunil', 'sachin', 'megha', 'deepti'])
3. print (array_sample)
4. print(type(array_sample))

Output:
['numbers' 'sunil' 'sachin' 'megha' 'deepti']
<class 'numpy.ndarray'>

We have specified the string type and stored the string value.

Difference between Array and List

Searching

There are two types of searching -

 Linear Search

 Binary Search

Both techniques are widely used to search an element in the given list.
Linear Search

What is a Linear Search?

Linear search is a method of finding elements within a list. It is also called a
sequential search. It is the simplest searching algorithm because it searches the
desired element in a sequential manner.
It compares each and every element with the value that we are searching for. If
both are matched, the element is found, and the algorithm returns the key's
index position.

How Linear Search Works?

 Step 1: First, read the search element (Target element) in the array.
 Step 2: Set an integer i = 0 and repeat steps 3 to 4 till i reaches the end of
the array.
 Step 3: Match the key with arr[i].
 Step 4: If the key matches, return the index. Otherwise, increment i by 1.

Concept of Linear Search:

Consider the array arr[] = {10, 50, 30, 70, 80, 20, 90, 40} and key = 20
Step 1: Set i = 0 and check key with arr[0].

Compare key with index 0

Step 2: key and arr[0] are not the same. So make i = 1 and match key with
arr[1].

Compare key with index 1

Step 3: arr[1] and key are different. Increment i and compare key with arr[2].
Compare key with index 2

Step 4: arr[2] is not the same with key. Increment i and compare key with
arr[3].

Compare key with index 3

Step 5: key and arr[3] are different. Make i = 4 and compare key with arr[4].

Compare key with index 4

Step 6: key and arr[4] are not same. Make i = 5 and match key with arr[5].

Compare key with index 5

We can see here that key is present at index 5.

Implementation of Linear Search Algorithm:

# Python code to linearly search x in arr[].

# If x is present then return its location, otherwise return -1
def search(arr, N, x):

for i in range(0, N):

if (arr[i] == x):
return i
return -1

# Driver Code
if __name__ == "__main__":
arr = [2, 3, 4, 10, 40]
x = 10
N = len(arr)

# Function call
result = search(arr, N, x)
if(result == -1):
print("Element is not present in array")
else:
print("Element is present at index", result)

Explanation:

In the above code, we have created a function search(), which takes three
arguments - list1, length of the list, and number to search. We defined for loop
and iterate each element and compare to the key value. If element is found,
return the index else return -1 which means element is not present in the list.

Complexity Analysis of Linear Search:

Time Complexity:
 Best Case: In the best case, the key might be present at the first index. So
the best case complexity is O(1)
 Worst Case: In the worst case, the key might be present at the last index
i.e., opposite to the end from which the search has started in the list. So the
worst case complexity is O(N) where N is the size of the list.
 Average Case: O(N)

Auxiliary Space: O(1) as except the variable to iterate through the list, no other
variable is used.

Linear search algorithm is suitable for smaller list (<100) because it check every
element to get the desired number. Suppose there are 10,000 element list and
desired element is available at the last position, this will consume much time by
comparing with each element of the list.

Binary Search:

A binary search is an algorithm to find a particular element in the list. Suppose

we have a list of thousand elements, and we need to get an index position of a
particular element. We can find the element's index position very fast using the
binary search algorithm.
There are many searching algorithms but the binary search is most popular
among them.
The elements in the list must be sorted to apply the binary search algorithm. If
elements are not sorted then sort them first.
Let's understand the concept of binary search.

Concept of Binary Search

The divide and conquer approach technique is followed by the recursive method.
In this method, a function is called itself again and again until it found an
element in the list.
A set of statements is repeated multiple times to find an element's index position
in the iterative method. The while loop is used for accomplish this task.
Binary search is more effective than the linear search because we don't need to
search each list index. The list must be sorted to achieve the binary search
algorithm.

Let's have a step by step implementation of binary search.

 Sort the array in ascending order.

 Set the low index to the first element of the array and the high index to the
last element.
 Set the middle index to the average of the low and high indices.
 If the element at the middle index is the target element, return the middle
index.
 If the target element is less than the element at the middle index, set the
high index to the middle index – 1.
 If the target element is greater than the element at the middle index, set
the low index to the middle index + 1.
 Repeat steps 3-6 until the element is found or it is clear that the element is
not present in the array.

Binary Search Algorithm can be implemented in the following two ways

1. Iterative Method
2. Recursive Method

1. Iteration Method
2. Recursive Method (The recursive method follows the divide and conquer
approach)

Illustration of Binary Search Algorithm:

Step-by-step Binary Search Algorithm: We basically ignore half of the
elements just after one comparison.
1. Compare x with the middle element.
2. If x matches with the middle element, we return the mid index.
3. Else If x is greater than the mid element, then x can only lie in the right
half subarray after the mid element. So we recur for the right half.
4. Else (x is smaller) recur for the left half.

Recursive implementation of Binary Search:

# Python3 Program for recursive binary search.

# Returns index of x in arr if present, else -1

def binarySearch(arr, l, r, x):

# Check base case

if r >= l:

mid = l + (r - l) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
else:
return binarySearch(arr, mid + 1, r, x)
else:
# Element is not present in the array
return -1

# Driver Code
arr = [2, 3, 4, 10, 40]
x = 10

# Function call
result = binarySearch(arr, 0, len(arr)-1, x)

if result != -1:
print("Element is present at index % d" % result)
else:
print("Element is not present in array")

Output:
Element is present at index 3
Time Complexity: O(log n)
Auxiliary Space: O(log n)

Iterative Approach to Binary Search

# Iterative Binary Search Function Method Python Implementation

# It returns index of n in given list1 if present, else returns -1
def binary_search(list1, n):
low = 0
high = len(list1) - 1
mid = 0
while low <= high:
# for get integer result
mid = (high + low) // 2
# Check if n is present at mid
if list1[mid] < n:
low = mid + 1
# If n is greater, compare to the right of mid
elif list1[mid] > n:
high = mid - 1
# If n is smaller, compared to the left of mid
else:
return mid
return -1

# Initial list1
list1 = [12, 24, 32, 39, 45, 50, 54]
n = 45
# Function call
result = binary_search(list1, n) 35.
if result != -1:
print("Element is present at index", str(result))
else:
print("Element is not present in list1")

Output:
Element is present at index 4

Explanation:
In the above program -
 We have created a function called binary_search() function which
takes two arguments - a list to sorted and a number to be searched.

 We have declared two variables to store the lowest and highest values
in the list. The low is assigned initial value to 0, high to len(list1) - 1
and mid as 0.

 Next, we have declared the while loop with the condition that the
lowest is equal and smaller than the highest the while loop will
iterate if the number has not been found yet.

 In the while loop, we find the mid value and compare the index value
to the number we are searching for.

 If the value of the mid-index is smaller than n, we increase the mid

value by 1 and assign it to the search moves to the left side.

 Otherwise, decrease the mid value and assign it to the high. The
search moves to the right side.

 If the n is equal to the mid value then return mid.

 This will happen until the low is equal and smaller than the high.

 If we reach at the end of the function, then the element is not present
in the list. We return -1 to the calling function.

Sorting

Bubble Sort:
It is a simple sorting algorithm which sorts ‘n’ number of elements in the list by
comparing the ach pair of adjacent items and swaps them if they are in wrong
order.
Algorithm:
1. Starting with the first element (index=0), compare the current
element with the next element of a list.
2. If the current element is greater (>) than the next element of the
list then swap them.
3. If the current element is less (<) than the next element of the list
move to the next element.
4. Repeat step 1 until it correct order is framed.

#Write a python program to arrange the elements in ascending order

using bubble sort:

list1=[9,16,6,26,0]
print("unsorted list1 is", list1)
for j in range(len(list1)-1):
for i in range(len(list1)-1):
if list1[i]>list1[i+1]:
list1[i],list1[i+1]=list1[i+1],list1[i]
print(list1)
else:
print(list1)
print( )
print("sorted list is",list1)

Output:
unsorted list1 is [9, 16, 6, 26, 0]
[9, 16, 6, 26, 0]
[9, 6, 16, 26, 0]
[9, 6, 16, 26, 0]
[9, 6, 16, 0, 26]
[6, 9, 16, 0, 26]
[6, 9, 16, 0, 26]
[6, 9, 0, 16, 26]
[6, 9, 0, 16, 26]
[6, 9, 0, 16, 26]
[6, 0, 9, 16, 26]
[6, 0, 9, 16, 26]
[6, 0, 9, 16, 26]
[0, 6, 9, 16, 26]
[0, 6, 9, 16, 26]
[0, 6, 9, 16, 26]
[0, 6, 9, 16, 26]
sorted list is [0, 6, 9, 16, 26]

#If we want to reduce no of iterations/steps in output:

#If we want to reduce no of iterations/steps in output:
list1=[9,16,6,26,0]
print("unsorted list1 is", list1)
for j in range(len(list1)-1,0,-1):
for i in range(j):
if list1[i]>list1[i+1]:
list1[i],list1[i+1]=list1[i+1],list1[i]
print(list1)
else:
print(list1)
print( )
print("sorted list is",list1)

Output:
unsorted list1 is [9, 16, 6, 26, 0]
[9, 16, 6, 26, 0]
[9, 6, 16, 26, 0]
[9, 6, 16, 26, 0]
[9, 6, 16, 0, 26]
[6, 9, 16, 0, 26]
[6, 9, 16, 0, 26]
[6, 9, 0, 16, 26]
[6, 9, 0, 16, 26]
[6, 0, 9, 16, 26]
[0, 6, 9, 16, 26]
sorted list is [0, 6, 9, 16, 26]
# In a different way:
list1=[9,16,6,26,0]
print("unsorted list1 is", list1)
for j in range(len(list1)-1):
for i in range(len(list1)-1-j):
if list1[i]>list1[i+1]:
list1[i],list1[i+1]=list1[i+1],list1[i]
print(list1)
else:
print(list1)
print( )
print("sorted list is",list1)

Output:
unsorted list1 is [9, 16, 6, 26, 0]
[9, 16, 6, 26, 0]
[9, 6, 16, 26, 0]
[9, 6, 16, 26, 0]
[9, 6, 16, 0, 26]
[6, 9, 16, 0, 26]
[6, 9, 16, 0, 26]
[6, 9, 0, 16, 26]
[6, 9, 0, 16, 26]
[6, 0, 9, 16, 26]
[0, 6, 9, 16, 26]
sorted list is [0, 6, 9, 16, 26]

# Program to give input from the user to sort the elements

list1=[]
num=int(input("enter how many numbers:"))
print("enter values")
for k in range(num):
list1.append(int(input()))
print("unsorted list1 is", list1)
for j in range(len(list1)-1):
for i in range(len(list1)-1):
if list1[i]>list1[i+1]:
list1[i],list1[i+1]=list1[i+1],list1[i]
print(list1)
else:
print(list1)
print( )
print("sorted list is",list1)

Output:
enter how many numbers:5 enter values
5
77
4
66
30
unsorted list1 is [5, 77, 4, 66, 30]
[5, 77, 4, 66, 30]
[5, 4, 77, 66, 30]
[5, 4, 66, 77, 30]
[5, 4, 66, 30, 77]
[4, 5, 66, 30, 77]
[4, 5, 66, 30, 77]
[4, 5, 30, 66, 77]
[4, 5, 30, 66, 77]
[4, 5, 30, 66, 77]
[4, 5, 30, 66, 77]
[4, 5, 30, 66, 77]
[4, 5, 30, 66, 77]
[4, 5, 30, 66, 77]
[4, 5, 30, 66, 77]
[4, 5, 30, 66, 77]
[4, 5, 30, 66, 77]
sorted list is [4, 5, 30, 66, 77]

#bubble sort program for descending order

list1=[9,16,6,26,0]
print("unsorted list1 is", list1)
for j in range(len(list1)-1):
for i in range(len(list1)-1):
if list1[i]<list1[i+1]:
list1[i],list1[i+1]=list1[i+1],list1[i]
print(list1)
else:
print(list1)
print( )
print("sorted list is",list1)

Output:
[9, 16, 6, 26, 0]
[16, 9, 6, 26, 0]
[16, 9, 6, 26, 0]
[16, 9, 26, 6, 0]
[16, 9, 26, 6, 0]
[16, 9, 26, 6, 0]
[16, 26, 9, 6, 0]
[16, 26, 9, 6, 0]
[16, 26, 9, 6, 0]
[26, 16, 9, 6, 0]
[26, 16, 9, 6, 0]
[26, 16, 9, 6, 0]
[26, 16, 9, 6, 0]
[26, 16, 9, 6, 0]
[26, 16, 9, 6, 0]
[26, 16, 9, 6, 0]
[26, 16, 9, 6, 0]
sorted list is [26, 16, 9, 6, 0]

Selection Sort:

Sort (): Built-in list method Sorted (): built in function

 Generally, this algorithm is called as in-place comparison-based
algorithm. We compare numbers and place them in correct position.
 Search the list and find out the min value, this we can do it by min ()
method.
 We can take min value as the first element of the list and compare
with the next element until we find small value.

Algorithm:

1. Starting from the first element search for smallest/biggest element in the
list of numbers.
2. Swap min/max number with first element
3. Take the sub-list (ignore sorted part) and repeat step 1 and 2 until all the
elements are sorted.

#Write a python program to arrange the elements in ascending order using selection
sort:

def selection_sort(arr):
n = len(arr)
for i in range(n):
# Find the minimum element in the unsorted part
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j

# Swap the minimum element with the first element of the unsorted part
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr

arr = [5,3,7,1,9,6]
print(selection_sort(arr))
Output:
[5, 3, 7, 1, 9, 6]
[1, 3, 7, 5, 9, 6]
[1, 3, 7, 5, 9, 6]
[1, 3, 5, 7, 9, 6]
[1, 3, 5, 6, 9, 7]
[1, 3, 5, 6, 7, 9]
[1, 3, 5, 6, 7, 9]

#Write a python program to arrange the elements in descending order using selection
sort:

list1=[5,3,7,1,9,6]
print(list1)
for i in range(len(list1)):
min_val=max(list1[i:])
min_ind=list1.index(min_val)
list1[i],list1[min_ind]=list1[min_ind],list1[i]
print(list1)

Output:
[5, 3, 7, 1, 9, 6]
[9, 3, 7, 1, 5, 6]
[9, 7, 3, 1, 5, 6]
[9, 7, 6, 1, 5, 3]
[9, 7, 6, 5, 1, 3]
[9, 7, 6, 5, 3, 1]
[9, 7, 6, 5, 3, 1]
Note: If we want the elements to be sorted in descending order use max ()
method in place of min ().

Merge Sort:
Generally, this merge sort works on the basis of divide and conquer algorithm.
The three steps need to be followed is divide, conquer and combine. We will be
dividing the unsorted list into sub list until the single element in a list is found.

Algorithm:
1. Split the unsorted list.
2. Compare each of the elements and group them
3. Repeat step 2 until whole list is merged and sorted.

# Write a python program to arrange the elements in ascending order

using Merge sort (with functions)

def merge_sort(arr):
# Base case: if the input array is empty or has only one element, it is already
sorted
if len(arr) <= 1:
return arr

# Divide the array into two halves

mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]

# Recursively sort each half

left_sorted = merge_sort(left_half)
right_sorted = merge_sort(right_half)

# Merge the sorted halves

result = []
i=j=0
while i < len(left_sorted) and j < len(right_sorted):
if left_sorted[i] < right_sorted[j]:
result.append(left_sorted[i])
i += 1
else:
result.append(right_sorted[j])
j += 1

# Append the remaining elements of the left or right half

result.extend(left_sorted[i:])
result.extend(right_sorted[j:])
return result

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(merge_sort(arr))
# Write a python program to arrange the elements in descending order
using Merge sort (with functions)

def merge_sort(arr):
# Base case: if the input array is empty or has only one element, it is already
sorted
if len(arr) <= 1:
return arr
# Divide the array into two halves
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]

# Recursively sort each half

left_sorted = merge_sort(left_half)
right_sorted = merge_sort(right_half)

# Merge the sorted halves

result = []
i=j=0
while i < len(left_sorted) and j < len(right_sorted):
if left_sorted[i] > right_sorted[j]:
result.append(left_sorted[i])
i += 1
else:
result.append(right_sorted[j])
j += 1

# Append the remaining elements of the left or right half

result.extend(left_sorted[i:])
result.extend(right_sorted[j:])

return result

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(merge_sort(arr))

Quick Sort:
• The quick sort algorithm falls under the divide and conquer class of
algorithms, where we break (divide) a problem into smaller chunks that
are much simpler to solve (conquer).
• In this case, an unsorted array is broken into sub-arrays that are partially
sorted, until all elements in the list are in the right position, by which time
our unsorted list will have become sorted.
• The Quick sorting process is mainly considered in three phases.
• Partitioning the list/array
• Pivot selection
• Implementation
• Before we divide the list into smaller chunks, we have to partition it. This
is the heart of the quick sort algorithm.
• To partition the array, we must first select a pivot. All the elements in the
array will be compared with this pivot. At the end of the partitioning
process, all elements that are less than the pivot will be to the left of the
pivot, while all elements greater than the pivot will lie to the right of the
pivot in the array.
• There are different variations of quicksort where the pivot element is
selected from different positions (start, median, random, end).
• For the sake of simplicity, we’ll take the first element in any array as the
pivot. This kind of pivot selection degrades in performance, especially
when sorting an already sorted list.
• Randomly picking the middle or last element in the array as the pivot does
not improve the situation any further.
• There are two famous partition schemes for Quick sort
• Hoare Partition
• Lomuto Partition
• Hoare Partition : This takes first element as pivot, and places all the
elements smaller than the pivot on the left side and all the elements greater
than the pivot on the right side. It returns the index of the last element on
the smaller side.
• Lomuto Partition : This takes last element as pivot, places the pivot
element at its correct position in sorted array, and places all smaller
(smaller than pivot) to left of pivot and all greater elements to right of pivot.

Hoare Partition:
• The Hoare Partition Scheme is a popular algorithm used for quick sort. It
works by selecting a pivot element, and then partitioning the elements into
two groups such that all elements less than the pivot are in one group and
all elements greater than the pivot are in another.

Algorithm:
1. Select the pivot element
2. Find out the correct position of pivot element in the list by rearranging it.
3. Divide the list based on pivot element
4. Sort the sub list recursively

Note: Pivot element can be first, last, random elements or median of three
values.
In the following program we are going to write 3 functions. The first function is
to find pivot element and its correct position. In second function we divide the
list based on pivot element and sort the sub list and third function (main fun)
is to print input and output.
# Write a python program to arrange the elements in ascending order using Quick
sort (with functions)

def quick_sort(elements, start, end):

if start < end:
pi = partition(elements, start, end)
quick_sort(elements, start, pi-1)
quick_sort(elements, pi+1, end)

def partition(elements, start, end):

pivot_index = start
pivot = elements[pivot_index]
while start < end:
while start < len(elements) and elements[start] <= pivot:
start+=1
while elements[end] > pivot:
end-=1
if start < end:
elements[start], elements[end] = elements[end], elements[start]
elements[pivot_index], elements[end] = elements[end], elements[pivot_index]
return end

elements = [11,9,29,7,2,15,28]
# elements = ["mona", "dhaval", "aamir", "tina", "chang"]
quick_sort(elements, 0, len(elements)-1)
print(elements)

# Write a python program to arrange the elements in descending order using

Quick sort (with functions)

def quick_sort_descending(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
left = []
right = []
for i in range(1, len(arr)):
if arr[i] > pivot:
left.append(arr[i])
else:
right.append(arr[i])
return quick_sort_descending(left) + [pivot] + quick_sort_descending(right)

# Example usage
arr = [3, 5, 2, 8, 1, 4, 7, 6]
sorted_arr = quick_sort_descending(arr)
print(sorted_arr)

Lomuto Partition Scheme:

• In the Lomuto partition scheme, usually the last element of the list is
chosen as the pivot element.
• Two pointers are also maintained for tracking and comparison purposes.
A pointer i is maintained while another pointer j is scanning through the
array, from its starting all the way to the end (up to the pivot element).
• The scan ensures that any element e₀ that is present from the starting
point of the array to the (i-1)ᵗʰ index is lesser than the pivot element in
terms of value and the elements present at any index ranging from i to j
are equal to or bigger than the pivot element in terms of value.
• Through this technique, the array will be sorted by the time we reach the
end of the array.

def quicksort(A, low, high):

if low < high:
parti = lomutoPartition(A, low, high)
quicksort(A, low, parti-1)
quicksort(A, parti+1, high)

def lomutoPartition(A, low, high):

pivot = A[high]
i = low-1
for j in range(low, high):
if pivot >= A[j]:
i += 1
A[i], A[j] = A[j], A[i]
A[i+1], A[high] = A[high], A[i+1]
return i+1

if __name__ == "__main__":
A = [4, 2, 7, 3, 1, 9, 6, 0, 8]
low, high = 0, len(A)-1
print("BEFORE SORTING:", A)
quicksort(A, low, high)
print("AFTER SORTING:", A)
UNIT – II
Dynamic Linear Data Structure: Stacks, Stack operations, Characteristics of a Stacks,
Applications of Stacks.
Dynamic Linear Data Structure: Queues, Characteristics of a Queues, Circular Queues,
Applications of Queue.

Stacks:

A stack is a data structure that stores a collection of elements and operates on

them based on the principle of Last-In-First-Out (LIFO). This means that the last
element added to the stack is the first one to be removed. Also, the inbuilt
functions in Python make the code short and simple. To add an item to the top
of the list, i.e., to push an item, we use append() function and to pop out an
element we use pop() function.

#Python code to demonstrate Implementing stack using list

stack = ["Amar", "Akbar", "Anthony"]
stack.append("Ram")
stack.append("Iqbal")
print(stack)
print(stack.pop())
print(stack)
print(stack.pop())
print(stack)
Output:
['Amar', 'Akbar', 'Anthony', 'Ram', 'Iqbal']
Iqbal
['Amar', 'Akbar', 'Anthony', 'Ram']
Ram
['Amar', 'Akbar', 'Anthony']

Stack Operations:

1. push() : Insert the element into linked list nothing but which is the top node
of Stack.
2. pop() : Return top element from the Stack and move the top pointer to the
second node of linked list or Stack.
3. peek(): Return the top element.
4. display(): Print all element of Stack.

The stack has two primary operations:

1. Push - Adds an element to the top of the stack

2. Pop - Removes the element from the top of the stack

Let's take a look at these operations with examples:

Push:
When a new element is added to the stack, it is placed on top of the existing
elements. This is called a push operation.

For instance, consider an empty stack that can store integers. If we push the
following elements in the order given:

push(5)
push(8)
push(2)

The stack will look like this:

|2|
|8|
|5|

Pop:
When an element is removed from the stack, it is removed from the top of the
stack. This is called a pop operation.
Let's continue from the previous example. If we perform the following pop
operations in the order given:
pop()
pop()

The stack will look like this:

|5|
The first pop() operation removed the element 2 from the top of the stack, and
the second pop() operation removed the element 8.

Note that if we try to pop an element from an empty stack, we will get an error
as there is no element to remove.

Python program for static implementation of stack

class Stack:
def __init__(self, capacity):
self.capacity = capacity
self.stack = [None] * capacity
self.top = -1

def push(self, item):

if self.top == self.capacity - 1:
print("Stack Overflow")
return
self.top += 1
self.stack[self.top] = item

def pop(self):
if self.top == -1:
print("Stack Underflow")
return None
item = self.stack[self.top]
self.top -= 1
return item

def peek(self):
if self.top == -1:
print("Stack is empty")
return None
return self.stack[self.top]

def is_empty(self):
return self.top == -1

def is_full(self):
return self.top == self.capacity - 1

def display(self):
if self.top == -1:
print("Stack is empty")
return
for i in range(self.top, -1, -1):
print(self.stack[i])

# Example usage:
stack = Stack(5)
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
stack.push(6) # This will cause a stack overflow
print(stack.pop()) # Outputs: 5
print(stack.pop()) # Outputs: 4
print(stack.peek()) # Outputs: 3
stack.display() # Outputs: 3 2 1
In this implementation, the stack has a fixed capacity specified during
initialization, and it uses a list to store the items. The top variable keeps track of
the index of the top item in the stack. The push() method adds an item to the top
of the stack, the pop() method removes and returns the top item, and the peek()
method returns the top item without removing it. The is_empty() and is_full()
methods check whether the stack is empty or full, respectively. Finally, the
display() method prints all the items in the stack from top to bottom.

Python program for dynamic implementation of stack

class Stack:
def __init__(self):
self.stack = []
self.top = -1

def push(self, item):

self.top += 1
self.stack.append(item)

def pop(self):
if self.top == -1:
print("Stack Underflow")
return None
item = self.stack.pop()
self.top -= 1
return item

def peek(self):
if self.top == -1:
print("Stack is empty")
return None
return self.stack[self.top]

def is_empty(self):
return self.top == -1

def display(self):
if self.top == -1:
print("Stack is empty")
return
for i in range(self.top, -1, -1):
print(self.stack[i])

# Example usage:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
stack.push(6)
print(stack.pop()) # Outputs: 6
print(stack.pop()) # Outputs: 5
print(stack.peek()) # Outputs: 4
stack.display() # Outputs: 4 3 2 1

In this implementation, the stack has no fixed capacity specified during initialization, and it uses a
list to store the items. The top variable keeps track of the index of the top item in the stack. The
push() method adds an item to the top of the stack, and if the list is already full, it automatically
resizes the list by allocating more memory. The pop() method removes and returns the top item,
and the peek() method returns the top item without removing it. The is_empty() method checks
whether the stack is empty. Finally, the display() method prints all the items in the stack from top
to bottom.

Implementing a Stack using List in Python:

stack = []

# Function to push elements into the stack

def push(item):
stack.append(item)
print("Pushed item:", item)

# Function to pop elements from the stack

def pop():
if not stack:
print("Stack is empty!")
else:
item = stack.pop()
print("Popped item:", item)

# Driver code
push(10)
push(20)
push(30)
pop()
pop()
pop()
pop()
OR

stack = []

# Push operation
stack.append(10)
stack.append(20)
stack.append(30)

# Pop operation
stack.pop()
stack.pop()

# Print the stack

print(stack)

Implementing a Stack using LinkedList in Python:

class Node:
def __init__(self, data):
self.data = data
self.next = None

class Stack:
def __init__(self):
self.top = None

# Function to push elements into the stack

def push(self, data):
new_node = Node(data)
if not self.top:
self.top = new_node
else:
new_node.next = self.top
self.top = new_node
print("Pushed item:", data)

# Function to pop elements from the stack

def pop(self):
if not self.top:
print("Stack is empty!")
else:
item = self.top.data
self.top = self.top.next
print("Popped item:", item)
# Driver code
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
stack.pop()
stack.pop()
stack.pop()
stack.pop()

Implementing a Stack using Queue in Python:

from queue import LifoQueue

stack = LifoQueue()

# Function to push elements into the stack

def push(item):
stack.put(item)
print("Pushed item:", item)

# Function to pop elements from the stack

def pop():
if stack.empty():
print("Stack is empty!")
else:
item = stack.get()
print("Popped item:", item)

# Driver code
push(10)
push(20)
push(30)
pop()
pop()
pop()
pop()

Characteristics of a Stacks:

1. LIFO ordering: The last item pushed onto the stack is the first item popped
off the stack.

2. Push and Pop Operations: The two primary operations that can be
performed on a stack are "push," which adds an item to the top of the
stack, and "pop," which removes the item from the top of the stack.
3. Top Element Access: A stack allows access only to the top element, which
is the most recently added item. Other elements are not directly accessible
and must be removed first.

4. Limited Accessibility: Stacks do not allow access to elements in the middle

of the stack. To access a specific element, all elements on top of it must be
removed first.

5. Dynamic Size: Stacks can grow or shrink dynamically as items are added
or removed.

6. Contiguous Memory Allocation: Stacks typically use contiguous memory

allocation, meaning that elements are stored in adjacent memory
locations.

7. Stack Overflow: A stack has a finite amount of memory allocated to it.

When the stack exceeds this memory limit, a stack overflow occurs.

8. Stack Underflow: A stack underflow occurs when an attempt is made to

remove an element from an empty stack.

These characteristics make stacks useful for many applications, such as

implementing recursive function calls, undo-redo operations, and parsing
expressions.

Applications of Stack
There are many applications of a stack. Some of them are:
 Stacks are used in backtracking algorithms.
 They are also used to implement undo/redo functionality in a software.
 Stacks are also used in syntax parsing for many compilers.
 Stacks are also used to check proper opening and closing of parenthesis.

Implementing a Queue using a List:

queue = []

# Adding elements to the queue

queue.append(1)
queue.append(2)
queue.append(3)

print("Initial queue:", queue)

# Removing elements from the queue

queue.pop(0)
queue.pop(0)

print("Final queue:", queue)

Implementing a queue using LinkedList in Python

To implement a queue using a linked list in Python, you can define a Node class
to represent each element in the linked list and a Queue class to manage the
operations of the queue. Here's an example implementation:

class Node:
def __init__(self, value):
self.value = value
self.next = None

class Queue:
def __init__(self):
self.front = None
self.rear = None

def is_empty(self):
return self.front is None

def enqueue(self, value):

new_node = Node(value)
if self.rear is None:
self.front = new_node
self.rear = new_node
else:
self.rear.next = new_node
self.rear = new_node

def dequeue(self):
if self.is_empty():
raise Exception("Queue is empty")
else:
dequeued_node = self.front
self.front = dequeued_node.next
if self.front is None:
self.rear = None
return dequeued_node.value

def peek(self):
if self.is_empty():
raise Exception("Queue is empty")
else:
return self.front.value

def __str__(self):
if self.is_empty():
return "[]"
else:
queue_str = "["
node = self.front
while node is not None:
queue_str += str(node.value) + ", "
node = node.next
queue_str = queue_str[:-2] + "]"
return queue_str