Data Structures and Algorithms Using Python | Part 1

Data Structures:

Data Structure is defined as a way to organize and store the data so that we can access the data and work more efficiently. Data structures also describe the relationship between the data and the operations.

Data structures in Python mainly deal with Arrays, Lists, Sets, dictionaries, Tuples, and Files.

Python Data Structures are divided into two types

• Primitive Data Structures
• Non-Primitive Data Structures

Primitive/Primary Data Structures consist of various Data Types such as

• Integer
• Float
• String
• Boolean, etc.

Non-Primitive/Secondary Data Structures consist of Some Data Types like

• Array
• List/Linked List
• Tuple
• Dictionary
• Files
• Sets, etc.

The Linked List is again divided into two types

• Linear Linked List

The Linear Linked List consists of Stacks and Queues of Data Structures.

• Non-Linear Linked List

The Non-Linear Linked List also consists of two different data structures Trees and Graphs.

Algorithms:

An Algorithm is defined as a set of instructions to be executed in a particular order to get the desired output. The algorithm is a step-by-step procedure to run the program and get the desired outcome.

Characteristics of Algorithm:

Input: An algorithm must have 0 or more well-defined inputs.

Output: An algorithm must have one or more well-defined outcomes and match the desired result.

Finiteness: Any algorithm must terminate after a finite number of steps. Finiteness means the algorithm must have a limited number of commands/instructions.

Effectiveness: In the algorithm, all the steps must be precise because every effort will be necessary. If any of the steps are ineffective, it will affect all the algorithms.

Definiteness: Every step of an algorithm must be precisely defined.

Performance Analysis of Algorithm:

Two properties can predict the performance analysis of an algorithm. They are

• Time Complexity
• Space Complexity

Time Complexity:

The Time complexity of an algorithm is defined as the time required to execute or run a program.

Space Complexity:

The Space complexity of an algorithm is defined as the total amount of space required by the program to get stored during the program's execution.

Asymptotic Notations:

Asymptotic Notations are the notations that are used to describe the running time of an algorithm. There are five notations

• Big-O notation
• Big-Omega notation
• Theta notation
• Little-o notation
• Little-omega notation

Big-O Notation(O):

Big-O notation is used to represent the upper bound of the running time of an algorithm. Thus, it gives the worst-case time complexity of an algorithm. Any notation is said to be Big-O notation if it satisfies the condition f(n) <= c*g(n). The Big-O is denoted by f(n) = O(g(n)) and n>=n_o.

 The above diagram shows that the function f(n) should always be less than the other function, g(n). Here n₀ is a value that represents that after the n_o matter, the condition f(n)<=c*g(n) will be accurate.

Big-Omega Notation:

Big-Omega notation is used to represent the lower bound of the running time of an algorithm. Thus, it gives the best-case time complexity of an algorithm. Any notation is said to be Big-Omega notation if it satisfies the condition f(n) >= c*g(n). The Big-Omega is denoted by f(n) = Ω(g(n)) and n>=n_o. Big-Omega notation is denoted by the symbol Ω-notation.

The above diagram shows that the function f(n) should always be greater than the other function, g(n). Here n₀ is a value that represents that after the n_o matter, the condition f(n)>=c*g(n) will be accurate.

Theta Notation:

Theta notation encloses the function from the upper and lowers bound of an algorithm's running time. Thus, it gives the average-case time complexity of an algorithm. Any notation is said to be Theta notation if it satisfies the condition c₁*g(n)<= f(n) <= c₂*g(n). The Theta notation is denoted by f(n) = θ(g(n)) and n>=n_o. Theta notation is denoted by the symbol θ(n).

Little-o Notation:

Little-o notation provides an upper bound of the running time of an algorithm that is not tight. A notation is said to be Little-o notation if it satisfies the condition

lim f(n)/g(n) = 0. It means the result of the function after applying the limit must be
n→∞

equal to 0. It should satisfy the condition f(n)=o(g(n)).

Little-omega Notation:

Little-omega notation provides a lower bound of the running time of an algorithm that is not tight. A notation is said to be Little-omega notation if it satisfies the condition

