Introduction to Data Structures and Algorithms With Python

Python provides data types that provides a flexible way to access and organize multiple data. They are called Data Structures. Data Structures are a specialized means of organizing and storing data in computers in such a way that we can perform operations on the stored data more efficiently.
A Data structure is a particular way of organizing data in a computer so that it can be used effectively. It is a specialized format for organizing, processing, retrieving and storing data.
Algorithm on the hand is a set of well-defined instructions in calculation or to solve a particular problem.

The basic Python data structures in Python include:

1. Lists
2. Tuples
3. Sets
4. Dictionaries

Their some data structures that are user-defined (not part of python data types). They include:

1. Stack - LIFO
2. Queues - FIFO
3. Linked Lists
4. Hash Tables
5. Trees
6. Graphs

1. Lists

A list is a value that contains multiple values in an ordered sequence. A list begins with an opening square bracket and ends with a closing square bracket, []. Values inside the list are also called items which are separated with commas. For example:

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
num = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

• To get individual values in a List we use Indexes. Example:

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
# subjects[0] will evaluate to Maths
print(subjects[0]) # Maths 
# subjects[1] will evaluate to Physics
print(subjects[0]) # Physics 

The integer inside the square brackets that follows the list is called an index. The first value in the list is at index 0 , the second value is at index 1 , the third value is at index 2 , and so on.

NOTE: Python will give you an IndexError error message if you use an index that exceeds the number of values in your list value.

• Lists can also contain other list values.

food = [['tea', 'coffee', 'water'], ['beef', 'pork', 'mutton', 'fish', 'chicken'], ['rice', 'pasta']]
beverage = food[0]
print(beverage) # ['tea', 'coffee', 'water']
# print individual value
print(food[1][3]) # 'fish'

The first index dictates which list value to use, and the second indicates the value within the list value. Example:
food[1][3] # 'fish'

• negative indexes

You can also use negative integers for the index. The integer value -1 refers to the last index in a list, the value -2 refers to the second-to-last index in a list, and so on. Example:

num = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
print(num[-1]) # 0
print(num[-2]) # 9
print(num[-5]) # 6

• Slicing a List to get a Sub-lists A slice can get several values from a list, in the form of a new list. A slice is typed between square brackets, like an index, but it has two integers separated by a colon.

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
print(subjects[1:4]) # ['Physics', 'Biology', 'Geography']

The first integer in a slice is the index where the slice starts. The second integer is the index where the slice ends but will not include it.

Leaving out the first index is the same as using 0 , or the beginning of the list. Leaving out the second index is the same as using the length of the list, which will slice to the end of the list.

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
print(subjects[:3]) # ['Maths', 'Physics', 'Biology']
print(subjects[3:]) # ['Geography', 'History']

• Changing Values in a List with Indexes

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subject[0] = 'Mathematics'
print(subject) # ['Mathematics', 'Physics', 'Biology', 'Geography', 'History']

• Adding two lists using + operator

core_subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
supplementary_subjects = ['Programming', 'Sports', 'Communication']
subjects = core_subjects + supplementary_subjects
print(subjects)  
['Maths', 'Physics', 'Biology', 'Geography', 'History', 'Programming', 'Sports', 'Communication']

• Replicating a list using * operator

num = [1, 3, 5]
print(num*3) # [1, 3, 5, 1, 3, 5, 1, 3, 5]

• Removing Values from Lists with del Statements

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
del subjects[2]
print(subjects) # ['Maths', 'Physics', 'Geography', 'History']

• Using for Loops with Lists

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
for sub in subjects:
    print(sub)

• The in and not in Operators You can determine whether a value is or isn’t in a list with the in and not in operators.

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']

print('Physics' in subjects) # True

print('Physics' not in subjects) # False

print('Programming' in subjects) # False

print('Programming' not in subjects) # True

• Getting a List’s Length with len()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
print(len(subjects))

• Multiple Assignment using Lists

You can assign multiple variables with the values in a list in one line of code.

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
maths, physics, bio, geo, history = subjects
print(geo) # 'Geography'
print (physics) # 'Physics'

• Converting Types with the list() Functions

line1 = 'hello'
line1_list = list(line1)
print(line1_list) # ['h', 'e', 'l', 'l', 'o']

