Data Structures Using Python

LECTURE NOTES

[Link] (DS) I YEAR–I-SEM (2023-24)

B V Raju Institute of Technology Narasapur

SYLLABUS

DATA STRUCTURES USING PYTHON

COURSE OBJECTIVES:

This course will enable students to

Implement Object Oriented Programming concepts in Python.

Understand Lists, Dictionaries and Regular expressions in Python.

Understanding how searching and sorting is performed in Python.

Understanding how linear and non-linear data structures works.

To learn the fundamentals of writing Python scripts.

UNIT – I

Oops Concepts- class, object, constructors, types of variables, types of methods. Inheritance: single, multiple,
multi-level, hierarchical, hybrid, Polymorphism: with functions and objects, with class methods, with
inheritance,Abstraction: abstract classes.

UNIT – II

Data Structures – Definition,Linear Data Structures,Non-Linear Data Structures

Python Specific Data Structures: List,Tuples, Set, Dictionaries, Comprehensions and its Types,Strings,slicing.

UNIT -III

Arrays - Overview, Types of Arrays, Operations on Arrays, Arrays vs List.

 Searching -Linear Search and Binary Search.

Sorting - Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort.

UNIT -IV

Linked Lists – Implementation ofSingly Linked Lists, Doubly Linked Lists, Circular Linked Lists.

Stacks - Overview of Stack, Implementation of Stack (List & Linked list), Applications of Stack

Queues:Overview of Queue, Implementation of Queue(List & Linked list), Applications of Queues, Priority
Queues.

UNIT -V

Graphs -Introduction, Directed vs Undirected Graphs, Weighted vs Unweighted Graphs, Representations,

Breadth First Search, Depth First Search.

Trees - Overview of Trees, Tree Terminology, Binary Trees: Introduction, Implementation, Applications. Tree
Traversals, Binary Search Trees: Introduction, Implementation, AVL Trees: Introduction, Rotations,
Implementation.

TEXTBOOKS:

Data structures and algorithms in python by Michael T. Goodrich

Data Structures and Algorithmic Thinking with Python by NarasimhaKarumanchi

REFERENCE BOOKS:

Hands-On Data Structures and Algorithms with Python: Write complex and powerful code using the latest
features of Python 3.7, 2nd Edition by Dr. Basant Agarwal, Benjamin Baka.

Data Structures and Algorithms with Python by Kent D. Lee and Steve Hubbard.

Problem Solving with Algorithms and Data Structures Using Python by Bradley N Miller and David L. Ranum.

Core Python Programming -Second Edition,R. Nageswara Rao, Dreamtech Press

COURSE OUTCOMES:

The students should be able to:

Examine Python syntax and semantics and apply Python flow control and functions.

Create, run and manipulate Python Programs using core data structures like Lists,
 Apply Dictionaries and use Regular Expressions.

Interpret the concepts of Object-Oriented Programming as used in Python.

Master object-oriented programming to create an entire python project using objects and classes

INDEX

UNIT – I

Oops Concepts- class, object, constructors, types of variables, types of methods. Inheritance: single, multiple,
multi-level, hierarchical, hybrid, Polymorphism: with functions and objects, with class methods, with
inheritance,Abstraction: abstract classes.

OOPs in Python

OOPs in Python is a programming approach that focuses on using objects and classes as same as other
general programming languages. The objects can be any real-world entities. Python allows developers to
develop applications using the OOPs approach with the major focus on code reusability.

Example:

class Parrot:

# class attribute species = "bird"

# instance attribute

def init (self, name, age): [Link] = name

[Link] = age

# instantiate the Parrot class blu = Parrot("Blu", 10)

woo = Parrot("Woo", 15)

# access the class attributes

print("Blu is a {}".format(blu. class .species)) print("Woo is also a {}".format(woo. class .species))

# access the instance attributes

print("{} is {} years old".format( [Link], [Link])) print("{} is {} years old".format( [Link], [Link]))
constructor

The constructor is a method that is called when an object is created. This method is defined in the class and
can be used to initialize basic variables.

If you create four objects, the class constructor is called four times. Every class has a constructor, but its not
required to explicitly define it.

Example:

Each time an object is created a method is called. That methods is named the constructor.

The constructor is created with the function init. As parameter we write the self keyword, which refers to itself
(the object). The process visually is:

Inside the constructor we initialize two variables: legs and arms. Sometimes variables are named properties in
the context of object oriented programming. We create one object (bob) and just by creating it, its variables
are initialized.

The newly created object now has the variables set, without you having to define them manually. You could
create tens or hundreds of objects without having to set the values each time.

python init

The function init(self) builds your object. Its not just variables you can set here, you can call class methods too.
Everything you need to initialize the object(s).

Lets say you have a class Plane, which upon creation should start flying. There are many steps involved in
taking off: accelerating, changing flaps, closing the wheels and so on.

The default actions can be defined in methods. These methods can be called in the constructor.

To summarize: A constructor is called if you create an object. In the constructor you can set variables and call
methods.

Default value

The constructor of a class is unique: initiating objects from different classes will call different constructors.
Default values of newly created objects can be set in the constructor.

The example belwo shows two classes with constructors. Then two objects are created but different
constructors are called.

But creating multiple objects from one class, will call the same constructor.

Python Variable Types: Local & Global

There are two types of variables in Python, Global variable and Local variable. When you want to use the
same variable for rest of your program or module you declare it as a global variable, while if you want to use
the variable in a specific function or method, you use a local variable while Python variable declaration.
Let's understand this Python variable types with the difference between local and global variables in the below
program.

Let us define variable in Python where the variable "f" is global in scope and is assigned value 101 which is
printed in output

Variable f is again declared in function and assumes local scope. It is assigned value "I am learning Python."
which is printed out as an output. This Python declare variable is different from the global variable "f" defined
earlier

Once the function call is over, the local variable f is destroyed. At line 12, when we again, print the value of "f"
is it displays the value of global variable f=101

Python 2 Example

Python 3 Example

While Python variable declaration using the keyword global, you can reference the global variable inside a
function.

Variable "f" is global in scope and is assigned value 101 which is printed in output

Variable f is declared using the keyword global. This is NOT a local variable, but the same global variable
declared earlier. Hence when we print its value, the output is 101

We changed the value of "f" inside the function. Once the function call is over, the changed value of the
variable "f" persists. At line 12, when we again, print the value of "f" is it displays the value "changing global
variable"

Python 2 Example

Python 3 Example

Types of methods:

Generally, there are three types of methods in Python:

Instance Methods.

Class Methods

Static Methods

Before moving on with the topic, we have to know some key concepts.

Class Variable: A class variable is nothing but a variable that is defined outside the constructor. A class
variable is also called as a static variable.

Accessor(Getters): If you want to fetch the value from an instance variable we call them accessors.

Mutator(Setters): If you want to modify the value we call them mutators.

Instance Method

This is a very basic and easy method that we use regularly when we create classes in python. If we want to
print an instance variable or instance method we must create an object of that required class.

If we are using self as a function parameter or in front of a variable, that is nothing but the calling instance
itself.

As we are working with instance variables we use self keyword.

Note: Instance variables are used with instance methods.

Look at the code below

Copy

Output:

In the above program, a and b are instance variables and these get initialized when we create an object for the
Student class. If we want to call avg() function which is an instance method, we must create an object for the
class.

If we clearly look at the program, the self keyword is used so that we can easily say that those are instance
variables and methods.

Class Method

classsmethod() function returns a class method as output for the given function. Here is the syntax for it:

The classmethod() method takes only a function as an input parameter and converts that into a class method.

There are two ways to create class methods in python:

Using classmethod(function)
Using @classmethod annotation

A class method can be called either using the class (such as C.f()) or using an instance (such as C().f()). The
instance is ignored except for its class. If a class method is called from a derived class, the derived class
object is passed as the implied first argument.

As we are working with ClassMethod we use the cls keyword. Class variables are used with class methods.
Look at the code below.

Copy

Output:

In the above example, name is a class variable. If we want to create a class method we must use
@classmethod decorator and cls as a parameter for that function.

Static Method

A static method can be called without an object for that class, using the class name directly. If you want to do
something extra with a class we use static methods.
For example, If you want to print factorial of a number then we don't need to use class variables or instance
variables to print the factorial of a number. We just simply pass a number to the static method that we have
created and it returns the factorial.

Look at the below code

Copy

Output

This a student class

Types of inheritances:

The inheritance is a very useful and powerful concept of object-oriented programming. Using the inheritance
concept, we can use the existing features of one class in another class.

In inheritance, we use the terms like parent class, child class, base class, derived class, superclass, and
subclass.

The Parent class is the class which provides features to another class. The parent class is also known as
Base class or Superclass.

The Child class is the class which receives features from another class. The child class is also known as the
Derived Class or Subclass.

There are five types of inheritances, and they are as follows.

Simple Inheritance (or) Single Inheritance

Multiple Inheritance

Multi-Level Inheritance

Hierarchical Inheritance

Hybrid Inheritance

The following picture illustrates how various inheritances are implemented.

Creating a Child Class

In Python, we use the following general structure to create a child class from a parent class.

Syntax

Let's look at individual inheritance type with an example.

Simple Inheritance (or) Single Inheritance

In this type of inheritance, one child class derives from one parent class. Look at the following example code.

Example
When we run the above example code, it produces the following output.

Multiple Inheritance

In this type of inheritance, one child class derives from two or more parent classes. Look at the following
example code.

Example

When we run the above example code, it produces the following output.

Multi-Level Inheritance

In this type of inheritance, the child class derives from a class which already derived from another class. Look
at the following example code.

Example

When we run the above example code, it produces the following output.

Hierarchical Inheritance

In this type of inheritance, two or more child classes derive from one parent class. Look at the following
example code.

Example

When we run the above example code, it produces the following output.

Hybrid Inheritance

The hybrid inheritance is the combination of more than one type of inheritance. We may use any combination
as a single with multiple inheritances, multi-level with multiple inheritances, etc.,

Polymorphism:

Polymorphism is a concept of object oriented programming, which means multiple forms or more than one
form. Polymorphism enables using a single interface with input of different datatypes, different class or may be
for different number of inputs.

In python as everything is an object hence by default a function can take anything as an argument but the
execution of the function might fail as every function has some logic that it follows.

For example,
In this case the function len is polymorphic as it is taking string as input in the first case and is taking list as
input in the second case.

In python, polymorphism is a way of making a function accept objects of different classes if they behave
similarly.

Method overriding is a type of polymorphism in which a child class which is extending the parent class can
provide different definition to any function defined in the parent class as per its own requirements.

Method Overloading

Method overriding or function overloading is a type of polymorphism in which we can define a number of
methods with the same name but with a different number of parameters as well as parameters can be of
different types. These methods can perform a similar or different function.

Python doesn't support method overloading on the basis of different number of parameters in functions.

Defining Polymorphic Classes

Imagine a situation in which we have a different class for shapes like Square, Triangle etc which serves as a
resource to calculate the area of that shape. Each shape has a different number of dimensions which are used
to calculate the area of the respective shape.

Now one approach is to define different functions with different names to calculate the area of the given
shapes. The program depicting this approach is shown below:

The problem with this approach is that the developer has to remember the name of each function separately.
In a much larger program, it is very difficult to memorize the name of the functions for every small operation.
Here comes the role of method overloading.

Now let's change the name of functions to calculate the area and give them both same

name calculate_area() while keeping the function separately in both the classes with different definitions. In
this case the type of object will help in resolving the call to the function. The program below shows the
implementation of this type of polymorphism with class methods:

As you can see in the implementation of both the classes i.e. Square as well as Triangle has the function with
same name calculate_area(), but due to different objects its call get resolved correctly, that is when the
function is called using the object sq then the function of class Square is called and when it is called using the
object tri then the function of class Triangle is called.

Polymorphism with Class Methods

What we saw in the example above is again obvious behaviour. Let's use a loop which iterates over a tuple of
objects of various shapes and call the area function to calculate area for each shape object.

