#### 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.
Preface
Free Chapter
Python Data Types and Structures
Introduction to Algorithm Design
Algorithm Design Techniques and Strategies
Stacks and Queues
Trees
Heaps and Priority Queues
Hash Tables
Graphs and Algorithms
Searching
Sorting
Selection Algorithms
String Matching Algorithms
Other Books You May Enjoy
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:

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