Evans Mutwiri

Posted on

Introduction to Data Structures and Algorithms With Python

This post will help you guys understand the fundamentals of data structures and algorithms.

Data is bits of information. We store them so we can use them later. It’s like putting clothes in a drawer. The drawer is the data structure.

Data structures are a way of storing and organizing data efficiently. This will allow you to easily access and perform operations on the data. They define the relationship between the data, and the operations that can be performed on the data.
This defination will guide the approach of this post to make us understand data structures better and to work with the more effectively using Python.

Types of Data Structures in Python

They can be mainly classified into two types as shown in this diagram:

TL,DR:

1. Python Built-in data structures: These are the data structures that come along with Python and can be implemented same as primitive data types like integers, etc. These can be further classified into:

a. Lists
b. Sets
c. Tuples
d. Dictionaries

1. Python User-defined data structures: These data structures are the ones built using the built-in data structures and have their own properties. Based on these features, these are used in suitable situations. These can be subdivided into:

a. Stacks
b. Queues
d. Hash Maps
e. Trees
f. Graphs

Having known the types, we will define a data structure and work with each in detail.

Data Structure #1: Lists

A list is a data structure in Python that is a mutable, or changeable, ordered sequence of elements.
Lists are among the 4 built in data structures in Python, used to store collections of data.
Just as strings are defined as characters between quotes, lists are defined by having values between square brackets [ ].

``````droids = ['C-3P0', 'IG-88', 'R2-D2', 'R5-4', 'BB-8']

print(droids)
``````

`Output: ['C-3P0', 'IG-88', 'R2-D2', 'R5-4', 'BB-8']`

Each element or value that is inside of a list is called an item. Items in a list are separated using a comma. List items are indexed, the first item has index [0], the second item has index [1] etc.

We can call a specific droid(a item of the list) by referring to its index number:

```droids[0] = 'C-3P0' droids[1] = 'IG-88' droids[2] = 'R2-D2' droids[3] = 'R5-4' droids[4] = 'BB-8'```

If we call an index number greater than 4 say:

``````print(droids[6])
``````

the program will throw an error because the index number is out of bounds.
`Output: IndexError: list index out of range`

List items can also be accessed using negative indexes. For instance `droids[-1]` can be used to access the last item in a list and so on till the first item.

``````print(droids[-3])
``````

`Output: R2-D2`

List items are ordered, changeable, and allow duplicate values. When we say lists are ordered, it means that the items have a defined order, and that order will not change. If you add new items to a list, the new items will be placed at the end of the list.

Lists let you save lots of things in a single variable. A list can be of any data type, and can contain different data types. A list can store numbers, booleans or even other lists! Since lists are indexed they allow duplicate values.

``````fruits = ["apple", "banana", "cherry", "apple", "cherry"]
print(fruits)
``````

To determine the number of items a list has, use the len() function:

``````print (len(fruits))
``````

`Output: 4`

You can definetly do alot more with lists using list methods and functions available in Python 3..

Data Structure #2: Tuples in Python

Tuples are used to store multiple items in a single variable. Just like a list it is also a sequence data type capable of containing elements of multiple data types. In other words, a tuple refers to a collection of various objects(items) that stay separated by commas, and enclosed in rounded brackets(). A tuple is comparatively much faster than a list because it is static in nature.

``````fruits_tuple = ("apple", "banana", "cherry")
print(fruits_tuple)

fruits_tuple = tuple(("apple", "banana", "cherry")) # note the double round-brackets
print(fruits_tuple)

// brackets are actually optional
weekdays = "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"
print(weekdays)
``````

Output:

``````("apple", "banana", "cherry")

("apple", "banana", "cherry")

("Monday", "Tuesday", "Wednesday", "Thursday", "Friday")
``````

If, for some reason, you need to create a tuple with a single item, you need to include a comma, otherwise you'll end up with a string.

They differ from lists in a number of ways as shown in the figure below:

Tuples are used to pass arguments and return results from functions. This is because they can contain multiple elements and are immutable.
Tuples are also good for storing closely related data. For example, (x, y, z) coordinates or (r, g, b) colour components can be stored as tuples.
Tuple values cannot be modified.

`fruits_tuple[0] = 'mango'`

``````---------------------------------------------------------------------------

TypeError                                 Traceback (most recent call last)

<ipython-input-74-b5d6da8c1297> in <module>()
----> 1 fruits_tuple[0] = 0 # Cannot change values inside a tuple

TypeError: 'tuple' object does not support item assignment
``````

You can actually make changes to a tuple by converting it to a list using list(). And when you are done making the changes, you can again convert it back to a tuple using tuple().

This change, is resource expensive as it involves making a copy of the tuple. Use lists instead if values can change during the lifetime of the object.

To append the values, you use the ‘+’ operator which will take another tuple to be appended to it.

``````my_tuple = (1, 2, 3)
my_tuple = my_tuple + (4, 5, 6) #add elements
print(my_tuple)
``````

`Output: (1, 2, 3, 4, 5, 6)`

Data Structure #3: Dictionary in Python

In Python, a dictionary is an ordered* collection of items, with each item consisting of a key: value pair (separated by a colon). Dictionaries changeable and do not allow duplicates.

*As of Python version 3.7, dictionaries are ordered. In Python 3.6 and earlier, dictionaries are unordered.Ref

A Dictionary is created by placing a sequence of elements within curly {} braces, separated by ‘comma’. Dictionary holds pairs of values, one being the Key and the other corresponding pair element being its Key:value.

``````d = {"Key1": "Value1", "Key2": "Value2"}
print(d)
print(type(d))
``````

Output:

``````{"Key1": "Value1", "Key2": "Value2"}
<class 'dict'>
``````

Another way of creating a dictionary is with the `dict()` function

``````d = dict({"Key1": "Value1", "Key2": "Value2"})
d = dict(Key1: Value1, Key2: Value2)
``````

There are a few important things to note when creating dictionaries in Python:

• Each key should be unique. Dictionaries do not support duplicate keys. They are however case sentive so similar keys written in different cases will be treated as different keys.

• Keys are immutable. That means you can use a data type that can't be changed such as strings, numbers, or even tuples as keys, but you can't use lists, or other dictionaries.

• These restrictions only apply only on keys not values.