lim f(n)/g(n) = ∞. It means the result of the function after applying the limit must be
n→∞

equal to ∞. It should satisfy the condition f(n)=Ω(g(n)).

Arrays:

An array is a collection of similar or homogenous data elements stored under a single variable name or location. We can create the array in Python by importing the array module.

Syntax:

import array as arr

Example:

#simple program to create an array of integer types using Python
#importing the array module into our program
import array as arr
#creating an array of size 5 with integer elements
a = arr.array('i', [10, 20, 30, 40, 50])        
#printing the array elements using for loop
print("The array elements are:")
for i in range (0, 4):
	print(a[i])      #array elements will be printed one after the other

Output:

The array of elements are:
array('i', [10, 20, 30, 40, 50])

Example 1:

#simple program to create an array of floating types using Python
#importing the array module into our program
import array as arr
#creating an array of size 5 with float elements
a = arr.array('i', [10.2, 20.1, 30.5, 40.7, 50.8])        
#printing the array elements using for loop
print("The array elements are:")
for i in range (0, 4):
	print(a[i])      #array elements will be printed one after the other

Output:

The array of elements are:
array('i', [10.2, 20.1, 30.5, 40.7, 50.8])

Array Methods:

We have a set of built-in methods in Python that can be used on arrays.

append():

append() method is used to add an element at the end of the list or array.

Example:

#simple program to add an element to the array using Python
#importing the array module into our program
import array as arr
#creating an array of size 5 with integer elements
a = arr.array('i', [10, 20, 30, 40, 50])        
#printing the array elements using for loop
print("The array elements before appending elements:")
for i in range (0, 4):
	print(a[i])      #array elements will be printed one after the other
#adding an element to the array using the append() method
a.append(80)
print("The array elements after appending the elements:")
for i in range (0, 5):
	print(a[i])      
#array elements will be printed one after the other after adding of element

Output:

The array elements before appending elements:
array('i', [10, 20, 30, 40, 50])
The array elements after appending elements:
array('i', [10, 20, 30, 40, 50, 80])

Indexing of elements in Arrays:

We can access the array elements using their index values. In arrays, every element has a different index. Below is an array of size 6 with their initial index values.

           0                       1                      2                      3                      4                      5

Example:

#simple program to create an array using Python
#importing the array module into our program
import array as arr
#creating an array of size 5 with integer elements
a = arr.array('i', [10, 20, 30, 40, 50])        
#printing the array elements using for loop
print("The array elements are:")
for i in range (0, 4):
	print(a[i])      #array elements will be printed one after the other
print(a[0])            #printing the array element of index 0
print(a[1])	      #printing the array element of index 1
print(a[2])	      #printing the array element of index 2
print(a[3])           #printing the array element of index 3
print(a[4])          #printing the array element of index 4

Output:

The array of elements are:
array('i', [10, 20, 30, 40, 50])
10                  #0th index value is 10
20                   #1st index value is 20
30                    #2nd index value is 30
40                     #3rd index value is 40
50                      #4th index value is 50

How to Modify elements in an Array:

We can modify any elements in the array by assigning them with a different value using their index.

Example:

#simple program to modify an element from an array using Python
#importing the array module into our program
import array as arr
#creating an array of size 5 with integer elements
a = arr.array('i', [10, 20, 30, 40, 50])        
#printing the array elements using for loop
print("The array elements are:")
for i in range(0, 4):
	print(a[i])      #array elements will be printed one after the other
#modifing the elements of the array
a[0] = 1
a[1] = 2
a[2] = 3
a[3] = 4
a[4] = 5
#printing the array elements after modifying the elements
print("The array elements after modifying the elements are")
for i in range(0, 4):
	print(a[i])

Output:

The array of elements are:
array('i', [10, 20, 30, 40, 50])
The array elements, after modifying the elements, are
array('i', [1, 2, 3, 4, 5])

How to remove or delete an element from an array:

In Python, we can delete an element from an array using two methods

• Pop()
• Remove()

Pop() Method:

Using the pop() method, we can remove an element from an array using its index value.

Example:

