Introduction to Data Structures and Algorithms With Python.

This is my second article after Introduction to Modern Python 101 which aims to discuss python data structures such as lists, tuples, sets, stack, dictionaries, queues, linked list among others. Data plays a very important role in different fields like machine learning, artificial intelligence and web development which means that the data should be organized in an orderly manner, stored correctly and accessible at any convenient time.
In this article you will be introduced to Python data structures: learn more about data structure, types of data structures in Python that is built-in data structures as well as user-defined data structures including List, Dictionary, Tuple, Sets, Stack, Queue etc.

Python Data Structures

Data structures are a way of organizing and storing data so that they can be accessed and worked with efficiently.
A structured data brings about structured variables which gives a clear definition on the relationship between the data and the operations that can be performed on the same data.
Data structuring is important in python since it makes it easier for the programmer, data scientist or computer engineer mainly think of the big picture of solving critical and larger problems by figuring out the best way to go through the program in an efficient way and making accurate modifications.

Types of Data Structures in Python

In python, there are built-in data types which supports the data structures which allows you to store a collection of data and be able to access them at the same time. They include List, Dictionary, Tuple and Set.
Consequently, Python also enables many programmers to write and develop their own functions hence having the ability to control the data. Data Structures like Stack, Queue, Tree, Linked List and others are readily available to you in other programming languages therefore you can create different data functions which can influence the entire data structure.

Lists

A list is a way to give a single name to a collection of values. These values or elements can have any data type; int, float, etc., and also more advanced Python types, even other lists.
Lists are used to store data of different data types in a sequential manner. There are addresses assigned to every element of the list, which is called as Index.
The index value starts from 0 and goes on until the last element called the positive index.
There is also negative indexing which starts from -1 enabling you to access elements from the last to first in the list.

Creating a list in Python

You use the square brackets and add elements into it accordingly separated by commas.
If you do not pass any elements inside the square brackets, you get an empty list as the output.

thislist = [1, 3, 5, 'Hello', 9.91] #creating list with data
print(thislist)

thislist = [] #create empty list
print(thislist)

Adding and Changing Elements

Adding the elements in the list is done by use of the append(), extend() and insert() functions whereas changing the elements is achieved by defining the list with new values and then refer to the range of index numbers where you want to insert the new values:

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.
List is mutable, meaning that you can change and add items without changing their identity in the list after it has been created.

thislist = [a, b, c]
print(thislist)

thislist.append([1, 2, 3]) #add as a single element
print(thislist)

thislist.extend([4, "Welcome", 2022]) #add as different elements
print(thislist)

thislist.insert(1, "adabracadabra") #add element i
print(thislist)

Deleting Elements

To delete elements, use the del keyword which is built-in into Python but this does not return any output since it has deleted the list.
If you want the element back, you use the pop() function which takes the index value.
To remove an element by its value, you use the remove() function.

mylist = ["Maths", "English", "CRE", "Biology", "Physics"]
del mylist[5] #delete element at index 2
print(mylist)

mylist.remove("CRE") #remove element with value
print(mylist)

z = mylist.pop(1) #pop element from list
print('Popped Element: ', z, ' List remaining: ', mylist)

mylist.clear() #empty the list
print(mylist)

Accessing Elements

List items are indexed and you can access them by passing the index values and hence can obtain the values as needed.

mylist = ["Maths", "English", "CRE", "Biology", "Physics", 90]
for element in my_list: #access elements one by one
     print(element)

print(mylist) #access all elements
print(mylist[4]) #access index 3 element
print(mylist[0:4]) #access elements from 0 to 3 and exclude 4
print(mylist[-1]) #access elements in reverse

Other important functions when handling Lists

The len() function returns to us the length of the list.
The index() function finds the index value of value passed where it has been encountered the first time.
The count() function finds the count of the value passed to it.
The sorted() and sort() functions do the same thing, that is to sort the values of the list. The sorted() has a return type whereas the sort() modifies the original list.

my_list = [10, 20, 30, 40, 50, 60, 70, 80, 90, 40]
print(len(my_list)) #find length of list
print(my_list.index(40)) #find index of element that occurs first
print(my_list.count(40)) #find count of the element
print(sorted(my_list)) #print sorted list but not change original