Now this is a better example of polymorphism because now we are treating objects of different classes as an
object on which same function gets called.
Here python doesn't care about the type of object which is calling the function hence making the class method
polymorphic in nature.

Polymorphism with Functions

Just like we used a loop in the above example, we can also create a function which takes an object of some
shape class as input and then calls the function to calculate area for it. For example,

In the example above we have used the same function find_area_of_shape to calculate area of two different
shape classes. The same function takes different class objects as arguments and executes perfectly to return
the result. This is polymorphism.

Polymorphism with Inheritance

Polymorphism in python defines methods in the child class that have the same name as the methods in the
parent class. In inheritance, the child class inherits the methods from the parent class. Also, it is possible to
modify a method in a child class that it has inherited from the parent class.

This is mostly used in cases where the method inherited from the parent class doesn’t fit the child class. This
process of re-implementing a method in the child class is known as Method Overriding. Here is an example
that shows polymorphism with inheritance:

Output:

There are different types of birds

Most of the birds can fly but some cannot There are different types of bird

Parrots can fly

There are many types of birds Penguins do not fly

These are different ways to define polymorphism in Python. With this, we have come to the end of our article. I
hope you understood what is polymorphism and how it is used in Python.

Abstraction

Abstraction is one of the most important features of object-oriented programming. It is used to hide the
background details or any unnecessary implementation.

Pre-defined functions are similar to data abstraction.

For example, when you use a washing machine for laundry purposes. What you do is you put your laundry
and detergent inside the machine and wait for the machine to perform its task. How does it perform it? What
mechanism does it use? A user is not required to know the engineering behind its work. This process is
typically known as data abstraction, when all the unnecessary information is kept hidden from the users.

Code

In Python, we can achieve abstraction by incorporating abstract classes and methods.

Any class that contains abstract method(s) is called an abstract class. Abstract methods do not include any
implementations – they are always defined and implemented as part of the methods of the sub-classes
inherited from the abstract class. Look at the sample syntax below for an abstract class:

The class type_shape is inherited from the ABC class. Let’s define an abstract method area inside the class
type_shape:
 The implementation of an abstract class is done in the sub-classes, which will inherit the class type_shape.
We have defined four classes that inherit the abstract class type_shape in the code below

Example:

from abc import ABC class type_shape(ABC):

def area(self):

#abstract method pass

class Rectangle(type_shape):

length = 6

breadth = 4 def area(self):

return [Link] * [Link]

class Circle(type_shape):

radius = 7

def area(self):

return 3.14 * [Link] * [Link]

class Square(type_shape):

length = 4 def area(self):

return [Link]*[Link]

class triangle:

length = 5

width = 4

def area(self):

return 0.5 * [Link] * [Link]

r = Rectangle() # object created for the class 'Rectangle' c = Circle() # object created for the class 'Circle'

s = Square() # object created for the class 'Square'

t = triangle() # object created for the class 'triangle'

print("Area of a rectangle:", [Link]()) # call to 'area' method defined inside the class. print("Area of a circle:",
[Link]()) # call to 'area' method defined inside the class. print("Area of a square:", [Link]()) # call to 'area'
method defined inside the class. print("Area of a triangle:", [Link]()) # call to 'area' method defined inside the
class.

Output 1.14s

Area of a rectangle: 24 Area of a circle: 153.86 Area of a square: 16 Area of a triangle: 10.0

UNIT – II
Data Structures – Definition,Linear Data Structures,Non-Linear Data Structures,Python Specific Data
Structures, List,Tuples, Set, Dictionaries, Comprehensions and its Types,Strings,slicing.

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.

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.

Let's discuss each linear data structure in detail.

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 ad 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.

Let's discuss both the data structures in detail.

Tree
 It is a non-linear data structure that consists of various linked nodes. It has a hierarchical tree structure that
forms a parent-child relationship. The diagrammatic representation of a tree data structure is shown below:

For example, the posts of employees are arranged in a tree data structure like managers, officers, clerk. In the
above figure, A represents a manager, B and C represent the officers, and other nodes represent the clerks.

Graph

A graph is a non-linear data structure that has a finite number of vertices and edges, and these edges are
used to connect the vertices. The vertices are used to store the data elements, while the edges represent the
relationship between the vertices. A graph is used in various real-world problems like telephone networks,
circuit networks, social networks like LinkedIn, Facebook. In the case of facebook, a single user can be
considered as a node, and the connection of a user with others is known as edges.

Python Specific Data Structures:

List:

It is a general purpose most widely used in data structures

List is a collection which is ordered and changeable and allows duplicate members. (Grow and shrink as
needed, sequence type, sortable).

To use a list, you must declare it first. Do this using square brackets and separate values with commas.

We can construct / create list in many ways.

Ex:

>>> list1=[1,2,3,'A','B',7,8,[10,11]]

>>> print(list1)

[1, 2, 3, 'A', 'B', 7, 8, [10, 11]]

>>> x=list()

>>> x []

>>> tuple1=(1,2,3,4)

>>> x=list(tuple1)

>>> x

[1, 2, 3, 4]

The list data type has some more methods. Here are all of the methods of list objects:
List Operations:

Del()

Append()

Extend()

Insert()

Pop()

Remove()

Reverse()

Sort()

Delete: Delete a list or an item from a list

>>> x=[5,3,8,6]

>>> del(x[1]) #deletes the index position 1 in a list

[5, 8, 6]

>>> del(x)

>>> x # complete list gets deleted

Append: Append an item to a list

>>> x=[1,5,8,4]

>>> [Link](10)

>>> x

[1, 5, 8, 4, 10]

Extend: Append a sequence to a list.

>>> x=[1,2,3,4]

>>> y=[3,6,9,1]

>>> [Link](y)

>>> x

[1, 2, 3, 4, 3, 6, 9, 1]

Insert: To add an item at the specified index, use the insert () method:

>>> x=[1,2,4,6,7]

>>> [Link](2,10) #insert(index no, item to be inserted)

>>> x

[1, 2, 10, 4, 6, 7]

>>> [Link](4,['a',11])

>>> x

[1, 2, 10, 4, ['a', 11], 6, 7]

Pop: The pop() method removes the specified index, (or the last item if index is not specified) or simply pops
the last item of list and returns the item.

>>> x=[1, 2, 10, 4, 6, 7]

>>> [Link]() 7

>>> x

[1, 2, 10, 4, 6]

>>> x=[1, 2, 10, 4, 6]

>>> [Link](2) 10

>>> x

[1, 2, 4, 6]

Remove: The remove() method removes the specified item from a given list.

>>> x=[1,33,2,10,4,6]

>>> [Link](33)

>>> x

[1, 2, 10, 4, 6]

>>> [Link](4)

>>> x

[1, 2, 10, 6]

Reverse: Reverse the order of a given list.

>>> x=[1,2,3,4,5,6,7]

>>> [Link]()

[7, 6, 5, 4, 3, 2, 1]

Sort: Sorts the elements in ascending order

>>> x=[7, 6, 5, 4, 3, 2, 1]

>>> [Link]()

>>> x

[1, 2, 3, 4, 5, 6, 7]

>>> x=[10,1,5,3,8,7]

>>> [Link]()

>>> x

[1, 3, 5, 7, 8, 10]

Slicing: Slice out substrings, sub lists, sub Tuples using index.

[Start: stop: steps]

Slicing will start from index and will go up to stop in step of steps.

Default value of start is 0,

Stop is last index of list

And for step default is 1

Example:

>>> x='computer'
>>> x[1:4]

'omp'

>>> x[1:6:2]

'opt'

>>> x[3:]

'puter'

>>> x[:5]

'compu'

>>> x[-1]

'r'

>>> x[-3:]

'ter'

>>> x[:-2]

'comput'

>>> x[::-2]

'rtpo'

>>> x[::-1]

'retupmoc'

List:

>>> list1=range(1,6)

>>> list1 range(1, 6)

>>> print(list1) range(1, 6)

>>> list1=[1,2,3,4,5,6,7,8,9,10]

>>> list1[1:]

[2, 3, 4, 5, 6, 7, 8, 9, 10]

>>> list1[:1] [1]

>>> list1[2:5] [3, 4, 5]

>>> list1[:6] [1, 2, 3, 4, 5, 6]

>>> list1[1:2:4] [2]

>>> list1[1:8:2] [2, 4, 6, 8]

Tuple:

>>> list1=(11,12,13,14)

>>> list1[:2] (11, 12)

To create a slice:

>>> print(slice(3)) slice(None, 3, None)

>>> print(slice(2))
 slice(None, 2, None)

>>> print(slice(1,6,4)) slice(1, 6, 4)

To get substring from a given string using slice object:

>>> pystr='python'

>>> x=slice(3)

>>> print(pystr[x]) Pyt

Using –ve index:

>>> pystr='python'

>>> x=slice(1,-3,1)

>>> print(pystr[x])

>>> yt

To get sublist and sub-tuple from a given list and tuple respectively:

>>> list1=['m','r','c','e','t']

>>> tup1=('c','o','l','l','e','g','e')

>>> x=slice(1,4,1)

>>> print(tup1[x]) ('o', 'l', 'l')

>>> print(list1[x]) ['r', 'c', 'e']

>>> x=slice(1,5,2)

>>> print(list1[x]) ['r', 'e']

>>> print(tup1[x]) ('o', 'l')

>>> x=slice(-1,-4,-1) #negative index

>>> print(list1[x]) ['t', 'e', 'c']

>>> x=slice(-1,-4,-1) #negative index

>>> print(tup1[x]) ('e', 'g', 'e')

>>> print(list1[0:3]) #extending indexing syntax ['m', 'r', 'c']

Tuples:

A tuple is a collection which is ordered and unchangeable. In Python tuples are written with round brackets.

Supports all operations for sequences.

Immutable, but member objects may be mutable.

If the contents of a list shouldn’t change, use a tuple to prevent items from accidently being added, changed,
or deleted.

Tuples are more efficient than list due to python’s implementation.

We can construct tuple in many ways: X=() #no item tuple

X=(1,2,3)
X=tuple(list1) X=1,2,3,4

Example:

>>> x=(1,2,3)

>>> print(x) (1, 2, 3)

>>> x (1, 2, 3)

>>> x=()

>>> x ()

>>> x=[4,5,66,9]

>>> y=tuple(x)

>>> y

(4, 5, 66, 9)

>>> x=1,2,3,4

>>> x

(1, 2, 3, 4)

Some of the operations of tuple are:

Access tuple items

Change tuple items

Loop through a tuple

Count()

Index()

Length()

Access tuple items:Access tuple items by referring to the index number, inside square brackets

>>> x=('a','b','c','g')

>>> print(x[2]) c

Change tuple items: Once a tuple is created, you cannot change its values. Tuples are unchangeable.

>>> x=(2,5,7,'4',8)

>>> x[1]=10

Traceback (most recent call last):

File "<pyshell#41>", line 1, in <module> x[1]=10

TypeError: 'tuple' object does not support item assignment

>>> x

(2, 5, 7, '4', 8) # the value is still the same

Loop through a tuple: We can loop the values of tuple using for loop

>>> x=4,5,6,7,2,'aa'
 >>> for i in x: print(i)

aa

Count ():Returns the number of times a specified value occurs in a tuple

>>> x=(1,2,3,4,5,6,2,10,2,11,12,2)

>>> [Link](2) 4

Index (): Searches the tuple for a specified value and returns the position of where it was found

>>> x=(1,2,3,4,5,6,2,10,2,11,12,2)

>>> [Link](2) 1

(Or)

>>> x=(1,2,3,4,5,6,2,10,2,11,12,2)

>>> y=[Link](2)

>>> print(y) 1

Length (): To know the number of items or values present in a tuple, we use len().

>>> x=(1,2,3,4,5,6,2,10,2,11,12,2)

>>> y=len(x)
>>> print(y) 12

Set:

