Python Data Structures for Engineers
Python Data Structures for Engineers
This book:
Rakesh Nayak
and Nishu Gupta
Front cover image: Rakesh Nayak
Reasonable efforts have been made to publish reliable data and information, but the author and
publisher cannot assume responsibility for the validity of all materials or the consequences of their
use. The authors and publishers have attempted to trace the copyright holders of all material repro-
duced in this publication and apologize to copyright holders if permission to publish in this form
has not been obtained. If any copyright material has not been acknowledged please write and let us
know so we may rectify in any future reprint.
Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced,
transmitted, or utilized in any form by any electronic, mechanical, or other means, now known
or hereafter invented, including photocopying, microfilming, and recording, or in any information
storage or retrieval system, without written permission from the publishers.
For permission to photocopy or use material electronically from this work, access www.copyright
.com or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA
01923, 978-750-8400. For works that are not available on CCC please contact mpkbookspermis-
sions@ tandf.co.uk
Trademark notice: Product or corporate names may be trademarks or registered trademarks and
are used only for identification and explanation without intent to infringe.
Typeset in Sabon
by Deanta Global Publishing Services, Chennai, India
Contents
1 Introduction to Python 1
1.1 Variables, identifiers and keywords 1
1.2 Input and output 2
1.3 Indentation 5
1.4 Comment statement 5
1.5 Standard data types 5
1.6 Operators 14
1.7 Flow control statements 19
1.8 Functions 30
1.9 Classes and objects 39
1.10 Variables and methods 45
1.11 Public, private and protected variables 49
1.12 Methods 51
1.13 Class inside a class (inner class) 54
True–false questions 56
Fill-in-the-blank questions 57
Multiple-choice questions 57
Descriptive questions 62
Answers to true–false questions 62
Answers to fill-in-the-blank questions 62
Answers to multiple-choice questions 62
v
vi Contents
3 Arrays 87
3.1 Introduction 88
3.2 Multidimensional arrays 104
3.3 Applications 105
True–false questions 123
Fill-in-the-blank questions 123
Multiple-choice questions 123
Descriptive questions 130
Answers to true–false questions 130
Answers to fill-in-the-blank questions 130
Answers to multiple-choice questions 130
5 Stacks 183
5.1 Stacks 183
5.2 Stack operations 184
5.3 Stack (ADT) 186
5.4 Implementation 187
5.5 Applications of stack 209
C ontents vii
6 Queues 227
6.1 Queue 227
6.2 Queue operations 228
6.3 Queue (ADT) 231
6.4 Implementation 232
6.5 Circular queue 251
6.6 Double-ended queue 257
6.7 Priority queue 262
True–false questions 273
Fill-in-the-blank questions 274
Multiple-choice questions 274
Descriptive questions 277
Answers to true–false questions 277
Answers to fill-in-the-blank questions 277
Answers to multiple-choice questions 277
7 Trees 278
7.1 Trees 278
7.2 Binary trees 280
7.3 Types of binary trees 281
7.4 Representation 285
7.5 Operations in a binary tree 287
7.6 Binary search trees 295
7.7 AVL trees (height-balanced trees) 315
7.8 Splay trees 328
True–false questions 336
Fill-in-the-blank questions 336
Multiple-choice questions 336
Descriptive questions 339
Answers to true–false questions 340
Answers to fill-in-the-blank questions 340
Answers to multiple-choice questions 340
viii Contents
8 Graphs 341
8.1 Introduction 341
8.2 Graph representation 348
8.3 Traversals 350
8.4 AND/OR graphs 359
8.5 Bi-connected components 361
8.6 Shortest-path problem 365
8.7 Topological sorting 367
True–false questions 369
Fill-in-the-blank questions 369
Multiple-choice questions 370
Descriptive questions 372
Answers to true–false questions 374
Answers to fill-in-the-blank questions 374
Answers to multiple-choice questions 374
Index 397
About the authors
ix
x About the authors
Introduction to Python
LEARNING OBJECTIVES
DOI: 10.1201/9781003510758-1 1
2 Data structures for engineers and scientists using Python
To get the input from the keyboard, the input() function is called. The gen-
eral format of the input function is
Introduction to Python 3
variable _ name input " Prompt Message"
The prompt message (optional) is something that is used to show a mes-
sage to the user before he/she types anything. It is basically used for better
understanding of the program. Output statements are the statements that
are used to show the result on the screen. For that, we use the print() state-
ment. A simple print statement looks like
All non-keyword arguments are converted to strings like str() and written
to the stream, separated by comma ‘sep’ and followed by ‘end’. Both sep
and end must be strings; use of sep and end is optional. If no objects are
given, print() will just print a blank line.
Example 1
name = input ("Enter your name :")
print("Your name is ", name)
Output
Enter your name : “Shiva”
Your name is Shiva
When we get an input from the keyboard by using input(), it takes strings.
To make it numeric we need to do type casting.
Example 2
no1 = int(input("Enter Number 1 : "))
no2 = int(input("Enter Number 2 : "))
sum = no1 + no2
print("The sum is ", sum)
Output
Enter Number 1 : 33
Enter Number 2 : 55
The sum is 88
Example 3
no1 = eval(input("Enter number 1 : "))
no2 = eval(input("Enter number 2 : "))
sum = no1 + no2
print("The sum is ", sum)
Output 1
Enter number 1 : 2
Enter number 2 : 3
The sum is 5
4 Data structures for engineers and scientists using Python
Output 2
Enter number 1 : "Hello"
Enter number 2 : " How are you !"
The sum is Hello How are you !
There are many escape characters that are used to format a print() state-
ment (Table 1.2).
Example 4
print("I am learning Python \nand I am enjoying it")
print("I am learning Python \tand I am enjoying it")
print("I\'m learning Python and I\'m enjoying it")
print("I am learning \"Python\" and I am enjoying it")
print("I am learning Python \\ I am enjoying it")
Output
I am learning Python
and I am enjoying it
I am learning Python and I am enjoying it
I'm learning Python and I'm enjoying it
I am learning "Python" and I am enjoying it
I am learning Python \ I am enjoying it
There are two keyword parameters that may be used with the print()
method. It is required to understand the following guidelines in order to
utilize it. A keyword argument is made up of three parts: a keyword that
identifies the argument (end or sep), an equal sign (=) and a value applied to
that argument. Any keyword argument must come after the final positional
argument (this is very important).
The end keyword argument determines the characters the print() func-
tion sends to the output once it reaches the end of its positional arguments.
This behavior can be changed too with the help of the second keyword
argument that is named sep (derived from separator). Note that the argu-
ment’s value may be an empty string also.
Introduction to Python 5
Example 5
print("I am learning Python","and","I am enjoying it.", sep =
"...", end = "***")
Output
I am learning Python...and...I am enjoying it.***
1.3 INDENTATION
1.4 COMMENT STATEMENT
Example 6
# This is a single line comment
no1 = eval(input("Enter Something : ")) # Anything after HASH
Symbol
""" This is
an example of
multiple line comment"""
print("You have entered ",no1)
Output
Enter Something : "Shiva"
You have entered Shiva
A data type indicates the type of data that the identifier is capable of stor-
ing. Because there are several data types available as shown next, the pro-
grammer can choose which one is most appropriate for their application. In
Python, each data type is a class.
6 Data structures for engineers and scientists using Python
• Numeric
• Boolean
• String
• List
• Tuple
• Set
• Dictionaries
Example 7
a1 = 5
a2 = 5.5
a3 = 5555555555555555555
a4 = 4+5j
print("int data is ",a1)
print("float data is ",a2)
print("long integer data is ",a3)
print("complex data is ",a4)
Output
int data is 5
float data is 5.5
long integer data is 5555555555555555555
complex data is (4+5j)
Example 8
a = True
b = False
a1 = bool(0)
b1 = bool(1)
print(a,a1)
print(b,b1)
Introduction to Python 7
Output
True False
False True
Example 9
str1 = "I am Learning Python"
str2 = 'I am enjoying it.'
no=2
print(str1)
print(str2)
print(str1 + str2)
print(str2 * no)
Output
I am Learning Python
I am enjoying it.
I am Learning PythonI am enjoying it.
I am enjoying it.I am enjoying it.
Substring of strings may be obtained by using the slice operator ([ ] and [:]),
with indices starting at 0 while moving from left to right and starting at –1
while moving from right to left.
The general syntax is string_Name=string[start : end : step], where the
start is the starting index, the end is the ending index and step (optional) is
the integer to skip before getting the next character. The start index must
always be smaller than the end index, or else the function will return an
empty string. Furthermore, the element in the end index is not included.
Example 10
str = "I am Learning Data Structure using Python"
print("The first character : ",str[0])
print("Sub string between index 0 and 13 : ",str[0:14])
print("Reverse Order : ",str[-1:-14:-1])
print("Every alternative character starting at index 0 :
",str[0::2])
Output
The first character : I
Sub string between index 0 and 13 : I am Learning
Reverse Order : nohtyP gnisu
Every alternative character starting at index 0 : Ia erigDt
tutr sn yhn
8 Data structures for engineers and scientists using Python
There are several built-in methods available with string. Few frequently
used methods are listed in Table 1.3.
1.5.4 List
A list is a mutable sequence of objects. It means we can change (update,
insert, delete) the objects in a list. It can have data of all different data types
under one name.
The general syntax for a list is
Just like elements of a string, the elements of a list can be accessed with an
index. A sub-list can be obtained from a list by slicing.
Introduction to Python 9
Example 11
lst=[]
print("Empty List : ",lst)
str1 = "Python"
lst = list(str1)
print("List from a string : ",lst)
lst = [4,4.5,"Hello",[1,2,3],(9,7,6),{'a','b','c'},{1:'aa',2:'bb'}]
print("Type of list : ",type(lst))
print("Data in list : ",lst)
print("Third element in the list ",lst[3])
print("1st to 4th element in the list : ",lst[1:5])
Output
Empty List : []
List from a string : ['P', 'y', 't', 'h', 'o', 'n']
Type of list : <class 'list'>
Data in list : [4, 4.5, 'Hello', [1, 2, 3], (9, 7, 6), {'a', 'c',
'b'}, {1: 'aa', 2: 'bb'}]
Third element in the list [1, 2, 3]
1st to 4th element in the list : [4.5, 'Hello', [1, 2, 3], (9, 7, 6)]
A new list can also be created from more than one existing list by the “+”
(concatenation) operation and “*” (repetition) operation.
Example 12
lst1 = [1,2,3]
lst2 = [7,8,9]
print("New list with concatenation is ", lst1 + lst2)
print("New list with repetition is ", lst1 * 2)
Output
New list with concatenation is [1, 2, 3, 7, 8, 9]
New list with repetition is [1, 2, 3, 1, 2, 3]
There are several built-in methods available with lists. Few frequently used
methods are listed in Table 1.4.
1.5.5 Tuple
A tuple is an immutable sequence of objects. It can have data of all different
data types under one name.
The general syntax for a list is
Or
Just like elements of a string, the elements of a tuple can be accessed with
an index. A sub-tuple can be obtained from a list by slicing.
To create a tuple with a single item, a comma is used after the element.
All the methods that are available with a list are the same in a tuple except
for insert() and deleting a few elements from a tuple.
Example 13
tup = ()
print("Empty Tuple : ",tup)
tup = (1,)
print("Tuple with one element: ",tup)
tup = (4,4.5,"Hello",[1,2,3],(9,7,6),{'a','b','c'},{1:'aa',2:
'bb'})
print("Type of Tuple : ",type(tup))
tup1 = tup[1:6:2]
print("1st element to 6th alternative element of tuple: ",tup1)
tup1 = (1,2,3)
tup2 = (7,8,9)
print("The tuple-2 is ",tup2)
tup3 = tup1 + tup2
print("New tuple with concatenation is ",tup3)
tup3 = tup1 * 3
print("New tuple with repetition is ",tup3)
Introduction to Python 11
Output
Empty Tuple : ()
Tuple with one element: (1,)
Type of Tuple : <class 'tuple'>
1st element to 6th alternative element of tuple: (4.5, [1, 2,
3], {'a', 'c', 'b'})
The tuple-2 is (7, 8, 9)
New tuple with concatenation is (1, 2, 3, 7, 8, 9)
New tuple with repetition is (1, 2, 3, 1, 2, 3, 1, 2, 3)
1.5.6 Set
A set is an unordered and unindexed collection of unique elements. A set in
Python is defined as a collection of elements in curly brackets.
Example 14
s = {1}
s1 = set()
print("Empty set : ",s,s1)
print("Type is : ",type(s),type(s1))
lst= [1,2,3,4,5]
set_A=set(lst)
print("The elements are ", set_A, " the type is ", type(set_A))
Output
Empty set : {1} set()
Type is : <class 'set'> <class 'set'>
The elements are {1, 2, 3, 4, 5} the type is <class 'set'>
There are several built-in set operations available. Few frequently used
methods are listed in Table 1.5.
Example 15
set_A = {1,2,3}
set_B = {3,4,5}
set_C = set_A | set_B
set_D = set_A & set_B
set_E = set_A ^ set_B
set_F = set_A.symmetric_difference(set_B)
print("Set A :",set_A)
print("Set B :",set_B)
print("Union of Set A and Set B :",set_C)
print("Intersection of Set A and Set B :",set_D)
print("Exclusive-or of Set A and Set B :",set_E)
print("Symmetric difference of Set A and Set B :",set_F)
12 Data structures for engineers and scientists using Python
Output
Set A : {1, 2, 3}
Set B : {3, 4, 5}
Union of Set A and Set B : {1, 2, 3, 4, 5}
Intersection of Set A and Set B : {3}
Exclusive-or of Set A and Set B : {1, 2, 4, 5}
Symmetric difference of Set A and Set B : {1, 2, 4, 5}
1.5.7 Dictionary
A dictionary in Python is an unordered collection of items. A key is assigned
to each item in a dictionary, and each key is connected with a value. The
items in a dictionary are not arranged in any particular sequence. Instead
of being regarded as a series of things, the dictionary is handled as a bag
of stuff.
The general syntax is
A dictionary starts and ends with a pair of curly brackets { }. The elements
are filled within the curly brackets in the form of a key and a value pair
separated by a colon. Each key-value pair is separated by comma. The ele-
ments inside a directory may have different types. The keys and the values
in a directory may be numeric or string. Each key must be unique. It means
Introduction to Python 13
it is not possible to have more than one key of the same value. A dictionary
is a one-way tool. It means, if a key is given, the corresponding value can
be retrieved, but not vice versa. Refer to an item in a dictionary by its key.
Example 16
dict_A={}
print("Empty Dictionary with { }",dict_A," type is ",type(dict_A))
dict_B= dict()
print("The Empty dictionary with dict() ", dict_B, " and ", dict_B)
dict_C = {1:'RAMA', 2:'HARI', 3:'SHYAM', 4:'KRISHNA'}
print('The dictionary with { }', dict_C)
dict_D = dict([ [1,'DURGA'],[2,'SITA'],
[3,'RADHA'],[4,'SARASWATI']])
print("The dictionary is with dict() ", dict_D)
keys = [1,2,3,4]
values = ['RAMA', 'LAKSHMAN', 'BHARAT', 'SATRUGHNA']
dict_E = dict(zip(keys,values))
print("The dictionary with zip ", dict_E)
Output
Empty Dictionary with { } {} type is <class 'dict'>
The Empty dictionary with dict() {} and {}
The dictionary with { } {1: 'RAMA', 2: 'HARI', 3: 'SHYAM', 4:
'KRISHNA'}
The dictionary is with dict() {1: 'DURGA', 2: 'SITA', 3:
'RADHA', 4: 'SARASWATI'}
The dictionary with zip {1: 'RAMA', 2: 'LAKSHMAN', 3: 'BHARAT',
4: 'SATRUGHNA'}
There are various ways we can access the dictionary. Some of the ways are
listed in Table 1.6.
Example 17
dict_A = {1:'RAMA', 2:'HARI', 3:'SHYAM', 4:'KRISHNA'}
print("The value with key = 2 ",dict_A[2])
print("The value with key=1 is ",dict_A.get(1))
print("The keys of the dictionary are ",dict_A.keys())
print("The items in the dictionary are ",dict_A.items())
14 Data structures for engineers and scientists using Python
Output
The value with key = 2 HARI
The value with key=1 is RAMA
The keys of the dictionary are dict_keys([1, 2, 3, 4])
The items in the dictionary are dict_items([(1, 'RAMA'), (2,
'HARI'), (3, 'SHYAM'), (4, 'KRISHNA')])
There are several built-in set operations available. Few frequently used
methods are listed in Table 1.7.
1.6 OPERATORS
1.6.1 Arithmetic operators
Python provides all basic arithmetic operators. The symbols that are used
for mathematical operations are +, -, *, /, **, %, //, and a unary minus sign
(Table 1.8).
Example 18
a = 10
b = 2
print("The value of a and b is ",a,b)
c = a + b
print(a," + ", b ," = ",c)
c = a - b
print(a," - ", b," = " ,c)
c = a * b
print(a," * ", b," = " ,c)
c = a / b
print(a," / ", b," = " ,c)
c = a ** b
print(a," ** ",b," = " ,c)
c = a // b
print(a," // ",b," = " ,c)
Output
The value of a and b is 10 2
10 + 2 = 12
10 - 2 = 8
10 * 2 = 20
10 / 2 = 5.0
10 ** 2 = 100
10 // 2 = 5
1.6.2 Assignment operators
The equal sign is used to assign a value to a variable. An assignment oper-
ator is a statement that assigns the right side value to the identifier that
is on the left of the “=” sign, and the most basic form of this statement
is Variable_name=Expressions. Other assignment operators are listed in
Table 1.9.
Example 19
a = 10
print("The value of a is ",a)
a += 10
print("The value of a after += is ",a)
a -= 10
print("The value of a after -= is ",a)
a *= 10
print("The value of a after *= is ",a)
a /= 2
print("The value of a after /= is ",a)
a **= 2
print("The value of a after **= is ",a)
a //= 10
print("The value of a after //= is ",a)
Output
The value of a is 10
The value of a after += is 20
The value of a after -= is 10
The value of a after *= is 100
The value of a after /= is 50.0
The value of a after **= is 2500.0
The value of a after //= is 250.0
Example 20
a = 10
b = 2
print("The value of a and b is ",a,b)
print(a," == ", b ,a == b)
print(a," != ", b, a != b)
print(a," > ", b, a > b)
print(a," < ", b, a < b)
print(a," >= ", b, a >= b)
print(a," <= ", b, a <= b)
Output
The value of a and b is 10 2
10 == 2 False
10 != 2 True
10 > 2 True
10 < 2 False
10 >= 2 True
10 <= 2 False
1.6.4 Logical operators
The meaning of these operators is the same as we use them in the English
language. Table 1.11 lists the Python logical operators and as it can be seen,
there are three operators in this set. They are and, or and not.
Example 21
a=20
b=10
c=30
if a >= b and a >= c:
print( "a is big")
elif b >= a and b >= c:
print ("b is big")
else:
print ("c is big")
Output
c is big
18 Data structures for engineers and scientists using Python
1.6.5 Membership operators
There are two membership operators to choose from. They are in and not
in. The in operator returns True if an item is part of a series, whereas the
not in operator returns False if the item is not a part of a series.
Example 22
lst = [1,2,3,4,5]
no1 =3
no2 = 10
print(no1," is in ",lst,no1 in lst)
print(no2," is not in ",lst,no2 not in lst)
Output
3 is in [1, 2, 3, 4, 5] True
10 is not in [1, 2, 3, 4, 5] True
1.6.6 Identity operators
We examine if two variables or objects are identical, that is, if they point
to the same memory address. The operators is and is not are called identity
operators.
Example 23
x = 5
print(type(x) is int)
print(type(x) is not int)
Output
True
False
1.6.7 Bitwise operators
There are six bitwise operators: bitwise AND, bitwise OR, bitwise XOR,
bitwise NOT(Complement), bitwise SHIFT TO THE LEFT and bitwise
SHIFT TO THE RIGHT (Table 1.12).
Example 24
x = 50
y = 2
print("x & y = ",x & y)
print("x | y = ",x | y)
print("x ^ y = ",x ^ y)
print("~x = ", ~x )
print("x << y = ",x << y)
print("x >> y = ",x >> y)
Output
x & y = 2
x | y = 50
x ^ y = 48
~x = -51
x << y = 200
x >> y = 12
1. if–else statement
2. if–elif–else statement
1. for loop
2. while loop
1.7.1 Conditional statements
Decision-making entails anticipating situations that may arise during pro-
gram execution and describing actions to be done in response to such con-
ditions. The conditional structures analyze several expressions and return
True or False as the result. Based on the result of the conditional expression
(True or False), we must decide which action to take or which statements
to execute.
This is the syntax for an if statement in Python:
if Conditional_Expression :
Statement(s)1
else:
Statement(s)2
In the if–else statement notice that the keyword if is used to begin the if–else
sentence. The conditional expression returns one of two values: True or
False. A colon (:) is necessary. Following the colon, begins the body of the
if, which consists of one or more statements. All of these statements must
also be tabbed. Any sentence that is not tabbed and follows the body of the
if–else clause is not included. If the conditional expression returns True,
the statements in the if body are performed. If the conditional expression
returns False, the lines in the else body are performed. The else clause in the
if–else statement is optional (Figure 1.1).
Introduction to Python 21
Example 25
a=10
b=15
if a < b:
print (a, "is small")
else:
print (b, "is small")
Output:
10 is small
if Conditional_Expression1 :
Statement(s)1
elif Conditional_Expression2 :
Statement(s)2
else:
Statement(s)3
22 Data structures for engineers and scientists using Python
Example 26
my_list1 = ["Hi", "How", "are", "You"]
my_list2 = ["I", "am", "Fine"]
my_input = input("Enter your String ")
if (my_input in my_list1):
print(my_input, "is in LIst1")
elif (my_input in my_list2):
print(my_input, 'is in List2')
else:
print(my_input, 'is NOT available in any List')
Output 1
Enter your String Hi
Hi is in LIst1
Output 2
Enter your String am
am is in List2
Output 3
Enter your String Happy
Happy is NOT available in any List
Introduction to Python 23
1.7.3 Ternary operator
The ternary operator is a simple if–else statement with only one line of
code. The ternary operator is used instead of multiline if–else expressions.
The syntax for a simple ‘ternary operator’ statement is:
Example 27
a = int(input("Enter First Number "))
b = int(input("Enter Second Number "))
print ("The bigger number is:", a) if a > b else print("The
bigger number is:",b)
Output
Enter First Number 10
Enter Second Number 5
The bigger number is: 10
1.7.4 Looping statement
Iterated (repeated) execution of statements is referred to as looping. In
Python, there are two types of looping structures:
1. while loop
2. for loop
[Link] While loop
While the conditional expression is true, the while loop repeats a series
of statements. Because the limit for terminating the loop is unknown in
advance, this looping structure is referred to as indefinite.
The syntax for while loop is:
while conditional_Expression :
Statement(s)1
else:
Statement(s)2
In the while loop, notice that, the while loop is initiated with the keyword
while. The conditional expression returns True or False. The conditional
expression does not have to be enclosed by a pair of parentheses. A colon
(:) is usually necessary. Following the colon, the following line begins the
body of the while loop, which consists of one or more statements. All of
these statements must also be tagged. Any statement that is not tabbed and
24 Data structures for engineers and scientists using Python
follows the body of the while loop is not a part of it. When the conditional
expression evaluates to True, the statement(s)1 in the while-loop body is
performed. Also, be aware that if the while conditional loop’s expression
constantly evaluates to true (never becomes false), the loop will never fin-
ish. A loop that never ends is referred to as an endless loop. The while–
else loop’s clause is optional. When the control variable’s value is not in
the collection of items, the statement(s)2 inside the else block is executed
(Figure 1.3).
Example 28
i = 0
while i < 5 :
print(i, "I \'m Learning Python")
i = i + 1
else:
print("inside the while-else")
print(i,"I \'m Enjoying it.")
Introduction to Python 25
Output
0 I 'm Learning Python
1 I 'm Learning Python
2 I 'm Learning Python
3 I 'm Learning Python
4 I 'm Learning Python
inside the while-else
5 I 'm Enjoying it.
Example 29
my_num = int(input("Enter a Number : "))
fact = 1
i = 1
while (i <= my_num):
fact = fact * i
i = i + 1
print("The factorial of ", my_num," is ", fact)
Output
Enter a Number : 7
The factorial of 7 is 5040
[Link] For loop
Another method for iterating (repeating) statement execution is the for
loop. The for loop is used in two situations: first, when we want to run over
each item in a sequence and, second, when we want to repeat an action a
specific number of times. This looping form is characterized as a definite
iteration since there is a defined boundary for loop termination.
The syntax of the for loop is:
It is important to remember that the for loop starts with the keyword for.
The loop’s control variable (or iterating variable) is any variable name fol-
lowing the for keyword; it counts the loop’s turns automatically. The in
keyword allows you to apply values to the control variable using the ele-
ment mentioned in the collection of items. The range() function, which is
responsible for producing all of the essential control variable values, may
be used to get the collection of items variable. This method creates inte-
ger sequences from only numbers as input. The usage of a colon is always
required. Following the colon, the body of the for loop, which consists
of one or more statements. All of these claims must be tagged as well.
26 Data structures for engineers and scientists using Python
Statements that are not tabbed and follow the body of the for loop are not
included in the for loop. The else condition in the for loop is optional. When
the value of the control variable is not found in the collection of items, the
statement(s)2 within the else block is performed.
When we know the maximum number of times the body of the loop will
be run, we utilize the for loop (Figure 1.4).
Example 30
for i in range(5):
print(i, "I \'m Learning Python")
else:
print("inside the for-else")
print(i,"I \'m Enjoying it.")
Output
0 I 'm Learning Python
1 I 'm Learning Python
2 I 'm Learning Python
3 I 'm Learning Python
4 I 'm Learning Python
inside the for-else
4 I 'm Enjoying it.
Example 31
my_num = int(input("Enter a Number : "))
fact = 1
for i in range (1,my_num+1):
fact = fact * i
print("The factorial of ", my_num," is ", fact)
Output
Enter a Number : 7
The factorial of 7 is 5040
Example 32
for i in range(5):
if(i == 3):
continue
print(i)
print("Out of Loop")
28 Data structures for engineers and scientists using Python
Output:
0
1
2
4
Out of Loop
The break statement ends the loop that contains it. When a break statement
is encountered within a loop, control moves to the sentence immediately
after the body of the loop.
Example 33
for i in range(5):
if(i == 3):
break
print(i)
i += 1
print("Out of Loop")
Output:
0
1
2
Out of Loop
The term pass refers to doing nothing (no code). It serves as a stand-in. It
means that instead of nothing, we write pass.
Example 34
for i in range(5):
if(i == 3):
pass
else:
print(i)
print("Out of Loop")
Output:
0
1
2
4
Out of Loop
[Link] Nested loops
A nested loop is one that is contained within another loop. Any loop can be
nested inside of another loop. This indicates that a for loop can be nested
within another for loop, or a for loop can be nested inside a while loop, or
Introduction to Python 29
a while loop can be nested inside another while loop, or a while loop can be
nested inside a for loop.
Example 35
lower = int(input("Enter lower range: "))
upper = int(input("Enter upper range: "))
if(lower < upper):
print("Prime numbers between ",lower," and ",upper," are :")
for num in range(lower, upper):
p = 1
for i in range(2, num):
if(num % i) == 0:
p = 0
break
if(p == 1):
print(num, "is a Prime Number")
Output
Enter lower range: 8
Enter upper range: 25
Prime numbers between 8 and 25 are :
11 is a Prime Number
13 is a Prime Number
17 is a Prime Number
19 is a Prime Number
23 is a Prime Number
1.7.6 Iterator
The iterator (iter) is a distinct data structure in Python. It may “iterate”
through the sequence, beginning at 0 and ending at the last item. Python
supports iterating not only over sequences, but also over non-sequence data
types (keys in a dictionary, lines in a file, and so on), as well as user-defined
objects. An iterator has a method named next that is unique to it (). As with
every looping structure, we increment the control variable to get to the next
value. The iterator__next__ () method is used to obtain the next item in an
iterator. After all of the objects have been exhausted, the iterator throws a
Stop exception.
Example 36
MyTup=(1, 'two', 3.0, 4j,"Five")
i = iter(MyTup)
print("The next item in Tuple is ",i.__next__())
Output
The next item in Tuple is 1
30 Data structures for engineers and scientists using Python
1.8 FUNCTIONS
There are various situations when we need to repeat a job several times
while building software. Consider a program that computes a number’s fac-
torial at various times throughout the program. It would be inefficient and
time-consuming to have to enter the same code for calculating the factorial
every time we required it. The solution is to give each piece of code a name
and then refer to it whenever it is required.
1.8.1 Defining a function
The general syntax for a function is:
1.8.2 Calling a function
A function cannot work by itself. It only works when we give it a command.
The next step is to call the function by name. When invoking the function,
we should provide the necessary values in the parentheses.
Example 37
def sum(a,b):
c = a + b
print("The sum is ",c)
A = int(input("Enter First number : "))
B = int(input("Enter Second number : "))
sum(A,B)
Introduction to Python 31
Output
Enter First number : 12
Enter Second number : 5
The sum is 17
Example 38
def sum(a,b):
c = a + b
return c
A = int(input("Enter First number : "))
B = int(input("Enter Second number : "))
print("The sum is ",sum(A,B))
Output
Enter First number : 12
Enter Second number : 5
The sum is 17
Example 39
def Arith_Op(a,b):
c = a + b
d = a - b
e = a * b
f = a / b
return c,d,e,f
A = int(input("Enter First number : "))
B = int(input("Enter Second number : "))
sum, sub, mul, div = Arith_Op(A,B)
print("The sum is ", sum)
print("The subtraction is ", sub)
print("The multiplication is ", mul)
print("The division is ", div)
32 Data structures for engineers and scientists using Python
Output
Enter First number : 15
Enter Second number : 3
The sum is 18
The subtraction is 12
The multiplication is 45
The division is 5.0
1.8.5 Pass by value
The phrase pass by value means that the function is given a copy of the vari-
able value, and any changes to that value will not be reflected outside the
function. In Python, object references are used to provide values to func-
tions. Everything is considered an object in Python. All numbers, strings,
tuples, lists and dictionaries are considered objects.
Example 40
def change(a):
a = a + 5
print("The value of a inside the function ",a)
a = int(input("Enter First number : "))
print("The value of a before calling the function ",a)
change(a)
print("The value of a after calling the function ",a)
Output:
Enter First number : 15
The value of a before calling the function 15
The value of a inside the function 20
The value of a after calling the function 15
1.8.6 Pass by reference
The phrase pass by reference refers to passing the variable’s reference or
memory address to the function. Because the function updates the variable
value through memory address, the new value is reflected both inside and
outside the function.
Example 41
def change(a,b):
[Link](b)
print("The list inside the function ",a)
lst = [5,10,15,20]
print("The list before calling the function ",lst)
change(lst,25)
print("The list after calling the function ",lst)
Output:
The list before calling the function [5, 10, 15, 20]
The list inside the function [5, 10, 15, 20, 25]
The list after calling the function [5, 10, 15, 20, 25]
Introduction to Python 33
1. Positional arguments
Assigning the ith argument to the ith parameter is called the positional
parameter; such arguments are called positional arguments.
Example 42
def Function_with_Parameter(a,b):
c= a + b
print("The sum of",a,"and",b,"is",c)
Function_with_Parameter(5,10)
Output
The sum of 5 and 10 is 15
2. Keyword arguments
Python has another pattern for passing arguments, termed keyword argu-
ment passing, in which the meaning of the argument is determined by its
name.
Example 43
def Function_with_Parameter(a,b):
c = a + b
print("The sum of",a,"and",b,"is",c)
Function_with_Parameter(a=5,b=10)
Output:
The sum of 5 and 10 is 15
34 Data structures for engineers and scientists using Python
Remember that the values supplied to the parameters are preceded by the
names of the target parameters, followed by the equal sign (=) and lastly a
value. It makes no difference in which order we supply the arguments. We
are unable to utilize a name for a parameter that does not exist. If we don’t,
we’ll get an error message. The value of each argument knows where it is
going because of the name. In both situations, the outcome is the same.
3. Default arguments
Example 44
def Function_with_Parameter(a,b,c=40):
sum1 = a + b + c
print("The sum of",a,",",b,"and",c,"is",sum1)
Function_with_Parameter(10,20)
Function_with_Parameter(10,b=30)
Output:
The sum of 10 , 20 and 40 is 70
The sum of 10 , 30 and 40 is 80
The function contains three arguments, as you can see. One of the param-
eters has the value 40 (i.e., c = 40). The remaining two parameters must be
given to the function when it is called (may be positional or may be key-
word argument).
The programmer might not be aware of how many values a function can
receive at any given time. The programmer is unable to identify the num-
ber of arguments to provide in the function definition. A variable length
parameter is utilized in the function definition for this reason. A variable
length argument is one that may be filled with any number of values. In
the function definition, the variable length parameter is written with a and
asterisk (*) before it:
Example 45
def sum_of_numbers(*no):
sum1 = 0
for i in no:
sum1 += i
return sum1
print("The sum is", sum_of_numbers())
print("The sum is", sum_of_numbers(4))
print("The sum is", sum_of_numbers(34,2))
print("The sum is", sum_of_numbers(15,50,52))
Output
The sum is 0
The sum is 4
The sum is 36
The sum is 117
1.8.8 Recursive functions
Recursion is a problem-solving technique. It involves breaking down a prob-
lem into smaller and smaller sub-problems until we get to a small enough
problem that can be solved quickly. A technique in which a function calls
itself is known as recursion.
There are three recursion laws:
1. A recursive function must provide a base case that indicates when the
function terminates.
2. A recursive function must progress toward the base case.
3. A recursive function must also call itself.
Example 46
def rec_fun_factorial(a):
if a<1:
return None
if a == 1:
return 1
else:
return rec_fun_factorial(a-1)*a
x = int(input("Enter a number: "))
print("The factorial of", x,"is", rec_fun_factorial(x))
Output:
Enter a number: 10
The factorial of 10 is 3628800
Observe that, the terminating condition is “if the value of ‘a’ is less than
1, it returns None and if the value of a is equal to 1” the factorial is 1.
Otherwise we call the function recursively to find the factorial.
36 Data structures for engineers and scientists using Python
Example 47
First= lambda a,b : a + b
no1 = int(input("Enter First Number : "))
no2 = int(input("Enter Second Number : "))
print("The sum is ", First(no1,no2))
Output:
Enter First Number : 12
Enter Second Number : 4
The sum is 16
With lambda functions, code becomes shorter, cleaner and more legible.
The lambda function returns the value of the expression implicitly, so we
don’t need to add a return statement directly. We can send a function as a
parameter to another function on occasion. Lambda functions are the best
option in these situations.
We can use lambda functions very commonly with inbuilt functions like
filter(), map() and reduce().
1.8.10 Function decorators
A decorator is a function that takes a parameter and returns another func-
tion. A decorator takes a function’s result, modifies it and then returns it.
As a result, decorators come in handy when a function requires some extra
processing. In most cases, the following stages are involved in the develop-
ment of decorators:
The current functions are given new meaning by the decorator. In other
words, decorators wrap one function around another. Decorators can also
be used on functions that are specified by the user.
Decorator is a function that takes a function as an argument and extends
the functionality of that function, returning a modified function with the
additional functionality. The behavior of the original function remains
unchanged while the functionality is extended.
Example 48
def improved_Div(func):
def inner(a,b):
if a < b and a==0:
return func(0,b)
elif b == 0:
return func(0,a)
elif a < b:
return func(b,a)
else:
return func(a,b)
return inner
@improved_Div
def Div(a,b):
return a/b
n,m= eval(input("Enter two numbers(separated by comma):"))
print("The division is", Div(n,m))
Output 1
Enter two numbers(separated by comma):15,6
The division is 2.5
Output 2
Enter two numbers(separated by comma):0,6
The division is 0.0
Output 3
Enter two numbers(separated by comma):23,0
The division is 0.0
1.8.11 Function generators
A generator is a function that is responsible for generating a set of values.
We may build generator functions in the same way we write regular func-
tions, but the yield keyword is used to return values. Iterators are used to
get one value at a time from a database.
38 Data structures for engineers and scientists using Python
Example 49
def even(n):
i = 1
while (i <= n):
if (i%2==0):
yield i
i += 1
j = even(10)
for k in j:
print(k)
Output
2
4
6
8
10
1.8.12 Modules
We also have the option of creating our own module. It’s comparable to
developing a standard program when we create our own modules. Two files
are required. The first one is the module itself. The file name is the module
name and must have a .py extension. The second file contains the code for
the new module.
Let us create a module “My_ Module.py”. It has two functions MY_
add(a,b) and My_mul(a,b).
Example 50
def MY_add(a,b):
return a + b
def My_mul(a,b):
return a * b
Example 51
import my_module
a=5
b=10
x= my_module.MY_add(a,b)
print("The sum is",x)
y= my_module.My_mul(a,b)
print("The multiplication is", y)
class ClassName:
'class documentation string'
class_suite
Notice that the term class is used to begin the definition. The keyword
class is followed by an identifier, which is the class’s name, and then a
colon (:). Inside the class, the class suite is described. Everything in the class
suite folder should be tabbed appropriately. The properties and behavior are
both contained in the class suite.
The variables are called attributes, and the methods specified in the class
are called behaviors. Each class is split into three sections:
Within its own namespace, a class has a name that uniquely identifies it.
Each class has its own set of attributes.
A class consists of a collection of operations. It is the capacity to carry
out certain tasks.
Example 52
class Two_Wheeler:
Make= 'Hero'
def __init__(self):
self.Regd_no= 'PY 37 PQ 7898'
self.owner= 'Srusti'
self.kind= 'Scooter'
def details(self):
print ('Owner ',self.owner, 'has a',self.kind,'with Regd
no',self.Regd_no)
Example 53
My_Byke = Two_Wheeler ()
My_Byke.details()
Two_Wheeler.details(My_Byke)
Output
Owner is : Srusti has a Scooter with no PY 37 PQ 7898
Owner is : Srusti has a Scooter with no PY 37 PQ 7898
There are two different ways we can use the methods defined in a class.
Method 1: Keep in mind that My_Byke is the object generated for the
class Two_Wheeler in the first line. The second line, My_Byke.details(),
invokes a method provided within the class. Remember that My_Byke is
an object of Two_Wheeler, and the details() method of My_Byke accepts
the parameter “self”. It implies we wish to use a method that is part of the
My_Byke object.
Method 2: The details() is a method defined in the Two_Wheeler class.
We must give the object name as a parameter to access the methods speci-
fied within the class. There might be a lot of objects produced from the same
class. The object name must be supplied as an argument to identify which
Introduction to Python 41
[Link] __init__()
This method’s primary goal is the initialization of an object.
The general syntax is:
__init__(self [,arguments])
It’s worth noting that the method’s name is “__init__()” and it’s preceded
and followed by two underscores (__). The method’s parameter is self and
in addition to it a list of arguments may be supplied. It does not return any
results.
The argument self is not passed to the method when it is called. Python
does it automatically. The argument self refers to the object itself. The
object that has invoked the method is this one. This indicates that the func-
tion __init__() accepts no parameters and should accept self. In the same
way, a method that accepts just one argument will really accept two: self
and the argument.
When an object is created, the first method that is automatically run is
this one. The __init__() function is invoked every time an object is created.
This function may be used to initialize variables in a class object.
There are two ways of assigning values to the variable in an object.
Method 1: Inside the __init__() method, we can assign the value to the
variable statically.
Example 54
class Two_Wheeler:
def __init__(self):
self.Regd_no= 'PY 37 PQ 7898'
self.owner = 'Srusti'
self.kind = 'Scooter'
My_byke = Two_Wheeler()
print(My_byke.Regd_no,My_byke.owner,My_byke.kind)
Take note of the method __init__(self). The value 'PY 37 PQ 7898' is set to
self.Regd_no, 'Srusti' is set to self.owner and 'Scooter' is set to self.kind in
42 Data structures for engineers and scientists using Python
this case. We did not explicitly use the __init__() method while instantiat-
ing the object My_byke. Automatically, variables are assigned to the values
supplied inside the method. The self refers to the object that is calling the
method, which in this instance is My_byke.
Method 2: A value can be passed to the __init__() method that can assign
the value to the variable dynamically.
Example 54
class Two_Wheeler:
def __init__(self,regd,owner,kind):
self.Regd_no = regd
self.owner = owner
self.kind = kind
My_byke = Two_Wheeler('PY 37 PQ 7898', 'Srusti', 'Scooter')
print(My_byke.Regd_no,My_byke.owner,My_byke.kind)
[Link] __new__()
The main purpose of this method is object creation. The general syntax is:
or
It is worth noting that the method’s name is “__new__()” and it’s preceded
and followed by two underscores (__). In the method, the argument is cls.
A list of arguments can be supplied in addition to cls. It returns an object.
It is a static method that returns a new object instance that accepts cls as
the first parameter. This approach is referred to as a “constructor.” When
the new class is ready to be instantiated, this method is invoked. This tech-
nique is used to modify an object’s creation.
Introduction to Python 43
Example 55
class Two_Wheeler(object):
def __new__(cls, regd, owner, kind):
if regd.find('TS') != -1 or regd.find('ts') != -1:
return object.__new__(cls)
else:
return None
def __init__(self, regd, owner, kind):
self.Regd_no= regd
self.owner= owner
self.kind = kind
def display(self):
print('Registration Number :',self.Regd_no, 'Owner :',self
.owner, 'Kind :',self.kind )
My_byke= Two_Wheeler('TS 04 DE 1234','Aruna Kranthi','Byke')
My_byke.display()
Output
Registration Number : TS 04 DE 1234 Owner : Aruna Kranthi Kind : Byke
cls, regd, owner and kind are the arguments in the __new__() function.
The method __new__() is a static method, as indicated by the cls argument.
When the value of regd is TS or ts, the object is created. When the object is
created, it returns the object together with its data, and when the object was
not generated, it returns None.
Before the __init__() function is invoked, the __new__() method is
called. It’s because value initialization is only possible when an instanti-
ation happens. When __new__() returns a class instance, the __init__()
method is executed automatically. This instance is given as a parameter
to the __init__() function. When utilizing the __new__() method, the __
init__() function is not necessary to initialize some value to a variable.
Example 56
class Two_Wheeler(object):
def __new__(cls, regd, owner, kind):
if regd.find('TS') != -1 or regd.find('ts') != -1:
self= object.__new__(cls)
self.Regd_no = regd
self.owner= owner
self.kind = kind
return self
else:
return None
def __str__(self):
return '{0}{1}'.format(self.__class__.__name__,
self.__dict__)
My_byke= Two_Wheeler('TS 04 DE 1234','Nakshatra','Byke')
print(My_byke.Regd_no,My_byke.owner,My_byke.kind)
My_byke1= Two_Wheeler('OD 23 EE 1034','Aruna Kranthi','Scooter')
print(My_byke1)
44 Data structures for engineers and scientists using Python
Output
TS 04 DE 1234 Nakshatra Byke
None
[Link] __del__()
The goal of the destructor is to clean up the object before the garbage col-
lector destroys it.
The general syntax is:
object.__del__(self):
Example 57
class Test:
def __init__(self,a):
self.no = a
print("Object ",a, " is Created")
def __del__(self):
print("Object is Deleted")
obj1 = Test(1)
obj1 = 5
obj2 = Test(2)
del obj2
print("Program End")
Introduction to Python 45
Output
Object 1 is Created
Object is Deleted
Object 2 is Created
Object is Deleted
Program End
Example 58
class Test:
def __init__(self,a):
self.no = a
print("Object ",a, " is Created")
def __del__(self):
print("Object is Deleted")
obj1 = Test(1)
obj2 = obj1
del obj1
print("Program End")
Output
Object 1 is Created
Program End
Observe that obj1 and obj2 both refer to the same object, which was cre-
ated by obj1 = Test (1). Because the object is still referenced by obj2, the
command del obj1 did not call the destructor.
The variables and the methods are an important part of any class.
1.10.1 Variables (attributes)
Object variables and class variables are the two types of variables. The class
variables are held by the class, but the object variables are owned by each
object.
46 Data structures for engineers and scientists using Python
Example 59
class Two_Wheeler:
def __init__(self):
self.Regd_no= 'PY 37 PQ 7898'
def kin(self):
self.kind = 'Scooter'
My_byke= Two_Wheeler()
My_byke.owner = 'Nakshatra'
My_byke.kin()
print("Owner : ", My_byke.owner, " has a ", My_byke.kind," with
redg no : ",My_byke.Regd_no)
Output
Owner : Nakshatra has a Scooter with redg no : PY 37 PQ 7898
instances. Only one copy of a static variable is produced for a class, and it
is shared by all objects of that class.
We can create a static variable in five different ways:
Example 60
class Two_Wheeler:
make = 'Hero'
def __init__(self):
self.Regd_no= 'PY 37 PQ 7898'
Two_Wheeler.kind = 'Scooter'
def colr(self):
Two_Wheeler.color = 'Red'
def capacity():
Two_Wheeler.engine = '100 CC'
@classmethod
def seat(cls):
cls.seater = 2
My_byke= Two_Wheeler()
My_byke.owner = 'Nakshatra'
My_byke.colr()
Two_Wheeler.capacity()
My_byke.seat()
print("Owner : ", My_byke.owner, " with redg no : ",My_byke.
Regd_no)
print("Make :",My_byke.make,"Colour :", Two_Wheeler.col
or,"Seater :",Two_Wheeler.seater)
Output:
Owner : Nakshatra with redg no : PY 37 PQ 7898
Make : Hero Colour : Red Seater : 2
In this example all the five ways of class variables are defined. The state-
ment make = 'Hero' is inside the class definition but not inside any method
that defines a class variable. Inside the __init__() method, the statement
Two_Wheeler.kind = 'Scooter' defines a class variable.
Inside colr(self), which is an instance method, the statement Two_Wheeler
.color = 'Red' defines a class variable.
Inside capacity(), which is a static method, the statement Two_Wheeler
.engine = '100 CC' defines a class variable. Inside seat(cls), which is a static
method, the statement cls. seater = 2 defines a class variable.
48 Data structures for engineers and scientists using Python
[Link] Accessing variables
It is not enough to just declare variables and assign values to them; we must
also be able to access them. In the software, there are several ways to access
these variables.
The different methods for accessing variables are:
Example 61
class Two_Wheeler:
make = 'Hero'
def __init__(self):
self.Regd_no= 'PY 37 PQ 7898'
Two_Wheeler.kind = 'Scooter'
def colr(self):
Two_Wheeler.color = 'Red'
@classmethod
def seat(cls):
cls.seater = 2
My_byke= Two_Wheeler()
My_byke.owner = 'Nakshatra'
My_byke.colr()
My_byke.seat()
print("Owner : ", My_byke.owner, " with redg no : ",My_byke.
Regd_no)
print("Make :",My_byke.make,"Colour :", Two_Wheeler.col
or,"Seater :",Two_Wheeler.seater)
My_byke1= Two_Wheeler()
My_byke1.Regd_no= 'TS 12 RR 3256'
My_byke1.owner = 'Srusti'
Two_Wheeler.make = 'Enfield'
Two_Wheeler.color = 'Black'
Two_Wheeler.seater = 1
print("Owner : ", My_byke.owner, " with redg no : ",My_byke1.
Regd_no)
print("Make :",My_byke1.make,"Colour :", Two_Wheeler.col
or,"Seater :",Two_Wheeler.seater)
Output
Owner : Nakshatra with redg no : PY 37 PQ 7898
Make : Hero Colour : Red Seater : 2
Owner : Nakshatra with redg no : TS 12 RR 3256
Make : Enfield Colour : Black Seater : 1
We can access the variable by object reference. The general syntax to access
a variable is object_name.variable_name. Observe that we have defined a
Introduction to Python 49
class variable make. In order to access the variable we can use the object
reference that is My_byke.make and My_byke1.make.
When accessing a static variable, we can use the class name instead of
the object name. Because the static variable is shared by all the objects gen-
erated, we may access it using the class name. To access a static variable,
use the general syntax class_name.variable_name. Observe that we have
access to the same static variable by writing Two_Wheeler.color and Two
_Wheeler.seater.
Static variables can also be accessed outside of the class. We may access
a class variable in the same manner we assigned values to it. class_name.
variable_name is the standard syntax for accessing a static variable outside
the class. Observe that there is a class variables make, colour and seater
defined inside the class changed to 'Enfield' , 'Black' and 1, respectively
after the creation of the object. There may be several class variables defined
for a class; we need to mention for which class variable the value is changed.
It is also possible to define a class variable the same way we changed the
value of a class variable.
Example 62
class Two_Wheeler:
def __init__(self,regd,knd,mk):
self.Regd_no= regd
self._kind = knd
self.__make = mk
def show(self):
print("From show() method:")
print(self.Regd_no)
print(self._kind)
print(self.__make)
My_byke= Two_Wheeler('PY 37 PQ 7898','Scooter','Hero')
My_byke.show()
print("Data saved by My_byke Object \n", My_byke.__dict__)
print("\nFrom Outside the class")
print(My_byke.Regd_no)
print(My_byke._kind)
print(My_byke.__make)
Output
From show() method:
PY 37 PQ 7898
Scooter
Hero
Data saved by My_byke Object
{'Regd_no': 'PY 37 PQ 7898', '_kind': 'Scooter', '_Two_
Wheeler__make': 'Hero'}
From Outside the class
PY 37 PQ 7898
Scooter
---------------------
-----
-----
-----
-----
-----
-----------------------------
AttributeError Traceback (most recent call last)
<ipython-input-38-d00836b25c11> in <module>()
19 print(My_byke.Regd_no)
20 print(My_byke._kind)
---> 21 print(My_byke.__make)
22
AttributeError: 'Two_Wheeler' object has no attribute '__make'
Introduction to Python 51
Observe that the variable Regd_no has no underscore, the variable kind
(_kind) has a single underscore and the variable make (__make) has two
underscores. We can see that these variables can be accessed from within
the class (show() method), and from outside the class the variables My_
byke.Regd_no and My_byke._kind can be accessed. Whereas, accessing
My_byke.__make outside the class raised AttributeError. The My_byke.__
dict__ shows the internal storage of data in the object My_byke.
1.12 METHODS
1. Instance method
2. Class method
3. Static method
1.12.1 Instance method
The term instance method refers to a method that works with the instance
variable. As an argument to the instance method, self must be provided.
Other than self, we may or may not have any other arguments.
In the parameter list, the first argument is always self. Furthermore, if
the method only has one argument, self, we do not supply any value for this
parameter when calling the method. Similarly, a method that accepts just
one argument will really accept two parameters, self and the parameter.
Example 63
class Two_Wheeler:
def __init__(self,regd,knd,mk):
self.Regd_no= regd
self.kind = knd
self.make = mk
def show(self):
print("From show() method:")
print("Registration no : ",self.Regd_no)
print("Kind of Two Wheeler : ",self.kind)
print("Make of the Two-Wheeler : ",self.make)
My_byke= Two_Wheeler('PY 37 PQ 7898','Scooter','Hero')
My_byke.show()
52 Data structures for engineers and scientists using Python
Output
From show() method:
Registration no : PY 37 PQ 7898
Kind of Two Wheeler : Scooter
Make of the Two-Wheeler : Hero
In this, self is a part of the parameter, so __init__() and show() are instance
methods.
1.12.2 Class method
We’ll need a class method to deal with the class variable. In two ways, class
methods vary from regular methods. They are first called by a class (not by
the instance of the class). Second, the class method’s first parameter is cls
rather than self. In most cases, class methods are used to instantiate a class
with arguments other than those given to the class constructor.
Example 64
class Two_Wheeler:
make = 'Hero'
def __init__(self,regd,knd):
self.Regd_no= regd
self.kind = knd
def mk_value(cls):
return cls.make
def show(self):
print("From show() method:")
print("Registration no : ",self.Regd_no)
print("Kind of Two Wheeler : ",self.kind)
print("Two wheeler maker : ",Two_Wheeler.
mk_value(Two_Wheeler))
My_byke = Two_Wheeler('PY 37 PQ 7898','Scooter')
My_byke.show()
Output
From show() method:
Registration no : PY 37 PQ 7898
Kind of Two Wheeler : Scooter
Two wheeler maker : Hero
It’s worth noting that the class variable make is specified. A class method
is required to access this class variable. Because it accepts cls as an argu-
ment, the method mk_value(cls) is a class method. We can see that we have
typed Two_Wheeler.mk value(Two_Wheeler) to retrieve the returned value
of this class method. It indicates that there is a class function mk_value(cls)
in the employee class, and we must give the class name Two_Wheeler as a
parameter.
Introduction to Python 53
1.12.3 Static method
Static methods are used when we require a method that has nothing to do
with the instance or class variables. This method can be used to interact
with a different class or object.
A static method is any functionality that belongs to a class but is not
required by the objects. The main distinction between static and class meth-
ods is that static methods do not take any extra parameters. They perform
the same functions as regular class methods.
Example 65
class Two_Wheeler:
make = 'Hero'
def __init__(self,regd,knd):
self.Regd_no= regd
self.kind = knd
def mk_value(cls):
return cls.make
def show(self):
print("From show() method:")
print("Registration no : ",self.Regd_no)
print("Kind of Two Wheeler : ",self.kind)
print("Two wheeler maker : ",Two_Wheeler.
mk_value(Two_Wheeler))
@staticmethod
def print_info():
print("\nFrom Static method")
print("This is printed for static method")
My_byke = Two_Wheeler('PY 37 PQ 7898','Scooter')
My_byke.show()
Two_Wheeler.print_info()
Output
From show() method:
Registration no : PY 37 PQ 7898
Kind of Two Wheeler : Scooter
Two wheeler maker : Hero
From Static method
This is printed for static method
Defining a class inside another class is sometimes required. The term inner
class describes such a class. It is self-evident that we require an outside class
in order to define an inner. For instance, departments are found at every
college. There is no department class unless there is a college class. As a
result, the department class must be part of the college’s inner circle.
We can create the object of the inner class in two ways:
1. The object of the inner class is created inside the outer class.
2. The object of the inner class is created outside the outer class.
Example 66
class Two_Wheeler:
make = 'Hero'
def __init__(self,regd,own):
self.Regd_no= regd
self.owner = own
[Link] = self.byke()
class byke:
def __init__(self):
self.make = 'Hero'
self.engine = '100 CC'
self.kind = 'Scooter'
class colr:
def __init__(self):
self.color = 'Red'
My_byke = Two_Wheeler('TS 77 AA 4325','Tusarika')
clr = Two_Wheeler.colr()
print("Owner : ",My_byke.owner,"Registration no : ",My_byke.
Regd_no )
print("Make of the Two Wheeler : ",My_byke.details.make)
print("Two wheeler maker : ",My_byke.details.engine)
print("Two wheeler maker : ",My_byke.details.kind)
print("Color of the two wheeler : ",clr.color)
Output
Owner : Tusarika Registration no : TS 77 AA 4325
Make of the Two Wheeler : Hero
Two wheeler maker : 100 CC
Two wheeler maker : Scooter
Color of the two wheeler : Red
For the outer class Two_Wheeler, we have defined two inner classes: byke
and colr. The object of inner class is created inside the outer class by self.
InnerClassObjectName = [Link](). The implementation is
done by [Link] = self.byke().
The object of the inner class can also be created outside the outer class
by InnerClassObjectName = OuterClassName. InnerClassName(). The
implementation is done by clr = Two_Wheeler.colr().
Introduction to Python 55
Example 67
class Two_Wheeler:
make = 'Hero'
def __init__(self,regd,own):
self.Regd_no= regd
self.owner = own
[Link] = self.byke()
def show(self):
print("\Attributes of inner class inside outer class:")
print("Registration no : ",self.Regd_no)
print("Owner of Two Wheeler : ",self.owner)
print("Two wheeler maker : ",self.details.make)
print("\nAttributes of inner class when inner and outer
class have same method:")
self.details.show()
class byke:
def __init__(self):
self.make = 'Hero'
self.engine = '100 CC'
self.kind = 'Scooter'
def show(self):
print("\nFrom show() method inside inner class:")
print("Registration no : ",self.regd)
print("Owner of Two Wheeler : ",self.own)
print("Two wheeler maker : ",self.make)
class colr:
def __init__(self):
self.color = 'Red'
My_byke = Two_Wheeler('TS 77 AA 4325','Tusarika')
clr = Two_Wheeler.colr()
My_byke.show()
print("\nAttribute of Inner class From Outside the outer
class:")
print("Two wheeler engine : ",My_byke.details.engine)
print("Two wheeler maker : ",My_byke.details.kind)
print("\nAttribute of Inner class Outside the outer class:")
print("Color of the two wheeler : ",clr.color)
56 Data structures for engineers and scientists using Python
Output
Attributes of inner class inside outer class:
Registration no : TS 77 AA 4325
Owner of Two Wheeler : Tusarika
Two wheeler maker : Hero
Attributes of inner class when inner and outer class have same
method:
From show() method inside inner class:
Registration no : TS 77 AA 4325
Owner of Two Wheeler : Tusarika
Two wheeler maker : Hero
Attribute of Inner class From Outside the outer class:
Two wheeler engine : 100 CC
Two wheeler maker : Scooter
Attribute of Inner class Outside the outer class:
Color of the two wheeler : Red
Here the outer class is Two_Wheeler, and there are two inner classes byke
and colr. The outer class Two_Wheeler has attributes ‘Regd_no’ and
‘owner’. The inner class byke has attributes ‘make’, ‘engine’ and ‘kind’. The
inner class colr has attribute ‘color’.
In order to access the attribute of the inner class outside the class, the
general syntax is
ObjectofOuterClass.ObjectofInnerCla[Link]tributeNameofInnerObject.
self.ObjectofInnerClass.At tributeNameofInnerObject.
ObjectofInnerClass.At tributeNameofInnerObject.
True–false questions
Fill-in-the-blank questions
Multiple-choice questions
a. 5
b. 4
c. True
d. False
4. The output of print(float(‘100.0’)) is
a. 100.0
b. 100
c. Error
d. None of the above
6. Find how many times “+” will be printed in the output of the follow-
ing code:
i=0
while i <= 5:
i+=1
if i % 2 == 0:
break
print("+")
a. 0
b. 1
c. 2
d. 3
c. KeyError
d. None of the above
Descriptive questions
1. False
2. True
3. True
4. False
5. False
1. decorator
2. Positional
3. array
4. variables, constants, operators
5. strings
1. b 2. c 3. b 4. a 5. b
6. b 7. c 8. a 9. d 10. c
11. d 12. a 13. b 14. b 15. a
16. c 17. a 18. d 19. a 20. b
Chapter 2
LEARNING OBJECTIVES
We will discuss the basics of data structure and abstract data types. Every
computer program has two parts: an algorithm and a data structure. The
algorithm tells us what the program will do and operates on variables,
whereas the data structure is a group of memory locations used to retain
the information used by the algorithm.
2.1 INTRODUCTION
Only the primitive data that are defined can be manipulated by a digital
computer. The user does not need to apply any additional effort while
manipulating the primitive data. However, in our real-world applications,
we use a variety of data types other than primitive data. Manipulation of
these data necessitates the completion of the following tasks.
DOI: 10.1201/9781003510758-2 63
64 Data structures for engineers and scientists using Python
People who create and develop computer programs such as system software
or application software must have a basic understanding of data structures.
We know that data is represented by data values that are either temporarily
stored in a program’s data area or permanently recorded on a file. Different
data values are frequently related to one another. These data values must
be arranged for programs to create a connection. The term data structure
refers to a structured collection of data. To access and process structured
data, the programs must follow a set of rules.
Data Structures
Integer
None Queues
String
List
Tuple
Set
Diconary
i. Create
ii. Delete
iii. Select
iv. Update
v. Search
vi. Sort
vii. Merge
[Link] Integer
Numeric data types include integers, floats, complex numbers, and Booleans.
Data in some variables are kept as whole numbers, for instance, the number
of students in a class. An integer-type variable is used to save the value of
such a sort of query. Integers are the only data types that do not support
decimal places. In other words, only the complete number is required. It
includes the values positive, negative, and zero. Integers such as 8, –432,
and 0 are examples. Take a look at the expression x = 3 + 5. Python com-
putes the right side of the equal sign, stores the result in memory, and con-
nects the memory location with the identifier x. In other words, it assigns
that location a name, and because the result of the right-hand expression
is an integer, the type of this variable will be “int.” We have a variable in
this scenario, and the identifier for this variable is x. A variable’s name can
alternatively be referred to as x. The variable has an integer value of 8 and
is of the type int. The statement print(type(x)) returns a class int, indicating
that its type is an integer, which can be confirmed.
[Link] Float
Some variables have fractional values. When asked, “How tall are you?” we
normally respond with 5.6 feet. We’ll need a floating-point representation
to hold the height value. Floating point numbers are those that have a deci-
mal point, for example, 43.9, –234.1, and 00.4. Take the statement y = 3 / 2
as an example. Python calculates the right side of the equal sign, saves the
result, and associates it with the identifier y in memory. Because the result
is a floating-point number, this variable’s type will be float. The value of the
variable is 1.5. This can be verified by “print(type(y)).”
F undamentals of data structures 67
[Link] Complex
One-dimensional numbers are integers and floats. We also require two-
dimensional integers on occasion. Another numeric data format, complex
number, is used to represent a two-dimensional number. The ordered pair
x+yj is used to represent complex numbers, where x and y are numeric data.
The real part is x, while the imaginary part is y. Complex numbers include
9+8j and complex (9, 8). The most common operations performed on com-
plex data types are addition, subtraction, multiplication, and division.
[Link] Boolean
Boolean is a binary variable that can have one of two potential values:
0 (False or F) or 1 (True or T). For instance, if the inquiry is, “Are you
happy?” The response is either yes or no. It means you’ll need a variable to
hold data of the Boolean type. The operations used with the Boolean data
type were AND, OR, and XOR.
Let's have a look at the bool type. Consider the proposition z = False.
True or False are both keywords in Python, and the first letter is uppercase.
Make sure that they are not typed as true or false (in lowercase letters).
Python computes the right side of the equal sign, stores the result in
memory, correlates that memory address with the identifier z, and since the
right-side result is a Boolean, the type is bool.
It's also worth noting that z was previously specified as “hello” and had
the typed string.
However, with the sentence z = False, Python immediately assigns the
value False to z. So, the prior value of z, “hello,” is no longer valid, and its
new type is bool. In Python, this is done automatically, so we don’t have to
worry about it.
Python includes several other built-in data types, including string, list,
tuple, dictionary, and set. We also have data structures like arrays that must
be imported before they can be used.
[Link] None
This data type stands for “no value” or “null.” It has no meaning when it
comes to “0,” “empty,” “False,” or “undefined.” It is a true data type; it
can be assigned to variables and takes up memory like any other data type.
When a function does not include a return statement and we want to print
the value returned by the function, we use the “None” data type.
[Link] String
If you’re asked, “What’s your name?” the string type of variable is used to
answer this question. It's simply a string of letters, numbers, and special
68 Data structures for engineers and scientists using Python
[Link] List
This sort of data is used to store numerous pieces of information at the
same time under a single variable name. It is analogous to an array in a
programming language such as C. C-array, on the other hand, is a homo-
geneous data type, whereas a list does not have to be of the same data type.
The data in a list is enclosed by a pair of square braces [ ].
[Link] Tuple
The main difference between a tuple and a list is that a tuple is immu-
table. It is made up of unchanging and indexed data. The data in a tuple is
enclosed by a pair of round brackets ( ).
[Link] Set
It’s a collection of datasets that aren’t in any particular sequence and aren’t
indexed. It’s an immutable data type that stores one-of-a-kind information
(no duplicates). A pair of curly braces { } surrounds the data in a set.
[Link] Dictionary
A dictionary is a specific data type in which data is stored in pairs of
(key:value). It's an unsorted, changing, and indexed collection. Dictionary
works similarly to a real-world dictionary. A dictionary’s keys must be
unique and immutable data types like strings, integers, and tuples, but the
key–values can be repeated and of any kind.
[Link] Array
This data type holds multiple data of homogeneous data types together
and is accessed by an index. In Python, an array can be implemented using
primitive data types such as a list or a dictionary. It can also be imple-
mented using a non-primitive data type by importing separate packages like
NumPy and array. The elements in an array are accessed sequentially. We
can implement an array with the help of a list or a dictionary.
[Link] Stack
A stack is also a linear data type, but it has a special way of inserting and
deleting data. In a stack, the insertion and deletion take place at one end
called the top of the stack. As a result, the element that is inserted last is to
be deleted first so it is also called last in, first out (LIFO). For example, as
shown in Figure 2.2, we can think of a stack of books on a table. We can
remove a book from the top, and also we can put a book on the top of the
stack. The operation of inserting and deleting is also known as push and
pop, respectively. Another operation in the stack is peek, which returns the
element at the top of the stack.
Top D
C
B
A
[Link] Queue
A queue is also a linear data type, but it has a special way of inserting and
deleting data. In a queue, insertion occurs at one end, known as the rear,
70 Data structures for engineers and scientists using Python
while deletion occurs at the opposite end, known as the front. As a result,
the element that is placed first is also the first to be deleted, hence the term
first in, first out (FIFO). For example, we can think of people standing in a
row waiting for a bus. The person who arrives first becomes the first person
in the queue and they get onto the bus first (Figure 2.3).
Rear Front
H G F E D C B A
[Link] Tree
This is a non-linear data structure in which there is no unique predeces-
sor and successor. This data structure represents a hierarchical relation-
ship between the elements. It is a collection element that is identified by a
unique element called the root and the sub-trees are children of the root
(Figure 2.4).
4 9
2 3 10
6
5 7
11 12
[Link] Graph
It is a mathematical non-linear data structure capable of representing any
kind of structure. A graph is made up of nodes (also known as vertices) that
are linked together by edges (also called arcs) (Figure 2.5).
6 5
3 2
[Link] File
In day-to-day life, all the information cannot be saved in terms of data.
Sometimes a file is used to store voluminous data in an external storage
device. A file is a collection of records with one or more fields. The com-
monly use organization for a file is:
i. Sequential file
ii. Relative file
iii. Direct file
iv. Index sequential file
v. Index file
The basic operations that we perform with a file are the same as any other
data structure.
72 Data structures for engineers and scientists using Python
Consider the set as an ADT; the elements of the set are the domain of val-
ues, and the operations on the domain are union, intersection, comple-
ments, and so on.
The fundamental idea is that these operations are implemented once in
the program, and then any other component of the program that needs to
do something with the ADT may call the relevant function. If any imple-
mentation details need to be changed for whatever reason, it should be triv-
ial to do so by simply changing the ADT operation functions. This change
would go unnoticed by the rest of the software.
There is no rule defining which operations each ADT must support; this
is a design decision. Some of the data structures we’ll look at in this book
are examples of ADT. We’ll show how to implement each one, but if you do
it well, the applications that use them won’t need to know which one you
used.
2.5 ALGORITHMS
2.5.1 Algorithm specifications
[Link] Pseudo-code
A natural language like English can be used to specify an algorithm. For
small and simple algorithms, graphic representations such as flowcharts are
also used. We may also define algorithms in pseudo-code that resembles a
computer language, making program translation simple. We may utilize
conditional statements, conditional repeated statements, and finite repeti-
tive statements while developing an algorithm using pseudo-code.
F undamentals of data structures 75
A sample algorithm:
Algorithm Max(a,n):
result = a[0];
for i in range (n):
if(a[i] > result):
result = a[i]
return result
This method finds the largest value in an array of size n. In this case, Max
is the name of the algorithm, and a and n are its parameters. The largest
element in the array is returned as the “result” in the preceding procedure.
[Link] Recursion
If the same algorithm is invoked in the body, it is considered to be recursive.
When algorithm A calls algorithm B and algorithm B calls algorithm A, it
is said to be indirectly recursive.
The Towers of Hanoi problem is an example of a recursive algorithm.
Suppose we want to find the sum of the integers in an array.
algorithm Rsum(a,n):
count=count+1
if(n<=0):
return 0
else:
count=count+1
return Rsum(a,n-1) + a[n]
With a different set of parameters, the algorithm calls itself. The number of
steps completed is shown by the count.
T Rsum(n) = 2 + T Rsum(n–1)
TRsum(n) = 2 + TRsum(n–1)
= 2 +2 + TRsum(n–2)
= …
= 2(n) + TRsum(0) = 2n + 2
76 Data structures for engineers and scientists using Python
In general, if T(n) is the time taken by the algorithm when the input size is
n, it can be expressed as
T(n) = c + T(n–1)
where the input is divided into b groups and for each group, we apply the
same algorithm. f(n) is the number of steps or the time taken to combine the
solutions of the sub-problems. Let us take a simple example.
T(1) = 1
T(n) = T(n/2) + c
T(n) = T(n/2) + c
T(n) = (T(n/22) + c) + c
= T(n/22) +2c
After k iterations
T(n) = T(n/2k) + kc
Example
= 2[2(n/22) + n/2} + n
= 2 * 2T(n/22) + 2n
After k iterations
=2kT(n/2k) + kn
2.5.2 Performance analysis
The algorithm’s efficiency may be assessed by measuring its performance.
The performance is determined by the amount of storage space required
for the program and data. This is referred to as space complexity, while the
time it takes to run the program is referred to as time complexity. In this
book, the focus will be more on data structures rather than performance
analysis.
[Link] Space complexity
Definition: The space complexity of an algorithm is the amount of memory
the algorithm needs to run until completion.
The space needed to run an algorithm consists of two parts:
S(p) = C + Sp
Algorithm MAX
{ result = a[i]
for ( i = 2 to n)
{ if (a[i] > result)
result = a[i]
} return result
}
In the preceding algorithm MAX, we need one word each for n, result, and
i, and n words for storing the array.
Therefore, S(p) ≥ n+3 words.
78 Data structures for engineers and scientists using Python
Algorithm RSum(a,n)
{ if( n<= 0) return 0.0
else return( RSum(a, n-1) + a[n])
}
Since the depth of recursion is n+1 and each recursive call needs the value of
n, a[n], and sum, we need S(p) ≥ 3(n+1) words.
[Link] Time complexity
Definition: The time complexity T(P) for a program P is the sum of compile
time and execution time.
The compile time is constant and does not depend on variable character-
istics (int, float, long, etc.). Therefore, T(P) = C P + Ca ADD(n) + Cs SUB(n) +
…, where n denotes the instance characteristic and Ca, Cs, … represent the
number of additions, subtractions, etc., that are performed on the instance
characteristic n.
A programming step is a syntactically and semantically important piece
of a program that executes independently of the instance characteristic.
Consider the program that computes the sum of the objects in an n-dimen-
sional array. A count variable is included in the program, which is incre-
mented by one for each statement executed.
Algorithm sum(a, n)
{
S=0.0;
count = count+1 //count is initialized to 0.
for i=1 to n do
{
count=count+1;
S = S + a[i];
count = count+1;
}
count=count+1; //last time for the for loop
return S;
};
The value of count after the execution will be 2n + 3, which indicates the
number of steps executed.
Let us look at matrix addition.
[Link] Complexity analysis
The complexity analysis can produce three different outcomes: worst case,
best case, and average scenario. The worst-case scenario occurs when the
algorithm takes a large number of steps, and the best-case scenario occurs
when the number of steps is the smallest. The average situation falls midway
between these two extremes. In simple cases, the average case is calculated
by looking at various inputs, calculating the number of steps necessary for
each one, adding the number of steps required for all inputs, and dividing
by the number of inputs. If we assume that the probability of occurrence of
the ith input is p(inputi), then we may calculate
Tave = Σ I p(inputi)*steps(inputi)
1 2 3 n n 1
n 2
80 Data structures for engineers and scientists using Python
Example: Take binary search, for example. Assume the input size is a power
of two without sacrificing generality. If the element is in the center, a binary
search can find it in one try. If it’s in the middle of the left or right half, it’ll
take two attempts, or three tries if it’s in the middle of the first quarter, or
the middle of the second quarter, or the middle of the fourth quarter, etc.,
or log 2n tries if it’s the first or last element.
Thus, the average number of possibilities is
n
1 .1 2 .2 4 .3 8 .4 log 2 n
2
loglog n 1
2 power i i 1
0
[Link].1 Big oh
Definition: The function f(n) is O(g(n)) if and only if there exists positive
constants c and n0, such that f(n) ≤ cg(n) for all n, n > n0.
If f1(n)H≈ O(g1(n)) and f2(n)=O(g2(n)), then f1(n) + f2(n) = O(max(g1(n),
g2(n)) and
f1(n) * f2(n) = O((g1(n)) * (g2(n)).
Graphically, the relationship between f(n) and g(n) can be represented by
the diagram in Figure 2.6.
c.g(n)
f(n)
n0
m
n
m
ai ni mv
i 0
[Link].2 Omega
Definition: The function f(n) is Ω(g(n)) if and only if there exist positive
constants c and n0, such that f(n) ≥ c*g(n) for all n ≥ n0 (see Figure 2.7).
f(n)
c.g(n)
n0
Example: Let f(n) = 4n + 3. Then f(n) ≥ 4n for all n > 0. Thus, f(n) is Ω(n)
with c = 5 and n0 = 3.
Example: Let f(n) = 6*2n + n 2 . Then f(n) ≥ 2n for all n ≥1. Hence, f(n) is
Ω(2n).
We can generalize and say if f(n) = amnm + … + a1n + a0, then f(n) is Ω(nm).
[Link].3 Theta
Definition: The function f(n) is Θ(g(n)) if and only if there exist positive
constants c1, c2 , and n0, such that c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0.
Example: Let f(n) = 3n + 2. Then 3n ≤ 3n+2 ≤ 4n for all n≥2. Hence, f(n)
is Θ (n).
We can generalize and say if f(n) = amnm + … +a1n + a0, then f(n) = Θ (nm).
In general, exponential functions grow faster than polynomial func-
tions and polynomial functions grow faster than logarithmic functions
(Figure 2.8).
82 Data structures for engineers and scientists using Python
c2.g(n)
f(n)
c1.g(n)
n0
[Link].4 Small oh
Definition: The function f(n) is o(g(n)) if and only if Lt (f(n)/g(n)) = 0 as
n →∞.
[Link].5 Little omega
Definition: The function f(n) is ω(g(n)) if and only if Lt(g(n)/f(n)) = 0 as
n →∞.
True–false questions
Fill-in-the-blank questions
Multiple-choice questions
4. Which one of the following is not the application of the queue data
structure?
a. Data transfer asynchronously
b. Load balancing
c. Resource shared between various systems
d. Balancing of symbols
5. Traversal refers to
a. Putting the data in order
b. Reaching each element
c. Combining data elements
d. Finding a data element
84 Data structures for engineers and scientists using Python
16. Which of the following is very useful in situations when data have to
be stored and then retrieved in reverse order?
a. Array
b. Stack
c. Tree
d. Graph
Descriptive questions
1. False
2. True
3. False
4. True
5. False
1. Non-linear
2. primitive
3. o(g(n))
4. storage space, data
5. recursive
1. d 2. c 3. a 4. d 5. b
6. b 7. d 8. d 9. d 10. a
11. b 12. d 13. c 14. b 15. c
16. b 17. d 18. d 19. d 20. d
Chapter 3
Arrays
LEARNING OBJECTIVES
The operations one needs to perform in an order are to traverse from left to
right and from right to left.
DOI: 10.1201/9781003510758-3 87
88 Data structures for engineers and scientists using Python
In Python there are several built-in data structures, such as a list, a tuple,
and a dictionary, that can be used to implement arrays.
3.1 INTRODUCTION
The third operation, insert(array, index, value), stores the given value at the
index position of the array and returns the updated array.
The operation delete(array, index) deletes the value at a given index posi-
tion of the array and returns the updated array.
The last operation is easy to understand. The access() function returns the
value in the ith position if i == j, else returns the value in the jth position.
Python program 1
The create(n) function creates a list with n elements. This method reads n
integers appended to a list after the user enters all n integers and then the
list is returned.
Program continues…
def display(a):
print("The data in the array are :")
print(a)
Program continues…
The access(a, i) method finds the element at ith location, if the location is
not less than 0 or not greater than the size of the array.
Program continues…
The insrt(a,i,x) function adds an element at the ith location. This can be
done by the [Link](i,x) command while using a list.
Program continues…
Deletion of an element which is at ith location can be done by the del a[i]
command.
Program continues…
# Main Program
n = int(input("Enter How many numbers in an array "))
Arr=create(n)
display(Arr)
print("\n--- Data at Location ---")
i = int(input("Element at which position element to get "))
access(Arr,i)
print("\n--- Insert at a Location ---")
j = int(input("Specify the Location to Insert "))
y = int(input("Specify the Data "))
Arr = insrt(Arr,j,y)
display(Arr)
print("\n--- Deletion at positon ---")
j = int(input("Specify the Location to Delete "))
Arr=delit(Arr,j)
display(Arr)
92 Data structures for engineers and scientists using Python
Output
Python program 2
def create():
A={}
n=int(input("\nEnter the number of elements :"))
print("\n")
for i in range(n):
print("Enter data at ",i,end=": ")
A[i]=int(input())
return A
A rrays 93
The create() function first creates an empty dictionary. And then for every
key, a corresponding value is appended. This is done by the A[i]=int(input())
command, which restricts the user to enter an integer value only.
Program continues…
def display(A):
for i in range(len(A)):
print("A[",i,"] = ",A[i])
The display(A) function displays the elements of the dictionary in the form
of an array.
Program continues…
0 1 2 3 4
10 15 20 25 30
The insert method takes three arguments: the array itself, the position
where the value is to be inserted and the value (Figure 3.1). If we want to
insert a value at the ith position, we have to move all the elements of the
array one position to the right starting from the ith position. Suppose i = 2
(Figure 3.2).
0 1 2 3 4
10 15 20 25 30
The size of the list will be increased by 1 after insertion of the element
(Figure 3.3).
0 1 2 3 4 5
10 15 20 25 30
We can now insert the element in the ith position. Let the element to be
inserted be 17. The array now is as shown in Figure 3.4.
0 1 2 3 4 5
10 15 17 20 25 30
Program continues…
def insrt(A,i,x):
if i < 0:
print("Location is below the range")
return A
elif i > len(A) :
print("Location is out of the range")
return A
else:
for j in range(len(A)-1,i-1,-1):
A[j+1] = A[j]
A[i]=x
return A
The delit(A, i) method deletes the element at the ith location (Figure 3.5).
0 1 2 3 4 5
10 15 17 20 25 30
Suppose we want to delete the element in the second position. Delete the
data 17 at the second location (Figure 3.6).
0 1 3 4 5
10 15 20 25 30
Observe that the value for key = 2 is deleted. Now we need to reorder the
keys and values by saving the data of the location. The key in a dictionary
is unique and it is not adjusted dynamically. We need to manage it by the
program.
All the elements to the right of the second location (the element in the
second position) are shifted one position to the left. This can be done by
overwriting the second cell with the element in the third cell, and the ele-
ment in the third cell is overwritten with the element in the fourth cell and
so on. Also we need to reorder the keys of the dictionary (Figure 3.7).
A rrays 95
0 1 2 3 4 5
10 15 20 25 30 30
0 1 2 3 4
10 15 20 25 30
Program continues…
for j in range(I,len(A)):
A[j]=A[j+1]
del (A[len(A)-1])
return A
Program continues…
Output
Enter data at 0: 1
Enter data at 1: 2
Enter data at 2: 3
Enter data at 3: 4
Enter data at 4: 5
Python program 3
To utilize the array module, we must first import it using the line from array
import *. Here A is the name of the array, and the method array() has two
parameters. The type code, in this example, i is the first parameter, and the
data is the second. Different type codes are given in Table 3.2.
The program for accessing an array, inserting an element into the array
and deleting an element from the array can be implemented as discussed in
the list.
The Python array module provides the following advantages over Python
lists:
• A list includes items of multiple data types, whereas the Python array
module has elements of the same data type.
• To declare an array in Python, the array module must be explicitly
imported, while in list, no module is required to be imported and no
declaration is made.
• The Array module in Python may perform arithmetic operations.
• All items in the Python array module must be the same size.
• The term is most commonly used in the context of a prolonged suc-
cession of data items.
• Because addition, deletion and update operations are done on a single
element at a time, modifying an array is complex.
• We’ll need an explicit loop to print or access array items.
• In comparison to the list, it is a more compact in-memory size.
98 Data structures for engineers and scientists using Python
Python program 4
import numpy as np
A = np.array([1,2,3],dtype = ‘int’)
print(A)
Python program 5
import numpy as np
A = np.array([1,2,3],’I’)
print(A)
The method for accessing array elements, inserting an element into the
array and deleting an element from the array can be implemented as dis-
cussed in Section 3.1.2.
A rrays 99
Python program 6
# Creating an Array
class Arr:
def __init__(self):
[Link] = 10
self .si
ze = 0
self .ite
ms = list()
The name of the array class is Arr and it can hold elements up to the max-
Size (initialized to 10). The size is also initialized to 0. It also has an empty
list. All the methods associated with the class are declared as public.
Let us define each method:
100 Data structures for engineers and scientists using Python
Program continues…
The readArray () method reads character values into the list. It prompts
how many characters to insert into the array. It checks if the input array_
size is greater than the maxSize and if so, prints the appropriate message
and comes out of the method. Otherwise, it prompts the user to insert data
into the array.
Suppose the data inserted into the array is as shown in Figure 3.9.
0 1 2 3 4
A B C D E
Program continues…
Insertions and deletions into or from an array are costly operations since
they involve data movement to the right, and to the left in the case of
deletions.
The addAtIndex() method takes two arguments, the position where the
value is to be inserted (index) and the value (data). We need to check if the
index at which we want to insert the data is beyond the current array size
or the current array size is greater than or equal to the maximum size of the
array. If either of the conditions is true, we cannot enter the data into the
A rrays 101
0 1 2 3 4
A B C D E
When we insert an element into the array, the size of the array increases
by 1. The elements are shifted one position to the right starting from the last
element (the element at position size –1) (Figure 3.11).
0 1 2 3 4 5
A B C C D E
We can now insert the element in the jth position. Let the element to be
inserted be Z. The array now is as shown in Figure 3.12.
0 1 2 3 4 5
A B Z C D E
Program continues…
#Searching
def search(self, data):
print("Searching for Element...",data)
if data in self .item
s:
position = 0
for i in range(self .si
ze):
if(self .items[i] == data):
break
else:
position += 1
print('Element {} found at position {}'.
format(data, position))
else:
print('This element is not in the Array!')
The method search() searches for the data passed as parameters. It is quite
straightforward. We will keep searching from index 0 until the current size
102 Data structures for engineers and scientists using Python
of the array. If it matches, come out of the looping structure and print an
appropriate message for finding the element. Otherwise print an appropri-
ate message for not finding the data.
Deletion of a data requires searching for data in the array and if found
then delete the data and reduce the size by 1, otherwise print an appropri-
ate message.
Program continues…
#Delete a Data
def deleteData(self, data):
print("Deletion ...",data)
if data in self .item
s:
self .items
.rem
ove(data)
self .si
ze -= 1
else:
print('This element is not in the Array!')
Unlike any other programming language, we need not write any code for
searching for data. Searching of data is performed simply by the if data in
self.items statement.
Suppose we want to delete the element in the second position. All the ele-
ments to the right of Z (the element in the second position) are shifted one
position to the left. This overwrites the second cell with the element in the
third cell, and the element in the third cell is overwritten with the element
in the fourth cell and so on, and the blank cell moves to the extreme right.
Program continues…
Program continues…
# Main Program
myArray = Arr()
[Link]()
print(myArray.items,”Array with” ,myArray.size,”Elements”)
A rrays 103
# Searching data
ele = input(“\nEnter data to search ”)
myArray.search(ele)
#Deleting Data
ele = input(“\nEnter data to Delete ”)
[Link](ele)
print(myArray.items,”Array with” ,myArray.size,”Elements”)
In the main program, an object, myArray of the class Arr, is created. All the
methods defined earlier are called to perform the operations.
Output
3.2 MULTIDIMENSIONAL ARRAYS
0 1 2 3 4 5
9 5 8 0 3 0
Index
y↓ x 0 1 2 3 4 5
0 1 3 12 27 48 75
1 5 9 23 43 69 101
2 32 15 36 52 92 129
We can declare such an array as z[3][6], with 3 and 6 indicating the num-
ber of rows and columns, and the values can be accessed as
1. row-major method
2. column-major method
In the row-major method, all rows are stored one row after another starting
from the first row like:
In the column-major method, all columns are stored from the first column
like:
0 1 4 3 9
15 12 23 3
6 27
43 52 48 6
9 92
75 10
1 129
The programmer need not know which method was used to store the two-
dimensional array.
The same method of storage can be extended to multidimensional arrays
(arrays of more than 2 dimensions). A three-dimensional array, A[m][n][p],
is represented as m × n × p dimensional matrices and these n × p matrices
are stored one after the other starting from m = 0 in a row-major fashion.
The element A[i][j][k], therefore, occurs in the memory where the ith n × p
matrix is stored. Therefore, we have to leave the first (i-1)np locations start-
ing from the first location where the three-dimensional matrix is stored,
and search for A[i][j][k] in the next n × p locations.
3.3 APPLICATIONS
Arrays have various applications and are widely used in programming and
data structures. We will discuss two important applications, polynomial
manipulation and sparse matrix implementation, in this section.
3.3.1 Polynomial manipulation
An array is a very useful data structure to implement polynomials in a
computer. A polynomial in a single variable can be written as P(x) = a0 +
a1x + a2x 2 + … + anxn. The degree of the polynomial is n and it contains
(n + 1) terms. A polynomial of nth degree may therefore be represented by
the array (a0, a1, a2 , …, an).
Where the ith element of the array represents the coefficient of xi. All the
elements of the array may not be non-zero. For example, the polynomial
3 – 2x – x 2 + x4 is represented by the array in Figure 3.15.
3 -2 -1 0 1
5 0 0 0 0 0 - - - 98
This is called a sparse polynomial since there are very few non-zero ele-
ments and the terms with 0 coefficients occupy a lot of space and may not
contribute much to the operations on the polynomial.
The sparsity of a polynomial is the ratio between the number of zeros and
the total number of elements. In the polynomial 3 – 2x – x 2 + x4, the number
of zeros is 1 (as the x3 term is missing) and the total number of terms is 5.
So the sparsity of the polynomial is 1/5. Similarly, for the polynomial 5 +
x98, the number of zero terms is 97 and the total number of terms is 99. So
the sparsity is 97/99.
We have discussed that every term in a polynomial is represented by a
coefficient and an exponent. Python has many such constructs that are
capable of representing a polynomial. We are using a dictionary to repre-
sent a polynomial.
A dictionary has two parts: a key and a value. In a dictionary, the key is
unique so we will use it to represent the exponent and the value to represent
the coefficient of a term in a polynomial.
We can represent the polynomial 3 – 2x –x 2 + x4 in a dictionary as {0:3,
1:-2, 2:-1, 3:0, 4:1}.
A polynomial is an example of ordered data structure. The abstract data
type for a polynomial is:
ADT Polynomial
Instance: create a polynomial
Pre-condition: At least one term is required to perform any operation.
Operations: Addition of two polynomial
Subtraction of two polynomial,
Multiplication of two polynomial and
Evaluation of a polynomial
Python program 7
# reads a polynomial
def readPoly():
p={}
n=int(input("\nEnter Degree of Polynomial :"))
print("\n")
for i in range(n):
print("Enter coefficient for x^",i,end=": ")
p[i]=int(input())
return p
A rrays 107
The size of the polynomial is given in line 3. The for loop from lines 5 to
7 reads the coefficients and the corresponding exponents and creates the
terms of the polynomial.
Program continues…
# displays the polynomial in a readable form
def print_poly(p):
res=""
for expo,coeff in [Link]():
if expo == 0:
res = str(coeff)
else:
if int(coeff) == 0:
pass
else:
res = res + ' + '+ str(coeff)+"x^"+str(expo)
print(res)
Program continues…
#adds two polynomials
def add_poly(p1,p2):
p3={}
i=0
j=0
else:
p3[i]= p1[i] + p2[j]
i+=1
j+=1
When we add two polynomials, the resultant polynomial is of the size of the
larger of the two polynomials. Here p1 and p2 are two polynomials passed
as parameters and defined in an empty dictionary, p3, to store the result.
There are three cases we come across while adding two polynomials.
The first case is that while each polynomial has some terms, we will
check each term of both polynomials. Starting with exponent 0, we will
check if the exponent of a term in p1 is less than the exponent of the term in
p2. If so, copy the coefficient of p1 to p3 at the exponent of p1. Otherwise,
copy the coefficient of p2 to p3 at the exponent of p2. If the exponent of
both terms are the same, add the coefficient of p1 and p2 to store it at the
same location of p3.
The second case is that if there are some elements left out in polynomial
p2 while there are no terms left in p1, copy the remaining terms of p2 to p3.
The third case is that if there are some elements left out in polynomial p1
while there are no terms left in p2, copy the remaining terms of p1 to p3. At
last, the resultant polynomial, p3, is returned.
Program continues…
# multiplies two polynomials
def mul_poly(p1,p2):
p3={}
#Initializing the Dictionary to 0
for expo1,coeff1 in p1.items():
for expo2,coeff2 in p2.items():
p3[expo1+expo2]=0
#Polynomial Multiplication
for expo1,coeff1 in p1.items():
for expo2,coeff2 in p2.items():
p3[expo1+expo2]= p3[expo1+expo2] + coeff1*coeff2
return p3
Here we have taken an empty dictionary, p3, to store the product of two
polynomials p1 and p2. The maximum terms possible in p3 is the sum of
terms in p1 and terms in p2. Now assign the coefficient of each term of p3
to 0. The actual polynomial multiplication is done after that.
A rrays 109
Program continues…
# The main Program
poly1=readPoly()
print("\nThe Polynomial-1 is ")
print_poly(poly1)
poly2=readPoly()
print("\nThe Polynomial-2 is ")
print_poly(poly2)
Output
The Polynomial-1 is
1 + 2x^1 + -3x^2
The Polynomial-2 is
0 + 6x^3 + 4x^4 + 8x^5
The same program can be written with very few codes using the numpy
package.
110 Data structures for engineers and scientists using Python
Python program 8
import numpy as np
def display(p1):
p={}
# Convert the coefficient and exponents to a dictionary
coeff = list(p1.c)
[Link]()
n = len(coeff)
for i in range(n):
p[i]=coeff[i]
# Constructing polynomial
p1 = np.poly1d([1, 2, 5, 3])
print("Polynomials-1")
display(p1)
p2 = np.poly1d([4, 9, 3])
print("Polynomials-2")
display(p2)
# Addition of polynomials
add = [Link](p1, p2)
print("Addition of two polynomials")
display(add)
# Subtraction of polynomials
sub = [Link](p1, p2)
print("Subtraction of two polynomials")
display(sub)
# Multiplication of polynomials
mul = [Link](p1, p2)
print("Multiplication of two polynomials")
display(mul)
A rrays 111
# Roots of polynomial
print("The roots of polynomial-1 are")
root=p1.r
print(root)
Output
Polynomials-1
3 + 5x^1 + 2x^2 + 1x^3
Polynomials-2
3 + 9x^1 + 4x^2
Addition of two polynomials
6 + 14x^1 + 6x^2 + 1x^3
Subtraction of two polynomials
0 + -4x^1 + -2x^2 + 1x^3
Multiplication of two polynomials
9 + 42x^1 + 63x^2 + 41x^3 + 17x^4 + 4x^5
The roots of polynomial-1 are
[-0.63136114+1.9158304j -0.63136114-1.9158304j -0.73727772+0.j ]
The value of polynomial-1 at x=2 is 29
The value of polynomial-2 at x=2 is 37
3.3.2 Sparse matrices
A matrix is the most frequently used data structure to solve many engi-
neering and scientific problems. As we had studied earlier, a matrix can be
represented in a row-major or a column- major method in a computer. In
engineering problems such as finite element analysis or in scientific prob-
lems in the analysis of nuclear reactions, the matrices can be very large and
most of the elements may be zero. Such matrices are called sparse matrices.
In either row-major method or column-major method, a huge amount of
space is used to represent such matrices, even though there are very few
non-zero elements that really contribute to the solution of the problem. We
need an alternate representation of such matrices for optimum utilization
of memory and minimum use of computer time. Consider the matrix in
Figure 3.17.
112 Data structures for engineers and scientists using Python
2 0 0 0 0 0 8 9 0 0 0
3 5 0 0 0 0 3 0 0 0 0
0 0 0 0 1 9 7 0 0 0 0
1 3 4 0 0 0 0 0 0 0 6
1 2 3
A[0] 0 0 2
A[1] 0 6 8
A[2] 0 7 9
A[3] 1 0 3
A[4] 1 1 5
A[5] 1 6 4
A[6] 2 4 1
A[7] 2 5 9
A[8] 2 6 7
A[9] 3 0 1
A[10] 3 1 3
A[11] 3 2 4
A[12] 3 10 6
elements. From the first row onward, we represent information about non-
zero elements. The first row says that the first row and the first column in
the sparse matrix contain the non-zero element 2. Similarly the seventh
row says that the first row and third column in the sparse matrix contains
1. Some of the operations we wish to perform on these matrices are ‘trans-
pose’, ‘addition’ and ‘multiplication’.
Let us represent the sparse matrix as a two-dimensional array:
Python program 9
Program continues…
Program continues…
Python program 10
import numpy as np
from scipy.sparse import csr_matrix
# create a 2-D representation of the matrix
A = np.array([[0, 1, 0, 5],
[0, 0, 2, 0],
[0, 1, 0, 2]])
Output
Dense matrix-1 :
[[0 1 0 5]
[0 0 2 0]
[0 1 0 2]]
Sparse matrix-1:
(0, 1) 1
(0, 3) 5
(1, 2) 2
(2, 1) 1
(2, 3) 2
[Link] Transpose
As we know, the transpose of a matrix is the matrix obtained by inter-
changing rows and columns. In other words, the element in the ith row and
A rrays 115
jth column will be in the jth row and ith column in the transposed matrix.
The transpose of the matrix in Figure 3.18 is shown in Figure 3.19.
1 2 3
A[0] 0 0 2
A[1] 0 1 3
A[2] 0 3 1
A[3] 1 1 5
A[4] 1 3 3
A[5] 2 3 4
A[6] 4 2 1
A[7] 5 2 9
A[8] 6 0 8
A[9] 6 1 4
A[10] 6 2 7
A[11] 7 0 9
A[12] 10 3 6
However, this does not correspond to the type of structure we had chosen
(i.e., the increased row number and with the same row number increased
column number) and it requires movement of rows and columns to bring
it to the required form. To avoid this, we may proceed interchanging rows
and columns starting from column 1 as follows:
Since the rows are originally in order, the transposed matrix will be in
the correct order (increased row number and with the same row number
increased column number).
def transposeMatrix(matrix):
matrix=np.array(matrix)
matrix[:,[0, 1]] = matrix[:,[1, 0]]
for i in range(len(matrix)):
for j in range(len(matrix)-i-1):
if ( (matrix[j][0] > matrix[j+1]
[0]) or (matrix[j][0] == matrix[j+1]
[0] and matrix[j][1] > matrix[j+1][1])) :
matrix[[j,j+1]] = matrix[[j+1,j]]
showMatrix(matrix)
116 Data structures for engineers and scientists using Python
In other words, add the elements if the row number and column numbers
are the same; copy otherwise in the appropriate order.
else:
for i in range (i,l1):
resMatrix.append(m1[i])
#Main Program
rows = int(input("How many rows "))
columns = int(input("How many columns "))
print("\nRead Matrix-1: ")
Matrix1=readMatrix(rows,columns)
print("\nRead Matrix-2: ")
Matrix2=readMatrix(rows,columns)
addSparse(sm1,sm2)
Output
Read Matrix-1:
Enter Matrix element 0 0 :0
Enter Matrix element 0 1 :0
Enter Matrix element 0 2 :7
Enter Matrix element 1 0 :0
Enter Matrix element 1 1 :6
Enter Matrix element 1 2 :7
Read Matrix-2:
Enter Matrix element 0 0 :0
Enter Matrix element 0 1 :0
Enter Matrix element 0 2 :1
Enter Matrix element 1 0 :2
Enter Matrix element 1 1 :0
Enter Matrix element 1 2 :0
The same program can be written with very few codes using numpy and
scipy packages as in the following program.
Python program 11
import numpy as np
from scipy.sparse import csr_matrix
# create a 2-D representation of the matrix
A = np.array([[0, 1, 0, 5],
[0, 0, 2, 0],
[0, 1, 0, 2]])
B = np.array([[0, 5, 0, 5],
[0, 1, 2, 0],
[0, 1, 0, 0]])
print("Dense matrix-1 :\n", A)
print("Dense matrix-2 :\n", B)
Output
Dense matrix-1 :
[[0 1 0 5]
[0 0 2 0]
[0 1 0 2]]
Dense matrix-2 :
[[0 5 0 5]
[0 1 2 0]
[0 1 0 0]]
Sparse matrix-1:
(0, 1) 1
(0, 3) 5
(1, 2) 2
(2, 1) 1
(2, 3) 2
Sparse matrix-2:
(0, 1) 1
(0, 3) 5
(1, 2) 2
(2, 1) 1
(2, 3) 2
A rrays 121
if (n != m1):
print("Matrix multiplication NOT possible!!!")
exit()
print("\nMatrix 1 is ")
for i in range(m):
for j in range(n):
print(Mat1[i][j], end = " ")
print()
print("\nMatrix 2 is ")
for i in range(m1):
for j in range(n1):
print(Mat2[i][j], end = " ")
print()
for i in range(m):
for j in range(n1):
for k in range(m1):
Mat 3[i][
j] += Mat1
[i][k
] * M
at2[k
][j]
Output
Matrix 1 is
1 2 2
3 0 4
Matrix 2 is
5 0
8 1
2 3
Matrix multiplication is
25 8
23 12
Output
True–false questions
Fill-in-the-blank questions
Multiple-choice questions
a. [0,1,2,3,4,5]
b. [5,4,3,2,1,0]
c. [0,0,0,0,0]
d. None of the above
a. 81.5
b. 30.1, 71.0, 81.5
c. Expected indentation
d. Raise an error ValueError
a. ['a','b','c','d']
b. ['A','B','C','D']
c. Raise an error
d. None of the above
Descriptive questions
1. Consider the following matrix:
00070000
10008000
20000009
00000050
04000000
Represent this as a sparse matrix.
2. Create a list with the following elements and write a program to
print it in the reverse order (without using the built-in function for
reversing):
3 5 7 9 11 13 15
3. Write a program to delete the duplicate elements from a list.
4. How do you represent a polynomial in a computer? Write a program
to add the following polynomials:
4x4+ 2x3 + 3x + 5 5x5 + 3x 2 – 8
5. Write a program to remove alternate elements from a list and create a
new list.
6. An array A = {3, 5, 7, 9} is given and it is full. Write a program to
insert a new element 11 to a list at a location without using the insert()
function.
7. Given a list of integers, write a program to find the largest and small-
est elements in the list without using max() and min().
8. Write a program to find a sub-list of a list from a given list.
Linked list
LEARNING OBJECTIVES
A linked list is a linear collection of data objects called nodes, each pointing
to the next node. A data element and an address to the next node may be
present in each node. This data structure makes it simple to add and remove
data objects. Other data structures such as stacks and queues can be imple-
mented using the linked list data structure.
The most essential advantage of a linked list over an array is that the
memory elements used to hold the data components do not have to be con-
tiguous, hence the size of the linked list is not restricted to the contiguous
memory locations available. Linked lists also allow for the insertion and
deletion of nodes at any point in the list with a fixed number of operations.
Linked lists make it difficult to access data. As a result, identifying a node
with a certain data element or the last node in a linked list may necessitate
sequential scanning of the majority or all of the elements.
Singly linked lists contain nodes which have two fields: a ‘data’ field and a
‘next’ field. The ‘next’ field contains the address of the next node. Sometimes
the address is also called a pointer to the next node (Figure 4.1).
data next
We describe the node in the linked list as a class in Python with two
attributes:
Python program 1
This class definition creates an object of type Node. It has two attributes:
data and next. Initially, the next is assigned to None and data is assigned to
the key, which is provided while creating the object.
Program continues…
class SLinkedList:
# Class definition of a Single Linked List
def __init__(self):
self .sta
rt = Node(None)
The class SLinkedList defines a single linked list with an attribute start,
which is an object of type node. The start is a pointer that points to the
starting node of the linked list.
Program continues…
# Main Program
if __name__ == '__main__':
list1 = SLinkedList()
Ans = 'y'
while (Ans == 'Y' or Ans == 'y'):
x = input("Enter data to create the node :")
NewNode = Node(x)
if (list1.start == None):
list1.start = NewNode
else:
temp = list1.start
while(temp.next != None):
temp = temp.next
temp.next=NewNode
Ans = input("Do you want to add More (Y | y) :")
L inked list 133
start
10 20 30 None
Output
i. Traversal
Traversal refers to visiting each node of a singly linked list. Before visiting
each node in a linked list we must define the class of a node and class of a
singly linked list.
Python program 2
While printing the elements of a singly linked list, each node of the linked
list must be visited. To do that we need to take a pointer temp, which is
assigned to start. While temp is not None, print the data part in temp and
move the pointer to the next node in the singly linked list.
Program continues…
ii. Insertion
There are four positions where we can insert a node: in the front, at the end,
after a given node and before a given bode.
We have already created a linked list in the previous program with data
elements 10, 20, 30.
Let us insert a node with some data element in the front. While inserting an
element as a front node, there are two cases.
Case 1: When there is no element in the singly linked list, start points to
None. After creating a new node, the start points to the new node.
L inked list 135
Case 2: When there is a singly linked list present, the new node’s next points
to the start node of the already existing singly linked list. And then the
existing start node moves to the new node (Figure 4.3).
(a) start
10 None 20 30 None
NewNode
start
(b)
10 20 30 None
NewNode
(c) start
10 20 30 None
NewNode
Figure 4.3 (a) Insertion at front. (b) Insertion at front. (c) Insertion at front
Program continues…
def insert_At_Begining(self,newdata):
NewNode = Node(newdata)
if (self .sta
rt == None):
self .sta
rt = NewNode
else:
NewNode.next = self.start
self .sta
rt = NewNode
Case 1: When there is no element in the singly linked list, start points to
None. After creating a new node, the start points to the new node.
Case 2: When there is a singly linked list present, assign a new pointer temp
to start, move temp to the last node. Assign the next of temp to the new
node (Figure 4.4).
136 Data structures for engineers and scientists using Python
(a) start
10 20 None 30 None
NewNode
10 20 None 30 None
NewNode
10 20 None 30 None
NewNode
10 20 30 None
NewNode
Figure 4.4 (a) Insertion at end. (b) Insertion at end. (c) Insertion at end. (d) Insertion at
end
Program continues…
def insert_At_End(self,newdata):
NewNode = Node(newdata)
if (self .sta
rt == None):
self .sta
rt = NewNode
else:
temp = self .sta
rt
while(temp.next):
temp = temp.next
temp.next=NewNode
Insertion in the middle is slightly more complicated since the link between
two nodes is to be “broken” and reattached to the new node appropriately.
While inserting a node after a node with a given key, first, take a pointer
temp and move the pointer to the location after which a new node to be
inserted (Figure 4.5). There are two cases.
L inked list 137
(a) start
10 20 40 None
30 None
NewNode
start temp
(b)
10 20 40 None
30 None
NewNode
10 20 40 None
30 None
NewNode
10 20 40 None
30
NewNode
10 20 40 None
30
NewNode
Figure 4.5 (a) New node created. (b) Assign temp to start node. (c)temp moved to the
required node after which new node to be inserted. (d) Assign new node’s
next to temp’s next node. (e) Assign temp’s next to NewNode
138 Data structures for engineers and scientists using Python
Case 1: When the node with the given key is not found in the linked list,
then print the appropriate message.
Case 2: When the node with the given key is found in the linked list, then
make the new node’s next point to the node to which temp’s next is pointing
and then make the temp’s next point to the new node.
Program continues…
While inserting a node before a node with a given key, assign temp to the
start. If the data in the first node is the same as the key (before which new
node to be inserted), use the insert_At_Begining() method.
If the node to be inserted is not the first node then take a pointer temp,
which points to the first node while checking the data in the second node
(that is temp’s next data). If it matches with the key, insert the new node as
a second node, otherwise move the temp pointer to the next one. There are
two cases.
Case 1: If the key is not found in the linked list, then print the appropriate
message.
Case 2: When the node with the given key is found in the linked list, then
make the new node’s next point to the node which temp’s next is pointing
to and then make the temp’s next point to the new node.
The diagram is same as the previous one, except for the pointer.
L inked list 139
Program continues…
iii. Deletion
Deletions from a linked list are comparatively easier than insertions. There
are five types of deletions: deletion of the node in the front, deletion of the
node at the end, deletion of a given node, deletion of the node after a given
node and deletion of the node before a given node.
Deleting a node that is the first node of a linked list is quite simple. Take a
pointer temp and assign temp to the start. Move the start to its next node.
Now delete the node pointed by temp (Figure 4.6).
(a) start
10 20 30 None
10 20 30 None
Figure 4.6 ( a) Deletion of the node at the front. (b) Assign temp to start. (c) Move start
to temp’s next. (d) delete the node pointed by temp
140 Data structures for engineers and scientists using Python
10 20 30 None
(d) start
20 30 None
Program continues…
def del_first(self):
temp = self .sta
rt
self.sta
rt = temp.next
del temp
Deleting a node that is the last node of a linked list is quite simple. Take a
pointer temp and assign temp to the start (Figure 4.7). There are two cases
of deleting the last node.
Case 1: If the last node is the same as the first node. In other words, there is
only one node present in the singleylinked list. Call the del_first() method.
Case 2: If there is more than one element in the linked list, move the temp
pointer to the last but one node using a while loop. Assign one more pointer
temp1 to temp’s next. Assign temp’s next to None and delete temp1.
(a) start
10 20 30 None
10 20 30 None
Figure 4.7 ( a) Deletion of the node at the end. (b) Assign pointer temp to start. (c) move
temp to last but one node. (d) Assign one more pointer temp1 to temp’s next.
(e) Assign none to temp’s next (f) Delete temp1
L inked list 141
10 20 30 None
10 20 30 None
10 20 None 30 None
10 20 None
Program continues…
def del_last(self):
temp = self .sta
rt
if temp.next == None :
self.del_first()
return
while(temp.next.next != None):
temp = temp.next
temp1 = temp.next
temp.next = None
del temp1
Deleting a node from the middle is a little more complicated since we have
to first traverse the list up to the node we wish to delete. Let the node to
be deleted contain the key. Depending on the presence of the key there are
three cases.
Case 1: If the key is present in the first node, call the del_first() method.
142 Data structures for engineers and scientists using Python
Case 2: If the key is not the first node, it can be anywhere in the linked list.
To traverse the linked list, take two pointers temp and temp1. Assign temp
to the start pointer and temp1 to next of temp. Keep moving both the point-
ers temp and temp1, till temp1’s data matches with the key, then assign
temp’s next to temp1’s next and delete temp1 (Figure 4.8).
Case 3: If the key does not match with data of any node, display appropri-
ate messages.
(a) start
10 20 30 None
10 20 30 None
10 20 30 None
10 20 30 None
10 30 None
Figure 4.8 (a) Deletion of the node. (b) Assign pointer temp to start. (c) move temp to
node previous to the node to be deleted. (d) Assign one more pointer temp1
to temp’s next. (e) Assign temp;s next to temp1’s next (f) Delete temp1
Program continues…
temp1 = temp.next
while(temp1.data != key):
temp = temp.next
temp1 = temp1.next
if (temp1.data != key and temp1.next == None ):
print(data, " Not Found")
else:
temp.next = temp1.next
del temp1
Case 1: If there is only node and the key matches with the data present
in the node. As there is no node after the first node, display appropriate
messages.
Case 2: If the key is not the first node, it can be anywhere in the linked list.
To traverse the linked list, take a pointer temp and assign it to the start
pointer. Keep moving the pointer until the temp’s data matches with the
key. Take one more pointer temp1 and assign it to temp’s next. Now assign
temp’s next to temp1’s next and delete temp1.
Case 3: If the key does not match with data of any node, display appropri-
ate messages.
The diagram is the same as the previous one.
Program continues…
Case 1: If the key matches with the data present in the first node. As there
is no node before the first node, before the node cannot be deleted, display
appropriate messages.
Case 2: If the key is in the second node, call the del_first() method.
Case 3: If the key is not the second node, it can be anywhere in the linked
list. To traverse the linked list, take two pointers temp and temp1. Assign
temp to the start pointer and temp1 to next-next of temp. Keep moving
both the pointers temp and temp1, until temp1’s data matches with the key.
Take one more pointer temp2 and assign temp’s next. For deleting, assign
temp’s next to temp2’s next and delete temp2 (Figure 4.9).
Case 4: If the key does not match with data of any node, display appropri-
ate messages.
(a) start
10 20 30 None
10 20 30 None
10 20 30 None
10 20 30 None
Figure 4.9 (a) Deletion of the node. (b) Assign temp to start. (c) Assign temp1 to last
node. (d) Assign temp2 to last but 1 node (f) connect next of temp to next
of temp2 (e) Deletion temp2
L inked list 145
10 20 30 None
10 30 None
Program continues…
Program continues…
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Create a Single Linked List ")
print("2. Insert at the Beginneing ")
print("3. Insert at the End")
print("4. Insert After a given Data ")
print("5. Insert before a given Data")
146 Data structures for engineers and scientists using Python
elif (i==2):
x = input("Enter data to create the node :")
list1.insert_At_Begining(x)
[Link]()
elif (i==3):
x = input("\n Enter data to create the node :")
list1.insert_At_End(x)
[Link]()
elif (i==4):
x = input("\n Enter data to create the node :")
y = input("Node to be created after data :")
list1.insert_After(y,x)
[Link]()
elif (i==5):
x = input("\n Enter data to create the node :")
y = input("Node to be created before data :")
list1.insert_Before(y,x)
[Link]()
elif (i==6):
list1.del_first()
[Link]()
elif (i==7):
list1.del_last()
[Link]()
L inked list 147
elif (i==8):
x = input("Node to be deleted :")
list1.del_node(x)
[Link]()
elif (i==9):
x = input("Node to be deleted after data :")
list1.del_after(x)
[Link]()
elif (i==10):
x = input("Node to be deleted before data :")
list1.del_before(x)
[Link]()
else:
print("End")
Output
In doubly linked lists each node, besides containing a pointer to the next
node, also contains a pointer to the previous node (Figure 4.10).
148 Data structures for engineers and scientists using Python
A doubly linked list contains an extra pointer, usually called prev (previ-
ous), together with the next pointer and data (Figure 4.11).
None 10 20 30 None
Python program 3
i. Traversal
Traversal refers to visiting each node in a data structure. Readers are advised
to refer the traversal in singly linked list.
L inked list 149
ii. Insertion
A node can be inserted in a doubly linked list in four different ways: at the
front, at the end, after a given node and before a given node.
When a node is added in the front, the newly added node becomes the
start node.
Let us insert a node with some data element in the front. While inserting
an element as a front node, there are two cases:
Case 1: When there is no element in the doubly linked list, the start points
to None. After creating a new node with prev and next set to None, the
start points to the new node.
Case 2: When there is a doubly linked list, follow these three steps to per-
form the operation (Figure 4.12).
(a) start
NewNode
(b) start
NewNode
(c) start
None 10 20 30 None
NewNode
(d) start
None 10 20 30 None
NewNode
Figure 4.12 (a) create a new node (b) Assign next of new node to start (c) Assign
previous of start to newnode (d) Assigne start to new node
150 Data structures for engineers and scientists using Python
Program continues…
def insert_At_Begining(self,newdata):
NewNode = Node(newdata)
if (self.start==N
one):
self .sta
rt = NewNode
else:
NewNode.next = self.start
self .start
.p
rev = NewNode
self .sta
rt = NewNode
Insertion of a node as the last node in a double linked list is almost the
same as insertion of a node as the last node in a single list. It also has two
cases:
Case 1: When there is no element in the single linked list, start points to
None. Call the insert_At_Begining () method.
Case 2: When there is a doubly linked list present, assign a pointer temp
to the start. Move temp to the node where next of the node is None (i.e.,
the last node). Assign temp’s next to New Node and then assign new node’s
prev to temp (Figure 4.13).
(a) start
Figure 4.13 ( a) Create a NewNode (b) Assign temp to start (c) Move temp till last node.
(d) Assign next of temp to NewNode (d) Assign previous of NewNode to
temp (e) Insertion of a node at the end in a doubly linked list
L inked list 151
None 10 20 30 None
NewNode
Program continues…
def insert_At_End(self,newdata):
if (self .start == None):
self.insert_At_Begining(newdata)
return
NewNode = Node(newdata)
temp = self .start
while(temp.next != None):
temp = temp.next
temp.next=NewNode
NewNode.prev = temp
Insertion in the middle is slightly more complicated since the link between
two nodes is to be “broken” and reattached to the new node appropriately.
While inserting a node after a node with a given key, first, take a pointer
temp and move the pointer to the location after which a new node to be
inserted. There are two cases:
Case 1: When the node with the given key is not found in the linked list,
then print the appropriate message.
152 Data structures for engineers and scientists using Python
Case 2: When the node with the given key is found in the linked list, check if
temp’s next points to None. If so, insert the new node as last node by calling
insert_At_End() method, otherwise follow these four steps (Figure 4.14):
i. Set a new node’s next point to the node to which temp’s next is
pointing.
ii. Assign the new node’s prev to temp.
iii. Make the temp’s next-prev point to the new node.
iv. Set temp’s next to the new node.
start
(a)
None 10 20 40 None
start temp
(b)
None 10 20 40 None
start temp
(c)
None 10 20 40 None
None 30 None
NewNode
temp
(d) start
None 10 20 40 None
None 30
NewNode
(e) start temp
None 10 20 40 None
30
NewNode
Figure 4.14 ( a) Insert a node after a given node in a doubly linked list. (b) Assign Temp
to start node (c) Move temp till required lication (d) Assign newNode next
to temp Next (e) Assign newnode previous to temp (f)Assign temp’s next’s
previous to NewNode. (g) Assign temp’s next to NewNode
L inked list 153
None 10 20 40 None
30
NewNode
None 10 20 40 None
30
NewNode
These steps can be executed through the insert_After() method shown next.
Program continues…
While inserting a node before a node with a given key, assign temp to the
start. If the data in the temp node is the same as the key (before which new
node to be inserted), call insert_At_Begining() method.
154 Data structures for engineers and scientists using Python
If the node to be inserted is not the first node then make a pointer temp
to check the data in the second node (that is temp’s next-data). If it matches
with the key, insert the new node as a second node, otherwise move the
temp pointer to the next one. There are two cases:
Case 1: If the key is not found in the linked list, then print the appropriate
message.
Case 2: When the node with the given key is found in the linked list, then
make the new node’s next point to the node that the temp’s next is pointing
to and then follow these steps.
i. Set a new node’s next point to the node to which temp’s next is
pointing.
ii. Assign the new node’s prev to temp.
iii. Make the temp’s next-prev point to the new node.
iv. Set temp’s next to the new node.
The diagram is same as the previous one, except for the pointer.
Program continues…
iii. Deletion
Deletions from a linked list are comparatively easier than insertions. Once
again there are five types of deletions: deletion of the first node, deletion of
the node in the end, deletion of a given node, deletion of the node after a
given node and deletion of the node before a given node.
L inked list 155
Deleting a node which is the first node of a doubly linked list is quite simple.
Take a pointer temp and assign it to the start. Move the start to its next
node. Set the start’s prev to None and delete the node pointed by temp.
The diagram is almost the same as the deletion of the first node in the
singly linked list.
Program continues…
def del_first(self):
if(self.start != None):
temp = self .sta
rt
self .sta
rt = self .start
.n
ext
temp.next = None
del temp
if (self .sta
rt != None ):
self .start.prev=
None
Deleting a node that is the last node of a doubly linked list is quite simple.
Take a pointer temp and assign temp to the start. There are two cases when
deleting the last node.
Case 1: If the last node is the same as the first node. In other words, there is
only one node present in the doubly linked list. Call the del_first() method.
Case 2: If there are more than one element in the doubley linked list, move
the temp pointer to the next to last one node using a while loop. Assign one
more pointer temp1, pointing to temp’s next. Assign temp’s next to None
and delete temp1.
The diagram is almost the same as deletion of the first node in the singly
linked list.
Program continues…
def del_last(self):
temp = self .sta
rt
if (temp.next == None) :
self.del_first()
return
while(temp.next.next != None):
temp = temp.next
temp1 = temp.next
temp.next = None
del temp1
156 Data structures for engineers and scientists using Python
Deleting a node from the middle is a little more complicated since we have
to first traverse the list up to the node we wish to delete. Let the node to
be deleted contain the key. Depending on the presence of the key, there are
three cases:
Case 1: If the key is present in the first node, call the del_first() method.
Case 2: If the key is not the first node, it can be anywhere in the linked list.
To traverse the linked list, take a pointer temp and assign it to the start
pointer. Keep moving the temp pointer until temp1’s data matches with the
key.
Program continues…
Case 1: If there is only node and the key matches with the data present
in the node. As there is no node after the first node, display appropriate
messages.
L inked list 157
Case 2: If the key is not the first node, it can be anywhere in the linked list.
To traverse the linked list, take a pointer temp and assign it to the start
pointer. Keep moving the pointer until temp’s data matches with the key.
i. If the key does not match with data of any node, display appropriate
messages.
ii. If the key matches with the last node, call the del_last() method.
iii. If the key matches with any other intermediate node, take one more
pointer temp1 and assign it to temp’s next. Assign temp1’s next-prev
to temp, assign temp’s next to temp1’s next. Now delete the temp1
node.
Program continues…
elif(temp.data == data and temp.next.next == None):
self.del_last()
else:
temp1=temp.next
temp1.next.prev=temp
temp.next = temp1.next
del temp1
Case 1: If the key matches with the data present in the first node. As there
is no node before the first node, before the node cannot be deleted, display
appropriate messages.
Case 2: If the key is in the second node, call the del_first() method.
158 Data structures for engineers and scientists using Python
Case 3: If the key is not the second node, it can be anywhere in the linked
list. To traverse the linked list, take a pointer temp. Assign temp to the start
pointer. Keep moving temp pointers, until temp’s data matches with the
key. There can be three options:
Program continues…
Program continues…
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Create a Double Linked List ")
print("2. Insert at the Beginneing ")
print("3. Insert at the End")
print("4. Insert After a given Data ")
print("5. Insert before a given Data")
print("6. Delete the First node")
print("7. Delete the Last node")
print("8. Delete the a given node")
print("9. Delete After a given Data")
print("10. Delete before a given Data")
print("11. Exit ")
L inked list 159
if __name__ == '__main__':
list1 = DLinkedList()
i=1
while (i > 0 and i <=10 ):
i = menu()
if i == 1:
x = input("Enter data to create the first node :")
list1.start = Node(x)
[Link]()
elif (i==2):
x = input("Enter data to create the node :")
list1.insert_At_Begining(x)
[Link]()
elif (i==3):
x = input("\n Enter data to create the node :")
list1.insert_At_End(x)
[Link]()
elif (i==4):
x = input("\n Enter data to create the node :")
y = input("Node to be created after data :")
list1.insert_After(y,x)
[Link]()
elif (i==5):
x = input("\n Enter data to create the node :")
y = input("Node to be created before data :")
list1.insert_Before(y,x)
[Link]()
elif (i==6):
list1.del_first()
[Link]()
elif (i==7):
list1.del_last()
[Link]()
elif (i==8):
x = input("Node to be deleted :")
list1.del_node(x)
[Link]()
elif (i==9):
x = input("Node to be deleted after data :")
list1.del_after(x)
[Link]()
160 Data structures for engineers and scientists using Python
elif (i==10):
x = input("Node to be deleted before data :")
list1.del_before(x)
[Link]()
else:
print("End")
In the last node of a singly linked list, we have a None reference to indicate
the lack of further nodes. If we make it point to the first node (or the start
node) of the list we have a circularly linked list. In other words, the last ele-
ment contains the address of the first element. We take one more pointer,
end, to point to the last node on a circular linked list (Figure 4.15).
start end
10 20 30
The node structure of a circular linked list and node structure of a singly
linked list are the same. When we create a circular linked list, we take an
additional point to point to the last node.
Python program 4
class Node:
def __init__(self, dataval=None):
self .da
ta = dataval
self .ne
xt = None
L inked list 161
class CLinkedList:
def __init__(self):
self .sta
rt = Node(None)
self .e
nd = Node(None)
self .start
.n
ext = self
.e
nd
self .end
.n
ext = self
.sta
rt
i. Look-up
Let us say, we are looking for data item x in the circular list. We execute
the following steps:
1. Start at the head node. (The head node can be any one of the nodes.)
2. Follow the links from the head node until we reach the node contain-
ing the desired value, if it exists.
3. If we reach back to the head node, report failure.
Let us first create a circular list. If we are creating the first node in the list,
let us call it head. We define the node as a structure:
Program continues…
def listprint(self):
print("The Elements in the Linked List are : ", end = "")
temp = self .sta
rt
if (self .sta
rt == None):
print("There is no data..")
return
else:
while(True):
print(temp.data, end= " ")
temp = temp.next
if (temp == self .sta
rt):
return
ii. Insertion
Insertion can be at the beginning, at the end, after a given node and before
a given node.
162 Data structures for engineers and scientists using Python
When a node is added in the front, the newly added node becomes the start
nod.
Let us insert a node with some data element in the front. While inserting
an element as a front node, there are two cases:
Case 1: When there is no element in the circular linked list, the start and
end points to None. After creating a new node with next of the new nodes
pointing to itself, the start and end points to the new node (Figure 4.16).
start end
10
New node
Case 2: When there is a circular linked list, follow these four steps to per-
form the operation (Figure 4.17).
(a)
10
start end
New node
20 30 40
(b)
10
start end
New node
20 30 40
Figure 4.17 (a) Insert a node after a given node in a doubly linked list. (b) Assign
NewNode’s next to start. (c) Assign end’s next to Newnode (d) Move
start to Newnode
L inked list 163
(c)
10
start end
New node
20 30 40
(d)
start
10
end
New node
20 30 40
We execute the following Python code to insert a node with data item 10
in the beginning of the circular list with the variables declared earlier. The
new node contains the data element 10.
Program continues…
def insert_At_Begining(self,newdata):
NewNode = Node(newdata)
if (self.start==
N
one):
self .sta
rt = NewNode
NewNode= self
.st
art
self .e
nd = self.sta
rt
self .end
.n
ext = self.start
else:
NewNode.next = self.start
self .sta
rt = NewNvode
self .end
.n
ext = self.start
164 Data structures for engineers and scientists using Python
When a node is added at the end, the newly added node becomes the end
node.
Let us insert a node with some data element at the rear (Figure 4.18).
While inserting an element as an end node, there are two cases:
Case 1: If the circular linked list is empty, then we simply add the new node
as in case 1 of insertion at the beginning.
Case 2: When there is a circular linked list, follow these three steps to per-
form the operations (Figure 4.18).
(a)
start end
10
New node
20 30 40
(b)
start 10
end
New node
20 30 40
(c)
end 10
start
New node
20 30 40
Figure 4.18 (a) Insertion at the end in circular linked lists. (b) Assign end’s next to
Newnode (c) Assign next of newnode to start
L inked list 165
A program segment that does this with the usual notation is the following:
• The method takes two parameters: self (referring to the instance of the
class) and newdata (the data to be inserted into the new node).
• A new node is created using the Node class, with newdata as its data.
• The code checks if the linked list is empty by verifying if self. start is
None. If it is empty, the insert_At_Begining method is called to insert
the new data at the beginning of the linked list. Then, the method
returns.
• If the linked list is not empty, the next attribute of the new node
(NewNode.next) is set to the current start of the linked list.
• The next attribute of the current end of the linked list (self.end.next)
is set to the new node (NewNode).
• Finally, the end attribute of the linked list is updated to point to the
new node (self.end = NewNode), making it the new end of the linked
list.
Program continues…
def insert_At_End(self,newdata):
NewNode = Node(newdata)
if (self .start == None) :
self.insert_At_Begining(newdata)
return
NewNode.next = self.start
self.end
.next = NewNode
self.e
nd = NewNode
Insertion in the middle is slightly more complicated since the link between
two nodes is to be “broken” and reattached to the new node appropriately.
While inserting a node after a node with a given key, first, take a pointer
temp and move the pointer to the location after which a new node is to be
inserted. Let us assume that temp points to nodes having data 30. We are
going to insert the new node after 30 as shown in Figure 4.19. There are
two cases:
Case 1: When the node with the given key is not found in the linked list,
then print the appropriate message.
Case 2: When the node with the given key is found in the linked list, check
if temp’s next points to start. If so, insert the new node as last node by call-
ing insert_At_End() method, otherwise follow these three steps:
166 Data structures for engineers and scientists using Python
i. Set a new node’s next point to the node to which temp’s next is
pointing.
ii. Assign the new node’s next to temp’s next.
iii. Make the temp’s next point to the new node.
(a)
10 end
start temp
New node
20 30 40
(b)
10
start
New node
20 30 40
(c)
10
start temp
New node
20 30 40
Figure 4.19 (a) Locate temp to desired location (b) Assign newnode’s next to temp’s
next (c) Assign temp’s next to Newnode
Program continues…
The method takes three parameters: self (referring to the instance of the
class), data (the data value after which the new node will be inserted), and
newdata (the data to be inserted into the new node).
While inserting a node before a node with a given key, assign temp to the
start. If the data in the temp node is the same as the key (before which new
node to be inserted), call the insert_At_Begining() method.
If the node to be inserted is not the first node, then make a pointer temp
to check the data in the second node (that is temp’s next-data). If it matches
with the key, insert the new node as a second node, otherwise move the
temp pointer to the next one. There are two cases:
Case 1: If the key is not found in the linked list, then print the appropriate
message.
Case 2: When the node with the given key is found in the linked list, then
make the new node’s next point to the node to which temp’s next is pointing
to. Let us assume that temp points to nodes having data 30. We are going to
insert the new node before 40 as shown in Figure 4.19; follow these steps.
i. Set a new node’s next point to the node to which temp’s next is
pointing.
168 Data structures for engineers and scientists using Python
Program continues…
iii. Deletion
Deletions from a linked list are comparatively easier than insertions. There
are five types of deletions: the first node, the node in the end, a given node,
after a given node and before a given node.
Deleting a node that is the first node of a circular linked list is quite simple.
Take a pointer temp and assign it to the start. Move the start to its next
node. Set the end’s next start and delete the node pointed by temp.
The diagram is almost same as deletion of the first node in the singly
linked list (Figure 4.20).
20 30 40
20 30 40
20 30 40
30 40
Figure 4.20 (a) Assign temp to start (b) Move start to temp’s next (c) Assign end’s next
to start (d) remove temp
170 Data structures for engineers and scientists using Python
Program continues…
def del_first(self):
temp = self .sta
rt
if (self .sta
rt == self .end):
self .start = self.end = None
del temp
return
self.start = temp.next
self.end.n
ext = self .start
del temp
Case 1: If the end node is the same as the first node. In other words, there is
only one node present in the doubly linked list. Call the del_first() method.
Case 2: If there are more than one element in the doubly linked list, move
the temp pointer until the temp’s next to next is not the start node using
a while loop. In other words, temp points the node before the end node.
Assign one more pointer temp1, pointing to temp’s next. Assign temp’s next
to start. Set end to temp and delete temp1.
L inked list 171
20 30 40
20 30 40
20 30 40
20 30 40
20 30
Figure 4.21 (a) Deletion of the node at the end in a circular linked list. (b) Assign
temp1 to end. (c) Assign temp’s next to start. (d) Assign end to temp.
(e) Remove temp1
Program continues…
def del_last(self):
temp = self .sta
rt
if (self .sta
rt == self .e
nd ) :
self.del_first()
return
while(temp.next.next != self.start):
temp = temp.next
temp1 = temp.next
temp.next = self.start
self.e
nd = temp
del temp1
172 Data structures for engineers and scientists using Python
Deleting a node from the middle is a little more complicated since we have
to first traverse the list up to the node we wish to delete (Figure 4.22). Let
the node to be deleted contain the key. Depending on the presence of the
key, there are four cases.
Case 1: If the key is present in the first node, call the del_first() method.
Case 2: If the key is not the first node, it can be anywhere in the linked list.
To traverse the linked list, take a pointer temp and assign it to the start
pointer. Keep moving the temp pointer until temp’s next data matches with
the key. If the key is found at the last node, call the del_last() method.
Case 3: If the key is found in between, take one more pointer temp1 (temp1
to be deleted) pointing to temp’s next, assign temp’s next to temp1’s next.
Now delete temp1.
10 20 30 40
10 20 30 40
10 20 30 40
10 20 40
Figure 4.22 (a) Assign temp to desired location (b) Assign temp1 to temp’s next
(c) Assign temp’s next to temp1’s next (d) Delete temp1
L inked list 173
Program continues…
if (temp.next.data != data and temp.next.next ==
self.start):
print(data, " Not Found")
elif(temp.next.data == data and temp.next.next ==
self.start):
self.del_last()
else:
temp1 = temp.next
temp.next = temp1.next
del temp1
Let the node to be deleted contain the key (Figure 4.22). Depending on the
presence of the key, there are four cases.
Case 1: If the key is present in the first node, call the del_first() method.
Case 2: If the key is not the first node, it can be anywhere in the linked list.
To traverse the linked list, take a pointer temp and assign it to the start
pointer. Keep moving the pointer until temp’s data matches with the key. If
the key is found at the last node, call the del_last() method.
Case 3: If the key matches with any other intermediate node, take one more
pointer temp1 and assign it to temp’s next. Assign temp1’s next-prev to
temp, assign temp’s next to temp1’s next. Now delete the temp1 node.
Case 4: If the key does not match with data of any node, display appropri-
ate messages.
Program continues…
return
while(temp.data != data and temp.next != self.start):
temp = temp.next
self.del_first()
return
else:
temp1 = temp.next
temp.next = temp1.next
del temp1
Case 1: If the key matches with the data present in the second node in the
circular linked list, call the del_first() method.
Case 2: If the key matches with the data present in the first node in the cir-
cular linked list, call the del_last() method.
Case 3: If none of the above cases are met, the code enters a while loop that
continues until either the data value is found or the next node becomes the
starting node again.
i. Inside the loop, temp is updated to the next node in the circular linked
list.
ii. After exiting the while loop, the code checks if the data value was
found or if the next node is the starting node (indicating that the data
value was not found).
iii. If the data value was not found, it prints a message indicating that the
data was not found.
iv. Otherwise, it initializes temp1 as the starting node and enters another
while loop to find the node immediately before temp in the circular
linked list.
v. Once the previous node is found (temp1), it updates its next pointer to
skip the node to be deleted (temp) and assigns temp2 to the node to be
deleted.
vi. Finally, it deletes temp2 using the del keyword.
L inked list 175
Program continues…
# temp = temp.next
if (temp.data != data and temp.next == self
.sta
rt ):
print(data, " data Not found")
else:
temp1 = self .sta
rt
while(temp1.next.next != temp):
temp1 = temp1.next
temp2 = temp1.next
temp1.next = temp
del temp2
Program continues…
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Create a Single Linked List ")
print("2. Insert at the Beginneing ")
print("3. Insert at the End")
print("4. Insert After a given Data ")
print("5. Insert before a given Data")
print("6. Delete the First node")
print("7. Delete the Last node")
print("8. Delete the a given node")
print("9. Delete After a given Data")
print("10. Delete before a given Data")
print("11. Exit ")
opt = int(input("Enter a valid menu item ... "))
return opt
if __name__ == '__main__':
list1 = CLinkedList()
i=1
while (i > 0 and i <=10 ):
i = menu()
176 Data structures for engineers and scientists using Python
if (i == 1):
x = input("Enter data to create the first node :")
list1.start = Node(x)
list1.end= list1.start
list1.end.next = list1.start
[Link]()
elif (i==2):
x = input("Enter data to insert at the beginning :")
list1.insert_At_Begining(x)
[Link]()
elif (i==3):
x = input("\n Enter data to insert at the end :")
list1.insert_At_End(x)
[Link]()
elif (i==4):
x = input("\n Enter data to create the node :")
y = input("Node to be created after data :")
list1.insert_After(y,x)
[Link]()
elif (i==5):
x = input("\n Enter data to create the node :")
y = input("Node to be created before data :")
list1.insert_Before(y,x)
[Link]()
elif (i==6):
list1.del_first()
[Link]()
elif (i==7):
list1.del_last()
[Link]()
elif (i==8):
x = input("Node to be deleted :")
list1.del_node(x)
[Link]()
elif (i==9):
x = input("Node to be deleted after data :")
list1.del_after(x)
[Link]()
elif (i==10):
x = input("Node to be deleted before data :")
list1.del_before(x)
[Link]()
else:
print("End")
L inked list 177
Applications
• In our personal computers, all the running programs are kept in a
circular linked list. The operating system fixes time slots for all the
running programs in the circular list.
• A circular linked list can also be used to create circular queues.
• A linked list is a useful data structure to represent and manipulate
polynomials. Most of the operating systems maintain the free list of
memory blocks in the form of a linked list.
True–false questions
Fill-in-the-blank questions
Multiple-choice questions
2. Each node in a linked list consists of two fields. One field is the data
field. The other one is
a. Pointer to a char c. Pointer to the node
b. Pointer to an integer d. None of the above
5. A variant of a linked list where the last node points to the first node,
is a
a. Singly linked list c. Circular linked list
b. Doubly linked list d. Multiple linked list
L inked list 179
6. You are given pointers to the first node and the last node of a singly
linked list. Which of the following operations is dependent on the
length of the list?
a. Delete the first element of c. Delete the last element
the list
b. Insert a new element as the d. Add a new element at the
first element end of the list
11. Which of the following methods is best for locating an entry in the
linked list at position k?
a. Singly linked list c. Circular linked list
b. Doubly linked list d. Array implementation
180 Data structures for engineers and scientists using Python
12. Which of the following issues can be resolved with a linked list and
two pointers?
a. Finding the intersection of c. Detecting a cycle in a linked
two linked lists list
b. Finding the middle ele- d. All of the above
ment of a linked list
19. The linked list data structure provides significant cost savings in
a. Space utilization c. Computational time and
space utilization
b. Computational time d. None of above
Descriptive questions
1. Let A and B be two singly linked lists. Write a program to attach these
two lists to construct a singly linked circular list
2. Create a doubly-linked list with the following elements and write a
program to print it in the reverse order: 3 5 7 9 11 13 15.
3. If A[3][3][3] is an integer matrix, calculate the addresses of the follow-
ing elements:
1. True
2. False
3. False
4. True
5. False
182 Data structures for engineers and scientists using Python
1. start
2. two
3. one
4. circular
5. linked list
1. a, b 2. c 3. a 4. c 5. c
6. c 7. b 8. b 9. b 10. d
11. d 12. d 13. a 14. c 15. a
16. c 17. d 18. b 19. c 20. a
Chapter 5
Stacks
LEARNING OBJECTIVES
We know that the linear data structures are divided into arrays, stacks and
queues. In this chapter, we will focus on the stack as a linear data structure.
Stack data structures can be implemented using arrays. Simple examples of
a stack are a stack of plates in a restaurant and a stack of books in a library.
5.1 STACKS
The insert and delete operations are done at the same end of a stack, which
is a special case of an ordered list. Stacks are used as a data structure in
programming languages to achieve recursion, to transform an infix expres-
sion to a postfix expression and so on.
A stack is a restricted ordered list in which only one end, termed the top
of the stack, allows insertions and deletions. The stack abstract data type
has the data member top, which points to the topmost element in the stack.
There are two basic operations: push() adds an element to the top of the
stack and pop() removes an element from the top of the stack. The element
Top D
C
B
A
5.2 STACK OPERATIONS
5.2.1 push()
The push(S) operation inserts an element on the top of the stack S
(Figure 5.2). It follows these steps:
Top Top E
Top D E D D
C Push (E) C C
B B B
A A A
Top=top+1 Stack[Top]=Data
5.2.2 pop()
We execute the following steps to perform the pop operation (also see
Figure 5.3):
Top E Top
E
D D Top D
C Pop() C C
B B B
A A A
Data=Stack[Top] Top=Top-1
5.2.3 peek()
peek() is similar to pop() except that this function removes the element from
the top of the stack without decrementing the top by one (Figure 5.4).
D D
Top Top D
C C
peek()
B B
A A
5.3 STACK (ADT)
Let us formally describe the structure of the stack together with a set of
axioms that we expect for the stacks.
The abstract data type stack can be described by the following methods
and axioms.
The first axiom says that when we create a stack, it is empty, hence the
isEmpty() boolean function returns true.
The second axiom is easy to understand since when we push an element
onto a stack, it is not empty, hence the isEmpty() function returns false.
We cannot pop() an element from an empty stack. Thus pop(create())
gives an error since the create() function creates an empty stack and so is
the case with peek(create()).
peek(push(e,S) returns e since after the push operation the topmost ele-
ment is [Link] see Table 5.3.
5.4 IMPLEMENTATION
Now let us implement a stack using list without restriction of the upper
limit or the size of the stack.
Python program 1
The create()method creates an empty stack with the top pointing to -1.
Here S = [] indicates an empty list.
Program continues…
The isEmpty() method checks if the stack is empty. It checks if the top is
pointing to -1. It returns 1 to indicate the stack is empty; otherwise returns
0 to indicate the stack is not empty (at least one element is there in the
stack).
Program continues…
The push()method takes two parameters, the stack and the top. Every time
an element is pushed onto the stack, the top is incremented by 1 and the
element is appended to the list. As a list is a heterogeneous data structure,
we force the user to enter an integer only.
S tacks 189
Program continues…
The pop() method takes two parameters, the stack and the top. Every time
an element is popped from the stack, it checks if the stack is not empty. If
the stack is empty, it shows an appropriate message, and if the stack is not
empty, then the top of the stack is printed and the top is decremented by 1.
At last the stack and the top is returned.
Program continues…
The peek() method takes two parameters, the stack and the top. It just
prints the element that is on the top of the stack.
Program continues…
The display() method takes two parameters, the stack and the top. This
function prints the elements in the stack in the reverse order (the element
inserted last is printed first).
190 Data structures for engineers and scientists using Python
Program continues…
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Push an element ")
print("2. Pop from stack ")
print("3. Peek the stack")
print("4. Display the stack")
print("5. Exit ")
opt = int(input("Enter a valid menu item ... "))
return opt
The menu() method shows a menu to perform the operations defined for a
stack. It returns a choice of operation to perform.
Program continues…
#Main Program
if __name__ == "__main__":
St,top=create()
i=1
while (i > 0 and i < 5 ):
i = menu()
if i == 1:
St,top = push(St,top)
display(St,top)
elif i == 2:
St,top = pop(St,top)
if (type(top) != str):
display(St,top)
elif i == 3:
peek(St,top)
elif i == 4:
display(St,top)
else:
print("Exit")
Output
Stack is Empty
Stack is Empty
Now let us implement a stack using list with a restriction of upper limit
or the size of the stack. There is no change in the create(), pop(), peek(),
isEmpty() and menu() functions and some changes in the push() and dis-
play() functions. A new function isFull() is also introduced. We are discuss-
ing only those functions that have some changes from Python program 1.
S tacks 193
Python program 2
def isFull(top,size):
if (top >= size-1):
return 1
else:
return 0
The isFull() method checks if the stack is full. It checks if the top is point-
ing to maximum size -1. It returns 1 to indicate the stack is full; otherwise
returns 0 to indicate the stack is not full.
Program continues…
def push(S,top,size):
if (isFull(top,size) == 1):
print("Overflow: No more place for the Stack")
else:
no = int(input(("Enter a number to push onto
the stack ")))
top += 1
[Link](no)
return S,top
The push()method takes two parameters, the stack and the top. Every time
an element is pushed onto the stack, it checks if the stack is full. If the stack
is full, it shows an appropriate message; otherwise the top is incremented by
one and the element is appended to the list.
Program Continues…
def display(S,top,size):
print("Top is at index -> ",top)
if (isEmpty(top) == 1 ) :
print("\nStack is Empty")
elif(isFull(top,size) == 1):
print("\nStack is Full")
else:
print("The elements in the Stack is")
for i in range(top,-1,-1):
print(i, "->",S[i])
The display() method takes two parameters, the stack and the top. This
function prints the elements in the stack in the reverse order (the element
inserted last is printed first) if the stack is neither full nor empty.
194 Data structures for engineers and scientists using Python
Output
Stack is Full
Stack is Full
Stack is Empty
Python program 3
def create():
S={}
top = -1
print(“Empty Stack created”)
return S,top
Program continues…
def isFull(top,size):
if (top >= size-1):
return 1
else:
return 0
Just like the previous program, the isFull() function checks if the stack is
full. When the location of the top is greater than or equal to maximum size
-1, it returns 1 indicating the stack is full; otherwise it returns 0 indicating
the stack is not full.
Program continues…
def isEmpty(top):
if (top <= -1):
return 1
else:
return 0
The isEmpty() function checks if the stack is empty. When the location of
the top is less than or equal to -1, it returns 1 indicating the stack is empty;
otherwise it returns 0 indicating the stack is not empty.
S tacks 197
Program continues…
def push(S,top,size):
if (isFull(top,size) == 1 ):
print("Overflow: No more place in the Stack")
else:
no = int(input(("Enter a number to push onto the stack ")))
top += 1
S[top] = no
return S,top
The push()function takes three parameters: the stack S, top and the size
of the stack. If the stack is full, it prints an appropriate message; otherwise
increment the top by one and insert the element on the top of the stack. It
returns the stack and the top of the stack.
Program continues…
def pop(S,top):
if (isEmpty(top) == 1):
print("Underflow: There is no element in the Stack")
else:
print("The element to pop is ",S[top])
del S[top]
top -= 1
return S,top
The pop()function takes two parameters: the stack S and top of the stack.
If the stack is empty, it prints an appropriate message; otherwise, decrement
the top by 1 and return the stack and the top.
Program continues…
def peek(S,top):
if (isEmpty(top) == 1):
print("Stack is Empty")
else:
print("The element at top is ",S[top])
The peek() method takes two parameters, the stack an: the top. It just
prints the element that is on the top of the stack.
198 Data structures for engineers and scientists using Python
Program continues…
def display(S,top,size):
print("Top is at index -> ",top)
if (isEmpty(top) == 1) :
print("\nStack is Empty")
elif(isFull(top,size) == 1):
print("The elements in the Stack is")
for i in reversed(list([Link]())):
print(i, "->",S[i])
print("\nStack is Full")
else:
print("The elements in the Stack is")
for i in reversed(list([Link]())):
print(i, "->",S[i])
The display() method takes two parameters: the stack and the top. This
function prints the elements in the stack in the reverse order (the element
inserted last is printed first) if the stack is neither full nor empty.
Program continues…
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Push an element ")
print("2. Pop from stack ")
print("3. Peek the stack")
print("4. Display the stack")
print("5. Exit ")
opt = int(input("Enter a valid menu item ... "))
return opt
Program continues…
if __name__ == "__main__":
size = int(input("Enter the size of the Stack "))
St,top=create()
i=1
while (i > 0 and i < 5 ):
i = menu()
if i == 1:
St,top = push(St,top,size)
display(St,top,size)
elif i == 2:
St,top = pop(St,top)
display(St,top,size)
elif i == 3:
peek(St,top)
S tacks 199
elif i == 4:
display(St,top,size)
else:
print("Exit")
Python program 4
class Stack:
def __init__(self,size):
self.S = list()
self.t
op = -1
[Link] = size
print("\nEmpty Stack Created")
Class ‘Stack’ is defined with three variables: a list, ‘top’ initialized to -1 and
maximum size of the stack. All the methods in the class are public.
Program continues…
def isFull(self):
if (self op >= [Link]-1):
.t
return 1
else:
return 0
The isFull() method is a Boolean method that returns 1 (true) if the stack
full condition is satisfied self.top >= [Link]-1 and returns
0 (false) otherwise.
Program continues…
def isEmpty(self):
if (self op <= -1):
.t
return 1
else:
return 0
Program continues…
def push(self):
if ([Link]() == 1):
print(“Overflow: No more place for the Stack”)
else:
no = int(input((“Enter a number to push onto the stack ”)))
self .top += 1
self.S.append(no)
The push()function first checks if the stack is full. If the stack is full, it
prints an appropriate message; otherwise, increment the top by one and
insert the element on the top of the stack.
The initial stack is shown in Figure 5.5.
Top 5
4
3
2
1
After executing push() method, the stack status is as shown in Figure 5.6.
Top Top 6
6 5 5
4 4
Push 6
3 3
2 2
1 1
Program continues…
def pop(self):
if ([Link]()==1):
print("Underflow: There is no element in the Stack")
else:
print("The element to pop is ",self.S[self
.t
op])
self.t
op -= 1
The pop()function first checks if the stack is empty. If the stack is empty, it
prints an appropriate message; otherwise it prints the element at the top of
the stack and then decrements the top by one.
The initial stack is shown in Figure 5.7.
Top 6
5
4
3
2
1
After the execution of pop(), the topmost element pops-out and leaves the
stack as shown in Figure 5.8.
Top 6 Top
5 5
4 4
3 3
Pop (top)
2 2
1 1
Program continues…
def peek(self):
if([Link]()==1):
print(“Stack is Empty”)
else:
print(“The element at top is ”,self.S[self
.t
op])
The peek()function first checks if the stack is empty. If the stack is empty,
it prints an appropriate message; otherwise it prints the element at the top
of the stack.
The initial stack is shown in Figure 5.9.
Top 5
5
4
3
2
1
Top
5
4
3
2
1
Program continues…
def display(self):
print("Top is at index -> ",
self
.top)
if([Link]()==1):
print("\nStack is Empty")
elif([Link]()==1):
for i in range(self .top,
-1,
-1):
print(i, "->",self.S[i])
print("\nStack is Full")
else:
print("The elements in the Stack is")
for i in range(self .top,
-1,
-1):
print(i, "->",self.S[i])
Program continues…
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Push an element ")
print("2. Pop from stack ")
print("3. Peek the stack")
print("4. Display the stack")
print("5. Exit ")
opt = int(input("Enter a valid menu item ... "))
return opt
Program continues…
if __name__ == "__main__":
size = int(input("Enter the size of the Stack "))
St = Stack(size)
i=1
while (i > 0 and i < 5 ):
i = menu()
if i == 1:
St.push()
[Link]()
elif i == 2:
St.pop()
[Link]()
elif i == 3:
St.peek()
elif i == 4:
[Link]()
else:
print("Exit")
204 Data structures for engineers and scientists using Python
Output
Stack is Full
Stack is Full
Stack is Empty
import queue
def Push(s):
if (not [Link]()):
data = input(("Enter a number to insert into the Stack "))
[Link](data)
else:
print("There is NO SPACE in the Stack")
Program continues…
def Pop(s):
if (not [Link]()):
data=s.get()
print("The Item Deleted is : ",data)
else:
print("There is NO DATA in the Stack")
Program continues…
def Display(s):
if([Link]()):
print("The Elements in the Stack are :")
for i in [Link]:
print(i)
print("\nThe Stack is Full")
elif([Link]()):
print("\nThe Stack is EMPTY")
else:
print("The Elements in the Stack are :")
for i in [Link]:
print(i)
Program continues…
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Push into Stack ")
print("2. Pop from Stack ")
S tacks 207
Program continues…
if __name__ == "__main__":
size = int(input("Enter the size of the Stack "))
St = [Link](size)
i=1
while (i > 0 and i < 4 ):
i = menu()
if (i == 1):
Push(St)
Display(St)
elif (i == 2):
Pop(St)
Display(St)
elif (i == 3):
Display(St)
else:
print("Exit")
Output
5.5 APPLICATIONS OF STACK
Stacks have various applications and are widely used in programming and
data structures. In this section, we will discuss delimiter matching, infix–
postfix conversion and evaluation of the postfix expression as examples of
stacks.
5.5.1 Delimiter matching
Generally, a stack is very useful in situations when data have to be stored
and retrieved in the reverse order. Let us consider the simple case where the
delimiters in an arithmetic expression are ‘(‘, ’)’, ’[‘, ‘]’, ‘{‘, ‘}’. An arithmetic
expression is said to be properly formed if the left delimiters and the cor-
responding right delimiters match. A Python program compiles correctly
if and only if they match. Some examples where the delimiters match are
a = b + (c – d) + (e – f)
a = (b + c) – (d + e))
p[10] = h[(a + b] – (c + d)
a[5]+(b-{c*(d-e)+(f-g)})
See Table 5.4. The stack is empty and there is no more input to be read.
Thus, the parentheses in the arithmetic expression match.
A simple program to illustrate use of stack for parentheses matching
is given next. The program takes a string of parentheses (an arithmetic
expression devoid of operands and operators) and checks for matching
parentheses.
Python program 6
def isEmpty(top):
if (top <= -1):
return 1
else:
return 0
def push(Stack,i,top):
top += 1
[Link](i)
return S,top
def pop(S,top):
del S[top]
return S,top-1
def peek(S,top):
if (isEmpty(top) == 1):
print("Stack is Empty: Mismatch")
return 0
S tacks 211
else:
return S[top]
if __name__ == "__main__":
Expr=input("Enter an Expression ")
S=[]
top = -1
for i in range(len(Expr)):
if (Expr[i] == '('):
S,top = push(S,Expr[i],top)
elif(Expr[i] == '['):
S,top = push(S,Expr[i],top)
elif(Expr[i] == '{'):
S,top = push(S,Expr[i],top)
212 Data structures for engineers and scientists using Python
elif(Expr[i] == ')'):
ele= peek(S,top)
if (ele == '(' and top != -1):
S,top = pop(S,top)
else:
break
else:
continue
Output 1
Output 2
5.5.2 Infix–postfix conversion
An arithmetic expression can be expressed in three ways:
Postfix expressions are preferred by computers because they are free from
operator precedence. However, we use infix expressions when writing a
program, and for the ease of evaluations, these are converted to postfix
expression by the computer.
A commonly agreed precedence of operators is in Table 5.5.
The higher the priority, the higher is the precedence. The operators may
be different in different languages. Notice that all relational operators have
the same precedence.
When we have an expression where the adjacent operators have the same
priority, we have to decide which one to evaluate first. If they are exponen-
tiation operators, the evaluation takes place from right to left. For all other
equal priority operators, the evaluation takes place from left to right. After
the delimiter matching is done, for easy evaluation of an arithmetic expres-
sion, the computer converts the infix expression to a postfix expression
using a stack.
Example
Convert the infix expression A + B * C to a postfix expression (Table 5.6a).
The next token is ‘*’. We have to decide if this is to be pushed onto the
stack or the operator ‘+’ has to be popped and written to the output. Since
‘*’ has higher precedence over ‘+’ and has to be evaluated first, we push ‘*’
onto the stack (Table 5.6b).
214 Data structures for engineers and scientists using Python
Since the input expression is exhausted, we output all the remaining ele-
ments on the stack and this gives the postfix expression as:
ABC*+
Example
Convert the infix expression A/(B+C)*D to a postfix expression.
As in the previous example, we initialize a stack and read the tokens of
the input infix expression from left to right (Table 5.7a).
When we read the next token, which is the right parenthesis ‘)’, we
unstack down up to the left parenthesis and delete the left parenthesis from
the stack (Table 5.7b).
ABC+*D*
S tacks 215
Python program 7
def isEmpty(top):
if (top <= -1):
return 1
else:
return 0
def push(Stack,i,top):
top += 1
[Link](i)
return S,top
def pop(S,top):
i=S.pop(top)
return S,top-1,i
def peek(S,top):
if (isEmpty(top) == 1):
print("Stack is Empty: Mismatch")
return 0
else:
return S[top]
if __name__ == "__main__":
Expr=input("Enter an Expression ")
S=[]
top = -1
post = []
operator = ['*','+','-','/','%']
result = 0
for i in range(len(Expr)):
if ((Expr[i] == '(' ) or (Expr[i] in operator) ):
S,top = push(S,Expr[i],top)
elif(Expr[i] == ')'):
ele= peek(S,top)
while (ele != '(' and top != -1):
S,top,item = pop(S,top)
post.append(item)
ele= peek(S,top)
if (ele == '('):
S,top,item = pop(S,top)
result = 1
else:
result = 0
break
216 Data structures for engineers and scientists using Python
elif (Expr[i] =='{'or Expr[i] =='}'or Expr[i] =='['
or Expr[i] ==']'):
result = 0
break
else:
post.append(Expr[i])
while(top != -1):
S,top,item = pop(S,top)
if (item == '('):
result=0
break
post.append(item)
result = 1
if (result == 1):
print("The postfix expression is : ",end ='')
for i in post:
print(i,end=' ')
else:
print("Parenthesis NOT Matched..")
Output
1. Initialize a stack
2. Read the next-token from the post-fix expression
3. If it is an operand push it on to the stack
4. If it is an operator pop required number of operands from the stack
5. Apply the operator to the operands and push the result on to the stack
6. If it is “#” indicating end of the stack
7. Pop the result
8. Else go to step 2
9. End.
Example
Evaluate the postfix expression 1 3 5 *+
S tacks 217
See Table 5.8. Now we have reached the end of expression, so pop the
contents of the stack. And the value of the postfix expression is 16.
A simple program in Python is given next to achieve this.
Python program 8
def isEmpty(top):
if (top <= -1):
return 1
else:
return 0
def push(S,i,top):
top += 1
[Link](i)
return S,top
def pop(S,top):
i = [Link](top)
return S,top-1,i
Python program 9
def calculate(op1,op2,i):
if i is '*':
return float(op1)*float(op2)
elif i is '/':
return float(op1)/float(op2)
elif i is '+':
return float(op1)+float(op2)
elif i is '-':
return float(op1)-float(op2)
else:
return float(op1)%float(op2)
218 Data structures for engineers and scientists using Python
Program continues…
if __name__ == "__main__":
Expr=input("Enter an Expression ")
S=[]
top = -1
operator = ['*','+','-','/','%']
for i in range(len(Expr)):
result = 0
if (Expr[i] in operator):
S,top,item = pop(S,top)
S,top,item1 = pop(S,top)
result= str(calculate(item1,item,Expr[i]))
S,top=push(S,result,top)
elif(Expr[i] in '0123456789'):
S,top=push(S,Expr[i],top)
else:
pass
S,top,item = pop(S,top)
print("The result of postfix expression ",Expr, "
is ", item)
Output
5.5.4 Recursion
Let us first understand what happens when a function is called. If the func-
tion has formal parameters, they are initialized with the actual parameters
S tacks 219
passed to the function. In addition, the system has to know where to resume
the execution of the program after the completion of the function call. In
other words, the system has to remember where the function has been called
from. This could be done by storing the return address in main memory,
set aside to store return addresses. However, we do not know, in advance,
how much space might be needed. Moreover, more information might be
needed to be stored, besides the return address. Therefore, dynamic allo-
cation using a run-time stack might be a better solution. For example, the
local variables need to be stored. If a function f has a local variable x and it
calls a function g that has a local variable also named x, the system must be
able to distinguish them. Thus the state of each function including main()
is characterized by the parameters passed to the function, its local variables
and the return address from where we start further execution of the calling
function. The data record that contains all this information is called the
activation record and is stored on a run-time stack. This activation record
exists as long as the corresponding function is executing. The activation
record of a called function disappears before the activation record of the
calling function disappears. Thus, the activation record of the main() func-
tion outlives all other activation records.
The activation record of any function contains the following information:
The activation record of the executing function is at the top of the stack. For
example, if the main function calls f1(), f1() calls f2() and f2() calls f5(), the
run-time stack, when f3() is being executed is as in Figure 5.11.
SP
Activation Record of f3()
Now, if we call a function that has the same name as the calling function,
we call it recursion. To put it more precisely, it is an instantiation of a func-
tion calling another instantiation of the same function. These invocations
220 Data structures for engineers and scientists using Python
Python program 10
def rev():
i=0
ch=input()
if (ch != 'z'):
rev()
print(ch)
if __name__ == "__main__":
rev()
Output
A
b
c
z
z
c
b
a
SP
‘A’
To
main()
The second character is read and after checking that it is not ‘z’, rev()
is called again which reads character ‘b’. Now the activation record for the
second call is pushed onto the run-time stack (Figure 5.12b).
S tacks 221
SP
‘b’
‘A’
To
main()
In a similar manner, all the elements are pushed onto the stack and finally
when ‘z’ is read the run-time stack is as shown in Figure 5.12c.
SP
‘z’
‘c’
‘b’
‘A’
To
main()
When the system finds the end of line character, no other statement is
executed. It then retrieves the return address from the activation record
and discards this record by decrementing the stack pointer by the proper
number of bytes.
Since the activation record of the fourth call to rev() is active, the value
of ch, which is ‘z’, is output as the first character and the activation record
for the fourth call is discarded by decrementing the stack pointer. ‘c’ is
assigned to ch and then printed. Finally the activation record of the first call
is reached and A is printed and what is seen on the screen is “zcbA”.
Let us consider a non-recursive version of reversing a string:
Python program 11
if __name__ == "__main__":
Expr=input("Enter an Expression ")
S=[]
top = -1
i=0
while(i < len(Expr)):
S,top = push(S,Expr[i],top)
i+=1
222 Data structures for engineers and scientists using Python
i=0
print("The Reverse of the String is :",end='')
while(i < len(Expr)):
S,top,item = pop(S,top)
print(item,end='')
i+=1
Output
True–false questions
Fill-in-the-blank questions
Multiple-choice questions
2. A single array A[1.. Max] is used to implement two stacks. The two
stacks grow from opposite ends of the array. Variables top1 and top2
(top1 > top2 ) point to the location of the topmost element in each
S tacks 223
stack. If the space is to be efficiently used, the condition for stack full
is
a. ( top1 = Max/2) and (top = c. ( top1 = Max/2) and (top =
max/2+1) max)
b. top1 + top2 = Max d. top1 = top2 -1
3. A linear set of elements in which deletion can be done from one end
(front) and insertion can take place only at the other end is known as a
a. Queue c. Tree
b. Stack d. Branch
4. The end at which a new element gets added to a queue is called the
a. Front c. Top
b. Rear d. Bottom
def f(n):
i=1
if (n >= 5):
return n
else:
n = n + i
i += 1
return(f(n))
12. If the elements A, B, C and D are placed in a stack and are deleted one
at a time, in what order will they be removed?
a. ABCD c. DCAB
b. DCBA d. ADBC
15. When several jobs arrive at the printer, the jobs join a
a. Queue c. Stack
b. Dequeue d. None of the above
17. Assume that the operators +, -, × are left associative and ^ is right
associative. The order of precedence (from highest to lowest) is ^, x ,
+, -. The postfix expression corresponding to the infix expression a +
b × c - d ^ e ^ f is
a. - + a × bc ^ ^ def c. abc × + de ^ f ^ -
b. ab + c × d - e ^ f ^ d. abc × + def ^ ^ -
Descriptive questions
1. True
2. False
3. True
4. True
5. True
1. pop()
2. push()
3. -1
4. Same
5. False
1. b 2. d 3. a 4. b 5. a
6. a 7. a 8. d 9. c 10. b
11. d 12. b 13. b 14. d 15. a
16. c 17. d 18. c 19. a 20. d
Chapter 6
Queues
LEARNING OBJECTIVES
Linear data structures are divided into arrays, stacks and queues. In this
chapter we will focus on the queue as a linear data structure. Queue data
structures can be implemented using list, dictionary, class and the queue
module. Simple examples of a queue are waiting for a bus in a bus stand and
jobs that are taken for printing by a printer.
6.1 QUEUE
end from where the elements are removed is called the front. A queue fol-
lows the FIFO (first in, first out) discipline (Figure 6.1).
Rear = 2
Front 10 15 20 Rear
-1 0 1 2 3 4 5
Front = 0
6.2 QUEUE OPERATIONS
Rear = -1
Front = 0
10
Rear = 0
Front = 0
Rear = 0
Front 10 Rear
-1 0 1 2 3 4 5
Front = 0
15
Rear = 1
Front = 0
Rear = 1
Front 10 15 Rear
-1 0 1 2 3 4 5
Front = 0
Rear = 1
Front 10 15 Rear
-1 0 1 2 3 4 5
Front = 0
Rear = 1
Front = 0
Rear = 1
Front 15 Rear
-1 0 1 2 3 4 5
Front = 1
Rear = 1
Front = 1
Rear = 1
Front Rear
-1 0 1 2 3 4 5
Front = 2
Since elements are entered at one end and removed from the other end, both
ends are to be monitored.
Consider the ordered list L = [a1, a2 , a3, …, an]. If we assume L represents
a queue, a1 is in the front end, an is at the rear and ai is behind a(i–1).
Queues are very important data structures in time-sharing and distrib-
uted network systems where the users try to access the system resources
simultaneously.
6.3 QUEUE (ADT)
The following are the operations and the set of axioms on the data struc-
ture queue.
232 Data structures for engineers and scientists using Python
6.4 IMPLEMENTATION
we can restrict the size of the list, hence the size of the queue can be made
fixed.
Now let us implement a queue using a list without a restriction of upper
limit or the size of the queue.
Python program 1
The create()method creates an empty queue with the front pointing to 0 and
rear pointing to -1. Here Q = [] indicates an empty list.
Program continues…
The isEmpty() method checks if the queue is empty. It checks if the front is
greater than the rear or the rear is at -1. It returns 1 to indicate the queue is
empty; otherwise it returns 0 to indicate the queue is not empty (at least one
element is there in the queue).
Program continues…
The enqueue() method takes two parameters: the queue and the rear. Every
time an element is inserted into the queue, the rear is incremented by one
and the element is appended to the list. As a list is a heterogeneous data
structure, we force the user to enter an integer only.
234 Data structures for engineers and scientists using Python
Program continues…
The dequque() method takes three parameters: the queue, the front and the
rear. Every time an element is deleted from the queue, it checks if the queue
is empty. If the queue is empty, it shows an appropriate message, and if the
queue is not empty, then the front of the queue is printed and the front is
decremented by one. At last, the front and the rear of the queue is returned.
Program continues…
The display() method takes three parameters: the queue, the front and the
rear. This function prints the elements in the queue (the element inserted
first is printed first).
Program continues…
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Insert to Queue ")
print("2. Delete from Queue ")
print("3. Display the Queue")
print("4. Exit ")
opt = int(input("Enter a valid menu item ... "))
return opt
Q ueues 235
The menu() method shows a menu to perform the operations defined for a
queue. It returns a choice of operation to perform.
Program continues…
if __name__ == "__main__":
Q,rear,front=create()
i=1
while (i > 0 and i <=3 ):
i = menu()
if i == 1:
Q,rear = enqueue(Q,rear)
display(Q,front,rear)
elif i == 2:
Q,front,rear = dequque(Q,front,rear)
if (front > rear):
front = 0
rear = -1
if (type(front) != str):
display(Q,front,rear)
elif i == 3:
display(Q,front,rear)
else:
print("Exit")
Output
Queue is Empty
Python program 2
The isFull() method checks if the queue is full. It checks if the (rear – front
+ 1) is greater than the (size -1). It returns 1 to indicate the queue is full;
otherwise returns 0 to indicate the queue is not full.
Program continues…
The enqueue()method takes four parameters: the queue, the front, the rear
and the size. Every time an element is inserted into the queue, it checks if the
queue is full. If the queue is full, it shows an appropriate message; otherwise
the rear is incremented by one and the element is appended to the list.
238 Data structures for engineers and scientists using Python
Program continues…
else:
print("The elements in the Queue is")
for i in range(front,rear+1):
print(i, "->",Q[i])
The display() method takes three parameters: the queue, the front and the
rear. This function prints the elements in the queue (the element inserted
first is printed first) if the queue is neither full nor empty.
Output
Queue is Full
Queue is Full
Queue is Full
4. Exit
Enter a valid menu item ... 2
The element to delete is 10
Front is at index -> 2
Rear is at index -> 2
2 -> 30
Queue is Full
~~~ MENU ~~~
1. Insert to Queue
2. Delete from Queue
3. Display the Queue
4. Exit
Enter a valid menu item ... 2
The element to delete is 10
Front is at index -> 0
Rear is at index -> -1
Queue is Empty
Python program 3
Program continues…
Just like the previous program, the isFull() function checks if the queue
is full. When the rear is greater than or equal to (size –1), it returns 1
indicating the queue is full; otherwise it returns 0 indicating the queue is
not full.
Program continues…
Program continues…
else:
no = int(input(("Enter a number to insert into the Queue ")))
rear += 1
Q[rear] = no
return Q,rear
Program continues…
else:
print("The element to delete is ",Q[front])
del Q[front]
front += 1
return Q,front
Program continues…
elif(isFull(front,rear,size) == 1):
print("The elements in the Queue is")
for i in list([Link]()):
print(i, "->",Q[i])
print("\nQueue is Full")
else:
print("The elements in the Queue is")
for i in list([Link]()):
print(i, "->",Q[i])
The display() function shows the elements in the queue. If isEmpty() is true,
it prints “Queue is empty”. If isFull() is true, it prints all the elements of the
queue; otherwise, it prints the elements in the queue.
Program continues…
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Insert into Queue ")
print("2. Delete from Queue ")
print("3. Display the Queue")
Q ueues 243
Program continues…
if __name__ == "__main__":
size = int(input("Enter the size of the Queue "))
Q,front,rear=create()
i=1
while (i > 0 and i < 4 ):
i = menu()
if i == 1:
Q,rear = enqueue(Q,front,rear,size)
display(Q,rear,size)
elif i == 2:
Q,front = dequeue(Q,front,rear)
if (front > rear):
front = 0
rear = -1
display(Q,rear,size)
elif i == 3:
display(Q,rear,size)
else:
print("Exit")
Python program 4
# Creating an Queue
class Queue:
def __init__(self,size):
[Link] = size
self.front=0
self .re
ar = -1
self.Q = list()
print("\nEmpty Queue Created")
The initializer takes the object and the size as the parameter to create an
empty queue. It assigns front = 0 and rear = –1. It creates:
244 Data structures for engineers and scientists using Python
Program continues…
def isFull(self):
#if (self.rear-self.front >= [Link]-1):
if ( self. rear >= [Link]-1):
return 1
else:
return 0
The method isFull() checks if the queue is full. It returns 1 if the queue is
full and 0 otherwise.
Program continues…
def isEmpty(self):
if (self.fro
nt self
.re
ar or self
.re
ar == -1):
return 1
else:
return 0
The method isEmpty() checks if the queue is empty. It returns 1 if the queue
is empty and 0 otherwise.
Program continues…
def enqueue(self):
if ([Link]() == 1):
print("Overflow: No more place for the Queue")
else:
no = int(input(("Enter a number to insert into the
Queue ")))
self .rear += 1
self.Q.append(no)
The enqueue() method enters an element into the queue. If the queue is not
full, increment the rear by one and append the new element to the queue.
Program continues…
def dequeue(self):
if ([Link]()==1):
print("Underflow: There is no element in the Queue")
else:
print("The element to Delete is ",self.Q[self
.fro
nt])
self.fro
nt += 1
The dequeue() method deletes an element from the queue. If the queue is not
empty, increment the front by one.
Q ueues 245
Program continues…
def display(self):
print("Front is at index -> ",
self
.front)
print("Rear is at index -> ",
self
.rear)
if([Link]()==1):
print("\nQueue is Empty")
elif([Link]()==1):
print("The elements in the Queue are")
for i in range(self .front,
self
.rear
+1):
print(i, "->",self.Q[i])
print("\nQueue is Full")
else:
print("The elements in the Queue is")
for i in range(self .front,
self
.rear+1):
print(i, "->",self.Q[i])
Program continues…
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Insert into Queue ")
print("2. Delete from Queue ")
print("3. Display the Queue")
print("4. Exit ")
opt = int(input("Enter a valid menu item ... "))
return opt
Program continues…
if __name__ == "__main__":
size = int(input("Enter the size of the Queue "))
Qu = Queue(size)
i=1
while (i > 0 and i < 4 ):
i = menu()
if i == 1:
[Link]()
[Link]()
elif i == 2:
[Link]()
if (Qu.front > Qu.rear):
Qu.front = 0
Qu.rear = -1
print()
246 Data structures for engineers and scientists using Python
[Link]()
elif i == 3:
[Link]()
else:
print("Exit")
Python program 5
The enqueue() function first checks if the queue is full. This is done by
the built-in method [Link](). Once this queue is full, insertion cannot be
performed until all queue items have been deleted. If the queue is not full,
insertion can be done by the [Link]() method.
Program continues…
def dequeue(q):
if (not [Link]()):
data=Q.get()
print("The Item Deleted is : ",data)
else:
print("There is NO DATA in the queue")
The dequeue() function first checks if the queue is empty. This is done by
the built-in method [Link](). Deletion cannot be performed until there is
at least one element in the queue. If the queue is not empty, deletion can be
done by the [Link]() method.
Program continues…
def Display(q):
if([Link]()):
print("The Elements in the Queue are : [ ",end="")
for i in [Link]:
print(i," ",end="")
Q ueues 247
print("]")
print("The Queue is Full")
elif([Link]()):
print("The Queue is EMPTY")
else:
print("The Elements in the Queue are : [ ",end="")
for i in [Link]:
print(i," ",end="")
print("]")
The Display() function shows all the elements in the queue. All the elements
can be fetched from [Link].
Program continues…
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Insert to Queue ")
print("2. Delete from Queue ")
print("3. Display the Queue")
print("4. Exit ")
opt = int(input("Enter a valid menu item ... "))
return opt
Program continues…
if __name__ == "__main__":
size = int(input("Enter the size of the Queue "))
Q = Queue(size)
i=1
while (i > 0 and i < 4 ):
i = menu()
if (i == 1):
enqueue(Q)
Display(Q)
elif (i == 2):
dequeue(Q)
Display(Q)
elif (i == 3):
Display(Q)
else:
print("Exit")
In queue, size is an integer that specifies the maximum number of items that
can be added to the queue. Once this size is achieved [Link](), insertion can-
not be performed until all queue items have been deleted. The queue size is
unlimited if it is less than or equal to zero.
248 Data structures for engineers and scientists using Python
Output
We can observe that except for the implementation of queue using the queue
module, all the previous examples have one thing in common. Even though
the queue had empty spaces, still we are not allowed to insert data into the
queue as the rear of the queue is pointing to the last element (Figure 6.8a).
Rear = -1
Front=0
Rear=-1 Front Rear
Max=4
-1 0 1 2 3
Front = 0
Rear = 0
Front=0
Rear=-1 Front 10 Rear
Max=4
-1 0 1 2 3
Front = 0
Rear = 1
Front=0
Rear=1 Front 10 20 Rear
Max=4
-1 0 1 2 3
Front = 0
Rear = 2
Front=0
Rear=2 Front 10 20 30 Rear
Max=4
-1 0 1 2 3
Front = 0
Rear = 3
Front=0
Rear=3 Front 10 20 30 40 Rear
Max=4
-1 0 1 2 3
Front = 0
Now the queue is full. Delete an element from the queue (Figure 6.8f).
Rear = 3
Front=1
Rear=3 Front 20 30 40 Rear
Max=4
-1 0 1 2 3
Front = 0
1. After each deletion, shift all the data elements to the left so that the
actual front is always –1, update rear to rear –1 so that rear = max – 1
is not always true. Obviously this is not a feasible solution since this
involves a lot of frequent data movement and is time-consuming.
2. The other way is to choose alternate representation: either circular
storage of data using the same array representation or use linked list
representation.
6.5 CIRCULAR QUEUE
The data structure circular queue uses the same array representation but
wraps around when a queue-full condition occurs using modular arithme-
tic. In other words, when the rear becomes equal to size, we reset rear to
rear = rear+1 % size.
Using this representation, let us define the class MyCircularQueue.
Python program 6
class MyCircularQueue():
def __init__(self, S):
self .si
ze = S
self .que
ue = [None] * S
self .fro
nt = self .re
ar = -1
Program continues…
elif (self
.fro
nt == -1):
self.fro
nt = 0
self.re
ar = 0
self.que
ue[self
.re
ar] = data
else:
self.re
ar = (self.re
ar + 1) % self
.si
ze
self.que
ue[self
.re
ar] = data
252 Data structures for engineers and scientists using Python
The enqueue() method adds an element at the rear. When the first element
is added, rear and front are assigned to 0. Every time an element is added to
the circular queue, it calculates the rear by (self.rear + 1) % self.size
and adds the element at the rear.
Let us assume the circular queue (Figure 6.9a).
Rear = 2
Front=0
Rear=3 Front 10 20 30
Max=4
-1 0 1 2 3
Front = 0
Rear = 3
Front=0
Rear=3 10 20 30 40
Max=4
-1 0 1 2 3
Front = 0
Rear = 3
Front=1
Rear=3 20 30 40
Max=4
-1 0 1 2 3
Front = 1
Now add one element 50 to the circular queue. Find the index by calcu-
lating (rear + 1) % size, i.e., (3+1) % 4 = 0. Add the new element 50 at the
0th index (Figure 6.9d).
Q ueues 253
Rear = 0
Front=1
Rear=0 50 20 30 40
Max=4
-1 0 1 2 3
Front = 0
Program continues…
elif (self
.fro
nt == self .re
ar):
self.que
ue[self
.fro
nt]= None
self.fro
nt = -1
self.re
ar = -1
else:
self.que
ue[self
.fro
nt]= None
self.fro
nt = (self.front + 1) % self
.si
ze
The dequeue() method deletes an element from the circular queue that is
at the front. When the front and rear are pointing to the same location,
after deletion the circular queue becomes empty. So initialize the front
and rear to –1. If not, the front is assigned to None and front is moved to
self.front = (self.front + 1) % self.size.
Let us assume the circular queue (Figure 6.10a).
Rear = 1
Front=2
Rear=1 50 20 30 40
Max=4
-1 0 1 2 3
Front = 2
Now delete the element at the front of the circular queue. After dele-
tion, the front points to the index (front+1) % size, i.e., (2+1) % 4 = 3
(Figure 6.10b).
254 Data structures for engineers and scientists using Python
Rear = 1
Front=3
Rear=1 50 20 40
Max=4
-1 0 1 2 3
Front = 3
Now delete the element at the front of the circular queue. After dele-
tion, the front points to the index (front+1) % size, i.e., (3+1) % 4 = 0
(Figure 6.10c).
Rear = 1
Front=0
Rear=1 50 20
Max=4
-1 0 1 2 3
Front = 0
Program continues…
def Display(self):
print("Front is at index -> ",
self
.front)
print("Rear is at index -> ",
self
.rear)
if(self.fro
nt == -1):
print("No element in the circular queue")
print()
elif(((self
.re
ar + 1) % self .si
ze == self
.fro
nt)):
print("Queue is Full")
for i in range(0, self .si
ze):
print(self .que
ue[i], end=" ")
print()
else:
for i in range(0, self.si
ze):
print(self
.que
ue[i], end=" ")
print()
The Display() method shows the elements in the circular queue. When front
points to –1, it prints “No element in the circular queue”, and when (rear
+ 1) % size = front, it shows the elements in the circular queue and prints
Q ueues 255
“Queue is Full”. In all other cases, it shows all the elements in the circular
queue.
Program continues…
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Insert to Circular Queue ")
print("2. Delete from Circular Queue ")
print("3. Display the Circular Queue")
print("4. Exit ")
opt = int(input("Enter a valid menu item ... "))
return opt
Program continues…
if __name__ == "__main__":
Size = int(input("Enter the size of the Circular Queue "))
CQ = MyCircularQueue(Size)
i=1
while (i > 0 and i < 4 ):
i = menu()
if (i == 1):
[Link]()
[Link]()
elif (i == 2):
[Link]()
[Link]()
elif (i == 3):
[Link]()
else:
print("Exit")
Output
6.6 DOUBLE-ENDED QUEUE
Insert Insert
6.6.1 ADT of dequeue
Operations: See Table 6.4.
Delete
Delete Front Rear
Insert Insert
Delete
Front Rear
Python program 7
import collections
def Insert(q):
data = int(input(("Enter a number to insert into the
Queue ")))
side= input("Enter the side (F-> at front and R -> at
rear) : ")
if (side == 'F' or side == 'f'):
[Link](data)
else:
[Link](data)
In Python, collections are simply container data types, such as lists, sets,
tuples and dictionaries.
Python’s collections module implements specialized data structures as
an alternative to the language's built-in container data types. Appends and
pops from either end of a list are supported by a deque object. It uses less
memory than a regular list object. When an item is removed from a regular
list object, all items to the right are relocated one index to the left. As a
result, it is extremely slow.
The Insert() function adds elements at both ends. There are two special-
ized methods, appendleft() and append(), available with the deque(). The
function appendleft() adds an element at the front, whereas append() adds
the element at the rear.
Program continues…
def Delete(q):
if (len(q) != 0):
side= input("Enter from where to Delete (F-> at front and
R -> at rear) : ")
if (side == 'F' or side == 'f'):
item = [Link]()
print("The element deleted is : ", item)
260 Data structures for engineers and scientists using Python
else:
item =q.pop()
print("The element deleted is : ", item)
else:
print("There is NO DATA in the queue")
The Delete() function deletes elements from both ends. There are two spe-
cialized methods popleft() and pop(), available with the deque(). The func-
tion popleft() deletes the element at the front, whereas pop() deletes the
element from the rear.
Program continues…
def Display(q):
if(len(q) == 0):
print("The Queue is EMPTY")
else:
print("The Elements in the Queue are : [ ",end="")
for i in q:
print(i," ",end="")
print("]")
Program continues…
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Insert to Queue ")
print("2. Delete from Queue ")
print("3. Display the Queue")
print("4. Exit ")
opt = int(input("Enter a valid menu item ... "))
return opt
Program continues…
if __name__ == "__main__":
Q = collections.deque()
i=1
while (i > 0 and i < 4 ):
i = menu()
if (i == 1):
Insert(Q)
Display(Q)
elif (i == 2):
Delete(Q)
Display(Q)
Q ueues 261
elif (i == 3):
Display(Q)
else:
print("Exit")
Output
6.7 PRIORITY QUEUE
The use of a queue data structure ensures that items are processed in the
order in which they are received.
Consider the setting of a hospital. In most cases, patients are treated in
the order that they arrive. There may be times, however, when the first in,
first out rule cannot be rigidly followed. For example, FIFO cannot be used
if a patient arrives in a life-threatening condition following an accident. He
must be attended immediately on priority basis.
In the world of computer science, an interactive program’s print request
takes precedence over a batch-processing program’s print request. There are
numerous instances when a work or a process is given a priority. Customers
and processes with higher importance are pushed to the front of the queue
using a particular data structure called a priority queue. A priority queue
can be implemented in two ways. Let’s give each element a priority (integer
value); the smaller the integer, the greater the priority.
1. Maintain a separate queue of all the elements with the same priority.
Let us assume there are jobs with three different priorities. Then there
will be three different queues as shown in Figure 6.14.
Q ueues 263
J1 J2 J3 J4 J5 J6 J7 J8 J9 Priority 1
H1 H2 H3 H4 H5 H6 H7 H8 H9 Priority 2
K1 K2 K3 K4 K5 K6 K7 K8 K9 Priority 3
The jobs with priority 2 will be processed only when all the jobs
of priority 1 are processed and the queue is empty. Jobs with priority
3 will be processed when the queues of priority 1 and 2 are empty.
If higher priority jobs keep on coming, the lower priority jobs get
delayed indefinitely.
2. The second method is to store all jobs as structures together with
their priorities. All the jobs are stored as a queue of elements, with the
highest priority job always in the front. When a new job arrives, it is
inserted at the appropriate position in the queue, based on its priority.
When we store the jobs (elements) in a sorted list, we can easily delete them
because the job with the highest priority is always at the front. However,
putting the job in the right place is difficult since we must first locate it in
the list.
If we keep the elements as an unsorted list, insertion is easy, since it can
be put at the end of the list. However, deletion is difficult, since from the
unordered list we have to pick up the job with highest priority.
Python program 8
Program continues…
def isFull(self):
if (self ar >= [Link]-1):
.re
return 1
else:
return 0
Program continues…
def isEmpty(self):
if (self nt >
.fro self
.re
ar or self
.re
ar == -1):
return 1
else:
return 0
Program continues…
def enqueue(self):
if ([Link]() == 1):
print("Overflow: No more place for the Queue")
else:
no = int(input(("Enter a number to insert into the
Queue ")))
p = int(input(("Enter priority of data (0 -> Low, 1->
High ) ")))
while (p not in [0,1]):
p = int(input(("Enter priority of data (0 -> Low, 1->
High ) ")))
elif (p ==1):
j=0
while ([Link][j][0] != 0 and len([Link]) > j ):
j+=1
temp=(p,no)
self.PQ.insert(j,temp)
else:
temp=(p,no)
self.PQ.append(temp)
self
.re
ar +=1
Q ueues 265
The enqueue() method adds an element to the priority queue. Along with
the data to be inserted, we need to insert the priority with value 0 for low
priority and 1 for high priority. This forms a tuple. Inserting the tuple into
the priority queue has three cases.
Case 1: When there is no data in the priority queue, the tuple of the key and
value pair is appended to the priority queue.
Case 2: When the priority queue contains some data, the tuple with priority
0 is appended to the queue.
Case 3: When a tuple with priority 1 is inserted, it is inserted before all the
tuples having priority 0 but after any other tuple with priority 1.
Program continues…
def dequeue(self):
if ([Link]()==1):
print("Underflow: There is no element in the Queue")
else:
print("The element to Delete is ",[Link][self
.fro
nt])
self.fro
nt += 1
The dequeue() method deletes an element that is at the front of the queue. It
simply increments the front by one.
Program continues…
def display(self):
print("Front is at index -> ",
self
.front)
print("Rear is at index -> ",
self
.rear)
if([Link]()==1):
print("\nQueue is Empty")
elif([Link]()==1):
print("The elements in the Queue are")
for i in range(self .front,
self
.rear
+1):
print(i, "->",[Link][i])
print("\nQueue is Full")
else:
print("The elements in the Queue is")
for i in range(self .front,
self
.rear+1):
print(i, "->",[Link][i])
266 Data structures for engineers and scientists using Python
Program continues…
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Insert into Queue ")
print("2. Delete from Queue ")
print("3. Display the Queue")
print("4. Exit ")
opt = int(input("Enter a valid menu item ... "))
return opt
Program continues…
if __name__ == "__main__":
size = int(input("Enter the size of the Queue "))
Qu = Queue(size)
i=1
while (i > 0 and i < 4 ):
i = menu()
if i == 1:
[Link]()
[Link]()
elif i == 2:
[Link]()
if (Qu.front > Qu.rear):
Qu.front = 0
Qu.rear = -1
print()
[Link]()
elif i == 3:
[Link]()
else:
print("Exit")
Output
Queue is Full
Queue is Full
268 Data structures for engineers and scientists using Python
Queue is Full
Queue is Empty
Python program 9
def enqueue(q):
data = input(("Enter a number to insert into the Queue "))
p = int(input(("Enter priority of data (0 -> Highest
Priority ) ")))
temp = (p,data)
[Link](temp)
Q ueues 269
The queue module inserts a tuple (priority, data) by the put() method. The
tuple having priority 0 has the highest priority.
Program continues…
def dequeue(q):
if (not [Link]()):
next_item = [Link]()
print("The Item Deleted is : ", next_item)
else:
print("Priority queue is Empty")
The queue module deletes the tuple (priority, data) with high priority data
that is at the front of the queue by the get() method.
Program continues…
def Display(q):
print([Link])
Program continues…
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Insert to Queue ")
print("2. Delete from Queue ")
print("3. Display the Queue")
print("4. Exit ")
opt = int(input("Enter a valid menu item ... "))
return opt
Program continues…
if __name__ == "__main__":
PQ = PriorityQueue()
i=1
while (i > 0 and i < 4 ):
i = menu()
if (i == 1):
enqueue(PQ)
Display(PQ)
elif (i == 2):
dequeue(PQ)
Display(PQ)
elif (i == 3):
Display(PQ)
else:
print("Exit")
270 Data structures for engineers and scientists using Python
Output
4. Exit
Enter a valid menu item ... 2
The Item Deleted is : (1, '10')
[(1, '30')]
6.7.3 Implementation of priority
queue using heapq module
A priority queue is also implemented in Python by the heapq module. The
tuple having priority 0 has the highest priority.
Python program 10
import heapq
def menu():
print("\n~~~ MENU ~~~ ")
print("1. Insert to Queue ")
print("2. Delete from Queue ")
print("3. Display the Queue")
print("4. Exit ")
opt = int(input("Enter a valid menu item ... "))
return opt
Program continues…
if __name__ == "__main__":
PQ = []
i=1
while (i > 0 and i < 4 ):
i = menu()
if (i == 1):
data = input(("Enter a number to insert into the Queue "))
272 Data structures for engineers and scientists using Python
The heapq module has a heappush() method to add a tuple with priority
and data. Every time we insert a tuple, it is appended to the heap. So, after
every insertion we need to apply the heapify() method to arrange the tuples
in descending order of priority. The heappop() method deletes tuples from
the front of the priority queue.
Output
4. Exit
Enter a valid menu item ... 1
Enter a number to insert into the Queue 30
Enter priority of data (0 -> Highest Priority ) 0
[(0, '30'), (2, '10'), (1, '20')]
True–false questions
Fill-in-the-blank questions
Multiple-choice questions
1. A linear list of elements in which deletion can be done from one end
(front) and insertion can take place only at the other end is known as a
a. Queue c. Tree
b. Stack d. Branch
2. The end at which a new element gets added to a queue is called the
a. Front c. Top
b. Rear d. Bottom
6. If the elements A, B, C and D are placed in a queue and are deleted one
at a time, in what order will they be removed?
a. ABCD c. DCAB
b. DCBA d. ADBC
7. When several jobs arrive at the printer, the jobs join the
a. Queue c. Stack
b. Dequeue d. None of the above
13. While implementing propriety queue using the heapq module, thr
highest priority is
a. –1 c. 0
b. 1 d. 2
19. A list of size 10 is used to build a circular queue. The list index begins
with 0 and ends with 9. The front index is 6, and the rear index is 9.
The list index determines where the next element is inserted.
a. 0 c. 9
b. 7 d. 10
Q ueues 277
Descriptive questions
1. False
2. True
3. False
4. True
5. True
1. double-ended
2. enqueue
3. isFull
4. deletion
5. circular
1. a 2. b 3. d 4. d 5. a
6. a 7. a 8. c 9. a 10. a
11. d 12. d 13. c 14. b 15. d
16. b 17. c 18. b 19. a 20. d
Chapter 7
Trees
LEARNING OBJECTIVES
We’ve learned about linear data structures like arrays, stacks and queues
up to this point. In this chapter will concentrate on trees, which are non-
linear data structures. The list, dictionary, class and queue modules can all
be used to create tree data structures. Simple examples of trees include files
and folders in a directory, decision-based algorithms, domain name system,
representing a family tree and so on.
7.1 TREES
2 3 4
5 6 7
In the non-linear data structure tree, a node can have more than one
successor but not more than one predecessor and in a graph, a node can
have more than one successor and more than one predecessor as shown in
Figure 7.2.
B C
D
E F
Definition: A tree can be defined as a finite set of one or more nodes such
that
7.2 BINARY TREES
A binary tree (BT) is an important type of tree that is often used in com-
puter science and is characterized by the fact that each node can have a left
child only, right child only or both (Figure 7.3). In other words, there is no
node with more than two branches. (A branch is an edge coming out of the
node.)
2 3
4 5 6
Strictly binary tree: A binary tree in which every node has zero or two
children (Figure 7.6).
4 9
2 3 10
6
5 7
11 12
Full binary tree: A binary tree in which all the interior nodes have two
children and all the leaf nodes are at the same level. In a full binary tree,
each node has two children or no child (Figure 7.7).
B B
D E D E
F G H I J K L M
1 + 2 + 22 + 23 + … +2h = 2h+1 – 1
n = 2h+1 – 1
Therefore, 2h+1 = n + 1 or
h = log 2(n+1) – 1.
B C
J K
D E
F G H I
In other words, in a complete binary tree, the leaf nodes are at the same
level or at two consecutive levels. Add children of a node from left to right.
A full binary tree is a complete binary tree but not vice versa.
If the tree is a complete binary tree (not a full binary tree) with n nodes,
then
Assume that the hypothesis is true for level i – 1, i.e., the number of nodes at
level i – 1 is 2i–2 . Each node at level i – 1 can at maximum have two children.
284 Data structures for engineers and scientists using Python
Proof: Let n be the total number of nodes in the binary tree. Then, we have
n = n0 + n1 + n 2 (7.1)
Now, every node except the root node has an edge coming into it. Thus,
n – 1 = E or n = E + 1where E is the total number of edges.
Total number of edges = n1 (nodes with degree 1) + n 2 (edges with degree
2) × 2.
E = n1 + 2n 2which implies
n = 1 + n1 + 2n 2 (7.2)
0 = n0 – 1 – n 2
or
n0 = n 2 + 1
B C
D E F G
Here n 2= 3 and n0 = 4.
Therefore, n0 = n 2 + 1.
Theorem: The number of vertices in a binary tree is one more than the
number of edges.
Proof: Let there be one vertex in the binary tree. Then there are no edges
and the theorem is true.
If there are two vertices, there can only be one edge. Again, the theorem
is true. Let the theorem be true for vertices (v) and edges (e). Therefore, v
= e + 1.
If we add a new vertex to the binary tree, connecting it to a vertex in the
binary tree, then we are also adding a new edge. Thus, v + 1= e + 2, which
proves that the theorem is true for v = v + 1.
7.4 REPRESENTATION
There are various ways of representing a binary tree. The first method to
represent a binary tree can be represented with the help of a list of tuples.
As a tuple, the node is declared as a structure with a data field and two
286 Data structures for engineers and scientists using Python
index fields. The index fields contain indices of the tuple in which the left
and right children are stored. For example, consider the tree in Figure 7.11.
20
25 19
71 39 51
The root is always stored as the first node. The list of tuples for the tree
in Figure 7.11 is shown in a tabular form where each row represents a tuple
(Table 7.3).
left
left child
left
child
child
Data → 20 25 19 71 None 39 51
Index → 0 right1 2 3 4 5 6
child right right
child child
The None cell stores no information. If the tree is heavily skewed to one
side there will be many such NULL cells, causing wastage of a lot of mem-
ory space. However, the list representation as described earlier has some
advantages. For example, given the index of the node in the list, it is easy to
find the index of its parent and vice versa. For example, if a node has index
i, its children will be at 2i and 2i+1 in the list and its parent will be at └ i/2
┘. Since the size of the list can change during the execution of the program,
the tree can grow dynamically. A dynamic data structure is more efficient
to represent a binary tree, since there is always scope for the tree to expand.
Python program 1
# List of nodes
nodes =[100,10,20,5,3,77,None,8]
binary_tree = build(nodes)
print('Binary tree from list :\n', binary_tree)
print('\nList from binary tree :', binary_tree.values)
Output
Like any other data structure, insertion, deletion and traversal are the oper-
ations we perform in a tree.
B C
J K
D E
F G H I
B C
J K
D E
F G H I L
extract the data from the node. Traversals can be specified by the ordering
of three objects: the current node, its left sub-tree and its right sub-tree.
There are several methods to traverse a tree and reach a particular node.
For example, we may traverse the left sub-tree of a node first recursively,
print the data in the node and then traverse the right sub-tree recursively.
Let us call this LDR (Table 7.4).
Similarly, we can define DLR, DRL, LRD and RLD. Let us apply these
traversal methods to the following binary tree (Figure 7.14).
B E
F G
C D
LDR: CBDAFEHG
RDL: GHEFADBC
DLR: ABCDEFGH
RLD: HGFEDCBA
DRL: AEGHFBDC
LRD: CDBFHGEA
290 Data structures for engineers and scientists using Python
Ignoring the mirror images (or assuming that the left sub-tree comes before
the right sub-tree) we call:
1 1 1
1 1 2 2
2 1
2 3 2 3 2 3
Example: Write the pre-order, in-order and post-order traversal for the
given tree in Figure 7.16.
A B
i. Pre-order traversal: + A B
ii. In-order traversal: A + B
iii. Post-order traversal: A B +
Python program 2
class Node:
def __init__(self, key):
self .k
ey = key
self .le
ft = None
self .rig
ht = None
Trees 291
Program continues…
# Inorder traversal
def inorder(root):
if root is not None:
# Traverse left
inorder(root.left)
# Traverse root
print(str(root.key), end=' -> ')
# Traverse right
inorder(root.right)
Program continues…
# preorder traversal
def preorder(root):
if root is not None:
# Traverse root
print(str(root.key) , end=' -> ')
# Traverse left
preorder(root.left)
# Traverse right
preorder(root.right)
Program continues…
# postorder traversal
def postorder(root):
if root is not None:
# Traverse left
postorder(root.left)
# Traverse right
postorder(root.right)
# Traverse root
print(str(root.key) , end=' -> ')
Program continues…
nodes =[10,20,30,40,50]
print('\nnodes in the binary tree :', nodes)
root = Node(nodes[0])
root.left = Node(nodes[1])
root.right = Node(nodes[2])
root.left.left = Node(nodes[3])
root.left.right = Node(nodes[4])
292 Data structures for engineers and scientists using Python
Output
Step 1: In the post-order traversal, identify the last node as the root node.
Step 2: In the in-order traversal, identify the root node somewhere at the
middle.
Step 3: After identifying the root node, the nodes in the left sub-tree and
the right sub-tree of the root are the nodes to the left and right of the
root node in the in-order traversal.
Step 4: Repeat steps 1 through 3 to the node of the left sub-tree and the
right sub-tree.
BCD EFGH
The nodes in the left sub-tree occur in post-order traversal in the order
C, D, B indicating that B is the root of the left sub-tree. The nodes F, E, G,
H occur in the right sub-tree in the order F, H, G, E, which implies that E
is the root of the right sub-tree (Figure 7.17b).
B E
FGH
CD
In-order traversal: C BD A F E H G
Post-order traversal: CDBFHGEA
B E
F G
C D
H
B E
F G
C D
Step 1: In the pre-order traversal, identify the first node as the root node.
Step 2: In the in-order traversal, identify the root node somewhere at the
middle.
Step 3: After identifying the root node, the nodes in the left sub-tree and
the right sub-tree of the root are the nodes to the left and right of the
root node in the in-order traversal.
Step 4: Repeat steps 1 through 3 to the node of the left sub-tree and the
right sub-tree.
In-order traversal 15 20 24 25 33 35 38 40 45
Pre-order traversal 25 20 15 24 35 33 40 38 45
Solution: From the pre-order traversal, we observe that 25 is the root. From
the position of 25 in the in-order traversal, we notice that (15 20 24) and (33
35 38 40 45) constitute the left sub-tree and right sub-tree (Figure 7.18a).
25
15 20 24 33 35 38 40 45
Figure 7.18a Construction of binary tree with given in-order and pre-order traversals
Trees 295
25
20 35
15 24 33 38 40 45
Figure 7.18b Construction of binary tree with given in-order and pre-order traversals
The elements 38, 40, 45 occur in the sequence 40, 38, 45 in the pre-
order traversal. Therefore, 40 is the root, with 38 and 45 as the left and
right children of 40, respectively. We finally have the tree as shown in
Figure 7.18c.
25
20 35
15 24 33 40
38 45
Figure 7.18c Construction of binary tree with given in-order and pre-order traversals
The information stored in the nodes of the binary tree will be useful and
easily accessible if the data is stored in an organized way. The binary search
tree (BST) is such a structure where the data stored in the nodes follow a
pattern (Figure 7.19).
296 Data structures for engineers and scientists using Python
20
10 35
5 17 28 42
3 7 12 19 25 30 37 45
Definition: A binary search tree is a binary tree that is either empty or each
node satisfies the following properties:
1. The data value in the left child of the root is less than the data value
in the root.
2. The data value in the right child of the root is greater than the data
value in the root.
3. The left sub-tree and the right sub-tree of the root are also binary
search trees.
Example: Construct the binary search tree as we read the following charac-
ters “E D U C A T I O N”.
Step 2: Read the next character D. Construct the node with this charac-
ter as data. Compare the data with the data in the root. Since it is less
(dictionary order) and the left child of the root is NULL, add it as the
left child of the root (Figure 7.20b).
D U
Step 4: We compare the next character C with the value in the root, i.e.,
E. Since it is less and the left child of the root is not NULL, we make
the left child as the root and repeat the procedure. Therefore, we add
C as the left child of D (Figure 7.20d).
D U
Step 5: We compare the next character A with the value in the root, i.e.,
E. Since it is less and the left child of the root is not NULL, compare
A with D. Since A is less than D and the left child is not NULL, com-
pare it with C. As A is less than C, we add A as the left child of C
(Figure 7.20e).
D U
Step 6: We compare the next character T with the value in the root, i.e.,
E. Since it is greater and the right child of the root is not NULL, com-
pare T with U. Since U is greater than T, we add T as the left child of
U (Figure 7.20f).
D U
C T
Step 7: We compare the next character I with the value in the root, i.e.,
E. Since it is greater and the right child of the root is not NULL, com-
pare I with U. Since U is greater than I and the left child is not NULL,
compare I with T. Since I is less than T, we add I as the left child of T
(Figure 7.20g).
D U
C T
A
I
Step 7: We compare the next character O with the value in the root,
i.e., E. Since the value is greater and the right child of the root is not
NULL, compare O with U. Since U is greater than O and the left child
is not NULL, compare O with T. Since O is less than T and the left
child is not NULL, compare O with I. Since O’ is greater than I, we
add O as the right child of I (Figure 7.20h).
Trees 299
D U
C T
A
I
Step 8: We compare the next character N with the value in the root,
i.e., E. Since it is greater and the right child of the root is not NULL,
compare N with U. Since U is greater than N and the left child is not
NULL, compare N with T. Since N is less than T and the left child is
not NULL, compare N with I. Since N is greater than I, and the right
child is not NULL, compare N with O. Since N is less than O and the
left child is NULL, we add N as the left child of O.
D U
C T
A
I
Python program 3
if(tree[parent] == None):
tree[parent] = element
return tree
else:
if(element < tree[parent]):
parent = parent*2 + 1
insert(tree,parent, element,level+1)
else:
parent=parent*2+2
insert(tree,parent, element,level+1)
return tree
Program continues
def display(tree):
binary_tree = build(tree)
print('The Binary Search Tree is :\n', binary_tree)
Search
When we want to insert a value in a binary search tree , we have to first
check (or search the tree) if that value is already contained in a node since
duplicate values are not allowed. We first compare the value with the value
contained in the root. If the root contains the value we are searching for,
the search is over. If not, we compare the value we are looking for with the
value in the root. If it is less, we search the left sub-tree since all the key
values in the left sub-tree are less than the key value in the root. If not, we
search the right sub-tree. In either case, we search only one sub-tree as in
the case of a binary search of a sorted array.
If the element we are searching is less than the “element” in the root,
we search the left sub-tree of the root. Else we search the right sub-tree. If
found, the pointer to the node is returned. The null pointer is returned if
not found.
Trees 301
Example
Suppose we are searching for x = 46 in the binary search tree given in
Figure 7.21. The path traced by the algorithm is shown by bold arrows, and
not found is the result of the search.
45
35 50
30 38 48 55
47 49
Null
Program continues
#Searching a tree
def search(tree,loc, data):
if (tree[loc] == data) :
print(data,"Exist in the tree at location ",loc)
Program continues
Deletion
Three cases arise when we try to delete a node from a binary search tree:
Case 1: The leaf node is deleted, i.e., replaced with NULL. We free the
memory that was used by the node we deleted. The node to be deleted
is shaded, i.e., the node containing 3 is to be deleted (Figures 7.22a
and 7.22b).
2
3
7 2
5
4 1
2
2 6 9 1
9
3 5 8 1 1 2
1 5 0
23
7 25
4 12
2 6 9 19
5 8 11 15 20
23
7 25
4 12
2 6 9 19
5 8 11 15 20
23
7 25
4 12
2 5 9 19
8 11 15 20
Case 3: If the node we want to delete has both the children, replace the
node with its in-order successor and delete the successor that will be a
leaf or a node with only a right child (Figures 7.22e and 7.22f.
23
7 25
4 12
2 5 9 19
8 11 15 20
23
8 25
4 12
5 9 19
2
11 15 20
The following algorithm illustrates the process of deletion for all three
cases.
Program continues
Program continues
def menu():
print("\n~~~ M E N U ~~~")
print("1. Insert")
print("2. Search")
print("3. Delete")
print("4. Display")
print("5. Exit")
opt = int(input("Enter a valid menu item ... "))
return opt
Program continues
if __name__ == "__main__":
tree = [None]
level=1
parent = 0
choice = 1
while (choice > 0 and choice < 5 ):
choice = menu()
if (choice == 1):
print("Enter 0 to exit Inserting Data into the BST ")
x = int(input("Enter an element: "))
while (x != 0):
insert(tree,parent,x,level)
#print(tree)
x = int(input("Enter an element: "))
display(tree)
306 Data structures for engineers and scientists using Python
elif(choice == 2):
value = int(input("Enter element to search : "))
search(tree,parent,value)
elif(choice == 3):
value = int(input("Enter element to delete : "))
delNode(tree,parent,value)
display(tree)
elif(choice == 4):
display(tree)
else:
print("Exit")
Output 1
~~~ M E N U ~~~
1. Insert
2. Search
3. Delete
4. Display
5. Exit
Enter a valid menu item ... 1
Enter 0 to exit Inserting Data into the BST
Enter an element: 23
Enter an element: 7
Enter an element: 25
Enter an element: 4
Enter an element: 12
Enter an element: 2
Enter an element: 6
Enter an element: 9
Enter an element: 19
Enter an element: 3
Enter an element: 5
Enter an element: 8
Enter an element: 11
Enter an element: 15
Enter an element: 20
Enter an element: 0
The Binary Search Tree is :
___________________23
/ \
____7_______ 25
/ \
__4__ ___12___
/ \ / \
2 6 9 _19
\ / / \ / \
3 5 8 11 15 20
Trees 307
Output 2
~~~ M E N U ~~~
1. Insert
2. Search
3. Delete
4. Display
5. Exit
Enter a valid menu item ... 2
Enter element to search : 6
6 Exist in the tree at location 8
Output 3
~~~ M E N U ~~~
1. Insert
2. Search
3. Delete
4. Display
5. Exit
Enter a valid menu item ... 3
Enter element to delete : 3
The Binary Search Tree is :
___________________23
/ \
____7_______ 25
/ \
__
4 ___12___
/ \ / \
2 6 9 19
_
/ / \ / \
5 8 11 15 20
Output 4
~~~ M E N U ~~~
1. Insert
2. Search
3. Delete
4. Display
5. Exit
Enter a valid menu item ... 3
Enter element to delete : 7
The Binary Search Tree is :
_________________23
/ \
____8_____ 25
/ \
__
4 ___
1_
2__
/ \ / \
2 6 9 19
_
/ \ / \
5 11 15 20
308 Data structures for engineers and scientists using Python
Output 5
~~~ M E N U ~~~
1. Insert
2. Search
3. Delete
4. Display
5. Exit
Enter a valid menu item ... 3
Enter element to delete : 12
The Binary Search Tree is :
______________23
/ \
____8_____ 25
/ \
_
4_ 15
___
/ \ / \
2 6 9 19
/ \ \
5 11 20
Output 6
~~~ M E N U ~~~
1. Insert
2. Search
3. Delete
4. Display
5. Exit
Enter a valid menu item ... 3
Enter element to delete : 12
The Binary Search Tree is :
______________23
/ \
____8_____ 25
/ \
4__ ___15
/ \ / \
2 6 9 19
/ \ \
5 11 20
Output 7
~~~ M E N U ~~~
1. Insert
2. Search
3. Delete
4. Display
5. Exit
Enter a valid menu item ... 5
Exit
Trees 309
Python program 4
# Create a node
class Node:
def __init__(self, key):
self .k
ey = key
self .le
ft = None
self .rig
ht = None
Program continues
#Search
def search(root,val):
if (root is None or root.key == val):
return root
return search(root.left,val)
Program continues
# Inorder traversal
def inorder(root):
if root is not None:
# Traverse left
inorder(root.left)
# Traverse root
print(str(root.key), end=' -> ')
# Traverse right
inorder(root.right)
Program continues
# Insert a node
def insert(node, key):
temp = search(node,key)
if (temp != None):
print("\n",temp.key," Exists in the BST... Try another
Number ")
return node
else:
# Return a new node if the tree is empty
if node is None:
return Node(key)
310 Data structures for engineers and scientists using Python
return node
Program continues
# Find the inorder successor
def minValueNode(node):
current = node
Program continues
# Deleting a node
def deleteNode(root, key):
root.key = temp.key
return root
Trees 311
Program continues
def menu():
print("\n~~~ M E N U ~~~")
print("1. Insert")
print("2. Search")
print("3. Delete")
print("4. Display")
print("5. Exit")
opt = int(input("Enter a valid menu item ... "))
return opt
Program continues
if __name__ == "__main__":
root = None
choice = 1
while (choice > 0 and choice < 5 ):
choice = menu()
if (choice == 1):
print("Enter 0 to exit Inserting Data into the BST\n ")
x = int(input("Enter an element: "))
while (x != 0):
root = insert(root, x)
x = int(input("Enter an element: "))
print("Inorder traversal: ", end=' ')
inorder(root)
elif(choice == 2):
val = int(input("Enter an element to Search: "))
temp = search(root,val)
if (temp != None):
print("\n",temp.key," Exists in the BST")
else:
print("\n",temp.key,"Does not Exist in the BST")
elif(choice == 3):
value = int(input("Enter element to delete : "))
root = deleteNode(root, value)
print("Inorder traversal: ", end=' ')
inorder(root)
elif(choice == 4):
print("Inorder traversal: ", end=' ')
inorder(root)
else:
print("Exit")
312 Data structures for engineers and scientists using Python
Output
~~~ M E N U ~~~
1. Insert
2. Search
3. Delete
4. Display
5. Exit
Enter a valid menu item ... 1
Enter 0 to exit Inserting Data into the BST
Enter an element: 6
Enter an element: 3
Enter an element: 6
~~~ M E N U ~~~
1. Insert
2. Search
3. Delete
4. Display
5. Exit
Enter a valid menu item ... 2
Enter an element to Search: 4
~~~ M E N U ~~~
1. Insert
2. Search
3. Delete
4. Display
5. Exit
Enter a valid menu item ... 3
Enter element to delete : 3
Inorder traversal: 4 -> 6 ->
~~~ M E N U ~~~
1. Insert
2. Search
3. Delete
4. Display
5. Exit
Enter a valid menu item ... 4
Inorder traversal: 4 -> 6 ->
Trees 313
~~~ M E N U ~~~
1. Insert
2. Search
3. Delete
4. Display
5. Exit
Enter a valid menu item ... 6
Exit
2
3
7 2
5
4 1
2
2 6 9 1
9
3 5 8 1 1 2
1 5 0
2 7
1 5 8
4 6 9
If there are n elements in the skewed binary search tree, we need n steps to
reach the last node, n–1 steps to reach the next to last node, etc. Therefore,
on the average we need n/2 steps and the search time is O(n). We need to
keep the height of the tree as small as possible to keep the average search
time minimum since the search time is proportional to the height of the tree.
Trees 315
1. The height of the left sub-tree and right sub-tree of the root is the
same.
2. The left sub-tree and the right sub-tree are also perfectly balanced
trees.
0
1
3 7
0 0
0 4 6 8
4 0 0 0
1 1 3 4 5 6 7 9
0 2 5 5 5 5 5 0
1. The heights of the left sub-tree and right sub-tree of the root differ by
at most 1.
2. The left sub-trees and right sub-trees are also AVL trees.
Let x be a node of the binary search tree. Let xl and xh be the heights of its
left sub-tree and right sub-tree. Then we define the balance factor at node
x as:
bf(x) = xl – xr
The permissible values bf(x) are {–1, 0, +1} for an AVL tree. Thus, the node
in the AVL tree must contain besides the data value and left and right point-
ers the value of the balance factor.
The constructor function initializes the left and right pointers to NULL
and the balance factor to 0.
Proof: Let n(h) be the minimum number of internal nodes in an AVL tree of
height h. We can see that n(1) = 0 and n(2) = 1. For n >= 3, an AVL tree of
height contains the root node, an AVL sub-tree of height h – 1 and an AVL
sub-tree of height h – 2. Thus, we can write n(h) as
taking logarithms,
Most of the algorithms used for a binary search tree (such as searching,
traversals, counting nodes) remain the same. However, insertions and dele-
tions are different since after every insertion and deletion, the AVL prop-
erty may be lost.
Examples of AVL trees are shown in Figure 7.26.
15
15 +1
15 0
15 0
10 0 20 +1
10 0 10 0 20
18 0
7.7.2 Insertion
After inserting a node, as is done in any binary search tree, it is necessary to
check that each of its ancestors satisfies the AVL property. This is achieved
by considering the balance factor at each node. Since the insertion into a
binary tree cannot increase the height by more than 1, the balance factor of
each node lies in {–2, 2}. If the balance factors of all the nodes lie in {–1, +1},
no further operation is needed. However, if the balance factor at any node
is more than +1 or less than –1, the AVL property is lost and a rebalancing
is needed. Let us trace the operations of insertion with an example.
Imagine the situation where we arrive at the structure in Figure 7.27a
while constructing a binary search tree.
a -2
b>a ; b<c
b -1
c 0
This does not satisfy the AVL property since the balance factor of the
root node is –2. To fix this we have to perform a rotation. This is done using
the following steps.
318 Data structures for engineers and scientists using Python
LL rotation
a -2
b 0
b>a ; b < c
b -1
a 0 c 0
c 0
a +2
b +1 a>b> c
BST property is preserved
c 0
The balance factor of node a is +2 and hence does not satisfy the AVL
property. We fix it with the following steps (RR rotation) (Figure 7.27d).
RR rotation
a +2
b 0
b +1
c 0
c 0 a 0
Both the AVL property and binary search tree property are restored.
Let us see what happens when the new node is the left child of the right
sub-tree (see Figure 7.27e).
a -2
b +1 b>a; b> c
c 0
a -2 a -2
0
c
-1
b +1 c
a 0 b 0
b 0
c 0
+2
-1
AVL structure, we first rotate about c, which makes b take the position of
c, and c becomes the left child of b, and then rotate about a. This double
rotation is called LR rotation.
We arrive at Figure 7.27h.
+2 +2
0
-1 +1
0 0
0 0
+2
50
+1 0
50
17
17
+1
17
0 0 0
12
50
12
-1 0
17
17
Add 23 Add 9
12
50
12
50
0 +1 +1 +1
23
23
0 0
17
Add 14 +1
0
12
50
0
14
0
23
0
0
17
0
17
Add 19 0 LL Rotaon
12
50
+2 0 0
12
23
0 0
0
14
+1
23
0
14
0 0
19
50
19
-1
17
Add 72
0 -1
12
23
0
0
14
0 -1
19
50
0
72
17
-2
1
17
0
12
-2
23
Add 54
12
0 1
23
RL Rotaon
0
0 0
-2
14
50
0
19
0 0
14
19
54
0
72
1
0
72
0
50
0
54
7.7.3 Deletion
As with insertion, the deletion of a node may cause the violation of AVL
property. The sub-tree shown in Figure 7.29a is strictly in the AVL form.
-1
50
0
45
-1
70
65
1
80
0
75
If we delete node 65, it is no longer an AVL tree since node 70 has balance
factor (–2) and also node 50 has balance factor –2 as shown in Figure 7.29b.
-2
50
0
45
-2
70
80
0
75
-1
32
-1
48
-1
16
-1
40
56
0
0 -1
24
52
60
0 0 0
28
30
44
0 0
58
62
0 0
-2
32
-1
48
0
24
1
-1
40
56
0
0
16
28
0 0
52
56
0 0
30
44
0 0
58
62
The next node in the path is the root itself and it has a balance factor
–2. Since it is the right sub-tree that is causing the imbalance (height of the
right sub-tree is greater than the height of the left sub-tree). We make an
RR rotation to restore the balance and obtain the AVL tree in Figure 7.29e.
48
0
32
-1
56
24
40
0 0
52
0
60
0
44
0 0
28
30
0
16
0 0 0
62
58
Figure 7.29e Deletion of element from an AVL tree
Let us write a program in Python to insert a node into an AVL tree and
delete a node from the tree using various rotations as needed.
Program continues
class AVLTree(object):
return root
balanceFactor = [Link](root)
326 Data structures for engineers and scientists using Python
return 0
return [Link](root.left) - [Link]
(root.right)
myTree = AVLTree()
root = None
nums=[]
print("Enter 0 to exit Inserting Data into the AVL Tree ")
print("Enter the node of AVL Tree ")
x = int(input("Enter an element: "))
while(x!=0):
nums.append(x)
x = int(input("Enter an element: "))
nums=set(nums)
for num in nums:
root = myTree.insert_node(root, num)
[Link](root, "", True)
Output
7.8 SPLAY TREES
Case 1: X’s parent P is the root. Perform a single rotation about the root (P)
making X the root. This is called a “zig” step (also called singular splay). It
is the same as a single right rotation (Figure 7.30).
P X
C
X A P
zig
A B B C
Its mirror situation is known as a “zag” step. It is the same as a single left
rotation (Figure 7.31).
P X
A X P C
zag
B C A B
Case 2: X is the left child of its parent P and P is the left child of its parent G
(Figure 7.32). Or the mirror situation where X is the right child of its parent
P and P is the right child of its parent G. This is called a homogeneous con-
figuration. First rotate P about G and then rotate X about P. This is called
P D
X C
A B
the “zig-zig” step. It is also known as a double zig (double right rotation)
(Figure 7.33a).
P X
zig G zig A P
X
B G
A B C D
C D
G X
P D A P
X C B G
zig-zig
A B C D
Case 3: X is the left child of its parent P and P is the right child of its par-
ent G. Or its mirror situation where X is the right child of P and P is the
left child of G. This is called a heterogeneous configuration. First, perform
a rotation of X about P and then about G. This is called a “zig-zag” step
(Figure 7.35a).
Same as Figure 7.35b.
Its mirror situation is known as a “zag-zig” step. It is the same as left-
right rotation (Figure 7.36a).
Same as Figure 7.36b.
Trees 331
G
P
P
A zag
G X
B X
A B C D
C D
D
zag P
C
G
A B
G X
P D
A zag-zag P
B X C
G
C D A B
G G X
D D X zag
P zig G P
X C P
A D C B A
C B B A
G X
D P G P
zig-zag
X A D C B A
C B
G
G
X
P D X D
zag zig P G
A X P C
A B C D
B C A B
G
X
P D
zag -zig P G
A X
A B C D
B C
Example: With 5, 10, 15, 6, 9, 7, 11, 4 form a splay tree inserting the ele-
ments in the same order (Figures 7.37a to 7.37g).
Trees 333
10
Insert 10 Zig
5
10
Figure 7.37a Insertion of 10 into a splay tree
15
10
Insert 15 Zig
10
15
15
10
15
10
10
Zig
Insert 9
15
Zig-Zig
10
10
10
15
15
Insert 7 Zig-Zag
10
15
10
15
Figure 7.37e Insertion of 7 into a splay tree
Insert 11 Zig-Zag
10
11
15
15
10
11
11
Zig-Zig
15
10
11
11
15
15
Insert 4 Zig-Zig
10
10
11
11
15
15
Zig Zig
10
10
11
Zig
15
10
True–false questions
Fill-in-the-blank questions
1. The number of edges from the node to the deepest leaf is called the
of the tree.
2. The maximum number of nodes at level i is .
3. The depth of a tree is defined as the of any of the
nodes.
4. A node with no children is called a .
5. A tree in which the right sub-tree is missing in every node is known as
a .
Multiple-choice questions
3. If a new node is inserted as the right child to a node that is the left
child of its parent, then we make an
a. RL rotation c. LL rotation
b. LR rotation d. RR rotation
Trees 337
4. If a new node is inserted as the left child to a node that is the right
child of its parent, then we make an
a. RL rotation c. LL rotation
b. LR rotation d. RR rotation
7. If the key values 2, 3, 7, 8, 9, 1 are inserted into a splay tree, the root
contains
a. 2 c. 1
b. 7 d. 9
10. Which of the following rotation in AVL tree known as single rotation?
a. LL and RR c. LR and RL
b. LL and LR d. RR and Rl
338 Data structures for engineers and scientists using Python
15. The minimum number of key values in a node of a B-tree with m+1
links is
a. ϒm/2/ c. m+1
b. ≤m/2f d. m–1
20. If 2000 numbers are used to construct a binary search tree, the maxi-
mum height of the tree is
a. 1 c. 1999
b. 11 d. 2000
Descriptive questions
B C
D E
F
G
2. The nodes visited in the pre-order traversal and in-order traversal are
given below.
Pre-order: ABCDEFGHIJKLM
In-order: CEDFBAHJIKGML
Draw the binary tree.
3. Insert node 100 in the following AVL tree. The resulting tree must be
an AVL tree.
60
50 70
40 65 65 80
90
340 Data structures for engineers and scientists using Python
4. Starting from an empty AVL tree, insert the following key values:
24, 39, 35, 47, 58, 36, 71, 100 in that order
1. True
2. False
3. True
4. True
5. False
1. height
2. 2i–1
3. maximum level
4. leaf node
5. left-skewed tree
1. c 2. a 3. b 4. a 5. a
6. d 7. d 8. c 9. a 10. a
11. d 12. b 13. d 14. b 15. a
16. a 17. d 18. d 19. d 20. c
Chapter 8
Graphs
LEARNING OBJECTIVES
8.1 INTRODUCTION
V = {1, 2, 3, 4, 5, 6}
E = { (1, 2), (1, 5), (2, 3), (3, 4), (4, 5), (4, 6)}
For the graph shown in Figure 8.2, the vertex set is {1, 2, 3, 4, 5}
and the edge set is {(1, 2), (2, 3), (2, 4), (2, 5), (4, 2), (4, 3), (5, 4)}.
• Vertex-labeled graph: Each vertex in addition to the label it carries
also contains some data. In the graph in Figure 8.3, the labels to the
vertices are shown outside the nodes and the data is shown inside the
nodes.
G raphs 343
V = {(1, A), (2, B), (3, C), (4, D), (5, E), (6, F)}
E = {(1, 2), (2, 3), (2, 4), (3, 5), (4, 5), (6, 1), (6,5)}
• Cyclic graph: A cyclic graph is a directed graph with at least one cycle.
A cycle in a graph is a directed path from any vertex to itself. In Figure
8.4, there are two cycles and they are
2→4→5→7→6→2
and
4 → 3 → 7 → 6 → 2 →4
A
1 2
B
F C
E
D
4 3
In the graph in Figure 8.5, the vertex set is {1, 2, 3, 4} and the edge set
is {(1, 2, A), (2, 1, B), (2, 3, C), (3, 4, D), (4, 1, E), (1, 3, F), where
A is the label associated with (1, 2).
B is the label associated with (2, 1).
C is the label associated with (2, 3).
D is the label associated with (3, 4).
E is the label associated with (4, 1).
F is the label associated with (1, 3).
• Weighted graphs: If the labels associated with the edges are numbers
indicating the importance of the edge, we call the graph a weighted
graph (Figure 8.6). The numbers can be distances between two cit-
ies where the nodes represent cities or the cost associated with the
completion of phase I of a project and taking it to phase II, where the
nodes represent different phases of a project.
2N v V
deg ree v
1 2 3
5 4
• The in-degree of 1 is 2
• The out-degree of 1 is 3.
• The in-degree of 2 is 1.
• The out-degree of 2 is 1.
• The in-degree of 3 is 3.
• The out-degree of 3 is 0.
• The in-degree of 4 is 1.
• The out-degree of 4 is 2.
• The in--degree of 5 is 2.
• The out-degree of 5 is 2.
2N vV
in deg ree v vV
out deg ree v
This is just an extension of the earlier theorem. The in-degree counts the
edges into a node and the out-degree counts the edges going out of a node
and the sum, therefore, gives the total number of edges, counted twice, i.e.,
2N.
G raphs 347
• Complete graph: The graph in which all the nodes have the same
degree is called a complete graph.
A complete graph, with n vertices, denoted as K n, is a simple graph
in which there is an edge between every pair of vertices (Figure 8.10).
Example
Given a graph with seven vertices, three of them of degree 2 and four of
them of degree 1, is the graph connected?
Answer: No
Let V = n+1. The number of edges added is maximum n, when the new
vertex is connected to all other n vertices. Therefore, the maximum number
of edges when V = n + 1 is n(n–1)/2 + n = (n+1)n/2.
8.2 GRAPH REPRESENTATION
• Adjacency list
• Adjacency matrix
8.2.1 Adjacency list
Adjacency list representation is used when the number of edges is less than
V×log V. The adjacency list representation of a graph G consists of an array
of linked lists, one for each vertex. Consider the graph in Figure 8.11.
1 4
2 3
8.2.2 Adjacency matrix
If M is the matrix representing a graph G, then
1 2 3 4 5
1 0 0 0 1 0
2 1 0 1 0 0
3 0 1 0 0 1
4 0 0 1 0 0
5 0 0 0 0 0
8.3 TRAVERSALS
In tree traversals, we start at the root and follow the edges until we encoun-
ter a null node. A node is never visited twice since there are no cycles.
However, in graph traversals it is possible we visit the same node many
times by following the edges. Hence it is necessary to keep track of nodes
already visited and ignore them the second time. This may be accomplished
by maintaining a Boolean array “visited,” which may be of the size of the
number of nodes, one entry for each node of the graph, and is initialized to
false. This array keeps track of the nodes already visited so far and ignores
them when we reach them again.
8.3.1 Depth-first search
The depth-first search (DFS) visits all child vertices, recursively, before visit-
ing the sibling vertices. In other words, it traverses the depth of any particu-
lar path before exploring its breadth. Often a stack is used for implementing
the algorithm. There is nothing called a “root” vertex in a graph. We arbi-
trarily choose a vertex and start the search from there. It then iteratively vis-
its adjacent unvisited vertices until it can no longer find an unvisited vertex
from its present position. In other words, all adjacent vertices of the current
position are already visited. The algorithm, then, “backtracks” along the
previously visited vertices until it finds a vertex that is not yet visited. It fol-
lows the new path backtracking whenever necessary (if it finds dead ends)
and ends only when the algorithm backtracks to the root.
Algorithm 1
1. Algorithm dfs(G,v)
2. Mark v visited and push it onto a stack
3. While stack is not empty do
G raphs 351
Let us start from A. Mark it visited. Push it onto the stack (Figure 8.16a).
Visited is a Boolean array of the size of the number of nodes; one entry for
each node. True if the node is visited, false otherwise.
Pop an element from the stack, show it in the output, and push its adja-
cent vertices D, B in that order onto the stack (any of the adjacent sides can
be pushed onto the stack, but we push them in alphabetical order) after
marking them visited. The stack position now is as in Figure 8.16b.
352 Data structures for engineers and scientists using Python
We have B on top of the stack, pop it out and show it in the output. Its
adjacent nodes are A, E, F. A is already visited. Push F and E onto the stack,
in that order, after marking them visited. The stack position now is as in
Figure 8.16c.
The top element E in the stack is popped out and shown in the output. Its
adjacent is G. It is marked as visited and pushed onto the stack. Now the
stack is as shown in Figure 8.16d.
We have G on top of the stack. Pop it out and show it in the output. As
there is no element to push, the position of the stack is as in Figure 8.16e.
The top element F in the stack is popped out and shown in the output. Its
adjacent is C. It is marked as visited and pushed onto the stack. Now the
stack is as shown in Figure 8.16f.
G raphs 353
The top element C in the stack is popped out and shown in the output.
Its adjacent is H. It is marked as visited and pushed onto the stack. Now the
stack is as shown in Figure 8.16g.
We have H on top of the stack. Pop it out and show it in the output. As
there is no element to push, the position of the stack is as in Figure 8.16h.
We have D on top of the stack. Pop it out and show it in the output. As
there is no element to push, the stack is empty.
The sequence of nodes contained in the output is
A B E G F C H D
G raphs 355
Python program 1
graph = {
'E' : ['B','G'],
'G' : ['A', 'E'],
'B' : ['A','E','F'],
'A' : ['B','D','G'],
'D' : ['A','F'],
'F' : ['B','C','D'],
'C':['F','H'],
'H':['C']
}
# Driver Code
print("Following is the Breadth-First Search")
bfs(visited, graph, 'A') # function calling
Output
Following is the Depth-First Search
A
B
E
G
F
C
H
D
8.3.2 Breadth-first search
In a breadth-first search (BFS), we start at any node and visit all the adja-
cent nodes. We use the data structure queue to determine the next node to
be visited. We also maintain a Boolean array visited to keep track of all
356 Data structures for engineers and scientists using Python
the nodes processed so far. To illustrate the procedure, let us use the same
graph we used to illustrate the depth-first traversal (Figure 8.17). We use a
queue instead of a stack.
We start from A. Mark it visited. Insert into the queue. Now remove A
from the queue, display in the output and insert its adjacent vertices B D G
in alphabetical order into the queue and mark them as visited.
The status of the queue now is shown in Figure 8.18a.
Visited AGDB
Output A
B is removed from the queue, and is put in the output. Its adjacent nodes E
and F are inserted into the queue in that order and marked as visited. The
current status of the queue and the array ‘visited’ are shown in Figure 8.18b.
Visited A G D B E F
Output A B
Visited AGDBEF
Output ABD
The next vertex in the queue is G. It is removed from the queue and added
to the output (Figure 8.18d).
Visited AGDBEF
Output ABDG
G’s neighbors are already visited. The next vertex E is taken out from the
queue and added to the output (Figure 8.18e). The status of the queue, the
array visited and output are
358 Data structures for engineers and scientists using Python
Visited AGDBE
Output ABDGEF
Remove F from the queue and add to the output. Its neighbor C is added to
the queue (Figure 8.18f).
Visited ABDGEFC
Output ABDGEF
Remove C from the queue and add to the output. Its neighbor H is added to
the queue after marking it visited (Figure 8.18g).
Visited ABDGEFCH
Ouput ABDGEFC
G raphs 359
A B D G E F C H
Python program 2
graph = {
'E' : ['B','G'],
'G' : ['A', 'E'],
'B' : ['A','E','F'],
'A' : ['B','D','G'],
'D' : ['A','F'],
'F' : ['B','C','D'],
'C':['F','H'],
'H':['C']
}
# Driver Code
print("Following is the Breadth-First Search")
bfs(visited, graph, 'A') # function calling
Output
Following is the Breadth-First Search
A B D G E F C H
8.4 AND/OR GRAPHS
The tree structure in Figure 8.19a implies that, to solve problem A, solve
both problems B and C or solve D or solve E. The tree structure can further
be extended breaking down the problems B, C, D, E into sub-problems. The
terminal square nodes represent solvable problems without further decom-
position. As we can see. AND/OR graphs are not necessarily trees.
P1
2 8
2
P2 P3 P4
1 1 3
1
P5 P6 P7
8.5 BI-CONNECTED COMPONENTS
8.5.1 Connectivity
An undirected graph is said to be connected if there is a path between any
two vertices. A graph is said to be n-connected if there are at least different
paths between any two vertices and the paths having no common vertices.
A special type of graph is a 2-connected or bi-connected graph in which
there are at least two different paths between any two vertices. A graph is
not bi-connected if a vertex can be found that always has to be included in
a path between at least two different vertices, say a and b. In other words,
if this vertex is removed (along with incident edges), there is no way to reach
from a to b and vice versa. This means that the graph is split into two or
more sub-graphs. Such vertices are called articulation points or cut-vertices.
If an edge causes its removal by a split of the graph into two sub-graphs, the
edge is called a bridge. The sub-graphs obtained by removing the articula-
tion points are called bi-connected components.
Consider the graph in Figure 8.20 (Horowitz, Sahni, Rajsekharan et al.).
362 Data structures for engineers and scientists using Python
Algorithm 2
1. Algorithm bi-connected(G)
2. for each articulation point a do
3. {
4. let B1, B2,….Bk be the bi-connected components
containing the vertex a.
5. let vi ≠ a be a vertex in Bi , 1<=i<=k
6. add to G the edges <vi,vi+1>
7. }
The presence of a back edge means the presence of an alternate path to the
ancestors.
Let us define L(u) as the lowest depth-first number that can be reached
from u using a path of its descendants and a back edge. Applying the defini-
tion we have L[1:10] = [1,1,1,1,6,8,6,6,5,4].
Let us calculate some of these numbers.
L[1] = 1, since it can reach itself through 1 →4→3→2 and the back edge
2→1.
L[2] = 1, since we can reach 1 from 2 through the back edge 2→1.
Similarly, l[3] = 1 and l[4] = 1.
L[5] = 6, since 5 can reach 2 through its descendants 7 and 8 and the back
edge 8→2 and dfn(2) = 6.
L[6] = dfn(6) = 8, since it has no descendants.
L[7] = 6, since we can reach node 2 whose dfn is 6 through 7→8 and back
edge 8→2. And similarly, L[8] = 6.
G raphs 365
L[9] = 5 and L[10] = 4 , their own depth-first numbers, since they have no
descendants and no back edges.
If u is not a root, then u is an articulation point if and only if u has a child
w such that L(w) ≥ dfn(u). Vertex 2 is an articulation point since its child 5
satisfies L(5) ≥ dfn(2), since L(5) = 6 and dfn(2) = 6.
Similarly, nodes 3 and 5 are articulation points.
8.6 SHORTEST-PATH PROBLEM
Let G = (V, E) be a directed graph. The shortest path between two vertices
in the graph is the path with shortest length (least number of edges) called
the link distance. A breadth-first search discussed earlier is the algorithm
for finding the shortest link distance from a single source vertex to all other
vertices in the graph. A breadth-first search processes all vertices in the
increasing order of distance from the source.
Now, let G = (V, E) be a weighted graph. Let us use a weight function that
maps the edges to real numbers:
w: E → R
if e is an edge, w(e) is called the weight associated with the edge e. The
length of the path from a vertex u to a vertex v is the sum of the weights
associated with the edges that constitute the path between u and v. Let us
denote the minimum distance between u and v as d(u, v), if one exists.
Dijkstra’s algorithm
1. Let d(v) be the length of the shortest path from ‘s’ to each vertex v.
2. Initialize d(v) to ∞ for all vertices of the graph.
3. Let d(s) = 0.
4. Process vertices to find new paths and update d(v).
The last statement can be made more precise by the following statement:
d(A)=0;
d(B) = d(C) = d(D) = d(E) = ∝
Step 4
Adj(B)=E;
d(E) = d(B) + w(B,E) = 3 + 3 = 6;
pred(E) = B;
G raphs 367
Step 5
Adj(D) = E;
d(E) = d(D) + w(D,E) = 3 + 3 = 6
which is the same value computed earlier and we keep the earlier value and
earlier predecessor. We show the shortest paths in the following diagram.
Step 6
Adj(E) = φ.
This means there are no outgoing edges from E. And there are no more
vertices. The algorithm terminates.
Using the information about the predecessors of each vertex, we show the
shortest paths to each vertex from A (Figure 8.24).
8.7 TOPOLOGICAL SORTING
Algorithm 3
1. Algorithm topological sort.
2. Input the AOV network and let n be the number of vertices.
3. for i =1 to n do
4. {
4.1. If every vertex has a predecessor, then the network has a
cycle and is infeasible. Stop
5. Pick a vertex v that has no predecessors.
6. Output v.
7. Delete v and all edges leading out of v.
8. }
368 Data structures for engineers and scientists using Python
Now neither v2 , nor v3, nor v4 have any predecessors. Choose any one of
them, say, v2 and remove v2 and all edges leading out of it (Figure 8.26).
True–false questions
1. A graph is a tree.
a. True b. False
2. An edge is a connection between two vertices.
a. True b. False
3. A bi-connected graph is not essentially a connected graph.
a. True b. False
4. The shortest path between two vertices in the graph is the least num-
ber of edges.
a. True b. False
5. A queue is used for depth-first search.
a. True b. False
Fill-in-the-blank questions
Multiple-choice questions
1. An AND/OR graph is a
a. Multiway tree c. Not necessarily a tree
b. Binary tree d. Not necessarily a binary
tree
9. A simple graph that contains exactly one edge between each pair of
distinct vertices is a
a. Tree c. Path
b. Degree d. Complete graph
10. When information about the vertices is more desirable than informa-
tion about the edges, we use
a. Adjacency matrix c. Both a and b
b. Adjacency list d. None of the above
15. What is the maximum degree of any node in a simple graph with n
vertices?
a. n/2 c. n
b. n–1 d. n+1
18. What is the number of distinct simple graphs with up to three nodes?
a. 7 c. 10
b. 9 d. 15
20. In any undirected graph, the sum of degrees of all the nodes
a. Must be even c. Both a and b
b. Twice the number of edges d. None of the above
Descriptive questions
3. Find the order of nodes that is printed in DFS for the following graph.
4. Find the adjacency matrix and adjacency lists for the following graph.
374 Data structures for engineers and scientists using Python
1. False
2. True
3. False
4. True
5. False
1. vertices, edges
2. adjacency lists
3. complete graph
4. weighted graph
5. cycle
1. c 2. c 3. c 4. b 5. c
6. d 7. b 8. a 9. d 10. c
11. a 12. c 13. b 14. b 15. b
16. a 17. c 18. a 19. b 20. c
Chapter 9
LEARNING OBJECTIVES
9.1 INTRODUCTION TO SORTING
The size of the data collection, how the data are distributed, memory
requirements and desired performance characteristics all play a role in
selecting the best sorting method. To choose an algorithm that satisfies the
particular needs of the current problem, it is critical to take these elements
into account.
9.1.1 Bubble sort
The first sorting method we’ll learn about is the bubble sort. By continu-
ally comparing neighboring elements and swapping them if they are unor-
dered, it sorts a given list of elements. When two items are swapped, their
relative positions are also changed. Pass is the term used in algorithms to
describe each iteration of a list’s elements. The bubble sort sorts a list with
n elements over a total of n – 1 passes. The necessary adjacent pairs of list
entries will be compared in each pass. The largest element is determined
after each pass and positioned at the appropriate location in the list in order
to arrange the components in ascending order. This can be considered as
the largest element being “bubbled up.” Hence the name bubble sort. This
sorted element is not considered in the remaining passes and thus the list of
elements gets reduced in successive passes.
Algorithm 1
1. BUBBLESORT( numList, n)
2. SET i = 0
3. WHILE i< n REPEAT STEPS 3 to 8
4. SET j = 0
5. WHILE j< n-i-1,REPEAT STEPS 5 to 7
6. IF numList[j] > numList[j+1] THEN
7. swap(numList[j],numList[j+1])
8. SET j=j+1
9. SET i=i+1
Example
Sort the elements in Figure 9.1a using the bubble sort algorithm.
Python program 1
def bubblesort(elements):
swapped = False
# Looping from size of array from last index[-1] to index [0]
for n in range(len(elements)-1, 0, -1):
for i in range(n):
if elements[i] > elements[i + 1]:
swapped = True
# swapping data if the element is less than next
element in the array
elements[i], elements[i + 1] = elements[i + 1],
elements[i]
if not swapped:
# exiting the function if we didn't make a single swap
# meaning that the array is already sorted.
return
Output
9.1.2 Insertion sort
Another sorting technique that can place items in a given list in either
ascending or descending order is insertion sort. Similar to selection sort,
S orting and searching 381
insertion sort divides the list into two sections: one with sorted entries and
the other with unsorted elements. One by one, each item in the unsorted
list is taken into account and added to the sorted list in the proper location.
The sorted list is walked through once for each pass to locate the potential
spot to insert an unsorted element. Thus, the sorting technique is known as
insertion sort.
In pass 2, starting with element e of the unsorted list in the backward
direction, each element of the sorted list will be compared with element e
of the unsorted list until the proper position for insertion is identified. The
components of the sorted list will be moved to the right, creating room for
element e to be entered.
This keeps happening until every element from unsorted lists has been
added to the sorted list at the proper places.
As a consequence, a sorted list is produced, with the components orga-
nized in ascending order.
Algorithm 2
INSERTIONSORT( numList, n)
1. i=1
2. WHILE i< n REPEAT STEPS 3 to 9
3. temp = numList[i]
4. j = i-1
5. WHILE j> = 0 and numList[j]>temp,REPEAT STEPS 6 to 7
numList[j+1] = numList[j]
j=j-1
6. numList[j+1] = temp #insert temp at position j
7. i=i+1
Example
Sort the data in Figure 9.2a using insertion sort.
Comparison in Pass 2: The next data 18 is inserted into the list (Figure 9.2c).
Comparison in Pass 3: The next data 6 is inserted into the list (Figure 9.2d).
Comparison in Pass 4: The next data –4 is inserted into the list (Figure 9.2e).
382 Data structures for engineers and scientists using Python
Comparison in Pass 5: The next data 9 is inserted into the list (Figure 9.2f).
Python program 2
Output
9.1.3 Selection sort
Another sorting method is selection sort. The selection sort makes (n – 1)
number of trips through the list in order to sort a list with n elements. The
list is thought to be split into two lists, with the right list containing the
unsorted elements and the left list carrying the sorted elements. The right
list initially has all the elements, but the left list is initially empty.
In the first pass, all of the elements in the unsorted list are scanned to
identify the smallest element in order to arrange the elements in ascending
order. The leftmost element of the unsorted list is then switched for the
smallest element. This element is at the top spot in the sorted list and is
skipped over in subsequent passes. The leftmost member of the unsorted
list is swapped with the next-smallest element in the second pass, which is
chosen from the remaining items in the unsorted list.
S orting and searching 385
This element is the second item in the sorted list, and during the third
run, the unsorted list is reduced by one element. This procedure is repeated
until the n-1 smallest elements are located and placed in the appropriate
locations. The final and previously present ingredient is the nth one.
Algorithm 3
SELECTIONSORT( numList, n)
1. i=0
2. WHILE i< n REPEAT STEPS 3 to 11
3. min = i, flag = 0
4. j= i+1
5. WHILE j< num REPEAT STEPS 6 to 10
6. IF numList[j] < numList[min] THEN
7. min = j
8. flag = 1
9. IF flag = 1 THEN
10. swap(numList[i],numList[min])
11. i=i+1
Example
Sort the data in Figure 9.3a using insertion sort.
Python program 3
Output
UnSorted array
[13, 12, 18, 6, -4, 9]
Sorted array
[-4, 6, 9, 12, 13, 18]
9.2 INTRODUCTION TO SEARCHING
9.2.1 Linear search
Among search techniques, linear search is the most basic and straightfor-
ward. It is a thorough search method in which each entry in a list is com-
pared to the object you’re looking for, also known as the “key.” As a result,
the key is compared one by one with each member in the list. This proce-
dure is repeated until an element that matches the key is located, at which
point we proclaim the search to be successful. We deem the search failed if,
after searching the whole list, no element matches the key, indicating that
the key is not present in the list. The order in which the items are contained
in the list is followed when comparing each item individually, starting with
the first and working all the way down to the last. As a result, it is also
known as a serial or sequential search. When gathering little, unordered
things, this strategy might be helpful.
Algorithm 4
LinearSearch(numList, key, n)
1. index = 0
2. WHILE index < n, REPEAT Step 3
3. IF numlist[index]= key THEN
4. PRINT “Element found at position”, index+1 STOP
5. ELSE index = index+1
6. PRINT “Search unsuccessful”
Example
Search for key = 6 in the given list.
List 13 12 18 6 -4 9
Index 0 1 2 3 4 5
Observe that after four comparisons, the algorithm found the key 17 and
will display “Element found at position 4”.
Let us search for key = 17 (Table 9.2).
Observe that after six comparisons, the algorithm does not find the key
17 and will display “Search unsuccessful”.
Python program 4
n = len(list1)
res = linear_Search(list1, n, key)
if(res == -1):
print("Search unsuccessful")
else:
print("Element",key,"found at index: ", res)
Output
Element 6 found at index: 3
S orting and searching 391
9.2.2 Binary search
The binary search is a method of rapidly finding a key by using the
ordering of the list’s members. The list’s members can be ordered accord-
ing to their key values in either ascending or descending order for numeric
values. Textual data can either be sorted alphabetically from z to a or
from a to z.
In a binary search, the element in the center of a sorted list is compared
with the key to be searched. Any one of the following three outcomes might
arise from this:
The search is deemed successful and comes to an end if the element in the
middle position matches the key.
If the middle element exceeds the key, the key must unquestionably be in
the first half of the list, if it is present at all. Therefore, we may skip over
the second half of the list right away and limit our search to the first half.
If the middle element is smaller than the key, the key must be in the sec-
ond half of the list, if it is there at all. Thus, we may skip over the first half
of the list right away and limit our search to the second half. Until the key
was located or the remaining list had just one item, this splitting and list-
size reduction process is carried out. The search fails if that item is not the
key since the key is not in the list.
Therefore, it is clear that a binary search can be more effective than a
linear search of individual components if the list we need to search is orga-
nized in a certain way. In other words, the list must be sorted. The floor
division (//) operator is used to determine the mid value if the list to be
searched has an even number of entries. The midpoint (mid) of the list, if
there are 10 entries, is equal to 10//2, or 5. Since the first element in the
list has an index value of 0, the sixth element in the list is thus regarded as
the middle element. If required, the list is further divided into two parts
where the first half contains five elements and the second half contains four
elements.
Interestingly, the intermediate comparisons that do not locate the key
nonetheless provide information about the section of the list that could con-
tain the key! They indicate whether the key is located before or after the
list’s current middle position, and we make use of this information to limit
the scope of our search. The term binary search comes from the fact that
every failed comparison cuts the amount of components that need to be
searched by half. Now let’s talk about the binary search algorithm.
392 Data structures for engineers and scientists using Python
Algorithm 5
BinarySearch(numList, key)
1. first = 0, last = n-1
2. mid = (first+last)//2
3. WHILE first <= last REPEAT Step 4
4. IF numList[mid] = key THEN
PRINT “Element found at position”, " mid+1
STOP
ELSE IF numList[mid] > key, THEN
last = mid-1 ELSE first = mid + 1
5. PRINT “Search unsuccessful”
Example
Consider a sorted list consisting of 15 elements: numList = [2, 3, 5, 7, 10,
11, 12]. The key = 10, has to be found in numList. The index values of the
first, middle and final elements are found in the numList.
Search for key = 10 in the given list. (Also see Tables 9.3 and 9.4.)
List 2 3 5 7 10 11 12
Index 0 1 2 3 4 5 6
Python program 5
# Test array
arr = [2, 3, 5, 7, 10, 11, 12]
x = 10
# Function call
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:
print("Element",x,"is present at index", str(result))
else:
print("Element is not present in array")
Output
True–false questions
Fill-in-the-blank questions
Multiple-choice questions
1. For the array {25, 45, 87, 21, 18, 49, 13, 115, 83, 65}, how many
searches are required to find 83?
a. 8 c. 10
b. 9 d. 11
3. Out of the following, which one does not involve the use of binary
search?
a. Union of intervals c. Debugging
b. To look through an d. Determining the top and
unsorted list lower bounds of an ordered
sequence
10. Which of the following is true about the search in an array with N
elements?
i. A linear search is also called a random search.
ii. At worst case, the number of comparisons needed in a linear
search is N.
a. Only i c. Both i and ii
b. Only ii d. None of the above
Descriptive questions
1. Consider a list of ten elements: numList = [7, 11, 3, 10, 17, 23, 1, 4,
21, 5]. Display the partially sorted list after three complete passes of
bubble sort.
2. Determine the number of swaps needed to sort the following list using
bubble and selection sort, and determine which sorting method is
more effective in terms of comparisons made (2, 5, 34, 8, 90, –33, 43,
–22 ,32).
396 Data structures for engineers and scientists using Python
1. False
2. True
3. True
4. True
5. False
1. 90, 99
2. 5, 4
3. four
4. when the size of the dataset is low
5. seven
1. b 2. d 3. b 4. c 5. c
6. a 7. b 8. a 9. d 10. b
Index
397
398 Index