my_list.sort(reverse=True) #sort original list
print(my_list)

Tuple

Tuples are similar to lists where multiple elements are stored in a single variable are with the exception that once the data has been entered into the tuple then they are unchangeable( immutability).

Creating a Tuple

A tuple is created using parenthesis, () and commas to separate items or using the tuple() function.

tuple1 = (1, 2, 3, 4, 5, 6) #create tuple
tuple2 = ("Hello", 2019 , "Hi", [10, 20, 30]);
tuple3 = False, "a", "b", True #create tuple without parenthesis
print(tuple1)
print(tuple2)
print(tuple3)

Accessing Elements in a Tuple

You can access elements in a tuple items by referring to the index number inside of a square brackets.
In a tuple, accessing elements is the similar to accessing values in lists.

mytuple = (a, b, c, 'Hello world', 3.142, 9) #access elements
for x in mytuple:
    print(x)
print(mytuple)
print(mytuple[0])
print(mytuple[:])
print(mytuple[3][4])

Appending Elements in a Tuple

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

thistuple = (100, 200, 300)
thistuple = thistuple + (400, 500, 600) #add elements
print(thistuple)

Other functions in a Tuple

These functions are the same as they are for lists.

my_tuple = (a, b, c, ['Java', 'python', 'CSS', 'C++'])
my_tuple[3][0] = 'HTML' 

print(my_tuple)
print(my_tuple.count(2))
print(my_tuple.index(['Java', 'python', 'CSS', 'C++']))

Dictionary

Dictionary is a collection of items where each item of a dictionary has a key/value pair that stores data values in those key:value pairs.
Dictionaries are made up of key-value pairs. key is used to identify the item and the value of the item.
Keys are unique within a dictionary while values may not be. The values of a dictionary can be of any type, but the keys must be of an immutable data type such as strings, numbers, or tuples.
Dictionary items are presented in key:value pairs, and can be referred to by using the key name

Creating a Dictionary

Dictionaries can be created using the curly braces, {} or using the dict() function. You need to add the key-value pairs when you work with dictionaries.

my_dict = {} #empty dictionary
print(my_dict)

my_dict = {1: 'apple', 2: 'banana'} #dictionary with elements
print(my_dict)

Changing and Adding key, value pairs

To change the values of the dictionary, you need to do that using the keys. So, you firstly access the key and then change the value accordingly. To add values, you simply just add another key-value pair as shown below.

mydict = {'First': 'Python', 'Second': 'Java', 'Third': 'CSS'}
print(mydict)

mydict['Second'] = 'HTML' #changing element
print(mydict)

mydict['Forth'] = 'C++' #adding key-value pair
print(mydict)

Deleting key, value pairs

To delete the values, you use the pop() function which returns the value that has been deleted.
To retrieve the key-value pair, you use the popitem() function which returns a tuple of the key and value.
To clear the entire dictionary, you use the clear() function.

thisdict = {'First': 'HTML', 'Second': 'CSS', 'Third': 'Java'}
a = thisdict.pop('Second') #pop element
print('Value:', a)
print('Dictionary:', thisdict)
b = thisdict.popitem() #pop the key-value pair
print('Key, value pair:', b)
print('Dictionary', thisdict)

thisdict.clear() #empty dictionary
print('n', thisdict)

Accessing Elements

You can access elements using the keys only. You can use either the get() function or just pass the key values and you will be retrieving the values.

my_dict = {'First': 'Javascript', 'Second': 'Python'}
print(my_dict['First']) #access elements using keys
print(my_dict.get('Second'))

Other Functions

You have different functions which return to us the keys or the values of the key-value pair accordingly to the keys(), values(), items() functions accordingly.

my_dict = {'First': 'Java', 'Second': 'Python', 'Third': 'HTML'}
print(my_dict.keys()) #get keys
print(my_dict.values()) #get values
print(my_dict.items()) #get key-value pairs
print(my_dict.get('First'))

Sets

Sets are a collection of unordered elements that are unique. Therefore this means that even if the data is repeated more than one time, it would be entered into the set only once.
Sets can also be used to perform mathematical set operations like union, intersection, symmetric difference, etc.
The difference of sets in comparison to lists and tuples is that sets cannot have multiple occurrences of the same element(duplicates or repeating items) and can store unordered values.