subjects = ('History', 'Geography', 'Biology', 'Physics', 'Maths')
subjects = list(subjects) # ['History', 'Geography', 'Biology', 'Physics', 'Maths']

List Methods

append() - Adds an item to the end of the list.
clear() - Removes all items from the list, leaving it empty.
copy() - Makes a copy of a list.
count() - Counts how many times an element appears in a list.
extend() - Appends the items from one list to the end of another list.
index() - Returns the index number (position) of an element within a list.
insert() - Inserts an item into the list at a specific position.
pop() - Removes an element from the list, and provides a copy of that item that you can store in a variable.
remove() - Removes one item from the list.
reverse() - Reverses the order of items in the list.
sort() - Sorts the list in ascending order. Put reverse=True inside the parentheses to sort in descending order.

index()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
print(subject.index('Physics')) # 1

append()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subject.append('Programming') 
print(subject) # ['Maths', 'Physics', 'Biology', 'Geography', 'History', 'Programming']

insert()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subject.insert('Programming', 1) 
print(subject) # ['Maths', 'Programming', 'Physics', 'Biology', 'Geography', 'History']

remove()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subject.remove('Biology') 
print(subject) # ['Maths', 'Physics', 'Geography', 'History']

NOTE: If the value appears multiple times in the list, only the first instance of the value will be removed.

sort()

# Arrange in alphabetical order
subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subjects.sort() 
print(subjects) # ['Biology', 'Geography', 'History', 'Maths', 'Physics' ]

# Arrange in numeric order
random_num = [5, 5, 3, 8, 2, 1, 8, 0, 7]
random_num.sort() # [0, 1, 2, 3, 5, 5, 7, 8, 8]

• You can also pass True for the reverse keyword argument to have sort() sort the values in reverse order.

random_num = [5, 5, 3, 8, 2, 1, 8, 0, 7]
random_num.sort(reverse=True) # [8, 8, 7, 5, 5, 3, 2, 1, 0]

• you cannot sort lists that have both number values and string values in them, since Python doesn’t know how to compare these values.
• sort() uses “ASCIIbetical order” rather than actual alphabetical order for sorting strings. This means uppercase letters come before lower-case letters.

spam = ['Alice', 'ants', 'Bob', 'badgers', 'Carol', 'cats']
spam.sort() # ['Alice', 'Bob', 'Carol', 'ants', 'badgers', 'cats']

• you need to sort the values in regular alphabetical order, pass str.lower for the key keyword argument in the sort() method call.

spam = ['a', 'z', 'A', 'Z']
spam.sort(key=str.lower) # ['a', 'A', 'z', 'Z']

pop()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']

# remove last subject
last_subject = subjects.pop()
print(subjects) # ['Maths', 'Physics', 'Biology', 'Geography']
print(last_subject) # 'History'

# remove first subject
first_subject = subjects.pop(0)
print(subjects) # ['Physics', 'Biology', 'Geography']
print(first_subject) # 'Maths' 

count()

num = [5, 7, 8, 5, 3, 8, 5, 2, 1, 8, 5, 7]
num_count = num.count(5)
print(num_count) # 4

extend()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
supplementary_subjects = ['Programming', 'Sports', 'Communication']
subjects.extend(supplementary_subjects)
print(subjects) # ['Maths', 'Physics', 'Biology', 'Geography', 'History', 'Programming', 'Sports', 'Communication']

clear()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subjects.clear()
print(subjects) # [ ]

reverse()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subjects.reverse()
print(subjects) # ['History', 'Geography', 'Biology', 'Physics', 'Maths']

copy()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subject_copy = subjects.copy()
print(subject_copy) # ['Maths', 'Physics', 'Biology', 'Geography', 'History']

2. Tuple

A tuple is just an immutable list. In other words, a tuple is a list, but after it’s defined you can’t change it. Tuples are typed with parentheses, ( and ) , instead of square brackets, [ and ]. Example:

subjects = ('History', 'Geography', 'Biology', 'Physics', 'Maths')
num = (5, 7, 8, 5, 3, 8, 5, 2, 1, 8, 5, 7)

List methods and techniques that modified list data won't with tuple but other methods will work:

print(num.count(5)) # 4
print(type(subjects)) # <class 'tuple'>
print(len(num)) # 12
print('Physics' in subjects) # True