A set is a collection which is unordered and unindexed with no duplicate elements. In Python sets are written
with curly brackets.

To create an empty set we use set()

Curly braces ‘{}’ or the set() function can be used to create sets

We can construct tuple in many ways: X=set()

X={3,5,6,8}

X=set(list1)

Example:

>>> x={1,3,5,6}
>>> x

{1, 3, 5, 6}

>>> x=set()

>>> x

set()

>>> list1=[4,6,"dd",7]

>>> x=set(list1)

>>> x

{4, 'dd', 6, 7}

We cannot access items in a set by referring to an index, since sets are unordered the items has no index.

But you can loop through the set items using a for loop, or ask if a specified value is present in a set, by using
the in keyword.

Some of the basic set operations are:

Add()

Remove()

Len()

Item in x

Pop

Clear

Add (): To add one item to a set use the add () method. To add more than one item to a set use the update ()
method.

>>> x={"mrcet","college","cse","dept"}

>>> [Link]("autonomous")

>>> x

{'mrcet', 'dept', 'autonomous', 'cse', 'college'}

>>> x={1,2,3}

>>> [Link]("a","b")

>>> x

{1, 2, 3, 'a', 'b'}

>>> x={1,2,3}

>>> [Link]([4,5],[6,7,8])

>>> x

{1, 2, 3, 4, 5, 6, 7, 8}

Remove (): To remove an item from the set we use remove or discard methods.

>>> x={1, 2, 3, 'a', 'b'}

>>> [Link](3)

>>> x

{1, 2, 'a', 'b'}

Len (): To know the number of items present in a set, we use len().

>>> z={'mrcet', 'dept', 'autonomous', 'cse', 'college'}

>>> len(z) 5

Item in X: you can loop through the set items using a for loop.

>>> x={'a','b','c','d'}

>>> for item in x: print(item)

cdab

pop ():This method is used to remove an item, but this method will remove the last item. Remember that sets
are unordered, so you will not know what item that gets removed.

>>> x={1, 2, 3, 4, 5, 6, 7, 8}

>>> [Link]() 1

>>> x

{2, 3, 4, 5, 6, 7, 8}

Clear (): This method will the set as empty.

>>> x={2, 3, 4, 5, 6, 7, 8}

>>> [Link]()

>>> x

set()

The set also consist of some mathematical operations like:

Dictionaries:

A dictionary is a collection which is unordered, changeable and indexed. In Python dictionaries are written with
curly brackets, and they have keys and values.

Key-value pairs

Unordered

We can construct or create dictionary like: X={1:’A’,2:’B’,3:’c’}

X=dict([(‘a’,3) (‘b’,4)] X=dict(‘A’=1,’B’ =2)

Examples:

>>> dict1 = {"brand":"mrcet","model":"college","year":2004}

>>> dict1

{'brand': 'mrcet', 'model': 'college', 'year': 2004}

To access specific value of a dictionary, we must pass its key,

>>> dict1 = {"brand":"mrcet","model":"college","year":2004}

>>> x=dict1["brand"]

>>> x

'mrcet'

To access keys and values and items of dictionary:

>>> dict1 = {"brand":"mrcet","model":"college","year":2004}

>>> [Link]() dict_keys(['brand', 'model', 'year'])

>>> [Link]() dict_values(['mrcet', 'college', 2004])

>>> [Link]()

dict_items([('brand', 'mrcet'), ('model', 'college'), ('year', 2004)])

>>> for items in [Link](): print(items)

mrcet college 2004

>>> for items in [Link](): print(items)

brand model year

>>> for i in [Link](): print(i)

('brand', 'mrcet')

('model', 'college')

('year', 2004)

Some of the operations are:

Add/change

Remove

Length

Delete

Add/change values:You can change the value of a specific item by referring to its key name

>>> dict1 = {"brand":"mrcet","model":"college","year":2004}

>>> dict1["year"]=2005

>>> dict1

{'brand': 'mrcet', 'model': 'college', 'year': 2005}

Remove(): It removes or pop the specific item of dictionary.

>>> dict1 = {"brand":"mrcet","model":"college","year":2004}

>>> print([Link]("model")) college

>>> dict1

{'brand': 'mrcet', 'year': 2005}

Delete: Deletes a particular item.

>>> x = {1:1, 2:4, 3:9, 4:16, 5:25}

>>> del x[5]

>>> x

Length: we use len() method to get the length of dictionary.

>>>{1: 1, 2: 4, 3: 9, 4: 16}

{1: 1, 2: 4, 3: 9, 4: 16}

>>> y=len(x)

>>> y 4

Iterating over (key, value) pairs:

>>> x = {1:1, 2:4, 3:9, 4:16, 5:25}

>>> for key in x: print(key, x[key])

11

24

39

4 16

5 25

>>> for k,v in [Link](): print(k,v)

11

24

39

4 16

5 25

List of Dictionaries:

>>> customers = [{"uid":1,"name":"John"},

{"uid":2,"name":"Smith"},

{"uid":3,"name":"Andersson"},

>>>>>> print(customers)

[{'uid': 1, 'name': 'John'}, {'uid': 2, 'name': 'Smith'}, {'uid': 3, 'name': 'Andersson'}]

## Print the uid and name of each customer

>>> for x in customers: print(x["uid"], x["name"])

John

Smith

Andersson

##Modify an entry, This will change the name of customer 2 from Smith to Charlie

>>> customers[2]["name"]="charlie"

>>> print(customers)

[{'uid': 1, 'name': 'John'}, {'uid': 2, 'name': 'Smith'}, {'uid': 3, 'name': 'charlie'}] ##Add a new field to each entry

>>> for x in customers: x["password"]="123456" # any initial value

>>> print(customers)

[{'uid': 1, 'name': 'John', 'password': '123456'}, {'uid': 2, 'name': 'Smith', 'password': '123456'},

{'uid': 3, 'name': 'charlie', 'password': '123456'}]

##Delete a field

>>> del customers[1]

>>> print(customers)

[{'uid': 1, 'name': 'John', 'password': '123456'}, {'uid': 3, 'name': 'charlie', 'password': '123456'}]

>>> del customers[1]

>>> print(customers)

[{'uid': 1, 'name': 'John', 'password': '123456'}]

##Delete all fields

>>> for x in customers: del x["uid"]

>>> x

{'name': 'John', 'password': '123456'}

Sequences:

A sequence is a succession of values bound together by a container that reflects their type. Almost every
stream that you put in python is a sequence. Some of them are:

String

List

Tuples

Range object

String: A string is a group of characters. Since Python has no provision for arrays, we simply use strings. This
is how we declare a string. We can use a pair of single or double quotes. Every string object is of the type ‘str’.
>>> type("name")

<class 'str'>

>>> name=str()

>>> name ''

>>> a=str('mrcet')

>>> a

'mrcet'

>>> a=str(mrcet)

>>> a[2]

'c'

List: A list is an ordered group of items. To declare it, we use square brackets.

>>> college=["cse","it","eee","ece","mech","aero"]

>>> college[1] 'it'

>>> college[:2] ['cse', 'it']

>>> college[:3] ['cse', 'it', 'eee']

>>> college[3:] ['ece', 'mech', 'aero']

>>> college[0]="csedept"

>>> college

['csedept', 'it', 'eee', 'ece', 'mech', 'aero']

Tuple: It is an immutable group of items. When we say immutable, we mean we cannot change a single value
once we declare it.

>>> x=[1,2,3]

>>> y=tuple(x)

>>> y (1, 2, 3)

>>> hello=tuple(["mrcet","college"])

>>> hello ('mrcet', 'college')

Range object: A range() object lends us a range to iterate on; it gives us a list of numbers.

>>> a=range(4)

>>> type(a)

<class 'range'>

>>> for i in range(1,6,2): print(i)

3
5

Some of the python sequence operations and functions are:

Indexing

Slicing

Adding/Concatenation

Multiplying

Checking membership

Iterating

Len()

Min()

Max()

Sum()

Sorted()

Count()

Index()

Indexing

Access any item in the sequence using its index.

Slicing

Slice out substrings, sub lists, sub tuples using index [start : stop : step size]

>>> x='computer'

>>> x[1:4]

'omp'

>>> x[1:6:2]

'opt'

>>> x[3:]

'puter'

>>> x[:5]

'compu'

>>> x[-1]

'r'

>>> x[-3:]

'ter'

>>> x[:-2]

'comput'

>>> x[::-2]

'rtpo'
>>> x[::-1]

'retupmoc'

Adding/concatenation:

Combine 2 sequences of same type using +.

Multiplying:

Multiply a sequence using *.

Checking Membership:

Test whether an item is in or not in a sequence.

Iterating:

Iterate through the items in asequence

>>> x=[1,2,3]

>>> for item in x:

print(item*2)

If we want to display the items of a given list with index then we have to use “enumerate” keyword.

>>> x=[5,6,7]

>>> for item,index in enumerate(x): print(item,index)

05

16

27

len():

It will count the number of items in a given sequence.

min():

Finds the minimum item in a given sequence lexicographically.

It is an alpha-numeric type but cannot mix types.

>>> x=["apple","ant1","ant",11]

>>> print(min(x))

Traceback (most recent call last):

File "<pyshell#73>", line 1, in <module> print(min(x))

TypeError: '<' not supported between instances of 'int' and 'str'

max():

Finds the maximum item in a given sequence

It is an alpha-numeric type but cannot mix types.

>>> x=["hello","yummy1","zebra1",22]

>>> print(max(x))

Traceback (most recent call last):

File "<pyshell#79>", line 1, in <module> print(max(x))

TypeError: '>' not supported between instances of 'int' and 'str'

Sum:

Finds the sum of items in a sequence

>>> x=[1,2,3,4,5]

>>> print(sum(x))

15

>>> print(sum(x[-2:])) 9

Entire string must be numeric type.

>>> x=[1,2,3,4,5,"mrcet"]

>>> print(sum(x))

Traceback (most recent call last):

File "<pyshell#83>", line 1, in <module> print(sum(x))

TypeError: unsupported operand type(s) for +: 'int' and 'str'

Sorted():

Returns a new list of items in sorted order but does not change the original list.

Count():

It returns the count of an item

Index()

Returns the index of first occurrence

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):

[Link](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]

Similarily 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}

String Sliceing in Python

If you want to slice strings in Python, it’s going to be as simple as this one line below. res_s =s[
start_pos:end_pos:step ]

Here,

res_s stores the returned sub-string,

s is the given string,

start_pos is the starting index from which we need to slice the string s,

end_pos is the ending index, before which the slicing operation would end,

step is the steps the slicing process would take from start_pos to end_pos.

Note: All of the above three parameters are optional. By default, start_pos is set to 0, end_pos is considered
equal to the length of the string, and step is set to 1.

Now let us take some examples to understand how to slice strings in Python in a better way.

Slice Strings in Python – Examples

Slicing Python strings can be done in different ways.

Usually, we access string elements(characters) using simple indexing that starts from 0 up to n-1(n is the
length of the string). Hence for accessing the 1st element of a string string1, we can simply use the below
code.

s1 =String1[0]

Again, there is another way to access these characters, that is, using negative indexing. Negative indexing
starts from -1 to -n(n is the length for the given string). Note, negative indexing is done from the other end of
the string. Hence, to access the first character this time we need to follow the below-given code.

s1 =String1[-n]

Now let us look at some ways following which we can slice a string using the above concept.

Slice Strings in Python with Start and End

We can easily slice a given string by mentioning the starting and ending indices for the desired sub-string we
are looking for. Look at the example given below, it explains string slicing using starting and ending indices for
both usual and negative indexing method.

#string slicing with two parameters

s ="Hello World!" res1 =s[2:8]

res2 =s[-4:-1] #using negative indexing

print("Result1 = ",res1) print("Result2 = ",res2)

Output:

Result1 = llo Wo Result2 = rld

Here,

We initialize a string, s as “Hello World!”,