#simple program to remove an element from an array
#importing the array module into our program
import array as arr
#creating an array of size 5 with integer elements
a = arr.array('i', [10, 20, 30, 40, 50])        
#printing the array elements using for loop
print("The original array elements are:")
for i in range(0, 4):
	print(a[i])      #array elements will be printed one after the other
#removing an element from an array using the pop() method
a.pop(0)
a.pop(3)
print("The array elements after removing elements are:")
for i in range(0, 4):
	print(a[i])      

Output:

The original array elements are:
array('i', [10, 20, 30, 40, 50])
The array of elements after removing elements are:
20
30
50

Explanation:

At first, I created an array of sizes five and printed all the elements. After that, we removed the 0^th index value and the 3^rd index value using the pop() method.

Remove() Method:

Using the remove() method, we can remove an element from an array directly by giving the value or element of the array.

Example:

#simple program to remove an element from an array
#importing the array module into our program
import array as arr
#creating an array of size 5 with integer elements
a = arr.array('i', [10, 20, 30, 40, 50])        
#printing the array elements using for loop
print("The original array elements are:")
for i in range(0, 4):
	print(a[i])      #array elements will be printed one after the other
#removing an element from an array using the remove() method
a.remove(20)
a.remove(40)
print("The array elements after removing elements are:")
for i in range(0, 4):
	print(a[i])      

Output:

The original array elements are:
array('i', [10, 20, 30, 40, 50])
The array of elements after removing elements are:
10
30
50

Length of an Array :

To get the size or length of an array, we use a pre-defined function or method len().

Example:

#simple program to know the length of an array using the len() method
#importing the array module into our program
import array as arr
#creating an array of size 5 with integer elements
a = arr.array('i', [10, 20, 30, 40, 50])        
#printing the array elements using for loop
print("The original array elements are:")
for i in range(0, 4):
	print(a[i])      #array elements will be printed one after the other
print("The length of an array is ")
l = len(a)
print(l)
a.remove(20)        # removing an element from the array
s = len(a)
print("The length of an array is ", s)

Output:

The original array elements are:
array('i', [10, 20, 30, 40, 50])
The length of an array is
5
The length of an array is 4

How to sort the elements of an array:

To sort the elements of an array, we use the sort() method, which arranges the array elements in ascending order, i.e., from more minor details to higher parts.

Example:

#simple program to sort the array elements using the sort() method
#importing the array module into our program
import array as arr
#creating an array of size 5 with integer elements
a = arr.array('i', [30, 20, 50, 40, 10])        
#printing the array elements using for loop
print("The original array elements are:")
for i in range(0, 5):
	print(a[i])      #array elements will be printed one after the other
print("sorting the elements of an array")
print(a.sort())

Output:

The original array elements are:
array('i', [30, 20, 50, 40, 10])
sorting the elements of an array
[10, 20, 30, 40, 50]

The reverse of an Array:

If we want to print the elements of an array in reverse order, then we can use the reverse() method.

Example:

#simple program to print the array elements in the reverse order
#importing the array module into our program
import array as arr
#creating an array of size 5 with integer elements
a = arr.array('i', [10, 20, 30, 40, 50])        
#printing the array elements using for loop
print("The original array elements are:")
for i in range(0, 5):
	print(a[i])      #array elements will be printed one after the other
print("Reversing the elements of an array")
print(a.sort(reverse=True))

Output:

The original array elements are:
array('i', [10, 20, 30, 40, 50])
Reversing the elements of an array
[50, 40, 30, 20, 10]

Linked List:

A linked list is a sequence of data elements stored in nodes and connected using pointers. There are mainly three types of Linked list. They are

• Single Linked List
• Double Linked List
• Circular Linked List

Single Linked List:

In a single linked list, a node consists of two parts one is data, and another is a pointer to the next node. The next node is a pointer that stores the address of the next node. The starting node of the linked list is called as Head node. The end node's next part consists of the NULL value.

Example:

#simple program to create a single linked list with three nodes
class Node:
    def __init__(self, data):
        self.data = data
        self.next = NULL