Converting to Tuple Types with tuple() Functions

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subjects = tuple(subjects)
print(subjects) # ('Maths', 'Physics', 'Biology', 'Geography', 'History')

3. Sets

Python Sets is also a means of organizing data. The difference between a set and a list is that the items in set have no specific order. Even though you may define the set with the items in a certain order, none of the items get index numbers to identify their positions.

To define a set, use curly braces where you would have used square brackets for a list and parentheses for a tuple. For example:

subjects = {'Maths', 'Physics', 'Biology', 'Geography', 'History'}
num = {5, 7, 8, 5, 3, 8, 5, 2, 1, 8, 5, 7}

You can’t change the order of items in a set, so you cannot use .sort() to sort the set or .reverse() to reverse its order. You can use len() to determine size of set and in operator to check if an item exists.

• add() - You can add a single new item to a set

subjects = {'Maths', 'Physics', 'Biology', 'Geography', 'History'}
subjects.add('Programming')
print(subjects) # {'Maths', 'Physics', 'Biology', 'Geography', 'History', 'Programming'}

• update() - add multiple items to a set

subjects = {'Maths', 'Physics', 'Biology', 'Geography', 'History'}
subjects.update(['Programming', 'Sports', 'Communication'])
print(subjects) # {'Maths', 'Physics', 'Biology', 'Geography', 'History', 'Programming', 'Sports', 'Communication'}

• copy() - replicate a set

subjects = {'Maths', 'Physics', 'Biology', 'Geography', 'History'}
subjects_copy = subjects.copy('Programming')
print(subjects_copy) # {'Maths', 'Physics', 'Biology', 'Geography', 'History'}

4. Dictionary

Like a list, a dictionary is a collection of many values, but unlike indexes for lists, indexes for dictionaries can use many different data types, not just integers. Indexes for dictionaries are called keys, and a key with its associated value is called a key-value pair.
In code, a dictionary is typed with braces, {}. Example:

person = {
"name": "Elkanah",
"gender": "Male",
"Height": "5.9 Foot",
"Weight": "67 kg",
}

• You can access these values through their keys:

print(person["name"]) # Elkanah
print(person["height"]) # 5.9 Foot

• Unlike lists, items in dictionaries are unordered. It does not matter in what order the key-value pairs are typed in a dictionary:

person = {"name": "Elkanah", "gender": "Male", "Height": "5.9 Foot","Weight": "67 kg",}
person2 = {"Height": "5.9 Foot", "name": "Elkanah", "Weight": "67 kg", "gender": "Male",}

print(person==person1) # True

• Changing the value of a key in dictionary

person = {"name": "Elkanah", "gender": "Male", "Height": "5.9 Foot","Weight": "67 kg",}
person["name"] = "Malonza"
print(person) # {"name": "Malonza", "gender": "Male", "Height": "5.9 Foot","Weight": "67 kg",}

Dictionary Methods

clear() - Empties the dictionary by remove all keys and values.
copy() - Returns a copy of the dictionary.
fromkeys() - Returns a new copy of the dictionary but with only specified keys and values.
get() - Returns the value of the specified key, or None if it doesn’t exist.
items() - Returns a list of items as a tuple for each key-value pair.
keys() - Returns a list of all the keys in a dictionary.
pop() - Removes the item specified by the key from the dictionary, and stores it in a variable.
popitem() - Removes the last key-value pair.
setdefault() - Returns the value of the specified key. If the key does not exist: insert the key, with the specified value.
update() - Updates the value of an existing key, or adds a new key-value pair if the specified key isn’t already in the dictionary.
values() - Returns a list of all the values in the dictionary.

• The keys(), values(), and items() Methods - will return list-like values of the dictionary’s keys, values, or both keys and values.

spam = {'color': 'red', 'age': 42}

v = spam.values()
print(v) # dict_values(['red', 42])

k = spam.keys()
print(k) # dict_keys(['color', 'age'])

kv = spam.items()
print(kv) # dict_items([('color', 'red'), ('age', 42)])

• The get() Method - takes two arguments: the key of the value to retrieve and a fallback value to return if that key does not exist.

picnicItems = {'apples': 5, 'cups': 2}
print(picnicItems.get('cups', 0)) # 2
print(get('cups', 0)) # 2

