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

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

## Dictionaries

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:

 Item Example Creating a dictionary, and accessing elements from a dictionary ``````person = {} print(type(person)) person['name'] = 'ABC' person['lastname'] = 'XYZ' person['age'] = 31 person['address'] = ['Jaipur'] print(person) print(person['name']) `````` ``````{'name': 'ABC', 'lastname': 'XYZ', 'age': 31, 'address': ['Jaipur']}ABC `````` `in` and `not` `in` operators ``````print('name' in person) print('fname' not in person) `````` ``````True True `````` Length of the dictionary ``````print(len(person)) `````` ``````4 ``````

Table 1.4: Characteristics of dictionary data structures with examples

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

 Function Description Example `mydict.clear()` Removes all elements from a dictionary. ``````mydict = {'a': 1, 'b': 2, 'c': 3} print(mydict) mydict.clear() print(mydict) `````` ``````{'a': 1, 'b': 2, 'c': 3} {} `````` `mydict.get()` 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} print(mydict.get('b')) print(mydict) print(mydict.get('z')) `````` ``````2 {'a': 1, 'b': 2, 'c': 3} None `````` `mydict.items()` Returns a list of dictionary items in (key, value) pairs. ``````print(list(mydict.items())) `````` ``````[('a', 1), ('b', 2), ('c', 3)] `````` `mydict.keys()` Returns a list of dictionary keys. ``````print(list(mydict.keys())) `````` ``````['a', 'b', 'c'] `````` `mydict.values()` Returns a list of dictionary values. ``````print(list(mydict.values())) `````` ``````[1, 2, 3] `````` `mydict.pop()` If a given key is present in the dictionary, then this function will remove the key and return the associated value. ``````print(mydict.pop('b')) print(mydict) `````` ``````{'a': 1, 'c': 3} `````` `mydict.popitem()` 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} print(mydict.popitem()) print(mydict) `````` ``````{'a': 1, 'b': 2} `````` `mydict.update()` 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} print(d1.update(d2)) print(d1) `````` ``````{'a': 10, 'b': 200, 'c': 30, 'd': 400} ``````

Table 1.5: List of methods of dictionary data structures

## Sets

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'])
print(x1)
print(type(x1))
x2 = {'and', 'python', 'data', 'structure'}
print(x2)
``````

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(len(x))
print('structure' in x)
``````

The output will be as follows:

``````4
True
``````

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:

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:

 Description 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 print(x3) print(x1.union(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.intersection(x2)) print(x1 & x2) `````` ``````{'data'} {'data'} `````` 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.difference(x2)) print(x1 - x2) `````` ``````{'structure'} {'structure'} `````` 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.symmetric_difference(x2)) 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.issubset(x2)) print(x1 <= x2) `````` ``````False False ``````

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'])
print(x)
``````

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}
print(x)
``````

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.