If you are a developer or what to learn python to kick start you programming career then read this article.

DSA which is known as a short from for data structure and algorithm serve as the backbone for efficient problem-solving and software development.

As, It will help you to understand how Python is known for its simplicity and versatility, offers a plethora of libraries and packages that facilitate the implementation of various DSA concepts.

In this article you will understand data structure and algorithm, covering arrays, linked lists, queues, hash maps, heaps, trees, and specialized algorithms like Bisect, Interval Trees, and Trie Trees.

Let’s get started –

Library Used to Implement Array in Python

‘Array’ library is used to implement an array in python. In simple terms and array is collection of data which can be character,string,numbers.

Important Methods in Array library

• array.itemsize()
• array.buffer_info()
• array.count(x)
• array.extend(iterable)

Syntax to use Array Library in Python –

import array

# Create an array
array_name = array.array('typecode', [element1, element2, ...])

Example which demonstrates the use of array library in Python

import array

# Create an array of integers
arr = array.array('i', [1, 2, 3, 4, 5])

# Access elements of the array
print("First element:", arr[0])
print("Second element:", arr[1])

# Append elements to the array
arr.append(6)
print("Appended array:", arr)

# Remove elements from the array
arr.remove(3)
print("Array after removing element 3:", arr)

# Find the index of an element
index = arr.index(4)
print("Index of element 4:", index)

# Get the length of the array
length = len(arr)
print("Length of the array:", length)

Output:

The typecode in the array creation specifies the type of elements in the array. Here are some common typecodes:

• 'i': signed integer
• 'f': floating point
• 'd': double precision floating point
• 'b': signed integer (char)
• 'u': unicode character

Explanation of the above code:

1. import array: This line tells Python to import the array module, which allows us to work with arrays.
2. arr = array.array('i', [1, 2, 3, 4, 5]): This line creates an array named arr containing integers. The 'i' in the array.array function specifies that the array will contain integers. The second argument [1, 2, 3, 4, 5] is a list of integers that initialize the array.
3. print("First element:", arr[0]): This line prints the first element of the array arr. Array elements are accessed using square brackets [ ], with the index of the element inside the brackets. In this case, arr[0] accesses the first element.
4. print("Second element:", arr[1]): This line prints the second element of the array arr. Array indexing in Python starts from 0, so arr[1] accesses the second element.
5. arr.append(6): This line appends the integer 6 to the end of the array arr. The append method adds a new element to the array.
6. print("Appended array:", arr): This line prints the entire array arr after appending 6 to it. This allows us to see the updated array.
7. arr.remove(3): This line removes the integer 3 from the array arr. The remove method removes the first occurrence of the specified value from the array.
8. print("Array after removing element 3:", arr): This line prints the entire array arr after removing 3 from it. This allows us to see the updated array.
9. index = arr.index(4): This line finds the index of the integer 4 in the array arr and stores it in the variable index. The index method returns the index of the first occurrence of the specified value in the array.
10. print("Index of element 4:", index): This line prints the index of the integer 4 in the array arr.
11. length = len(arr): This line calculates the length of the array arr (i.e., the number of elements in the array) and stores it in the variable length. The len function returns the length of the array.
12. print("Length of the array:", length): This line prints the length of the array arr, which indicates how many elements are in the array.

Library to Implement Linked list in Python

LinkedList can be implemented with the help of classes

The syntax for implementing a linked list in Python involves defining two classes: Node and LinkedList.

Node class: Represents an individual element of the linked list.

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

LinkedList class: Represents the linked list and contains methods to perform operations on the linked list.

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

    def insert_at_beginning(self, data):
        # Insert a new node at the beginning of the linked list
        ...

    def insert_at_end(self, data):
        # Insert a new node at the end of the linked list
        ...

    def print_list(self):
        # Print the contents of the linked list
        ...

To use the linked list, you would create an instance of the LinkedList class and then use its methods to insert nodes and print the list.

Example to implement LinkedList in Python

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

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

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def insert_at_end(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.data, end=" ")
            current_node = current_node.next
        print()

# Create a new linked list
llist = LinkedList()

# Insert some nodes
llist.insert_at_end(1)
llist.insert_at_end(2)
llist.insert_at_end(3)
llist.insert_at_beginning(0)

# Print the linked list
llist.print_list()

Explain each line of code above:

1. class Node:: This defines a class named Node, which represents a single element in a linked list.
2. def __init__(self, data):: This is a special method called the constructor, which initializes a new Node object with the given data value.
3. self.data = data: This line sets the data attribute of the Node object to the provided data value.
4. self.next = None: This line sets the next attribute of the Node object to None, indicating that it is initially not connected to any other node.
5. class LinkedList:: This defines a class named LinkedList, which represents the entire linked list.
6. def __init__(self):: This is the constructor for the LinkedList class, which initializes a new linked list with no nodes.
7. self.head = None: This line sets the head attribute of the LinkedList object to None, indicating that the list is initially empty.
8. def insert_at_beginning(self, data):: This method inserts a new node with the provided data value at the beginning of the linked list.
9. new_node = Node(data): This line creates a new Node object with the given data value.
10. new_node.next = self.head: This line sets the next attribute of the new node to the current head of the linked list.
11. self.head = new_node: This line updates the head attribute of the linked list to point to the new node, effectively inserting it at the beginning.
12. def insert_at_end(self, data):: This method inserts a new node with the provided data value at the end of the linked list.
13. new_node = Node(data): This line creates a new Node object with the given data value.
14. if self.head is None:: This condition checks if the linked list is empty (i.e., head is None).
15. self.head = new_node: If the list is empty, this line sets the head attribute to the new node, effectively making it the only node in the list.
16. last_node = self.head: This line initializes a variable last_node to the head of the linked list.
17. while last_node.next:: This loop iterates through the linked list until it reaches the last node (i.e., the node whose next attribute is None).
18. last_node = last_node.next: This line moves last_node to the next node in the list.
19. last_node.next = new_node: Once the last node is found, this line sets its next attribute to the new node, effectively inserting it at the end.
20. def print_list(self):: This method prints all the elements of the linked list.
21. current_node = self.head: This line initializes a variable current_node to the head of the linked list.
22. while current_node:: This loop iterates through the linked list until it reaches the end (i.e., current_node becomes None).
23. print(current_node.data, end=" "): This line prints the data attribute of the current node.
24. current_node = current_node.next: This line moves current_node to the next node in the list.
25. print(): This line prints a newline character to move to the next line after printing all the elements of the linked list.
26. llist = LinkedList(): This line creates a new instance of the LinkedList class, representing a new empty linked list.
27. llist.insert_at_end(1), llist.insert_at_end(2), llist.insert_at_end(3), llist.insert_at_beginning(0): These lines insert nodes with values 1, 2, 3, and 0 at the end and beginning of the linked list, respectively.
28. llist.print_list(): This line prints all the elements of the linked list, resulting in the output 0 1 2 3 in this case.

Library to Implement Queue in Python

The ‘queue.Queue library’ in Python is used to implement Queue in Python.

Important Methods which can he helpful –

• Queue.qsize(): Return the approximate size of the queue.
• Queue.empty(): Return True if the queue is empty, False otherwise.
• Queue.full(): Return True if the queue is full, False otherwise.
• Queue.put(): Put item into the queue.
• Queue.get(): Remove and return an item from the queue.

Example:

from queue import Queue
 
# Creating a queue
my_queue = Queue()
 
# Adding elements to the queue
my_queue.put(1)
my_queue.put(2)
my_queue.put(3)
 
# Removing elements from the queue
# Removes and returns the first element added (FIFO)
element = my_queue.get()  
print(element) 
 
# Checking if the queue is empty
print(my_queue.empty())  
 
# Getting the size of the queue
print(my_queue.qsize())  
 
# Other methods available in Queue include: empty,
# qsize, full, task_done, join, etc.

Explanation of the above code:

1. class Queue:: This line defines a new class named Queue, which will represent our queue data structure.
2. def __init__(self):: This is the constructor method for the Queue class. It initializes a new queue with an empty list of items.
3. self.items = []: This line creates an empty list called items to store the elements of the queue.
4. def enqueue(self, item):: This method adds a new item to the end of the queue. It takes an argument item which is the value to be added to the queue.
5. self.items.append(item): This line appends the item to the end of the items list, effectively adding it to the queue.
6. def dequeue(self):: This method removes and returns the item at the front of the queue.
7. if not self.is_empty():: This line checks if the queue is not empty before dequeuing. If the queue is empty, it raises an IndexError.
8. return self.items.pop(0): This line removes and returns the item at index 0 (the front of the queue) using the pop method.
9. else: raise IndexError("Queue is empty"): If the queue is empty, this line raises an IndexError with the message “Queue is empty”.
10. def is_empty(self):: This method checks if the queue is empty. It returns True if the queue is empty and False otherwise.
11. return len(self.items) == 0: This line uses the len function to check if the length of the items list is 0, indicating an empty queue.
12. def size(self):: This method returns the number of items in the queue.
13. return len(self.items): This line returns the length of the items list, which represents the number of items in the queue.
14. q = Queue(): This line creates a new instance of the Queue class, which initializes an empty queue.
15. q.enqueue(1), q.enqueue(2), q.enqueue(3): These lines enqueue three items (1, 2, and 3) into the queue q.
16. print("Queue size:", q.size()): This line prints the size of the queue using the size method.
17. print("Dequeued item:", q.dequeue()), print("Dequeued item:", q.dequeue()): These lines dequeue two items from the queue q and print them.
18. print("Queue size after dequeuing:", q.size()): This line prints the size of the queue after dequeuing two items.