class LL:
    def __init__(self):
        self.head = NULL
        self.last_node = NULL
         
    #adding the elements to a linked list
    def append(self, data):
        #if the linked list is empty, then the last node will be NULL
        if self.last_node is NULL:
            self.head = Node(data)
            self.last_node = self.head
        #adding node to the tail of the linked list
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next
             
#To print the data of the linked list
    def display(self):
        current = self.head
      #traversing the linked list
        while current is not NULL:
            print(current.data, end=' ')
            current = current.next
        print()
 
 
if __name__ == '__main__':
    L = LL()
    #adding elements to the linked list
    L.append(100)
    L.append(200)
    L.append(300)
    #displaying elements of the linked list
    L.display()

Output:

100
200
300

Double Linked List:

In a double-linked list, a node consists of three parts one is data, and the left part is a pointer to the prev node, i.e., it stores the address of the previous node. The right part is also a pointer node that consists of the address of the next node. In the double-linked list, we can traverse in both directions.

Example:

#simple program to create a double-linked list
class Node:
    def __init__(self, data):
        self.previous = NULL
        self.data = data
        self.next = NULL
 
 
class DLL:
    def __init__(self):
        self.head = NULL
        self.start_node = NULL
        self.last_node = NULL
 
    #adding elements to the doubly linked list
    def append(self, data):
        #if the doubly linked list is empty, then the last node will be NULL 
        if self.last_node is NULL:
            self.head = Node(data)
            self.last_node = self.head
        #adding node to the tail of the doubly linked list
        else:
            new_node = Node(data)
            self.last_node.next = new_node
            new_node.previous = self.last_node
            new_node.next = NULL
            self.last_node = new_node
 
    #traversing the doubly linked list from both directions, i.e., left to right and right to left
    print("Traversing in the forward direction, i.e., left to right")
    def display(self, Type):
        if Type == 'Left_To_Right':
            current = self.head
            while current is not NULL:
                print(current.data, end=' ')
                current = current.next
            print()
        else:
            print("Traversing in the backward direction, i.e., right to left")
            current = self.last_node
            while current is not NULL:
                print(current.data, end=' ')
                current = current.previous
            print()
 
 
if __name__ == '__main__':
    L = DLL()
    L.append(100)
    L.append(200)
    L.append(300)
    L.append(400)
    L.display('Left_To_Right')
    L.display('Right_To_Left')

Output:

Traversing in the forward direction, i.e., left to right
100     200     300     400
Traversing in the backward direction, i.e., right to left
400    300     200    100

Circular Linked List:

In a circular linked list, a node consists of three parts one is data, and the left part is a pointer to the prev node, i.e., it stores the address of the previous node. The right part is also a pointer node that consists of the address of the next node. In the double-linked list, we can traverse in both directions. The last node of the circular linked list is connected to the first node of the circular linked list. Circular Linked List is a loop model, i.e., it forms a loop while traversing the linked list. Circular Linked List consists of two types of linked lists.

• Circular Single Linked List:

It is a type of linked list in which the next pointer of the last node is connected to the first node of the linked list. It is linked or related only in one way.

• Circular Double Linked List:

It is a type of linked list in which the next pointer of the last node is connected to the previous node of the starting node of the linked list. It is linked or related only in two ways. It is also known as a two-way linked list.

Example:

#simple program to create a Circular linked list
#creating the nodes of the circular linked list
class Node:
    def __init__(self, data):
        self.data = data
        self.next = NULL
 
 
class CLL:
    def __init__(self):
        self.head = NULL
        self.last_node = NULL
 
    #adding elements to the circular linked list
    def append(self, data):
        #if the circular linked list is empty, then the last node will be NULL
        if self.last_node is NULL:
            self.head = Node(data)
            self.last_node = self.head
        #adding node to the tail of the circular linked list
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next
            self.last_node.next = self.head
 
    #printing the content of the circular linked list
    def display(self):
        current = self.head
        while current is not NULL:
            print(current.data, end=' ')
            current = current.next
            if current == self.head:
                break
        print("Data  or content of the circular linked list")
        print()
 
 
