Introduction to Data Structures and Algorithms With Python

This article is a continuation of Python 101: Introduction to Modern Python where we introduced, set up and gave some basic understanding of the python. In this article we will discuss about the various data structures in Python such as lists, dictionaries, tuples, sets, queues, stack, linked list etc.

What is a data Structure?

This is a particular way of organizing data in computer so that it can be accessed/used/processed effectively.

What is a data Algorithm?

This is a finite sequence of steps/instructions on how to perform a task, run an obligation or solve a problem.
Its Important in that it can enable one to estimate the amount of resources that will be needed during implementation.

Types of Data Structures in Python

Data structures in python are divided into 2:

• Inbuilt data structure: These types of data structures include lists, dictionaries, tuples, sets.
• User-defined Data structures: These types of data structures includes queues, stack, linked list,tree,linked-list, graph and HashMap.

They can also be categorized into linear or non-linear data structures where in Linear data structures the arrangements of data is in sequence manner e.g List, Linked-list, Queue, Stack etc while in Non-linear structures one element or node is connected to 'n' number of elements e.g tree and graphs.

List

Python Lists are just like the arrays, declared in other languages which is an ordered collection of data. It is very flexible as the items in a list do not need to be of the same type.

The implementation of Python List is similar ArrayList in JAVA. The costly operation is inserting or deleting the element from the beginning of the List as all the elements are needed to be shifted.These two operation usually takes order on n, i.e O(n) meaning the larger the size the longer the time taken.

Example of a list in Python is as shown below.

