Owino

Posted on

# Introduction to Data Structures and Algorithms With Python

Following my previous post on Python concepts Python 101: Ultimate Python Guide, I am excited to dive into the following aspects of python.

A Data structure is a method of organizing data in a system. Think of sequences of number, or tables of data: these are both well-defined data structures.
Python data structures are: Lists, Dictionaries, Tuples and Sets.

An Algorithm is a sequence of steps executed by a computer that takes some input and transforms into a target output.
Examples of algorithms that we will discuss in Python are: Queues, Stacks and Linked Lists.

Data structures:
I had covered some of these data structured but for those who haven't visited my previous post Python 101: Ultimate Python Guide, let's look at them.
1 - Lists
Lists in python is in other terms what other programming languages call arrays. Lists are mutable i.e. their elements can be changed, removed, new ones added etc.
Lists are used if you have collection of data that does not need random access.
The elements in a list are enclosed in square "[]" brackets. see below examples:
Here we declare a list named myFriends and use it.

``````myFriends = ["Mike", "John", "Peter", "Lenny", "Peter"]
print(myFriends)
``````

When we run our python program it will print out the below:

``````['Mike', 'John', 'Peter', 'Lenny', 'Peter']
``````

To count all my friends called 'Peter':

``````print(myFriends.count("Peter"))
``````

Output:

``````2
``````

Let's insert a friend to the list at index 1 of the list and print the list again:

``````print(myFriends.insert(1,"Arnold"))
print(myFriends
``````

output:

``````['Mike', 'Arnold', 'John', 'Peter', 'Lenny', 'Peter']
``````

Let's remove Friend 'Lenny' from the list and print the list once more:

``````print(myFriends.remove("Lenny"))
print(myFriends)
``````

Output:

``````['Mike', 'Arnold', 'John', 'Peter', 'Peter']
``````

Feel free to try out other list functions available in Python such as: clear(), copy(), extend(), index(), pop(), reverse() and sort().

2 - Dictionaries
Dictionaries are used to store data in key:value format.
Dictionaries are mutable.
You will need to use dictionaries if:
i - You need logical association between a key-value pair data.
ii - You need first lookup of your data based on a key.
iii - Your data is constantly being modified.
See below code:

``````student = {
"firstName" : "Mark",
"Age" : 23,
"Hobby" : "Soccer"
}
print(student)
``````

The output will be:

``````{'firstName': 'Mark', 'Age': 23, 'Hobby': 'Soccer'}
``````

To print out the value of key Hobby in the student dictionary:

``````print(student["Hobby"])
#also the below code will do the same
print(student.get("Hobby"))
``````

Output:

``````Soccer
``````

3 - Tuples
Tuples are similar to list but their contents cannot be changed; they are immutable.
Therefore tuples are used for cases where the data does not need to be changed e.g. geographical coordinates etc.
The elements in a tuple are enclosed in round brackets "()".
See below example with our tuple named daysOfTheWeek.

``````daysOfTheWeek = ("Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday")
print(daysOfTheWeek)
``````

The output when we run above:

``````('Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday')
``````

To print the third element of the tuple:

``````print(daysOfTheWeek[3])
``````

Output:

``````Wednesday
``````

If we try to change any element of the tuple e.g. assigning a new value to element at index 1:

``````daysOfTheWeek[1] = "Friday"
``````

Python will throw the following TypeError since elements in a tuple cannot be changed (tuples are immutable):

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

4 - Sets
Sets are unordered collections of unique objects.
Items in the set are unordered so they cannot be indexed, it either an item is in the set or not.
Sets elements are defined in curl braces "{}".
Sets are used if you need uniqueness of the elements.
Let's declare a set and print:

``````basket ={'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
``````

The printout will remove duplicates and only unique items will be displayed i.e.

``````{'pear', 'apple', 'banana', 'orange'}
``````

We can add an item to a set and print the current set:

``````basket.add('Pineapple')
``````

Here you can see we now have an additional element to the set being shown:

``````{'Pineapple', 'pear', 'apple', 'orange', 'banana'}
``````

There are other set functions like clear(), pop(), copy(), difference(), discard(), intersection(), issubset(), issuperset() etc please try them out.

Algorithms:
1 - Queues
A queue is a linear data structure that stores its elements in FIFO (First-In/First-out) manner.
Just like a queue of customers to be served in a supermarket, the ones who came first will be served first.
Python list is used as a way of implementing queues. The list’s append() and pop() methods can insert and delete elements from the queue.
Lets initialize an empty queue, add three element and prints it out:

``````myQueue = []

myQueue.append('Duncan')
myQueue.append('Owino')
myQueue.append('Mwamba')

print(myQueue)
``````

We can now see our queue has elements:

``````['Duncan', 'Owino', 'Mwamba']
``````

Lets dequeue (remove) elements from the queue:

``````myQueue.pop(0)
myQueue.pop(0)
myQueue.pop(0)

print(myQueue)
``````

Now we have our queue as empty:

``````[]
``````

2 - Stack
A stack is a linear data structure that stores items in LIFO (Last-In/First-Out) or FILO (First-In/Last-Out).
In a stack, a new element is added at one end and the element is removed from that end only.
The insert operation is called append() while the delete operation is called pop().

Lets declare an empty stack and append three elements into it and print the stack:

``````myStack = []

myStack.append('Duncan')
myStack.append('Owino')
myStack.append('Mwamba')
print(myStack)
``````

The output will be:

``````['Duncan', 'Owino', 'Mwamba']
``````

Now lets pop an element from the stack and print the stack:

``````myStack.pop()
print(myStack)
``````

The elements of the stack now are:

``````['Duncan', 'Owino']
``````

As you can see we have deleted element ['Mwamba'] from the stack.

Other operation/functions with stacks are: empty(), size(), top() etc. Please try them out.
A Linked list is an ordered collection of objects called nodes.
Each element of a linked list is called a node.
Every node has two different fields:

Data : This contains the value to be stored in the node.
Next : This contains a reference to the next node on the list.

Here’s what a typical node looks like:

The first node is called the head, and it’s used as the starting point for any iteration through the list. The last node must have its next reference pointing to None to determine the end of the list.
Therefore here is how a linked list looks:

There are many other algorithms that can be explored i.e. Hashtable, tree, graphs, sorting and searching, greedy algorithm ...