if __name__ == '__main__':
    L = CLL()
    L.append(100)
    L.append(200)
    L.append(300)
    L.append(400)
    L.display()

Output:

Data or content of the circular linked list:
100    200    300   400

Tuple:

A tuple is a collection of ordered and immutable objects or elements. List and Tuples are the same, but the list is mutable, whereas the tuples are immutable. Mutable means we can change the list's details or data after giving the data. Immutable means we can't change the list's details or data after providing the data. And also, the difference between the list and the tuple is that the tuple is created using parentheses, and the list is created using square brackets. In the tuple, we give different data separated by commas and enclosed in parenthesis.

Syntax:

Variable name = ("data", "data", "data")

• Empty tuple can be declared as two parentheses enclosing with nothing.
  Tp1 = ()

Creating a Tuple:

We can create a tuple using the parenthesis, and the data must be enclosed within the parenthesis.

Example:

#simple program to create an empty tuple 
#creating an empty tuple
Et = ()
print("Empty tuple:", Et)

Output:

()

Example 1:

#simple program to create a tuple with integer values
#creating a tuple with integer values
Et1 = (10, 42, 22, 35, 60)
print("printing the tuple data:", Et1)

Output:

Printing the tuple data: (10, 42, 22, 35, 60)

Example 2:

#simple program to create a tuple with values of different data types
#creating a tuple with values of different data types
Et2 = (10, "Vijay", 22.5, "Pavan", 60)
print("printing the tuple data:", Et2)

Output:

Printing the tuple data: (10, "Vijay", 22.5, "Pavan", 60)

Example 3:

#simple program to create a tuple with values of different data types
#creating a tuple with values of different data types
Et2 = (10, "Vijay", 22.5, "Pavan", 60)
print("printing the tuple data:", Et2)
#printing the data of the tuple using loops
For i in Et2:
    print("Using loops", i)

Output:

Printing the tuple data: (10, "Vijay", 22.5, "Pavan", 60)
Using loops
10
Vijay
22.5
Pavan
60

How to Access Tuple elements:

In tuple also, we can access the elements using indexing, like Arrays. Indexing in tuples starts from 0. If we want to access elements from the tuple, we can use the operator "[]". We can also perform slicing using the operator "[]".

Example:

#simple program to create a tuple and access the data using the indexing operator []
#creating a tuple with some values or elements
Et3= ("Vijay", "Sai", "Pavan", "John")
print("printing the tuple data:", Et3)
#accessing the tuple data or elements using the operator "[]."
print(Et3[0])
print(Et3[3])
print(Et3[1])

Output:

Printing the tuple data: ("Vijay", "Sai", "Pavan", "John")
Vijay
John
Sai

Example 1:

#simple program to create a tuple and to perform slicing operation
#creating a tuple with some values or elements
Et4= ("Vijay", "Sai", "Pavan", "John")
print("printing the tuple data:", Et4)
#slicing the tuple data or elements using the operator "[]."
print(Et4[0:2])
print(Et4[1:3])
print(Et4[0:4])

Output:

Printing the tuple data: ("Vijay", "Sai", "Pavan", "John")
Sai
Pavan
Sai, Pavan

Negative Indexing:

When we give the negative index -1, the last elements of the tuple will be printed, i.e., -1 represents the last element of the tuple.

Example:

#simple program to create a tuple and to perform negative indexing
#creating a tuple with some values or elements
Et5= ("Vijay", "Sai", "Pavan", "John")
print("printing the tuple data:", Et5)
#performing negative indexing
print("Element at -1 index:", Et5[-1])
print(Et5[-3:-1])
print(Et5[-4:-1])

Output:

Printing the tuple data: ("Vijay", "Sai", "Pavan", "John")
John
Pavan
Sai, Pavan

Dictionaries:

Python Dictionary stores the data in the form of the key with value pairs. It is a datatype in Python. Here in dictionaries, the key must be a single element, and the value can be any datatype, i.e., list, tuple, integers, etc. For example, in real life, dictionaries are used in many ways like contact book, i.e., which stores the phone number concerning the name; here, the name is a key. It must be only one, but the values can be more than one, i.e., we can store multiple phone numbers on a single name.