Python 3.9.9 (main, Dec 16 2021, 23:13:29) 
[GCC 11.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> mylist = ["Jeff", 44, 2.3, "Ous"]
>>> print(mylist)

Output

['Jeff', 44, 2.3, 'Ous']

List elements are accessed by the assigned index.Starting index of the list is 0 and the ending index is n-1 where n is the number of elements.
E.g to access Jeff in the above example we use 0
print(mylist[0]) this will output Jeff and print(mylist[2]) will output 2.3.
Adding Elements

Adding the elements in the list can be achieved using the append(), extend() and insert() functions.
The append() function adds all the elements passed to it as a single element.
The extend() function adds the elements one-by-one into the list.
The insert() function adds the element passed to the index value and increase the size of the list too.

mylist.append(12)
mylist.extend("Smart")
mylist.insert(1, "Lux")
print(mylist)

Output:

['Jeff', 'Lux', 44, 2.3, 'Ous', 12, 'S', 'm', 'a', 'r', 't']

Other methods associated with List are del() for deletion, len() function returns the length of the list,index() function that finds the index value of value passed where it has been encountered, count() function finds the count of the value passed to it, sorted() and sort() functions sort the values of the list and sorted() has a return type whereas the sort() modifies the original list.

Dictionaries

Dictionaries are used to store key-value pairs. It is an unordered collection of data values, used to store data values like a map. Key-value is provided in the dictionary to make it more optimized.

Indexing of Python Dictionary is done with the help of keys. These are of any hashable type. We can create a dictionary by using curly braces ({}) or dictionary.

Sample Code:

Python 3.9.9 (main, Dec 16 2021, 23:13:29) 
[GCC 11.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> dictionary = {1: "Jeff Odhiambo",2:"Lux Academy",3:"Laurent Ous"}
>>> print(dictionary)

Output:

{1: 'Jeff Odhiambo', 2: 'Lux Academy', 3: 'Laurent Ous'}

Accessing individual elements in a dictionary we can use the key e.g we can use 1 to access Jeff Odhiambo e.g run print(dictionary.get(<key>)) i.e print(dictionary.get(1)) will print Jeff Odhiambo,print(dictionary.get(2)) will print Lux Academy.

>>> print(dictionary.get(1))
Jeff Odhiambo
>>> print(dictionary.get(2))
Lux Academy 
>>> print(dictionary.get(3))
Laurent Ous
>>> 

Tuples

A tuple is an immutable data type in python, almost similar to a list in python in terms of indexing and having duplicate members. It stores python objects separated by commas.
Following is an example of how we can create or declare a tuple in python.

>>> tuple1=("Jeff","LUX")
>>> tuple2=(23,78)
>>> print(tuple1+tuple2)

Output

('Jeff', 'LUX', 23, 78)
>>> 

Accessing items in a tuple is similar to a list, we can access elements in a tuple using indexes. We can specify the index value and it will return the item stored at that particular index value. e.g print(tuple1[0]) will output Jeff.
Other operations such as slicing using the slicing operator :, changing, concatenating two tuples, deletion can be performed on a tuple.

Sets

A set is a data type consisting of a collection of unordered elements. These elements can be on any data types as sets, i.e they are not type specific. Sets are mutable(changeable) and do not have repeated copies of elements. The values of a set are unindexed, therefore, indexing operations cannot be performed on sets.

Sample Code:

>>> set1={1.2,56,"Jeff",'G'}
>>> print(set1)
{56, 1.2, 'Jeff', 'G'}

When you try to access an object using index in a set you get 'set' object is not subscriptable, this confirms the point that indexing operation cant be performed on set.

>>> print(set1[1])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'set' object is not subscriptable
>>> 

Since value in set can't be accessed using index, we can loop through it to access elements and display them as shown below.

>>> for setvalues in set1:
...     print(setvalues)
... 
56
1.2
Jeff
G
>>> 

We can also add values to set using the update() method, remove items in the set using remove(), discard() and the pop() functions, etc.

Queues

A queue is also a linear data structure that stores items in First In First Out (FIFO) manner. With a queue the least recently added item is removed first. A good example of queue is in one of the Operating system algorithm known as FIFO where the First process in the queue is the first to be executed. Or in real world, Queuing for service at a bank, you'll be served on the basis of first come first server.

Operations Associated with Queue

Enqueue: Adds an item to the queue.
Dequeue: Removes an item from the queue.
Front: Get the front item from queue.
Rear: Get the last item from queue.

Implementation using List

┌──(jeff㉿kali)-[~]
└─$ python3 
Python 3.9.9 (main, Dec 16 2021, 23:13:29) 
[GCC 11.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> queue = []
>>> queue.append("Jeff")
>>> queue.append("12")
>>> queue.append("LUX")
>>> queue.append(45.7)
>>> print(f"Initial Queue is {queue}")
Initial Queue is ['Jeff', '12', 'LUX', 45.7]
>>> queue.pop(0)
'Jeff'
>>> queue.pop(0)
'12'
>>> queue.pop(0)
'LUX'
>>> queue.pop(0)
45.7
>>> print(f"Queue after removing element: {queue}")
Queue after removing element: []
>>> 

Stack

A stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) manner. In stack, a new element is added ontop of the other e.g 1 is added ontop of 2 and while removing you have to start with the top most element e.g 1 is removed first followed by 2. The insert and delete operations are often called push and pop.

Associated Operations with Stack:

empty() – Returns whether the stack is empty.
size() – Returns the size of the stack.
top() – Returns a reference to the topmost element of the stack.
push(a) – Inserts the element ‘a’ at the top of the stack.
pop() – Deletes the topmost element of the stack.

Implementation using List

>>> stack = []
>>> stack.append("Jeff")
>>> stack.append("12")
>>> stack.append("LUX")
>>> stack.append(45.7)
>>> print(f"Initial stack : {stack}")
Initial stack : ['Jeff', '12', 'LUX', 45.7]
>>> stack.pop()
45.7
>>> stack.pop()
'LUX'
>>> stack.pop()
'12'
>>> stack.pop()
'Jeff'
>>> print(f"Stack after elements are removed : {stack}")
Stack after elements are removed : []
>>> 

Linked list

A linked list is a sequence of data elements, which are connected together via links. Each data element contains a connection to another data element in form of a pointer as shown below.

There are 4 types of linked list:

• Singly linked lists.
• Doubly linked lists.
• Circular linked lists.
• Circular doubly linked lists.

Implementation of Linked List

class Node:
    def __init__(self, data):
        self.data = data  # Assign data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def printList(self):
        temp = self.head
        while (temp):
            print (temp.data)
            temp = temp.next

if __name__=='__main__':
    linked_list = LinkedList()

    linked_list.head = Node("Jeff")
    second = Node(27)
    third = Node("LUX")

    linked_list.head.next = second;
    second.next = third;

    linked_list.printList()

Output

Jeff
27
LUX