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)
Other Books You May Enjoy

Complex data types

We have discussed basic data types. Next, we discuss complex data types, which are mapping data types, in other words, dictionary, and set data types, namely, set and frozenset. We will discuss these data types in detail in this section.


In Python, a dictionary is another of the important data types, similar to a list, in the sense that it is also a collection of objects. It stores the data in unordered {key-value} pairs; a key must be of a hashable and immutable data type, and value can be any arbitrary Python object. In this context, an object is hashable if it has a hash value that does not change during its lifetime in the program.

Items in the dictionary are enclosed in curly braces, {}, separated by a comma, and can be created using the {key:value} syntax, as shown below:

dict = {
    <key>: <value>,
    <key>: <value>,
    <key>: <value>

Keys in dictionaries are case-sensitive, they should be unique, and cannot be duplicated; however, the values in the dictionary can be duplicated. For example, the following code can be used to create a dictionary:

my_dict = {'1': 'data', 
           '2': 'structure', 
           '3': 'python', 
           '4': 'programming', 
           '5': 'language' 

Figure 1.5 shows the {key-value} pairs created by the preceding piece of code:

Figure 1.5: Example dictionary data structure

Values in a dictionary can be fetched based on the key. For example: my_dict['1'] gives data as the output.

The dictionary data type is mutable and dynamic. It differs from lists in the sense that dictionary elements can be accessed using keys, whereas the list elements are accessed via indexing. Table 1.4 shows different characteristics of the dictionary data structure with examples:



Creating a dictionary, and accessing elements from a dictionary

person = {}
person['name'] = 'ABC'
person['lastname'] = 'XYZ'
person['age'] = 31
person['address'] = ['Jaipur']
<class 'dict'>{'name': 'ABC', 'lastname': 'XYZ', 'age': 31, 'address': ['Jaipur']}ABC

in and not in operators

print('name' in person)
print('fname' not in person)

Length of the dictionary


Table 1.4: Characteristics of dictionary data structures with examples

Python also includes the dictionary methods as shown in Table 1.5:





Removes all elements from a dictionary.

mydict = {'a': 1, 'b': 2, 'c': 3}
{'a': 1, 'b': 2, 'c': 3}


Searches the dictionary for a key and returns the corresponding value, if it is found; otherwise, it returns None.

mydict = {'a': 1, 'b': 2, 'c': 3}
{'a': 1, 'b': 2, 'c': 3}


Returns a list of dictionary items in (key, value) pairs.

[('a', 1), ('b', 2), ('c', 3)]


Returns a list of dictionary keys.

['a', 'b', 'c']


Returns a list of dictionary values.

[1, 2, 3]


If a given key is present in the dictionary, then this function will remove the key and return the associated value.

{'a': 1, 'c': 3}


This method removes the last key-value pair added in the dictionary and returns it as a tuple.

mydict = {'a': 1,'b': 2,'c': 3}
{'a': 1, 'b': 2}


Merges one dictionary with another. Firstly, it checks whether a key of the second dictionary is present in the first dictionary; the corresponding value is then updated. If the key is not present in the first dictionary, then the key-value pair is added.

d1 = {'a': 10, 'b': 20, 'c': 30}
d2 = {'b': 200, 'd': 400}
{'a': 10, 'b': 200, 'c': 30, 'd': 400}

Table 1.5: List of methods of dictionary data structures


A set is an unordered collection of hashable objects. It is iterable, mutable, and has unique elements. The order of the elements is also not defined. While the addition and removal of items are allowed, the items themselves within the set must be immutable and hashable. Sets support membership testing operators (in, not in), and operations such as intersection, union, difference, and symmetric difference. Sets cannot contain duplicate items. They are created by using the built-in set() function or curly braces {}. A set() returns a set object from an iterable. For example:

x1 = set(['and', 'python', 'data', 'structure'])
x2 = {'and', 'python', 'data', 'structure'}

The output will be as follows:

{'python', 'structure', 'data', 'and'}
<class 'set'>
{'python', 'structure', 'data', 'and'}

It is important to note that sets are unordered data structures, and the order of items in sets is not preserved. Therefore, your outputs in this section may be slightly different than those displayed here. However, this does not affect the function of the operations we will be demonstrating in this section.

Sets are generally used to perform mathematical operations, such as intersection, union, difference, and complement. The len() method gives the number of items in a set, and the in and not in operators can be used in sets to test for membership:

x = {'data', 'structure', 'and', 'python'}
print('structure' in x)

The output will be as follows:


The most commonly used methods and operations that can be applied to set data structures are as follows. The union of the two sets, say, x1 and x2, is a set that consists of all elements in either set:

x1 = {'data', 'structure'}
x2 = {'python', 'java', 'c', 'data'}

Figure 1.6 shows a Venn diagram demonstrating the relationship between the two sets:

Diagram, venn diagram  Description automatically generated

Figure 1.6: Venn diagram of sets

A description of the various operations that can be applied on set type variables is shown, with examples, in Table 1.6:


Example sample code

Union of two sets, x1 and x2. It can be done using two methods, (1) using the | operator, (2) using the union method.

x1 = {'data', 'structure'}
x2 = {'python', 'java', 'c', 'data'}
x3 = x1 | x2
{'structure', 'data', 'java', 'c', 'python'}
{'structure', 'data', 'java', 'c', 'python'}

Intersection of sets: to compute the intersection of two sets, an & operator and the intersection() method can be used, which returns a set of items common to both sets, x1 and x2.

print(x1 & x2)

The difference between sets can be obtained using .difference() and the subtraction operator, -, which returns a set of all elements that are in x1, but not in x2.

print(x1 - x2)

Symmetric difference can be obtained using .symmetric_difference() , while ^ returns a set of all data items that are present in either x1 or x2, but not both.

print(x1 ^ x2)
{'structure', 'python', 'c', 'java'}
{'structure', 'python', 'c', 'java'}

To test whether a set is a subset of another, use .issubset() and the operator <=.

print(x1 <= x2)

Table 1.6: Description of various operations applicable to set type variables

Immutable sets

In Python, frozenset is another built-in type data structure, which is, in all respects, exactly like a set, except that it is immutable, and so cannot be changed after creation. The order of the elements is also undefined. A frozenset is created by using the built-in function frozenset():

x = frozenset(['data', 'structure', 'and', 'python'])

The output is:

frozenset({'python', 'structure', 'data', 'and'})

Frozensets are useful when we want to use a set but require the use of an immutable object. Moreover, it is not possible to use set elements in the set, since they must also be immutable. Consider an example:

a11 = set(['data'])
a21 = set(['structure'])
a31 = set(['python'])
x1 = {a11, a21, a31}

The output will be:

TypeError: unhashable type: 'set'

Now with frozenset:

a1 = frozenset(['data'])
a2 = frozenset(['structure'])
a3 = frozenset(['python'])
x = {a1, a2, a3}

The output is:

{frozenset({'structure'}), frozenset({'python'}), frozenset({'data'})}

In the above example, we create a set x of frozensets (a1, a2, and a3), which is possible because the frozensets are immutable.

We have discussed the most important and popular data types available in Python. Python also provides a collection of other important methods and modules, which we will discuss in the next section.