How to create a dictionary:

We can make a dictionary using multiple key-value pairs enclosed with the curly brackets {}, and each key and the value are separated by a colon (:). The syntax is given as

Syntax:

B = {"key1": "value1", "key2": "value2", "key3": "value3"}

Example:

#simple program to create a dictionary
A= {1: "Vijay", "Age": 20, "Roll No": 21}  
#creating a dictionary with some keys and values
print("printing the data of dictionary")
print(A)   #printing the dictionary data

Output:

Printing the data of dictionary
{1: "Vijay", "Age": 20, "Roll No": 21}

We can also create dictionaries using the built-in function dict() method.

Example:

#simple program to create the dictionaries using the dict() method 
#creating an empty dictionary
A = {}     #represent an empty dictionary
print("printing the empty dictionary")
print(A)
B = dict({1: "name", 2: "Age", 3: "Fees"})
print("printing the data of dictionary created with dict() method")
print(B)
#we can also create the pairs of keys and values using the dict() method
C = dict([(1, "Vijay"), (2, "Sai"), (3, "Pavan")])   
print("printing the dictionary with each item as a pair: ")   
print(C)

Output:

Printing the empty dictionary
{}
Printing the data of dictionary created with dict() method
{1: "name", 2: "Age", 3: "Fees"}
Printing the dictionary with each item as a pair:
{1: "Vijay", 2: "Sai", 3: "Pavan"}

How to Access the dictionary values:

We can also print the data of the dictionary in a different manner or by accessing the data of the dictionary.

Example:

#simple program to create the dictionary and access the data
D = {"name": "Vijay", "Age": 20, "Fees": 20000, "Tax": 2000, "Roll No": 21}
print("printing the data of dictionary or accessing the data of dictionary:")
print("Name: %s" %D["Name"])
print("Age: %d" %D["Age"])
print("Fees: %d" %D["Fees"])
print("Tax: %d" %D["Tax"])
print("Roll No: %d" %D["Roll No"])

Output:

Printing the data of dictionary or accessing the data of dictionary:
Name: Vijay
Age: 20
Fees: 20000
Tax: 2000
Roll No: 21

Adding dictionary values:

Dictionary is a mutable data type, i.e., we can change the values of a dictionary after assigning the values. In dictionaries, we can update the values along with the key as

Dict[key] = value.

Example:

#simple program to create a dictionary and update the values
#first, we will create an empty dictionary and update the values
A = {}   
print("printing the empty dictionary: ")   
print(A)   
    
# Adding elements to the dictionary one at a time   
A[0] = "Vijay." 
A[1] = "Sai."  
A[2] = "John."  
print("printing the dictionary data after adding three elements: ")   
print(A)   
    
# Adding a set of values to the dictionary with a single Key   
# The Std ages don't exist in the dictionary  
A['Std_rollno'] = 20, 31, 35  
print("printing the dictionary values: ")   
print(A)   

Output:

Printing the empty dictionary:
{}
Printing the dictionary data after adding three elements:
{0: "Vijay", 1: "Sai", 2: "John"}
Printing the dictionary values:
{0: "Vijay", 1: "Sai", 2: "John", "Std_rollno": (20, 31, 35)}

How to delete a value from the dictionary:

We can delete any value from the dictionary by using the del keyword.

Example:

#simple program to create a dictionary and use the del method to delete the values
B = {"name": "Vijay", "Age": 20, "Fees": 20000, "Tax": 2000, "Roll No": 21}
#type() method is used to print the type of the data 
print(type(B))           #printing the type of the data
print("printing the dictionary values or the data")
print(B)
print("Deleting the values from the dictionary")
del B["Age"]
del B["Tax"]
print("printing the dictionary data after deleting the values")
print(B)

Output:

<class  "dict">
Printing the dictionary values or the data
{"name": "Vijay", "Age": 20, "Fees": 20000, "Tax": 2000, "Roll No": 21}
Deleting the values from the dictionary
Printing the dictionary data after deleting the values
{"name": "Vijay", "Fees": 20000, "Roll No": 21}