Creating a Set in Python

Sets are created using the curly brackets and commas to separate different items then you just pass values to it.

my_set = {1, 2, 3, 4, 5, 5, 5, 6} #create set
print(my_set)

Adding elements to a Set

To add elements, you use the add() function and pass the value to it.

myset = {11, 12, 13}
myset.add(14) #add element to set
print(my_set)

Operations in sets

Sets are able to perform mathematical set operations like union, intersection, symmetric difference among others.

myset_1 = {1, 2, 3, 4}
myset_2 = {3, 4, 5, 6}
print(myset_1.union(myset_2), '----------', myset_1 | myset_2)
print(myset_1.intersection(myset_2), '----------', myset_1 & myset_2)
print(myset_1.difference(myset_2), '----------', myset_1 - myset_2)
print(myset_1.symmetric_difference(myset_2), '----------', myset_1 ^ myset_2)
myset_1.clear()
print(myset_1)

In the above program, you find that:

• The union() function combines the data present in both sets.
• The intersection() function finds the data present in both sets only.
• The difference() function deletes the data present in both and outputs data present only in the set passed.
• The symmetric_difference() does the same as the difference() function but outputs the data which is remaining in both sets.

User-Defined Data Structures

Python Arrays

Arrays, just like Lists, They are used to store multiple values in one single variable.
Lists allow heterogeneous data element storage while Arrays allow only homogenous elements to be stored within them.
Fundamentally, It is useful to use arrays to perform certain operations in python since with arrays, you can perform an operations on all its item individually easily, which may not be the case with lists.
Here is the syntax to create an array. Square brackets are used to define a list.

fruits = ["apple", "grapes", "mango", "plums"]  
print (fruits)

Arrays allow you to access the array elements using index and they usually start from zero.

fruits = ["apple", "grapes", "mango", "plums"]  
x = fruits[1]  
print (x) 

Similar to accessing the element, you can modify the element using index.

fruits = ["apple", "grapes", "mango", "plums"]  
fruits[2] = "melon"  
print (fruits)

You get to know the number of elements in an array by using the len() method.

fruits = ["apple", "grapes", "mango", "plums"]  
print (len(fruits))  # prints 4  

for statement is used to loop through the array elements. You process individual elements inside the loop.

fruits = ["mango", "apple", "grapes"]  

for i in fruits:  
     print(i)

The append() method adds a new element to the end of the array same as a list since arrays are mutable.

fruits = ["apple", "grapes", "mango", "plums"]  

fruits.append("guava")  
print(fruits)

Two methods are useful to remove elements from the array. pop() method takes the array index and removes the element in the particular position. remove() accepts the value of the element and removes it. For example:

fruits = ["apple", "grapes", "mango", "plums"]  

fruits.pop(2)  
print(fruits)  

fruits.remove("mango")  
print(fruits)  

Stack Data Structure

A stack is a container of objects that are inserted and removed according to the Last-In-First-Out (LIFO) concept.
Stacks are linear Data Structures which are based on the principle of Last-In-First-Out (LIFO) where data which is entered last will be the first to get accessed. It is built using the array structure and has operations namely, push operation(adding elements), pop operation (deleting, removing or accessing elements) only from one point in the stack called as the TOP. This TOP is the pointer to the current position of the stack.

Basic Stack Operations

There are some basic operations that allow you to perform different actions on a stack. They include:

Push: Add an element to the top of a stack
Pop: Remove an element from the top of a stack
IsEmpty: Check if the stack is empty
IsFull: Check if the stack is full
Peek: Get the value of the top element without removing it

   # Bottom -> 1 -> 2 -> 3 -> 4 -> 5 (Top)
stack = [1,2,3,4,5] 
stack.append(6) # Bottom -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 (Top)
print(stack)

stack.pop() # Bottom -> 1 -> 2 -> 3 -> 4 -> 5 (Top)
stack.pop() # Bottom -> 1 -> 2 -> 3 -> 4 (Top)
print(stack)

Stack Push and Pop Operations

The operations work as follows:

• A pointer called TOP is used to keep track of the top element in the stack.
• When initializing the stack, we set its value to -1 so that we can check if the stack is empty by comparing TOP == -1.
• On pushing an element, we increase the value of TOP and place the new element in the position pointed to by TOP.
• On popping an element, we return the element pointed to by TOP and reduce its value.
• Before pushing, we check if the stack is already full
• Before popping, we check if the stack is already empty

In the above image, although item 3 was kept last, it was removed first. This is the LIFO (Last In First Out) Principle.
We can implement a stack in any programming language like C, C++, Java, Python or C#, but the specification is pretty much the same.

Applications of Stack Data Structure

Stacks Data Structures are used :

To reverse a word - Put all the letters in a stack and pop them out. Due to LIFO principle of stack, you will get the letters in reverse order.
In compilers - Compilers use the stack to calculate the value of expressions like 2 + 4 / 5 * (7 - 9) by converting the expression to prefix or postfix form.
In browsers - The back button in a browser saves all the URLs you have visited previously in a stack. Each time you visit a new page, it is added on top of the stack. When you press the back button, the current URL is removed from the stack, and the previous URL is accessed.

Queue Data Structure

A queue is a container of objects that are inserted and removed according to the First-In-First-Out (FIFO) principle.
A queue is also a linear data structure which is based on the principle of First-In-First-Out (FIFO) where the data entered first will be accessed first. It is built using the array structure and has operations which can be performed from both ends of the Queue, that is, head-tail or front-back. Operations such as adding and deleting elements are called En-Queue and De-Queue and accessing the elements can be performed.

In the above image, since 1 was the first in the queue before 2, it is the first to be removed from the queue. This is the FIFO rule.

Queue Operations

A queue which is an abstract data structure ADT that allows the following operations:

• Enqueue: Add an element to the end of the queue
• Dequeue: Remove an element from the front of the queue
• IsEmpty: Check if the queue is empty
• IsFull: Check if the queue is full
• Peek: Get the value of the front of the queue without removing it

Queue operations work as follows:

1. two pointers FRONT and REAR
2. FRONT track the first element of the queue
3. REAR track the last element of the queue
4. initially, set value of FRONT and REAR to -1

Enqueue Operation

• check if the queue is full
• for the first element, set the value of FRONT to 0
• increase the REAR index by 1
• add the new element in the position pointed to by REAR

Dequeue Operation

• check if the queue is empty
• return the value pointed by FRONT
• increase the FRONT index by 1
• for the last element, reset the values of FRONT and REAR to -1

N/B:

• Insertion and deletion on a queue happen on different ends. So we need to keep track of the Front end and the Rear end of a queue.
• Although a queue has the ability to expand its size, a queue might have a maximum size also. If we try to insert an element beyond its maximum capacity, it will cause an overflow.
• If we try to remove an element from an empty queue, it will result in an underflow.
• An enqueue operation will insert an element to the queue. The time complexity of an enqueue() operation is O(1).
• A dequeue operation will delete an element from the queue. The time complexity of a dequeue() operation is also O(1).

Application of Queues in Python

1. CPU scheduling, Disk Scheduling
2. When data is transferred asynchronously between two processes. The queue is used for synchronization. For example: IO Buffers, pipes, file IO, etc
3. Handling of interrupts in real-time systems.
4. Call Center phone systems use Queues to hold people calling them in order.

Linked Lists

Linked lists are linear Data Structures which are not stored consequently but are linked with each other using pointers. The node of a linked list is composed of data and a pointer called next.
You develop linked lists with the following operations:

• Create a list with given elements
• Display the elements in a list
• Find the number of elements in a list
• Retrieve the element at a given position
• Add or remove element(s)

Here, you observe a linked list as a collection of nodes. 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 NULL to determine the end of the list.

Types of Linked lists

They include:

• Singly Linked lists
• Doubly Linked lists
• Circular Linked lists
• Circular Doubly Linked lists

Linked List Applications

• Dynamic memory allocation
• Implemented in stack and queue
• In undo functionality of softwares
• Hash tables, Graphs

Data Algorithms in Python

Python algorithms are a set of instructions that are executed to get the solution to a given problem.
Since algorithms are not language-specific there is no set of language rules on how to write algorithms and they are usually implemented in several programming languages.
Data Algorithms provide the guidelines to solve the problem of data analysis and plays a critical role to computer scientists/programmers for processing the information given as input data.