Book Image

Hands-On Data Structures and Algorithms with Python - Third Edition

By : Dr. Basant Agarwal
Book Image

Hands-On Data Structures and Algorithms with Python - Third Edition

By: Dr. Basant Agarwal

Overview of this book

Choosing the right data structure is pivotal to optimizing the performance and scalability of applications. This new edition of Hands-On Data Structures and Algorithms with Python will expand your understanding of key structures, including stacks, queues, and lists, and also show you how to apply priority queues and heaps in applications. You’ll learn how to analyze and compare Python algorithms, and understand which algorithms should be used for a problem based on running time and computational complexity. You will also become confident organizing your code in a manageable, consistent, and scalable way, which will boost your productivity as a Python developer. By the end of this Python book, you’ll be able to manipulate the most important data structures and algorithms to more efficiently store, organize, and access data in your applications.
Table of Contents (17 chapters)
14
Other Books You May Enjoy
15
Index

Basic data types

The most basic data types are numeric and Boolean types. We’ll cover those first, followed by sequence data types.

Numeric

Numeric data type variables store numeric values. Integer, float, and complex values belong to this data type. Python supports three types of numeric types:

  • Integer (int): In Python, the interpreter takes a sequence of decimal digits as a decimal value, such as the integers 45, 1000, or -25.
  • Float: Python considers a value having a floating-point value as a float type; it is specified with a decimal point. It is used to store floating-point numbers such as 2.5 and 100.98. It is accurate up to 15 decimal points.
  • Complex: A complex number is represented using two floating-point values. It contains an ordered pair, such as a + ib. Here, a and b denote real numbers and i denotes the imaginary component. The complex numbers take the form of 3.0 + 1.3i, 4.0i, and so on.

Boolean

This provides a value of either True or False, checking whether any statement is true or false. True can be represented by any non-zero value, whereas False can be represented by 0. For example:

print(type(bool(22)))
print(type(True))
print(type(False))

The output will be the following:

<class 'bool'>
<class 'bool'>
<class 'bool'>

In Python, the numeric values can be used as bool values using the built-in bool() function. Any number (integer, float, complex) having a value of zero is regarded as False, and a non-zero value is regarded as True. For example:

bool(False)
print(bool(False))
va1 = 0
print(bool(va1))
va2 = 11
print(bool(va2))
va3 = -2.3
print(bool(va3))

The output of the above code will be as follows.

False
False
True
True

Sequence data types are also a very basic and common data type, which we’ll look at next.

Sequences

Sequence data types are used to store multiple values in a single variable in an organized and efficient way. There are four basic sequence types: string, range, lists, and tuples.

Strings

A string is an immutable sequence of characters represented in single, double, or triple quotes.

Immutable means that once a data type has been assigned some value, it can’t be changed.

The string type in Python is called str. A triple quote string can span into multiple lines that include all the whitespace in the string. For example:

str1 = 'Hello how are you'
str2 = "Hello how are you"
str3 = """multiline 
       String"""
print(str1)
print(str2)
print(str3)

The output will be as follows:

Hello how are you
Hello how are you
multiline 
String

The + operator concatenates strings, which returns a string after concatenating the operands, joining them together. For example:

f = 'data' 
s = 'structure'
print(f + s)
print('Data ' + 'structure')

The output will be as follows:

datastructure
Data structure

The * operator can be used to create multiple copies of a string. When it is applied with an integer (n, let’s say) and a string, the * operator returns a string consisting of n concatenated copies of the string. For example:

st = 'data.'
print(st * 3)
print(3 * st)

The output will be as follows.

data.data.data.
data.data.data.

Range

The range data type represents an immutable sequence of numbers. It is mainly used in for and while loops. It returns a sequence of numbers starting from a given number up to a number specified by the function argument. It is used as in the following command:

range(start, stop, step)

Here, the start argument specifies the start of the sequence, the stop argument specifies the end limit of the sequence, and the step argument specifies how the sequence should increase or decrease. This example Python code demonstrates the working of the range function:

print(list(range(10)))
print(range(10))
print(list(range(10)))
print(range(1,10,2))
print(list(range(1,10,2)))
print(list(range(20,10,-2)))

