Advanced Data Structures in Python

This tutorial covers advanced data structures in Python, including custom implementations such as linked lists, trees, and graphs, along with specialized data structures from the collections module.

1. Custom Data Structures

Custom data structures allow for tailored solutions to specific problems. Here are examples of commonly used custom data structures:

Linked List

A linked list is a linear data structure where each element (node) points to the next element. It allows for efficient insertion and deletion operations.

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 display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Example usage
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.display()  # Expected output: 1 -> 2 -> 3 -> None

Binary Tree

A binary tree is a hierarchical data structure where each node has at most two children referred to as the left child and the right child.

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

class BinaryTree:
    def __init__(self, root):
        self.root = TreeNode(root)

    def insert(self, root, key):
        if root is None:
            return TreeNode(key)
        else:
            if key < root.val:
                root.left = self.insert(root.left, key)
            else:
                root.right = self.insert(root.right, key)
        return root

    def inorder_traversal(self, root):
        if root:
            self.inorder_traversal(root.left)
            print(root.val, end=" ")
            self.inorder_traversal(root.right)

# Example usage
bt = BinaryTree(5)
bt.insert(bt.root, 3)
bt.insert(bt.root, 7)
bt.inorder_traversal(bt.root)  # Expected output: 3 5 7

Graph

A graph is a collection of nodes (vertices) and edges connecting them. Graphs can be directed or undirected.

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

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

    def display(self):
        for vertex in self.graph:
            print(f"{vertex} -> {', '.join(map(str, self.graph[vertex]))}")

# Example usage
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.display()  # Expected output: 1 -> 2, 3; 2 -> 4

2. Collections Module

The collections module provides specialized data structures that offer alternatives to Python's built-in data types.

deque

deque is a double-ended queue that allows you to append and pop items from both ends efficiently.

from collections import deque

d = deque()
d.append(1)
d.append(2)
d.appendleft(0)
print(d)  # Expected output: deque([0, 1, 2])

defaultdict

defaultdict is a subclass of the built-in dict that returns a default value for a nonexistent key.

from collections import defaultdict

dd = defaultdict(int)
dd['a'] += 1
dd['b'] += 2
print(dd)  # Expected output: defaultdict(, {'a': 1, 'b': 2})

Counter

Counter is a subclass of dict specifically designed for counting hashable objects.

from collections import Counter

c = Counter(['apple', 'banana', 'apple', 'orange', 'banana', 'banana'])
print(c)  # Expected output: Counter({'banana': 3, 'apple': 2, 'orange': 1})

3. Summary

This tutorial explored custom data structures such as linked lists, trees, and graphs, highlighting their implementation and use cases. Additionally, we introduced specialized data structures available in the collections module, which can enhance performance and simplify code for specific scenarios.

0 Interaction

494 Views

27 Likes