At first, we slice the given string with starting index 2 and ending index as 8. This means that the resultant
sub-string would contain the characters from s[2] to s[8-1],

Similarly, for the next one, the resultant sub-string should contain characters from s[-4] to s[(-1)-1]. Hence, our
output is justified.

Slice Strings Using Only the Start or End

As mentioned earlier, all of the three parameters for string slicing are optional. Hence, we can easily
accomplish our tasks using one parameter. Look at the code below to get a clear understanding.

#string slicing with one parameter s1="Charlie"

s2="Jordan"

res1 =s1[2:] #default value of ending position is set to the length of string res2 =s2[:4] #default value of starting
position is set to 0

print("Result1 = ",res1) print("Result2 = ",res2)

Output:

Result1 = arlie Result2 = Jord

Here,

We firstly initialize two strings, s1 and s2,

For slicing both of them we just mention the start_pos for s1, and end_pos for s2 only,

Hence for res1, it contains a sub-string of s1 from index 2(as mentioned) up to the last(by default it is set to
n-1). Whereas for res2, the range of the indices lies from 0 upto 4(mentioned).
 Slice Strings in Python with Step Parameter

The step value decides the jump the slicing operation would take from one index to the other. Look at the
example below carefully.

#string slicing with step parameter s="Python"

s1="Kotlin"

res =s[0:5:2]

res1 =s1[-1:-4:-2] #using negative parameters

print("Resultant sliced string = ",res)

print("Resultant sliced string(negative parameters) = ",res1)

Output:

Resultant sliced string = Pto

Resultant sliced string(negative parameters) = nl

In the code above,

We initialize two strings s and s1, and try to slice them for the given starting and ending indices as we did for
our first example,

But this time we have mentioned a step value which was set to 1 by default for the previous examples,

For res, having a step size 2 means, that while the traversal to get the substring from index 0 to 4, each time
the index would be increased by a value of 2. That is the first character is s[0] (‘P’), the next characters in the
sub-string would be s[0+2], and s[2+2], until the index is just less than 5.

For the next one i.e. res1, the step mentioned is (-2). Hence, similar to the previous case, the characters in

the substring would be s1[-1] , then s1[(-1)+(-2)] or s1[-3] until the index is just less than (-4).

Reversing a String using Slicing in Python

With the use of negative index string slicing in Python, we can also reverse the string and store it in another
variable. For doing so we just need to mention a step size of (-1).

Let us see how that works in the example given below.

#reversing string using string slicing s="AskPython"

rev_s =s[::-1] #reverse string stored into rev_s

print(rev_s)

Output:

nohtyPksA

As we can see, the string s is reversed and stored into rev_s. Note: For this case too, the original string
remains intact and untouched.

UNIT – III

Arrays - Array Data Structure Overview, Types of Arrays, Operations on Arrays, Arrays vs [Link]

Linear Search and Binary [Link] - Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort
Python arrays:

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. 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.

Array Representation

Arrays can be declared in various ways in different languages. Below is an illustration.

Elements

Int array [10] = {10, 20, 30, 40, 50, 60, 70, 80, 85, 90}

Type Name Size Index 0

As per the above illustration, following are the important points to be considered.

Index starts with 0.

Array length is 10 which means it can store 10 elements.

Each element can be accessed via its index. For example, we can fetch an element at index 6 as 70

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.

Array is created in Python by importing array module to the python program. Then the array is declared as
shown below.

from array import * arrayName=array(typecode, [initializers])

Typecode are the codes that are used to define the type of value the array will hold. Some common typecodes
used are:

Creating an array:

from array import *

array1 = array('i', [10,20,30,40,50]) for x in array1:

print(x)

Output:

>>>
RESTART: C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/[Link] 10

20

30

40

50

Accessing Array Element

We can access each element of an array using the index of the element. from array import *

array1 = array('i', [10,20,30,40,50]) print (array1[0])

print (array1[2])

Output:

RESTART: C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link] 10

30

Insertion Operation

Insert operation is to insert one or more data elements into an array. Based on the requirement, a new
element can be added at the beginning, end, or any given index of array.

Here, we add a data element at the middle of the array using the python in-built insert() method. from array
import *

array1 = array('i', [10,20,30,40,50]) [Link](1,60)

for x in array1:

print(x)

Output:

============================================

C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link]

=========================================== 10

60

20

30

40

50

>>>

Deletion Operation

Deletion refers to removing an existing element from the array and re-organizing all elements of an array.
Here, we remove a data element at the middle of the array using the python in-built remove() method. from
array import *

array1 = array('i', [10,20,30,40,50]) [Link](40)

for x in array1:

print(x)
Output:

============================================

C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link]

=========================================== 10

20

30

50

Search Operation

You can perform a search for an array element based on its value or its index. Here, we search a data element
using the python in-built index() method. from array import *

array1 = array('i', [10,20,30,40,50]) print ([Link](40))

Output:

============================================

C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link]

=========================================== 3

>>>

Update Operation

Update operation refers to updating an existing element from the array at a given index. Here, we simply
reassign a new value to the desired index we want to update.

from array import *

array1 = array('i', [10,20,30,40,50]) array1[2] = 80

for x in array1:

print(x)

Output:

============================================

C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link]

=========================================== 10

20

80

40

50

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 -

list = [31, 60, 19, 12]

print(list)

print(type(list))

Output:

Example - 2

# creating a list containing elements

# belonging to different data types

list1 = [1,"Yash",['a','e']]

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.

import array as arr

or

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 -
Import array as arr

array_1 = [Link]("i", [31, 60,19, 12])

print(array_1)

print(type(array_1))

Output:

Example - 2: Using Numpy array

import numpy as np

array_sample = [Link](["str", 'sunil', 'sachin', 'megha', 'deepti'])

print (array_sample)

print(type(array_sample))

Output:

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

Difference between Array and List

Searching - Linear Search and Binary Search.

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.

Concept of Linear Search

Let's understand the following steps to find the element key = 7 in the given list.

Step - 1: Start the search from the first element and Check key = 7 with each element of list x.
Step - 2: If element is found, return the index position of the key.

Step - 3: If element is not found, return element is not present.

Linear Search Algorithm

There is list of n elements and key value to be searched. Below is the linear search algorithm.

LinearSearch(list, key)

for each item in the list

if item == value

return its index position

return -1 Python Program

Let's understand the following Python implementation of the linear search algorithm.

Program

def linear_Search(list1, n, key): 2.

# Searching list1 sequentially

for i in range(0, n):

if (list1[i] == key):

return i

return -1

list1 = [1 ,3, 5, 4, 7, 9]

key = 7

n = len(list1)

res = linear_Search(list1, n, key)

if(res == -1):

print("Element not found")

else:

print("Element found at index: ", res)

Output:

Element found at index: 4

Explanation:
In the above code, we have created a function linear_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.

Linear Search Complexity

Time complexity of linear search algorithm -

Base Case - O(1)

Average Case - O(n)

Worst Case -O(n)

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.

To get the fast result, we can use the binary search algorithm.

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.

We have a sorted list of elements, and we are looking for the index position of 45.

[12, 24, 32, 39, 45, 50, 54]

So, we are setting two pointers in our list. One pointer is used to denote the smaller value called low and the
second pointer is used to denote the highest value called high.

Next, we calculate the value of the middle element in the array.

mid = (low+high)/2

Here, the low is 0 and the high is 7.

mid = (0+7)/2

mid = 3 (Integer)

Now, we will compare the searched element to the mid index value. In this case, 32 is not equal to 45. So we
need to do further comparison to find the element.

If the number we are searching equal to the mid. Then return mid otherwise move to the further comparison.

The number to be search is greater than the middle number, we compare the n with the middle element of the
elements on the right side of mid and set low to low = mid + 1.

Otherwise, compare the n with the middle element of the elements on the left side of mid and set high to high
= mid - 1.

Repeat until the number that we are searching for is found.

Implement a Binary Search in Python

First, we implement a binary search with the iterative method. We will repeat a set of statements and iterate
every item of the list. We will find the middle value until the search is complete.

Let's understand the following program of the iterative method. Python Implementation

# 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 12.

# 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

# element was not present in the list, return -1

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, Selection Sort, Insertion Sort, Merge Sort, Quick Sort.

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:

Starting with the first element (index=0), compare the current element with the next element of a list.

If the current element is greater (>) than the next element of the list then swap them.

If the current element is less (<) than the next element of the list move to the next element.

Repeat step 1 until it correct order is framed.

For ex: list1= [10, 15, 4, 23, 0] so here we are comparing values again

If > --- yes ---- swap and again, so we use loops. If < --- No Do nothing/remains same

#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:

C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link]

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:

C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link] 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:
C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link]

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): [Link](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:

C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link]

enter how many numbers:5 enter values

77

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:

C:/Users/MRCET/AppData/Local/Programs/Python/Python38-2/pyyy/[Link] unsorted list1 is [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:

Starting from the first element search for smallest/biggest element in the list of numbers.

Swap min/max number with first element

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:

list1=[5,3,7,1,9,6]

print(list1)

for i in range(len(list1)): min_val=min(list1[i:]) min_ind=[Link](min_val)

list1[i],list1[min_ind]=list1[min_ind],list1[i] print(list1)

Output:

C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link] [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=[Link](min_val)

list1[i],list1[min_ind]=list1[min_ind],list1[i] print(list1)

Output:

C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link]

[5, 3, 7, 1, 9, 6]

[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 ().

Insertion Sort:

Insertion sort is not a fast sorting algorithm. It is useful only for small datasets.

It is a simple sorting algorithm that builds the final sorted list one item at a time.

Algorithm:

Consider the first element to be sorted & the rest to be unsorted.

Take the first element in unsorted order (u1) and compare it with sorted part elements(s1)

If u1<s1 then insert u1 in the correct order, else leave as it is.

Take the next element in the unsorted part and compare with sorted element.

Repeat step 3 and step 4 until all the elements get sorted.

# Write a python program to arrange the elements in ascending order using insertion sort (with functions)

def insertionsort(my_list):

#we need to sorrt the unsorted part at a time. for index in range(1,len(my_list)):

current_element=my_list[index] pos=index

while current_element<my_list[pos-1]and pos>0: my_list[pos]=my_list[pos-1]

pos=pos-1 my_list[pos]=current_element

list1=[3,5,1,0,10,2] num=int(input(“enter how many elements to be in list”))

insertionsort(list1) list1=[int(input()) for i in range (num)] print(list1)

Output:

C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link] [0, 1, 2, 3, 5, 10]

# Write a python program to arrange the elements in descending order using insertion sort (with functions)

def insertionsort(my_list):

#we need to sorrt the unsorted part at a time. for index in range(1,len(my_list)):

current_element=my_list[index] pos=index

while current_element>my_list[pos-1]and pos>0: my_list[pos]=my_list[pos-1]

pos=pos-1 my_list[pos]=current_element

#list1=[3,5,1,0,10,2]

#insertionsort(list1) #print(list1)

num=int(input("enter how many elements to be in list")) list1=[int(input())for i in range(num)] insertionsort(list1)

print(list1)

Output:
C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link] enter how many
elements to be in list 5

10

[10, 8, 4, 2, 1]

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:

Split the unsorted list.

Compare each of the elements and group them

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 mergesort(list1): if len(list1)>1:

mid=len(list1)//2 left_list=list1[:mid] right_list=list1[mid:] mergesort(left_list) mergesort(right_list) i=0

j=0 k=0

while i<len(left_list) and j<len(right_list): if left_list[i]<right_list[j]:

list1[k]=left_list[i] i=i+1

k=k+1 else:

list1[k]=right_list[j] j=j+1

k=k+1

while i<len(left_list):

list1[k]=left_list[i] i=i+1

k=k+1

while j<len(right_list): list1[k]=right_list[j] j=j+1

k=k+1

num=int(input("how many numbers in list1")) list1=[int(input()) for x in range(num)] mergesort(list1)

print("sorted list1",list1)

Output:

C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link]

how many numbers in list15 5

10