• The setdefault() Method - set a value in a dictionary for a certain key only if that key does not already have a value.

spam = {'name': 'Pooka', 'age': 5}

spam.setdefault('color', 'black')
print(spam) # {'color': 'black', 'age': 5, name: 'Pooka'}

spam.setdefault('color', 'white')
print(spam) # {'color': 'black', 'age': 5, name: 'Pooka'}

• update() method - to add a new item to a dictionary, or to change the value of a current key.

spam = {'name': 'Pooka', 'age': 5}

spam.update({'color': 'black'})
print(spam) # {'color': 'black', 'age': 5, name: 'Pooka'}

spam.update({'color': 'white'})
print(spam) # {'color': 'white', 'age': 5, name: 'Pooka'}

• copy() method - make a copy of a data dictionary to work with.

spam = {'name': 'Pooka', 'age': 5}
spam_copy = spam.copy()
print(spam_copy) # {name: 'Pooka', 'age': 5}

• clear() method - remove all key-value pairs from a dictionary without deleting the entire dictionary

spam = {'name': 'Pooka', 'age': 5}
spam.clear()
print(spam) # {}

• pop() method - Removes the item specified by the key from the dictionary, and stores it in a variable.

spam = {'color': 'Black', 'name': 'Pooka', 'age': 5}
color = spam.pop("color")
print(spam) # {name: 'Pooka', 'age': 5}
print(color) # Black

• popitem() method -Remove the last key-value pair from a dictionary

spam = {'color': 'Black', 'name': 'Pooka', 'age': 5}
color = spam.popitem()
print(spam) # {name: 'Pooka', 'age': 5}
print(color) # ('age', 5)

• fromkeys() method - Returns a new copy of the dictionary but with only specified keys and values

spam = {'color': 'Black', 'name': 'Pooka', 'age': 5}
spam1 = dict.fromkeys(spam.keys())
print(spam1) # {'color': None, 'name': None, 'age': None}

results = dict.fromkeys(['Maths', 'Physics', 'Biology', 'Geography', 'History'])
print(results) # {'Maths': None, 'Physics': None, 'Biology': None, 'Geography': None, 'History': None}

5. Stack

A stack is a linear data structure that follows the principle of Last In First Out (LIFO). This means the last element inserted inside the stack is removed. Stack has one end where the insertion and deletion happens i.e. from the top of the stack.
operation in stack data structures

• push() - Pushing (storing) an element on the stack
• pop() - Removing (accessing) an element from the stack
• peek() - get the top data element of the stack, without removing it.
• isEmpty() - check if stack is empty.
• isFull() - check if stack is full.

Example:

# Creating a stack
def stack():
    stack = []
    return stack

# Creating an empty stack
def isEmpty(stack):
    return len(stack) == 0

# Adding items into the stack
def push(stack, item):
    stack.append(item)
    print("pushed item: " + item)

# Removing an element from the stack
def pop(stack):
    if (isEmpty(stack)):
        return "stack is empty"
    return stack.pop()

stack = stack()
push(stack, "me")
push(stack, "we")
push(stack, "us")

print("popped item: " + pop(stack))
print("stack after popping an element: ", stack)

'''output
pushed item: me
pushed item: we
pushed item: us
popped item: us
stack after popping an element:  ['me', 'we']
'''

6. Queues

A Queue is a linear data structure that follows the principle of First In First Out (FIFO). This means the first element inserted inside the stack is removed first. Stack has two end where one is for insertion (enqueue) and the other is for deletion (dequeue).

operations in queue data structure

• enqueue() − add (store) an item to the queue.
• dequeue() − remove (access) an item from the queue.
• peek() − Gets the element at the front of the queue without removing it.
• isFull() − Checks if the queue is full.
• isEmpty() − Checks if the queue is empty.

Example:

class Queue:

    def __init__(self):
        self.queue = []

    # Add an element
    def enqueue(self, item):
        self.queue.append(item)

    # Remove an element
    def dequeue(self):
        if len(self.queue) < 1:
            return None

        return self.queue.pop(0)

    # Check the first element in a Queue
    def peek(self):
        if len(self.queue) < 1:
            return None

        return self.queue[0]

    # Check if the Queue is Empty
    def isEmpty(self):
        return len(self.queue) < 1

    # Display  the queue
    def display(self):
        print(self.queue)

    def size(self):
        return len(self.queue)