Which Library is used to implement Hash Map in Python ?

The ‘collections.Counter library’ in Python is used to implement Hash Map in Python.

the collections.Counter library in Python is like a special tool that helps you create and work with hash maps, which are data structures that store key-value pairs. This library makes it easy to count and manipulate the frequency of items in a collection, like a list or a string.

Example:

from collections import Counter

# Create a Counter object from a list
my_list = ['apple', 'banana', 'apple', 'orange', 'apple', 'banana']
my_counter = Counter(my_list)

print(my_counter)

Output:

Explanation of the above code:

In the above code, we’re using the Counter class from the collections module in Python to create a frequency counter for the items in the my_list list. The Counter class automatically counts the frequency of each item in the list and stores it as key-value pairs, where the key is the item and the value is its frequency. When we print my_counter, we’ll see a dictionary-like output showing the frequency of each item in the list.

Library for Maintaining dictionaries in Python ?

The most efficient library for maintaining dictionaries in python is ‘Chainmap‘ let us see an example below to understand what exactly it is and how does it works –

# Python program to demonstrate ChainMap 
from collections import ChainMap 
    
d1 = {'a': 1, 'b': 2} 
d2 = {'c': 3, 'd': 4} 
d3 = {'e': 5, 'f': 6} 
    
# Defining the chainmap 
c = ChainMap(d1, d2, d3) 

Output:

apart from the above library we also have a library which is known as ‘OrderedDict Library’. Now, how exactly this works ?

The OrderedDict is a dictionary subclass provided by the collections module in Python. It’s similar to the built-in dict class but with one key difference: it maintains the order of insertion of its keys.

from collections import OrderedDict
my_ordered_dict = OrderedDict()

Library to Implement Bisect Algorithm in Python

‘intervaltree library’ in Python is used to implement Queue in Python.

Important Methods in intervaltree library

The intervaltree module in Python provides several methods for efficiently working with interval trees.

• add(interval): Adds an interval to the interval tree.
• remove(interval): Removes an interval from the interval tree.
• search(begin): Searches for intervals that overlap with the given range defined by begin and end (inclusive).
• overlap(begin): Alias for search(). Searches for intervals that overlap with the given range defined by begin and end.
• at(begin): Searches for intervals that contain the specified point begin. Returns a set of intervals that contain the point.
• clear(): Clears all intervals from the interval tree, making it empty.
• copy(): Creates a shallow copy of the interval tree, including all intervals.
• discard(interval): Removes an interval from the interval tree if it exists, similar to the remove() method.
• items(): Returns a generator that yields all intervals stored in the interval tree.
• size(): Returns the number of intervals stored in the interval tree.
• empty(): Returns True if the interval tree is empty, False otherwise.

Example:

from intervaltree import IntervalTree, Interval

# Create an interval tree
tree = IntervalTree()

# Add intervals to the tree
tree.add(Interval(1, 5))
tree.add(Interval(3, 8))
tree.add(Interval(6, 10))
tree.add(Interval(12, 15))

# Query intervals that overlap with a given range
query_range = (4, 7)
result_intervals = tree.search(*query_range)

print("Intervals that overlap with the query range:", result_intervals)

# Iterate over the result intervals and print their start and end points
print("Start and end points of the overlapping intervals:")
for interval in result_intervals:
	print("Start:", interval.begin, "End:", interval.end)

Explanation of the above code:

1. from intervaltree import IntervalTree, Interval: This line imports the IntervalTree and Interval classes from the intervaltree module. These classes are used to work with interval trees in Python.
2. tree = IntervalTree(): This line creates an empty interval tree named tree.
3. tree.add(Interval(1, 5)), tree.add(Interval(3, 8)), etc.: These lines add intervals to the tree. Each Interval object represents a range of values, defined by its start and end points.
4. query_range = (4, 7): This line defines a query range as a tuple with start point 4 and end point 7.
5. result_intervals = tree.search(*query_range): This line searches the tree for intervals that overlap with the query_range. The * operator unpacks the query_range tuple into separate arguments for the search method.
6. print("Intervals that overlap with the query range:", result_intervals): This line prints the intervals that overlap with the query_range.
7. for interval in result_intervals:: This line starts a loop that iterates over each interval in result_intervals.
8. print("Start:", interval.begin, "End:", interval.end): This line prints the start and end points of each overlapping interval in result_intervals.