1
66

sorted list1 [1, 5, 9, 10, 66]

Quick Sort:

Algorithm:

Select the pivot element

Find out the correct position of pivot element in the list by rearranging it.

Divide the list based on pivot element

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)

#To get the correct position of pivot element: def pivot_place(list1,first,last):

pivot=list1[first] left=first+1 right=last

while True:

while left<=right and list1[left]<=pivot: left=left+1

while left<=right and list1[right]>=pivot: right=right-1

if right<left: break

else:

list1[left],list1[right]=list1[right],list1[left]

list1[first],list1[right]=list1[right],list1[first] return right

#second function

def quicksort(list1,first,last): if first<last:

p=pivot_place(list1,first,last) quicksort(list1,first,p-1) quicksort(list1,p+1,last)

#main fun list1=[56,25,93,15,31,44]

n=len(list1) quicksort(list1,0,n-1) print(list1)

Output:

C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link] [15, 25, 31, 44, 56, 93]

# Write a python program to arrange the elements in descending order using Quick sort (with functions)

#To get the correct position of pivot element: def pivot_place(list1,first,last):

pivot=list1[first] left=first+1 right=last

while True:

while left<=right and list1[left]>=pivot: left=left+1

while left<=right and list1[right]<=pivot: right=right-1

if right<left: break

else:
 list1[left],list1[right]=list1[right],list1[left] list1[first],list1[right]=list1[right],list1[first] return right

def quicksort(list1,first,last): if first<last:

p=pivot_place(list1,first,last) quicksort(list1,first,p-1) quicksort(list1,p+1,last)

#main fun list1=[56,25,93,15,31,44]

n=len(list1) quicksort(list1,0,n-1) print(list1)

Output:

C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link] [93, 56, 44, 31, 25, 15]

UNIT - IV

Linked Lists - Singly Linked Lists, Doubly Linked Lists, Circular Linked Lists.

Stacks - Overview of Stack, Implementation of Stack (List & Linked list), Applications of Stack

Queues: Overview of Queue, Implementation of Queue(List & Linked list), Applications of Queues, Priority
Queues.

Linked Lists:

Linked lists are one of the most commonly used data structures in any programming [Link] Lists, on
the other hand, are different. Linked lists, do not store data at contiguous memory locations. For each item in
the memory location, linked list stores value of the item and the reference or pointer to the next item. One pair
of the linked list item and the reference to next item constitutes a node.

The following are different types of linked lists.

Single Linked List

A single linked list is the simplest of all the variants of linked lists. Every node in a single linked list contains an
item and reference to the next item and that's it.

Doubly Linked List

Circular Linked List

Linked List with Header

# Python program to create a linked list and display its elements.

The program creates a linked list using data items input from the user and displays it.

Solution:

Create a class Node with instance variables data and next.

Create a class Linked List with instance variables head and last_node.

The variable head points to the first element in the linked list while last_node points to the last.

Define methods append and display inside the class Linked List to append data and display the linked list
respectively.
Create an instance of Linked List, append data to it and display the list.

Program:

Program Explanation

An instance of Linked List is created.

The user is asked for the number of elements they would like to add. This is stored in n.

Using a loop, data from the user is appended to the linked list n times.

The linked list is displayed.

Output:

C:/Users/MRCET/AppData/Local/Programs/Python/Python38-32/pyyy/[Link] How many elements would you

like to add? 5

Enter data item: 4 Enter data item: 4 Enter data item: 6 Enter data item: 8

Enter data item: 9

The linked list: 4 4 6 8 9

Doubly Linked List

A doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes.

Each node contains three fields: two link fields (references to the previous and to the next node in the
sequence of nodes) and one data field.

Advantages of Doubly Linked List

Traversal can be done on either side means both in forward as well as backward.

Deletion Operation is more efficient if the pointer to delete node is given.

Disadvantages of Linked List

Since it requires extra pointer that is the previous pointer to store previous node reference.

After each operation like insertion-deletion, it requires an extra pointer that is a previous pointer which needs
to be maintained.

So, a typical node in the doubly linked list consists of three fields:

Data represents the data value stored in the node.

Previous represents a pointer that points to the previous node.

Next represents a pointer that points to the next node in the list.

The above picture represents a doubly linked list in which each node has two pointers to point to previous and
next node respectively. Here, node 1 represents the head of the list. The previous pointer of the head node will
always point to NULL. Next pointer of node one will point to node 2. Node 5 represents the tail of the list
 whose previous pointer will point to node 4, and the next will point to NULL.

ALGORITHM:

Define a Node class which represents a node in the list. It will have three properties: data, previous which will
point to the previous node and next which will point to the next node.

Define another class for creating a doubly linked list, and it has two nodes: head and tail. Initially, head and tail
will point to null.

addNode() will add node to the list:

It first checks whether the head is null, then it will insert the node as the head.

Both head and tail will point to a newly added node.

Head's previous pointer will point to null and tail's next pointer will point to null.

If the head is not null, the new node will be inserted at the end of the list such that new node's previous pointer
will point to tail.

The new node will become the new tail. Tail's next pointer will point to null.

a. display() will show all the nodes present in the list.

Define a new node 'current' that will point to the head.

Print [Link] till current points to null.

Current will point to the next node in the list in each iteration.

PROGRAM:

#Represent a node of doubly linked list

class Node:

def init (self,data):

[Link] = data;

[Link] = None;

[Link] = None; 7.

class DoublyLinkedList:

#Represent the head and tail of the doubly linked list

def init (self):

[Link] = None;

[Link] = None; 13.

#addNode() will add a node to the list

def addNode(self, data):

#Create a new node

newNode = Node(data); 18.

#If list is empty

if([Link] == None):

#Both head and tail will point to newNode

[Link] = [Link] = newNode;

#head's previous will point to None

[Link] = None;

#tail's next will point to None, as it is the last node of the list

[Link] = None;

else:

#newNode will be added after tail such that tail's next will point to newNode

[Link] = newNode;

#newNode's previous will point to tail

[Link] = [Link];

#newNode will become new tail

[Link] = newNode;

#As it is last node, tail's next will point to None

[Link] = None; 36.

#display() will print out the nodes of the list

def display(self):

#Node current will point to head

current = [Link];

if([Link] == None):

print("List is empty");

return;

print("Nodes of doubly linked list: ");

while(current != None):

#Prints each node by incrementing pointer.

print([Link]),;

current = [Link]; 49.

dList = DoublyLinkedList();

#Add nodes to the list

[Link](1);

[Link](2);

[Link](3);

[Link](4);
 [Link](5);

#Displays the nodes present in the list

[Link]();

Output:

Circular Linked List

The circular linked list is a kind of linked list. First thing first, the node is an element of the list, and it has two
parts that are, data and next. Data represents the data stored in the node, and next is the pointer that will point
to the next node. Head will point to the first element of the list, and tail will point to the last element in the list. In
the simple linked list, all the nodes will point to their next element and tail will point to null.

The circular linked list is the collection of nodes in which tail node also point back to head node. The diagram
shown below depicts a circular linked list. Node A represents head and node D represents tail. So, in this list,
A is pointing to B, B is pointing to C and C is pointing to D but what makes it circular is that node D is pointing
back to node A.

ALGORITHM:

Define a Node class which represents a node in the list. It has two properties data and next which will point to
the next node.

Define another class for creating the circular linked list, and it has two nodes: head and tail. It has two
methods: add() and display() .

add() will add the node to the list:

It first checks whether the head is null, then it will insert the node as the head.

Both head and tail will point to the newly added node.

If the head is not null, the new node will be the new tail, and the new tail will point to the head as it is a circular
linked list.

a. display() will show all the nodes present in the list.

Define a new node 'current' that will point to the head.

Print [Link] till current will points to head

Current will point to the next node in the list in each iteration.

PROGRAM:

#Represents the node of list.

class Node:

def init (self,data):

[Link] = data;

[Link] = None; 6.

class CreateList:

#Declaring head and tail pointer as null.

def init (self):

[Link] = Node(None);

[Link] = Node(None);

[Link] = [Link];

[Link] = [Link]; 14.

#This function will add the new node at the end of the list.

def add(self,data):

newNode = Node(data);

#Checks if the list is empty.

if [Link] is None:

#If list is empty, both head and tail would point to new node.

[Link] = newNode;

[Link] = newNode;

[Link] = [Link];

else:

#tail will point to new node.

[Link] = newNode;

#New node will become new tail.

[Link] = newNode;

#Since, it is circular linked list tail will point to head.

[Link] = [Link]; 31.

#Displays all the nodes in the list

def display(self):

current = [Link];

if [Link] is None:

print("List is empty");

return;

else:

print("Nodes of the circular linked list: ");

#Prints each node by incrementing pointer.

print([Link]),

while([Link] != [Link]):

current = [Link];

print([Link]),

class CircularLinkedList:

cl = CreateList();

#Adds data to the list

[Link](1);

[Link](2);

[Link](3);

[Link](4);

#Displays all the nodes present in the list

[Link]();

Output:

Stacks:

Stack works on the principle of “Last-in, first-out”. 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"] [Link]("Ram") [Link]("Iqbal")

print(stack) print([Link]()) print(stack) print([Link]()) print(stack)

Output:

['Amar', 'Akbar', 'Anthony', 'Ram', 'Iqbal']

Iqbal

['Amar', 'Akbar', 'Anthony', 'Ram']

Ram

['Amar', 'Akbar', 'Anthony']

Stack Using Linked List

A stack using a linked list is just a simple linked list with just restrictions that any element will be added and
removed using push and pop respectively. In addition to that, we also keep top pointer to represent the top of
the stack. This is described in the picture given below.

Stack Operations:

push() : Insert the element into linked list nothing but which is the top node of Stack.
 pop() : Return top element from the Stack and move the top pointer to the second node of linked list or Stack.

peek(): Return the top element.

display(): Print all element of Stack.

A stack will be empty if the linked list won’t have any node i.e., when the top pointer of the linked list will be
null. So, let’s start by making a function to check whether a stack is empty or not.

Now, to push any node to the stack (S) - PUSH(S, n), we will first check if the stack is empty or not. If the stack
is empty, we will make the new node head of the linked list and also point the top pointer to it.

PUSH(S, n)

if IS_EMPTY(S) //stack is empty

[Link] = n //new node is the head of the linked list [Link] = n //new node is the also the top

If the stack is not empty, we will add the new node at the last of the stack. For that, we will point next of the top
to the new node - ([Link] = n) and the make the new node top of the stack - ([Link] = n).

PUSH(S, n)

if IS_EMPTY(S) //stack is empty

...

else

[Link] = n [Link] = n

Similarly, to remove a node (pop), we will first check if the stack is empty or not as we did in the
implementation with array.

POP(S)

if IS_EMPTY(S)

Error “Stack Underflow”

In the case when the stack is not empty, we will first store the value in top node in a temporary variable
because we need to return it after deleting the node.

POP(S)

if IS_EMPTY(S)
 ...

else

x = [Link]

Now if the stack has only one node (top and head are same), we will just make both top and head null.

POP(S)

if IS_EMPTY(S)

...

else

...

if [Link] == [Link] //only one node [Link] = NULL

[Link] = NULL

If the stack has more than one node, we will move to the node previous to the top node and make the next of
point it to null and also point the top to it.

POP(S)

...

...

if [Link] == [Link] //only one node

...

else

tmp = [Link]

while [Link] != [Link] //iterating to the node previous to top tmp = [Link]

[Link] = NULL //making the next of the node null [Link] = tmp //changing the top pointer

We first iterated to the node previous to the top node and then we marked its next to null - [Link] = NULL.
After this, we pointed the top pointer to it - [Link] = tmp.

At last, we will return the data stored in the temporary variable - return x.

Stack using linked list

class Node():

def init (self, data):

[Link] = data [Link] = None

class Stack():

def init (self):

[Link] = None [Link] = None

def traversal(s):

temp = [Link] #temporary pointer to point to head