q = Queue()

q.enqueue(0)
q.enqueue(2)
q.enqueue(0)
q.enqueue(2)
q.enqueue(2)

q.peek()
q.display()

q.dequeue()

print("After removing an element")
q.peek()
q.display()

''' output
0
[0, 2, 0, 2, 2]

After removing an element
2
[2, 0, 2, 2]
'''

7. Linked List

linked list is a linear data structure where data are connected together via links. It consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

Operations in linked list

• Insertion − Adds an element at the beginning of the list.
• Deletion − Deletes an element at the beginning of the list.
• Display − Displays the complete list.
• Search − Searches an element using the given key.
• Delete − Deletes an element using the given key.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None


class SLinkedList:
    def __init__(self):
        self.headval = None

    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

# Link first Node to second node
list.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

list.listprint()
'''output
Mon
Tue
Wed
'''

8. Hash Tables

Hash table is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found.
In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data.

Operations in hash tables

• Search − Searches an element in a hash table.
• Insert − inserts an element in a hash table.
• delete − Deletes an element from a hash table.

Example

hashTable = [[],] * 10

def checkPrime(n):
    if n == 1 or n == 0:
        return 0

    for i in range(2, n//2):
        if n % i == 0:
            return 0

    return 1

def getPrime(n):
    if n % 2 == 0:
        n = n + 1

    while not checkPrime(n):
        n += 2

    return n

def hashFunction(key):
    capacity = getPrime(10)
    return key % capacity

def insertData(key, data):
    index = hashFunction(key)
    hashTable[index] = [key, data]

def removeData(key):
    index = hashFunction(key)
    hashTable[index] = 0

insertData(123, "make a circle")
insertData(456, "a big circle")
insertData(789, "like a sufuria")
print(hashTable)

removeData(123)
print(hashTable)

'''output

[[], [], [123, 'make a circle'], [], [], [456, 'a big circle'], [], [], [789, 'like a sufuria'], []]

[[], [], 0, [], [], [456, 'a big circle'], [], [], [789, 'like a sufuria'], []]

'''

9. Trees

Tree represents the nodes connected by edges, Binary tree or binary search tree to be specifically. Binary Tree is a special data structure used for data storage purposes. A binary tree has a special condition that each node can have a maximum of two children.

Terms used in Binary Tree.

• Path − Path refers to the sequence of nodes along the edges of a tree.
• Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.
• Parent − Any node except the root node has one edge upward to a node called parent.
• Child − The node below a given node connected by its edge downward is called its child node.
• Leaf − The node which does not have any child node is called the leaf node.
• Subtree − Subtree represents the descendants of a node.
• Visiting − Visiting refers to checking the value of a node when control is on the node.
• Traversing − Traversing means passing through nodes in a specific order.
• Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.
• keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

Operations in Binary Trees

• Insert − Inserts an element in a tree/create a tree.
• Search − Searches an element in a tree.
• Preorder Traversal − Traverses a tree in a pre-order manner.
• Inorder Traversal − Traverses a tree in an in-order manner.
• Postorder Traversal − Traverses a tree in a post-order manner.

10. Graphs

A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.
Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices.

Terminologies in Graphs

• Vertex − Each node of the graph is represented as a vertex. In the following example, the labeled circle represents vertices. Thus, A to G are vertices. We can represent them using an array as shown in the following image. Here A can be identified by index 0. B can be identified using index 1 and so on.
• Edge − Edge represents a path between two vertices or a line between two vertices. In the following example, the lines from A to B, B to C, and so on represents edges. We can use a two-dimensional array to represent an array as shown in the following image. Here AB can be represented as 1 at row 0, column 1, BC as 1 at row 1, column 2 and so on, keeping other combinations as 0.
• Adjacency − Two node or vertices are adjacent if they are connected to each other through an edge. In the following example, B is adjacent to A, C is adjacent to B, and so on.
• Path − Path represents a sequence of edges between the two vertices. In the following example, ABCD represents a path from A to D.

Operations in graphs

• Add Vertex − Adds a vertex to the graph.
• Add Edge − Adds an edge between the two vertices of the graph.
• Display Vertex − Displays a vertex of the graph.