The output will be as follows.

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
range(0, 10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
range(1, 10, 2)
[1, 3, 5, 7, 9]
[20, 18, 16, 14, 12]

Lists

Python lists are used to store multiple items in a single variable. Duplicate values are allowed in a list, and elements can be of different types: for example, you can have both numeric and string data in a Python list.

The items stored in the list are enclosed within square brackets, [], and separated with a comma, as shown below:

a = ['food', 'bus', 'apple', 'queen']
print(a)
mylist  = [10, "India", "world", 8] 
# accessing elements in list.
print(mylist[1])

The output of the above code will be as follows.

['food', 'bus', 'apple', 'queen']
India

The data element of the list is shown in Figure 1.4, showing the index value of each of the list items:

Graphical user interface, text, application  Description automatically generated

Figure 1.4: Data elements of a sample list

The characteristics of a list in Python are as follows. Firstly, the list elements can be accessed by its index, as shown in Figure 1.4. The list elements are ordered and dynamic. It can contain any arbitrary objects that are so desired. In addition, the list data structure is mutable, whereas most of the other data types, such as integer and float are immutable.

Seeing as a list is a mutable data type, once created, the list elements can be added, deleted, shifted, and moved within the list.

All the properties of lists are explained in Table 1.1 below for greater clarity:

Property

Description

Example

Ordered

The list elements are ordered in a sequence in which they are specified in the list at the time of defining them. This order does not need to change and remains innate for its lifetime.

[10, 12, 31, 14] == [14, 10, 31, 12]
False

Dynamic

The list is dynamic. It can grow or shrink as needed by adding or removing list items.

b = ['data', 'and', 'book', 'structure', 'hello', 'st']
b += [32]
print(b)
b[2:3] = []
print(b)
del b[0]
print(b)
['data', 'and', 'book', 'structure', 'hello', 'st', 32]
['data', 'and', 'structure', 'hello', 'st', 32]
['and', 'structure', 'hello', 'st', 32]

List elements can be any arbitrary set of objects

List elements can be of the same type or varying data types.

a = [2.2, 'python', 31, 14, 'data', False, 33.59]
print(a)
[2.2, 'python', 31, 14, 'data', False, 33.59]

List elements can be accessed through an index

Elements can be accessed using zero-based indexing in square brackets, similar to a string. Accessing elements in a list is similar to strings; negative list indexing also works in lists. A negative list index counts from the end of the list.

Lists also support slicing. If abc is a list, the expression abc[x:y] will return the portion of elements from index x to index y (not including index y)

a = ['data', 'structures', 'using', 'python', 'happy', 'learning']
print(a[0])
print(a[2])
print(a[-1])
print(a[-5])
print(a[1:5])
print(a[-3:-1])
data
using
learning
structures
['structures', 'using', 'python', 'happy']
['python', 'happy']

Mutable

Single list value: Elements in a list can be updated through indexing and simple assignment.

Modifying multiple list values is also possible through slicing.

a = ['data', 'and', 'book', 'structure', 'hello', 'st']
print(a)
a[1] = 1
a[-1] = 120
print(a)
a = ['data', 'and', 'book', 'structure', 'hello', 'st']
print(a[2:5])
a[2:5] = [1, 2, 3, 4, 5]
print(a)
['data', 'and', 'book', 'structure', 'hello', 'st']
['data', 1, 'book', 'structure', 'hello', 120]
['book', 'structure', 'hello']
['data', 'and', 1, 2, 3, 4, 5, 'st']

Other operators

Several operators and built-in functions can also be applied in lists, such as in, not in, concatenation (+), and replication (*) operators. Moreover, other built-in functions, such as len(), min(), and max(), are also available.

a = ['data', 'structures', 'using', 'python', 'happy', 'learning']
print('data' in a)
print(a)
print(a + ['New', 'elements'])
print(a)
print(a *2)
print(len(a))
print(min(a))
['data', 'structures', 'using', 'python', 'happy', 'learning']
['data', 'structures', 'using', 'python', 'happy', 'learning', 'New', 'elements']
['data', 'structures', 'using', 'python', 'happy', 'learning']
['data', 'structures', 'using', 'python', 'happy', 'learning', 'data', 'structures', 'using', 'python', 'happy', 'learning']
6
data

Table 1.1: Characteristics of list data structures with examples

Now, while discussing list data types, we should first understand different operators, such as membership, identity, and logical operators, before discussing them and how they can be used in list data types or any other data types. In the coming section, we discuss how these operators work and are used in various data types.

Membership, identity, and logical operations

Python supports membership, identity, and logical operators. Several data types in Python support them. In order to understand how these operators work, we’ll discuss each of these operations in this section.

Membership operators

These operators are used to validate the membership of an item. Membership means we wish to test if a given value is stored in the sequence variable, such as a string, list, or tuple. Membership operators are to test for membership in a sequence; that is, a string, list, or tuple. Two common membership operators used in Python are in and not in.

The in operator is used to check whether a value exists in a sequence. It returns True if it finds the given variable in the specified sequence, and False if it does not:

# Python program to check if an item (say second 
# item in the below example) of a list is present 
# in another list (or not) using 'in' operator
mylist1 = [100,20,30,40]
mylist2 = [10,50,60,90]
if mylist1[1] in mylist2:
    print("elements are overlapping") 
else:
    print("elements are not overlapping")

The output will be as follows:

elements are not overlapping

The ‘not in' operator returns to True if it does not find a variable in the specified sequence and False if it is found:

val = 104
mylist = [100, 210, 430, 840, 108]
if val not in mylist:
    print("Value is NOT present in mylist")
else:
    print("Value is  present in mylist")

The output will be as follows.

Value is NOT present in mylist

Identity operators

Identity operators are used to compare objects. The different types of identity operators are is and is not, which are defined as follows.

The is operator is used to check whether two variables refer to the same object. This is different from the equality (==) operator. In the equality operator, we check whether two variables are equal. It returns True if both side variables point to the same object; if not, then it returns False:

Firstlist = []
Secondlist = []
if Firstlist == Secondlist: 
    print("Both are equal")
else:
    print("Both are not equal")
if Firstlist is Secondlist:
    print("Both variables are pointing to the same object")
else:
    print("Both variables are not pointing to the same object")
thirdList = Firstlist
if thirdList is Secondlist:
    print("Both are pointing to the same object")
else:
    print("Both are not pointing to the same object")

The output will be as follows:

Both are equal
Both variables are not pointing to the same object
Both are not pointing to the same object

The is not operator is used to check whether two variables point to the same object or not. True is returned if both side variables point to different objects, otherwise, it returns False:

Firstlist = []
Secondlist = []
if Firstlist is not Secondlist: 
  print("Both Firstlist and Secondlist variables are the same object")
else:
  print("Both Firstlist and Secondlist variables are not the same object")

The output will be as follows:

Both Firstlist and Secondlist variables are not the same object

This section was about identity operators. Next, let us discuss logical operators.

Logical operators

These operators are used to combine conditional statements (True or False). There are three types of logical operators: AND, OR, and NOT.

The logical AND operator returns True if both the statements are true, otherwise it returns False. It uses the following syntax: A and B:

a = 32
b = 132
if a > 0 and b > 0:
  print("Both a and b are greater than zero") 
else:
  print("At least one variable is less than 0")

The output will be as follows.

Both a and b are greater than zero

The logical OR operator returns True if any of the statements are true, otherwise it returns False. It uses the following syntax: A or B:

a = 32
b = -32
if a > 0 or b > 0:
  print("At least one variable is greater than zero")
else:
  print("Both variables are less than 0")

The output will be as follows.

At least one variable is greater than zero

The logical NOT operator is a Boolean operator, which can be applied to any object. It returns True if the object/operand is false, otherwise it returns False. Here, the operand is the unary expression/statement on which the operator is applied. It uses the following syntax: not A:

a = 32
if not a:
  print("Boolean value of a is False")
else:
  print("Boolean value of a is True")

The output will be as follows.

Boolean value of a is True

In this section, we learned about different operators available in Python, and also saw how membership and identity operators can be applied to list data types. In the next section, we will continue discussing a final sequence data type: tuples.

Tuples

Tuples are used to store multiple items in a single variable. It is a read-only collection where data is ordered (zero-based indexing) and unchangeable/immutable (items cannot be added, modified, removed). Duplicate values are allowed in a tuple, and elements can be of different types, similar to lists. Tuples are used instead of lists when we wish to store the data that should not be changed in the program.

Tuples are written with round brackets and items are separated by a comma:

tuple_name = ("entry1", "entry2", "entry3")

For example:

my_tuple = ("Shyam", 23, True, "male")

Tuples support + (concatenation) and * (repetition) operations, similar to strings in Python. In addition, a membership operator and iteration operation are also available in a tuple. Different operations that tuples support are listed in Table 1.2:

Expression

Result

Description

print(len((4,5, "hello")))
3

Length

print((4,5)+(10,20))
(4,5,10,20)

Concatenation

print((2,1)*3)
(2,1,2,1,2,1)

Repetition

print(3 in ('hi', 'xyz',3))
True

Membership

for p in (6,7,8):  
   print(p)
6,7,8

Iteration

Table 1.2: Example of tuple operations

Tuples in Python support zero-based indexing, negative indexing, and slicing. To understand it, let’s take a sample tuple, as shown below:

x = ( "hello", "world", " india")

We can see examples of zero-based indexing, negative indexing, and slicing operations in Table 1.3:

Expression

Result

Description

print(x[1])
"world"

Zero-based indexing means that indexing starts from 0 rather than 1, and hence in this example, the first index refers to the second member of the tuple.

print(x[-2])
"world"

Negative: counting from the right-hand side.

print(x[1:])
("world", "india")

Slicing fetches a section.

Table 1.3: Example of tuple indexing and slicing