a = ''

while temp != None: #iterating over stack a = a+str([Link])+'\t'

temp = [Link]

print(a)

def is_empty(s): if [Link] == None: return True return False

def push(s, n):

if is_empty(s): #empty [Link] = n

[Link] = n else:

[Link] = n [Link] = n

def pop(s):

if is_empty(s):

print("Stack Underflow") return -1000

else:

x = [Link]

if [Link] == [Link]: # only one node [Link] = None

[Link] = None else:

temp = [Link]

while [Link] != [Link]: #iterating to the last element temp = [Link]

[Link] = None del [Link]

[Link] = temp

return x
if name == ' main ':

s = Stack()

a = Node(10)

b = Node(20)

c = Node(30)

pop(s) push(s, a)

push(s, b)

push(s, c)

traversal(s) pop(s) traversal(s)

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.

Queue

Similar to stacks, a queue is also an Abstract Data Type or ADT. A queue follows FIFO (First-in, First out)
policy. It is equivalent to the queues in our general life. For example, a new person enters a queue at the last
and the person who is at the front (who must have entered the queue at first) will be served first.

Similar to a queue of day to day life, in Computer Science also, a new element enters a queue at the last (tail
of the queue) and removal of an element occurs from the front (head of the queue).

Similar to the stack, we will implement the queue using a linked list as well as with an array. But let’s first
discuss the operations which are done on a queue.
Enqueue → Enqueue is an operation which adds an element to the queue. As stated earlier, any new item
enters at the tail of the queue, so Enqueue adds an item to the tail of a queue.

Dequeue → It is similar to the pop operation of stack i.e., it returns and deletes the front element from the
queue.

isEmpty → It is used to check whether the queue has any element or not.

isFull → It is used to check whether the queue is full or not.

Front → It is similar to the top operation of a stack i.e., it returns the front element of the queue (but don’t
delete it).

Before moving forward to code up these operations, let’s discuss the applications of a queue.

Applications of Queue

Queues are used in a lot of applications, few of them are:

Queue is used to implement many algorithms like Breadth First Search (BFS), etc.

It can be also used by an operating system when it has to schedule jobs with equal priority

Customers calling a call center are kept in queues when they wait for someone to pick up the calls Queue
Using an Array

We will maintain two pointers - tail and head to represent a queue. head will always point to the oldest element
which was added and tail will point where the new element is going to be added.

To insert any element, we add that element at tail and increase the tail by one to point to the next element of
the array.

Suppose tail is at the last element of the queue and there are empty blocks before head as shown in the
picture given below.

In this case, our tail will point to the first element of the array and will follow a circular order.
Initially, the queue will be empty i.e., both head and tail will point to the same location i.e., at index 1. We can
easily check if a queue is empty or not by checking if head and tail are pointing to the same location or not at
any time.

Similarly, we will say that if the head of a queue is 1 more than the tail, the queue is full.

Now, we have to deal with the enqueue and the dequeue operations.

To enqueue any item to the queue, we will first check if the queue is full or not i.e., Enqueue(Q, x)

if isFull(Q)

Error “Queue Overflow”

else

If the queue is not full, we will add the element to the tail i.e, Q[[Link]] = x.

While adding the element, it might be possible that we have added the element at the last of the array and in
this case, the tail will go to the first element of the array.

Otherwise, we will just increase the tail by 1.

To dequeue, we will first check if the queue is empty or not. If the queue is empty, then we will throw an error.

Dequeue(Q, x) if isEmpty(Q)

Error “Queue Underflow” else

To dequeue, we will first store the item which we are going to delete from the queue in a variable because we
will be returning it at last.

Dequeue(Q, x) if isEmpty(Q)
Error “Queue Underflow” else

x = Q[[Link]]

Now, we just have to increase the head pointer by 1. And in the case when the head is at the last element of
the array, it will go 1.

class Queue:

def init (self, size): [Link] = 1

[Link] = 1

self.Q = [0]*(size) [Link] = size

def is_empty(self):

if [Link] == [Link]: return True

return False

def is_full(self):

if [Link] == [Link]+1: return True

return False

def enqueue(self, x): if self.is_full():

print("Queue Overflow") else:

self.Q[[Link]] = x

if [Link] == [Link]: [Link] = 1

else:

[Link] = [Link]+1

def dequeue(self):

if self.is_empty(): print("Underflow") else:

x = self.Q[[Link]]

if [Link] == [Link]: [Link] = 1

else:

[Link] = [Link]+1 return x

def display(self): i = [Link]

while(i < [Link]): print(self.Q[i]) if(i == [Link]): i = 0

i = i+1

if name == ' main ':

q = Queue(10) [Link](10) [Link](20) [Link](30) [Link](40) [Link](50) [Link]()

print("")

[Link]() [Link]() [Link]()

print("")

[Link](60) [Link](70) [Link]()

Queue Using Linked List

As we know that a linked list is a dynamic data structure and we can change the size of it whenever it is
needed. So, we are not going to consider that there is a maximum size of the queue and thus the queue will
never overflow. However, one can set a maximum size to restrict the linked list from growing more than that
size.

As told earlier, we are going to maintain a head and a tail pointer to the queue. In the case of an empty queue,
head will point to NULL.

We will point the head pointer to the first element of the linked list and the tail pointer to the last element of it
as shown in the picture given below.

The enqueue operation simply adds a new element to the last of a linked list.

However, if the queue is empty, we will simply make the new node head and tail of the queue.

To dequeue, we need to remove the head of the linked list. To do so, we will first store its data in a variable
because we will return it at last and then point head to its next element.

x = [Link] [Link] = [Link] return x

We will execute the above codes when the queue is not empty. If it is, we will throw the "Queue Underflow"
error.

Queue using Linked List

class Node():

def init (self, data): [Link] = data

[Link] = None

class Queue():

def init (self):

[Link] = None [Link] = None

def traversal(q):

temp = [Link] #temporary pointer to point to head

a = ''

while temp != None: #iterating over queue a = a+str([Link])+'\t'

temp = [Link]

print(a)

def is_empty(q):

if [Link] == None: return True

return False

def enqueue(q, n):

if is_empty(q): #empty [Link] = n

[Link] = n else:

[Link] = n [Link] = n

def dequeue(q):

if is_empty(q): print("Queue Underflow") return -1000

else:

x = [Link] temp = [Link] [Link] = [Link] del temp

return x

if name == ' main ': q = Queue()

a = Node(10)

b = Node(20)

c = Node(30)

dequeue(q) enqueue(q, a)

enqueue(q, b) enqueue(q, c)

traversal(q) dequeue(q) traversal(q)

Priority QueuesA queue has FIFO (first-in-first-out) ordering where items are taken out or accessed on a
first-come-first-served basis. Examples of queues include a queue at a movie ticket stand, as shown in the
illustration above. But, what is a priority queue?

A priority queue is an abstract data structure (a data structure defined by its behaviour) that is like a normal
queue but where each item has a special “key” to quantify its “priority”. For example, if the movie cinema
decides to serve loyal customers first, it will order them by their loyalty (points or number of tickets purchased).
In such a case, the queue for tickets will no longer be first-come-first-served, but most-loyal- first-served. The
customers will be the “items” of this priority queue while the “priority” or “key” will be their loyalty.

A priority queue can be of two types:

Max Priority Queue: Which arranges the data as per descending order of their priority.

Min Priority Queue: Which arranges the data as per ascending order of their priority.

In a priority queue, following factors come into play:

In priority queue, data when inserted, is stored based on its priority.

When we remove a data from a priority queue(min), the data at the top, which will be the data with least
priority, will get removed.

But, this way priority queue will not be following the basic priniciple of a queue, First in First Out(FIFO). Yes, it
won't! Because a priority queue is an advanced queue used when we have to arrange and manipulate data as
per the given priority.

Implementing Priority Queue

So now we will design our very own minimum priority queue using python list and object oriented concept.

Below are the algorithm steps:

Node: The Node class will be the element inserted in the priority queue. You can modify the Node class as per
your requirements.
insert: To add a new data element(Node) in the priority queue.

If the priority queue is empty, we will insert the element to it.

If the priority queue is not empty, we will traverse the queue, comparing the priorities of the existing nodes with
the new node, and we will add the new node before the node with priority greater than the new node.

If the new node has the highest priority, then we will add the new node at the end.

delete: To remove the element with least priority.

size: To check the size of the priority queue, in other words count the number of elements in the queue and
return it.

show: To print all the priority queue elements.

Priority Queue Program

# class for Node with data and priority class Node:

def init (self, info, priority):

[Link] = info [Link] = priority

# class for Priority queue class PriorityQueue:

def init (self):

[Link] = list()

# if you want you can set a maximum size for the queue

def insert(self, node):

# if queue is empty if [Link]() == 0:

# add the new node [Link](node) else:

# traverse the queue to find the right place for new node

for x in range(0, [Link]()):

# if the priority of new node is greater

if [Link] >= [Link][x].priority:

# if we have traversed the complete queue if x == ([Link]()-1):

# add new node at the end [Link](x+1, node) else:

continue else:

[Link](x, node) return True

def delete(self):
 # remove the first node from the queue return [Link](0)

def show(self):

for x in [Link]:

print str([Link])+" - "+str([Link])

def size(self):

return len([Link])

pQueue = PriorityQueue() node1 = Node("C", 3) node2 = Node("B", 2) node3 = Node("A", 1) node4 =

Node("Z", 26) node5 = Node("Y", 25) node6 = Node("L", 12)

[Link](node1) [Link](node2) [Link](node3) [Link](node4)

[Link](node5)

[Link](node6) [Link]() print(" ")

[Link]() [Link]()

UNIT -V

Graphs - Introduction, Directed vs Undirected Graphs, Weighted vs Unweighted Graphs, Representations,

Applications: Breadth First Search, Depth First Search.

Trees - Overview of Trees, Tree Terminology, Binary Trees: Introduction, Applications, Implementation. Tree
Traversals, Binary Search Trees: Introduction, Implementation, AVL Trees: Introduction, Rotations,

Implementation.
Graphs – Introduction:

A graph is an advanced data structure that is used to organize items in an interconnected network. Each item
in a graph is known as a node(or vertex) and these nodes are connected by edges.

In the figure below, we have a simple graph where there are five nodes in total and six edges.

The nodes in any graph can be referred to as entities and the edges that connect different nodes define the
relationships between these entities. In the above graph we have a set of nodes {V} = {A, B, C, D, E} and a set
of edges, {E} = {A-B, A-D, B-C, B-D, C-D, D-E} respectively

Types of Graphs

Let's cover various different types of graphs.

Null Graphs

A graph is said to be null if there are no edges in that graph. A pictorial representation of the null graph is
given below:

Undirected Graphs

If we take a look at the pictorial representation that we had in the Real-world example above, we can clearly
see that different nodes are connected by a link (i.e. edge) and that edge doesn't have any kind of direction

associated with it. For example, the edge between "Anuj" and "Deepak" is bi-directional and hence the
relationship between them is two ways, which turns out to be that "Anuj" knows "Deepak" and "Deepak" also
knows about "Anuj". These types of graphs where the relation is bi-directional or there is not a single direction,
are known as Undirected graphs.

A pictorial representation of another undirected graph is given below:

Directed Graphs

What if the relation between the two people is something like, "Shreya" know "Abhishek" but "Abhishek"
doesn't know "Shreya". This type of relationship is one-way, and it does include a direction. The edges with
arrows basically denote the direction of the relationship and such graphs are known as directed graphs.

A pictorial representation of the graph is given below:

It can also be noted that the edge from "Shreya" to "Abhishek" is an outgoing edge for "Shreya" and an
incoming edge for "Abhishek".

Cyclic Graph

A graph that contains at least one node that traverses back to itself is known as a cyclic graph. In simple
words, a graph should have at least one cycle formation for it to be called a cyclic graph.

A pictorial representation of a cyclic graph is given below:

It can be easily seen that there exists a cycle between the nodes (a, b, c) and hence it is a cyclic graph.
Acyclic Graph

A graph where there's no way we can start from one node and can traverse back to the same one, or simply
doesn't have a single cycle is known as an acyclic graph.

A pictorial representation of an acyclic graph is given below:

Weighted Graph

When the edge in a graph has some weight associated with it, we call that graph as a weighted graph. The
weight is generally a number that could mean anything, totally dependent on the relationship between the
nodes of that graph.

A pictorial representation of the weighted graph is given below:

It can also be noted that if any graph doesn't have any weight associated with it, we simply call it an
unweighted graph.

Connected Graph

A graph where we have a path between every two nodes of the graph is known as a connected graph. A path
here means that we are able to traverse from a node "A" to say any node "B". In simple terms, we can say that
if we start from one node of the graph we will always be able to traverse to all the other nodes of the graph
from that node, hence the connectivity.

A pictorial representation of the connected graph is given below:

Disconnected Graph

A graph that is not connected is simply known as a disconnected graph. In a disconnected graph, we will not
be able to find a path from between every two nodes of the graph.

A pictorial representation of the disconnected graph is given below:

Complete Graph

A graph is said to be a complete graph if there exists an edge for every pair of vertices(nodes) of that graph. A
pictorial representation of the complete graph is given below:

Multigraph

A graph is said to be a multigraph if there exist two or more than two edges between any pair of nodes in the
graph.

A pictorial representation of the multigraph is given below:

Commonly Used Graph Terminologies

Path - A sequence of alternating nodes and edges such that each of the successive nodes are connected by
the edge.
Cycle - A path where the starting and the ending node is the same.

Simple Path - A path where we do not encounter a vertex again.

Bridge - An edge whose removal will simply make the graph disconnected.

Forest - A forest is a graph without cycles.

Tree - A connected graph that doesn't have any cycles.

Degree - The degree in a graph is the number of edges that are incident on a particular node.

Neighbour - We say vertex "A" and "B" are neighbours if there exists an edge between them.

Weighted vs UnWeighted Graph

To understand difference between weighted vs unweighted graph, first we need to understand what weight
represent ?

A weight is a numerical value attached to each individual edge in the graph.

Weighted Graph will contains weight on each edge where as unweighted does not.

Following is an example, where both graphs looks exactly the same but one is weighted another is not.

What difference does it make ?

Let’s take the same example to find shortest path from A to F. Result is different, just because one is weighted
another doesn’t.

But how?

Because when you doesn’t have weight, all edges are considered equal. Shortest distance means less
number of nodes you travel.

But in case of weighted graph, calculation happens on the sum of weights of the travelled edges.

Breadth First Search:

BFS is an algorithm that is used to graph data or searching tree or traversing structures. The algorithm
efficiently visits and marks all the key nodes in a graph in an accurate breadthwise fashion.

This algorithm selects a single node (initial or source point) in a graph and then visits all the nodes adjacent to
the selected node. Once the algorithm visits and marks the starting node, then it moves towards the nearest
unvisited nodes and analyses them.

Once visited, all nodes are marked. These iterations continue until all the nodes of the graph have been
successfully visited and marked. The full form of BFS is the Breadth-first search.

Steps in Breadth First Search

Start by putting any one of the graph’s vertices at the back of a queue.

Take the front item of the queue and add it to the visited list.

Create a list of that vertex’s adjacent nodes. Add the ones which aren’t in the visited list to the back of the
queue.

Keep repeating steps 2 and 3 until the queue is empty.

Example of BFS

In the following example of DFS, we have used graph having 6 vertices. Example of BFS

Step 1)

Step 2)

Step 3)

Step 4)

8.

Remaining 0 adjacent and unvisited nodes are visited, marked, and inserted into the queue.

Step 5)

Depth First Search.

DFS is an algorithm for finding or traversing graphs or trees in depth-ward direction. The execution of the
algorithm begins at the root node and explores each branch before backtracking. It uses a stack data structure
to remember, to get the subsequent vertex, and to start a search, whenever a dead-end appears in any
iteration. The full form of DFS is Depth-first search.

Steps in Depth First Search

Start by putting any one of the graph’s vertices on top of a stack.

Take the top item of the stack and add it to the visited list.

Create a list of that vertex’s adjacent nodes. Add the ones which aren’t in the visited list to the top of the stack.

Keep repeating steps 2 and 3 until the stack is empty.

Example of DFS

In the following example of DFS, we have used an undirected graph having 5 vertices.
Step 1)

We have started from vertex 0. The algorithm begins by putting it in the visited list and simultaneously putting
all its adjacent vertices in the data structure called stack.

Step 2)

You will visit the element, which is at the top of the stack, for example, 1 and go to its adjacent nodes. It is
because 0 has already been visited. Therefore, we visit vertex 2.

Step 3)

Vertex 2 has an unvisited nearby vertex in 4. Therefore, we add that in the stack and visit it.

Step 4)

Finally, we will visit the last vertex 3, it doesn't have any unvisited adjoining nodes. We have completed the
traversal of the graph using DFS algorithm.

Tree Data Structures

Trees are non-linear data structures that represent nodes connected by edges. Each tree consists of a root
node as the Parent node, and the left node and right node as Child nodes.

Root → The topmost node of the hierarchy is called the root of the tree.

Child → Nodes next in the hierarchy are the children of the previous node.

Parent → The node just previous to the current node is the parent of the current node.

Siblings → Nodes with the same parent are called siblings.

Ancestors → Nodes which are higher in the hierarchy are ancestors of a given node.

Descendents → Nodes which are lower in the hierarchy are descendants of a given node.

Internal Nodes → Nodes with at least one child are internal nodes.

External Nodes/Leaves → Nodes which don't have any child are called leaves of a tree.

Edge → The link between two nodes is called an edge.

Level → The root of a tree is at level 0 and the nodes whose parent is root are at level 1 and so on.

Height → The height of a node is the number of nodes (excluding the node) on the longest path from the node
to a leaf.
Height of Tree → Height of a tree is the height of its root.

Depth → The depth of a node is the number of nodes (excluding the node) on the path from the root to the
node.

Node Degree → It is the maximum number of children a node has.

Tree Degree → Tree degree is the maximum of the node degrees. So, the tree degree in the above picture is
3.

Till now, we have an idea of what a tree is and the terminologies we use with a tree. But we don't know yet
what the specific properties of a tree are or which structure should qualify as a tree. So, let's see the properties
of a tree.

Properties of a Tree

A tree must have some properties so that we can differentiate from other data structures. So, let's look at the
properties of a tree.

The numbers of nodes in a tree must be a finite and nonempty set.

There must exist a path to every node of a tree i.e., every node must be connected to some other node.

There must not be any cycles in the tree. It means that the number of edges is one less than the number of
nodes.

Binary Trees

A binary tree is a tree in which every node has at most two children.

As you can see in the picture given above, a node can have less than 2 children but not more than that. We
can also classify a binary tree into different categories. Let's have a look at them:

Full Binary Tree → A binary tree in which every node has 2 children except the leaves is known as a full binary
tree.
Complete Binary Tree → A binary tree which is completely filled with a possible exception at the bottom level
i.e., the last level may not be completely filled and the bottom level is filled from left to right.

Let's look at this picture to understand the difference between a full and a complete binary tree.

A complete binary tree also holds some important properties. So, let's look at them.

The parent of node i is ■i2■■i2■. For example, the parent of node 4 is 2 and the parent of node 5 is also 2.

The left child of node i is 2i2i.

The right child of node i is 2i+12i+1

Perfect Binary Tree → In a perfect binary tree, each leaf is at the same level and all the interior nodes have
two children.

Thus, a perfect binary tree will have the maximum number of nodes for all alternative binary trees of the same
height and it will be 2h+1−12h+1−1 which we are going to prove next.

Maximum Number of Nodes in a Binary Tree

We know that the maximum number of nodes will be in a perfect binary tree. So, let's assume that the height
of a perfect binary tree is hh.

Number of nodes at level 0 = 20=120=1 Number of nodes at level 1 = 21=221=2 Similarly, the number of
nodes at level h = 2h2h

Thus, the total number of nodes in the tree = 20+21+...+2h20+21+...+2h

The above sequence is a G.P. with common ratio 2 and first term 1 and total number of terms are h+1. So, the
value of the summation will be 2h+1−12−1=2h+1−12h+1−12−1=2h+1−1.

Thus, the total number of nodes in a perfect binary tree = 2h+1−12h+1−1.

Height of a Perfect Binary Tree

We know that the number of nodes (n) for height (h) of a perfect binary tree = 2h+1−12h+1−1.

=>n=2∗2h−1=>n=2∗2h−1 or,2h=n+12or,2h=n+12 h=lgn+12h=lg n+12

Thus, the height of a perfect binary tree with n nodes = lgn+12lg n+12.

We know that the number of nodes at level i in a perfect binary tree = 2i2i. Thus, the number of leaves (nodes
at level h) = 2h2h.

Thus, the total number of non-leaf nodes = 2h+1−1−2h=2h−12h+1−1−2h=2h−1 i.e., number of leaf nodes

- 1.
Thus, the maximum number of nodes will be in a perfect binary tree and the minimum number of nodes will be
in a tree in which nodes are linked just like a linked list.

Array Representation of Binary Tree

In the previous chapter, we have already seen to make a node of a tree. We can easily use those nodes to
make a linked representation of a binary tree. For now, let's discuss the array representation of a binary tree.

We start by numbering the nodes of the tree from 1 to n(number of nodes).

As you can see, we have numbered from top to bottom and left to right for the same level. Now, these
numbers represent the indices of an array (starting from 1) as shown in the picture given below.

We can also get the parent, the right child and the left child using the properties of a complete binary tree we
have discussed above i.e., for a node i, the parent is ■i2■■i2■, the left child is 2i2i and the right child is
2i+12i+1.
 So, we represented a complete binary tree using an array and saw how to get the parent and children of any
node. Let's discuss about doing the same for an incomplete binary tree.

Array Representation of Incomplete Binary Tree

To represent an incomplete binary tree with an array, we first assume that all the nodes are present to make it
a complete binary tree and then number the nodes as shown in the picture given below.

Now according to these numbering, we fill up the array.

Coding a Binary Tree

For the linked representation, we can easily access the parent, right child and the left child with [Link],
[Link] and [Link] respectively.

So, we will first write explain the codes for the array representation and then write the full codes in C, Java and
Python for both array and linked representation.

Let's start by writing the code to get the right child of a node. We will pass the index and the tree to the
function - RIGHT_CHILD(index).

After this, we will check if there is a node at the index or not (if (T[index] != null)) and also if the index of the
right child (2∗index+12∗index+1) lies in the size of the tree or not i.e., if (T[index] != null and (2*index

+ 1) <= [Link]).

If the above condition is true, we will return the index of the right child i.e., return (2*index + 1).

Similarly, we can get the left child.

Similarly, we can also write the code to get the parent.

Code Using Array

'''

/\

/\

/\

AF
 /\/\

/\/\

EBRT

/\//\

G Q V J L '''

complete_node=15

tree=[None,'D','A','F','E','B','R','T','G','Q',None,None,'V',None,'J','L']

defget_right_child(index):

# node is not null

# and the result must lie within the number of nodes for a complete binary tree

iftree[index]!=Noneand((2*index)+1)<=complete_node: return(2*index)+1

# right child doesn't exist

Linked List Representation of Binary Tree

We use a double linked list to represent a binary tree. In a double linked list, every node consists of three
fields. First field for storing left child address, second for storing actual data and third for storing right child
address.

In this linked list representation, a node has the following structure...

Code Using Linked Representation

 '''

/\/\

/\/\

EBRT

/\//\

GQVJL

d=TreeNode('D') a=TreeNode('A') f=TreeNode('F') e=TreeNode('E') b=TreeNode('B') r=TreeNode('R')

t1=TreeNode('T') g=TreeNode('G') q=TreeNode('Q') v=TreeNode('V') j=TreeNode('J') l=TreeNode('L')

t=Tree(d)

[Link]=f [Link]=a

'''

