Python Advanced - Data Structures and Algorithms

Implementing data structures and algorithms in Python

Understanding data structures and algorithms is fundamental to writing efficient and effective code. This tutorial explores how to implement various data structures and algorithms in Python, including arrays, linked lists, stacks, queues, trees, graphs, sorting algorithms, and searching algorithms.

Arrays

Arrays are a collection of elements, each identified by an index. Here is an example of implementing an array in Python:

# Create an array
arr = [1, 2, 3, 4, 5]

# Access elements
print(arr[0])  # Output: 1

# Update elements
arr[1] = 10

# Iterate over the array
for elem in arr:
    print(elem)
            

Linked Lists

Linked lists are a collection of nodes where each node contains data and a reference to the next node. Here is an example of implementing a singly linked list in Python:

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Usage
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.print_list()  # Output: 1 -> 2 -> 3 -> None
            

Stacks

Stacks are a collection of elements that follow the Last-In-First-Out (LIFO) principle. Here is an example of implementing a stack in Python:

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, data):
        self.stack.append(data)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        return None

    def is_empty(self):
        return len(self.stack) == 0

# Usage
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.peek())  # Output: 2
            

Queues

Queues are a collection of elements that follow the First-In-First-Out (FIFO) principle. Here is an example of implementing a queue in Python:

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

    def enqueue(self, data):
        self.queue.append(data)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        return None

    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        return None

    def is_empty(self):
        return len(self.queue) == 0

# Usage
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # Output: 1
print(queue.peek())  # Output: 2
            

Trees

Trees are hierarchical data structures consisting of nodes with a parent-child relationship. Here is an example of implementing a binary tree in Python:

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, data):
        if self.root is None:
            self.root = TreeNode(data)
        else:
            self._insert(data, self.root)

    def _insert(self, data, node):
        if data < node.data:
            if node.left is None:
                node.left = TreeNode(data)
            else:
                self._insert(data, node.left)
        else:
            if node.right is None:
                node.right = TreeNode(data)
            else:
                self._insert(data, node.right)

    def inorder_traversal(self, node):
        if node:
            self.inorder_traversal(node.left)
            print(node.data, end=" ")
            self.inorder_traversal(node.right)

# Usage
bt = BinaryTree()
bt.insert(5)
bt.insert(3)
bt.insert(7)
bt.inorder_traversal(bt.root)  # Output: 3 5 7
            

Graphs

Graphs are a collection of nodes (vertices) connected by edges. Here is an example of implementing an undirected graph using an adjacency list in Python:

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        if v not in self.graph:
            self.graph[v] = []
        self.graph[u].append(v)
        self.graph[v].append(u)

    def print_graph(self):
        for node in self.graph:
            print(f"{node}: {self.graph[node]}")

# Usage
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.print_graph()
# Output:
# 0: [1, 2]
# 1: [2, 0]
# 2: [3, 0, 1]
# 3: [2]
            

Sorting Algorithms

Sorting algorithms arrange the elements of a list in a specific order. Here is an example of implementing the bubble sort algorithm in Python:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# Usage
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr)  # Output: [11, 12, 22, 25, 34, 64, 90]
            

Searching Algorithms

Searching algorithms are used to find an element in a list. Here is an example of implementing binary search in Python:

def binary_search(arr, x):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Usage
arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, x)
print(f"Element found at index {result}")  # Output: Element found at index 3
            

Summary

In this tutorial, you learned about implementing various data structures and algorithms in Python. Data structures such as arrays, linked lists, stacks, queues, trees, and graphs help organize and store data efficiently. Algorithms such as sorting and searching provide step-by-step procedures for solving problems. Understanding and implementing these data structures and algorithms is essential for improving coding skills and problem-solving abilities.