/\

/\

Applications of Binary tree

Binary trees are used to represent a nonlinear data structure. There are various forms of Binary trees. Binary
trees play a vital role in a software application. One of the most important applications of the Binary tree is in
the searching algorithm.

A general tree is defined as a nonempty finite set T of elements called nodes such that:

The tree contains the root element

The remaining elements of the tree form an ordered collection of zeros and more disjoint trees T1, T2, T3, T4
…. Tn which are called subtrees.

Binary Tree Traversal

We are ready with a binary tree. Our next task would be to visit each node of it i.e., to traverse over the entire
tree. In a linear data structure like linked list, it was a simple task, we just had to visit the next pointer of the
node. But since a tree is a non-linear data structure, we follow different approaches. Generally, there are three
types of traversals:
Preorder Traversal

Postorder Traversal

Inorder Traversal

Basically, each of these traversals gives us a sequence in which we should visit the nodes. For example, in
preorder traversal we first visit the root, then the left subtree and then the right subtree. Each traversal is
useful in solving some specific problems. So, we choose the method of traversal accroding to the need of the
problem we are going to solve. Let's discuss each of them one by one.

Preorder Traversal

In preorder traversal, we first visit the root of a tree, then its left subtree and after visiting the left subtree, the
right subtree.

So, we are first checking if the node is null or not - if(n != null). After this, we are visiting the root i.e., printing its
data - print([Link]). Then we are visiting the left subtree - PREORDER([Link]).

At last, we are visiting the right subtree - PREORDER([Link]). So, we will first visit the root as shown in the
picture given below.

Then, we will visit the left subtree.

In this left subtree, again we will visit its root and then its left subtree.

At last, we will visit the right subtree.

Postorder Traversal

In postorder traversal, we first visit the left subtree, then the right subtree and at last, the root.

We will first visit the left subtree.

When there is no left subtree, we will visit the right subtree.

Since the right subtree is null, we will visit the root.

Similarly, we will visit every other node.

Inorder Traversal

In inorder traversal, we first visit the left subtree, then the root and lastly, the right subtree.

142

We can also see the inorder traversal as projection of the tree on an array as shown in the picture given
below.

Binary Search Tree

In a binary tree, every node can have a maximum of two children but there is no need to maintain the order of
nodes basing on their values. In a binary tree, the elements are arranged in the order they arrive at the tree
from top to bottom and left to right.

A binary tree has the following time complexities...

Search Operation - O(n)

Insertion Operation - O(1)

Deletion Operation - O(n)

To enhance the performance of binary tree, we use a special type of binary tree known as Binary Search Tree.
Binary search tree mainly focuses on the search operation in a binary tree. Binary search tree can be defined
as follows...

In a binary search tree, all the nodes in the left subtree of any node contains smaller values and all the nodes
in the right subtree of any node contains larger values as shown in the following figure...

Example

The following tree is a Binary Search Tree. In this tree, left subtree of every node contains nodes with smaller
values and right subtree of every node contains larger values.

Every binary search tree is a binary tree but every binary tree need not to be binary search tree.

Operations on a Binary Search Tree

The following operations are performed on a binary search tree...

Search

Insertion

Deletion

Search Operation in BST

In a binary search tree, the search operation is performed with O(log n) time complexity. The search operation
is performed as follows...

Step 1 - Read the search element from the user.

Step 2 - Compare the search element with the value of root node in the tree.

Step 3 - If both are matched, then display "Given node is found!!!" and terminate the function

Step 4 - If both are not matched, then check whether search element is smaller or larger than that node value.

Step 5 - If search element is smaller, then continue the search process in left subtree.

Step 6- If search element is larger, then continue the search process in right subtree.

Step 7 - Repeat the same until we find the exact element or until the search element is compared with the leaf
node

Step 8 - If we reach to the node having the value equal to the search value then display "Element is found"
and terminate the function.

Step 9 - If we reach to the leaf node and if it is also not matched with the search element, then display
"Element is not found" and terminate the function.
Insertion Operation in BST

In a binary search tree, the insertion operation is performed with O(log n) time complexity. In binary search
tree, new node is always inserted as a leaf node. The insertion operation is performed as follows...

Step 1 - Create a newNode with given value and set its left and right to NULL.

Step 2 - Check whether tree is Empty.

Step 3 - If the tree is Empty, then set root to newNode.

Step 4 - If the tree is Not Empty, then check whether the value of newNode is smaller or larger than the node
(here it is root node).

Step 5 - If newNode is smaller than or equal to the node then move to its left child. If newNode is larger than
the node then move to its right child.

Step 6- Repeat the above steps until we reach to the leaf node (i.e., reaches to NULL).

Step 7 - After reaching the leaf node, insert the newNode as left child if the newNode is smaller or equal to that
leaf node or else insert it as right child.

Deletion Operation in BST

In a binary search tree, the deletion operation is performed with O(log n) time complexity. Deleting a node
from Binary search tree includes following three cases...

Case 1: Deleting a Leaf node (A node with no children)

Case 2: Deleting a node with one child

Case 3: Deleting a node with two children

Case 1: Deleting a leaf node

We use the following steps to delete a leaf node from BST...

Step 1 - Find the node to be deleted using search operation

Step 2 - Delete the node using free function (If it is a leaf) and terminate the function.

Case 2: Deleting a node with one child

We use the following steps to delete a node with one child from BST...

Step 1 - Find the node to be deleted using search operation

Step 2 - If it has only one child then create a link between its parent node and child node.

Step 3 - Delete the node using free function and terminate the function.

Case 3: Deleting a node with two children

We use the following steps to delete a node with two children from BST...

Step 1 - Find the node to be deleted using search operation

Step 2 - If it has two children, then find the largest node in its left subtree (OR) the smallest node in its right
subtree.

Step 3 - Swap both deleting node and node which is found in the above step.
Step 4 - Then check whether deleting node came to case 1 or case 2 or else goto step 2

Step 5 - If it comes to case 1, then delete using case 1 logic.

Step 6- If it comes to case 2, then delete using case 2 logic.

Step 7 - Repeat the same process until the node is deleted from the tree.

Example

Construct a Binary Search Tree by inserting the following sequence of numbers...

10,12,5,4,20,8,7,15 and 13

Above elements are inserted into a Binary Search Tree as follows...

[Link]=data [Link]=None [Link]=None [Link]=None

classBinarySearchTree: def init (self): [Link]=None

defminimum(self,x): [Link]!=None: x=[Link]

returnx

definsert(self,n): y=None temp=[Link] whiletemp!=None: y=temp [Link]<[Link]: temp=[Link] else:

temp=[Link]

[Link]=y

ify==None:#newly added node is root

[Link]=n [Link]<[Link]: [Link]=n

else: [Link]=n

deftransplant(self,u,v): [Link]==None: [Link]=v elifu==[Link]: [Link]=v

else: [Link]=v

ifv!=None: [Link]=[Link]

defdelete(self,z): [Link]==None: [Link](z,[Link])

[Link]==None: [Link](z,[Link])

else:

y=[Link]([Link])#minimum element in right subtree

[Link]!=z: [Link](y,[Link]) [Link]=[Link] [Link]=y

[Link](z,y) [Link]=[Link]

[Link]=y

definorder(self,n): ifn!=None: [Link]([Link]) print([Link]) [Link]([Link])

if name ==' main ': t=BinarySearchTree()

a=Node(10) b=Node(20) c=Node(30) d=Node(100) e=Node(90) f=Node(40) g=Node(50) h=Node(60)

i=Node(70) j=Node(80) k=Node(150) l=Node(110) m=Node(120)

[Link](a) [Link](b) [Link](c) [Link](d) [Link](e)

AVL Tree

AVL tree is a height-balanced binary search tree. That means, an AVL tree is also a binary search tree but it is
a balanced tree. A binary tree is said to be balanced if, the difference between the heights of left and right
subtrees of every node in the tree is either -1, 0 or +1. In other words, a binary tree is said to be balanced if the
height of left and right children of every node differ by either -1, 0 or +1. In an AVL tree, every node maintains
an extra information known as balance factor. The AVL tree was introduced in the year 1962 by

G.M. Adelson-Velsky and E.M. Landis.

An AVL tree is defined as follows...

Balance factor of a node is the difference between the heights of the left and right subtrees of that node. The
balance factor of a node is calculated either height of left subtree - height of right subtree (OR) height of right
subtree - height of left subtree. In the following explanation, we calculate as follows...

Example of AVL Tree

The above tree is a binary search tree and every node is satisfying balance factor condition. So this tree is
said to be an AVL tree.

Every AVL Tree is a binary search tree but every Binary Search Tree need not be AVL tree.

AVL Tree Rotations

In AVL tree, after performing operations like insertion and deletion we need to check the balance factor of
every node in the tree. If every node satisfies the balance factor condition then we conclude the operation
otherwise we must make it balanced. Whenever the tree becomes imbalanced due to any operation we use
rotation operations to make the tree balanced.

Rotation operations are used to make the tree balanced.

There are four rotations and they are classified into two types.

Single Left Rotation (LL Rotation)

In LL Rotation, every node moves one position to left from the current position. To understand LL Rotation, let
us consider the following insertion operation in AVL Tree...

Single Right Rotation (RR Rotation)

In RR Rotation, every node moves one position to right from the current position. To understand RR Rotation,
let us consider the following insertion operation in AVL Tree...
Left Right Rotation (LR Rotation)

The LR Rotation is a sequence of single left rotation followed by a single right rotation. In LR Rotation, at first,
every node moves one position to the left and one position to right from the current position. To understand LR
Rotation, let us consider the following insertion operation in AVL Tree...

Right Left Rotation (RL Rotation)

The RL Rotation is sequence of single right rotation followed by single left rotation. In RL Rotation, at first
every node moves one position to right and one position to left from the current position. To understand RL
Rotation, let us consider the following insertion operation in AVL Tree...

Operations on an AVL Tree

The following operations are performed on AVL tree...

Search

Insertion

Deletion

Search Operation in AVL Tree

In an AVL tree, the search operation is performed with O(log n) time complexity. The search operation in the
AVL tree is similar to the search operation in a Binary search tree. We use the following steps to search an
element in AVL tree...

Step 1 - Read the search element from the user.

Step 2 - Compare the search element with the value of root node in the tree.

Step 3 - If both are matched, then display "Given node is found!!!" and terminate the function

Step 4 - If both are not matched, then check whether search element is smaller or larger than that node value.

Step 5 - If search element is smaller, then continue the search process in left subtree.
Step 6 - If search element is larger, then continue the search process in right subtree.

Step 7 - Repeat the same until we find the exact element or until the search element is compared with the leaf
node.

Step 8 - If we reach to the node having the value equal to the search value, then display "Element is found"
and terminate the function.

Step 9 - If we reach to the leaf node and if it is also not matched with the search element, then display
"Element is not found" and terminate the function.

Insertion Operation in AVL Tree

In an AVL tree, the insertion operation is performed with O(log n) time complexity. In AVL Tree, a new node is
always inserted as a leaf node. The insertion operation is performed as follows...

Step 1 - Insert the new element into the tree using Binary Search Tree insertion logic.

Step 2 - After insertion, check the Balance Factor of every node.

Step 3 - If the Balance Factor of every node is 0 or 1 or -1 then go for next operation.

Step 4 - If the Balance Factor of any node is other than 0 or 1 or -1 then that tree is said to be imbalanced. In
this case, perform suitable Rotation to make it balanced and go for next operation.

Example: Construct an AVL Tree by inserting numbers from 1 to 8.

Deletion Operation in AVL Tree

The deletion operation in AVL Tree is similar to deletion operation in BST. But after every deletion operation,
we need to check with the Balance Factor condition. If the tree is balanced after deletion go for next operation
otherwise perform suitable rotation to make the tree Balanced.