Можно ли создать свою структуру данных в Python?

# Можно ли создать свою структуру данных в Python?

Абсолютно да! Python предоставляет множество способов создания собственных структур данных. Это один из самых мощных аспектов языка, позволяющий разработчикам проектировать специализированные решения под конкретные задачи.

Базовые способы создания структур данных

1. Пользовательские классы

Самый прямолинейный способ — создать обычный класс:

class Stack:
    """Простая реализация стека"""
    def __init__(self):
        self._items = []
    
    def push(self, item):
        """Добавить элемент в стек"""
        self._items.append(item)
    
    def pop(self):
        """Извлечь элемент из стека"""
        if not self.is_empty():
            return self._items.pop()
        raise IndexError("Стек пуст")
    
    def is_empty(self):
        return len(self._items) == 0
    
    def __len__(self):
        return len(self._items)

# Использование
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop())  # 2

2. Использование dataclass (Python 3.7+)

Для простых структур данных с меньшим количеством кода:

from dataclasses import dataclass, field
from typing import List, Optional

@dataclass
class Node:
    """Узел связного списка"""
    value: int
    next: Optional['Node'] = None

@dataclass
class LinkedList:
    """Связный список"""
    head: Optional[Node] = None
    _length: int = field(default=0, init=False)
    
    def append(self, value: int):
        """Добавить элемент в конец списка"""
        if self.head is None:
            self.head = Node(value)
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = Node(value)
        self._length += 1
    
    def __len__(self):
        return self._length
    
    def __iter__(self):
        current = self.head
        while current:
            yield current.value
            current = current.next

# Использование
linked_list = LinkedList()
linked_list.append(10)
linked_list.append(20)
for val in linked_list:
    print(val)  # 10, 20

3. Использование NamedTuple

Легкая и типобезопасная структура:

from typing import NamedTuple

class Point(NamedTuple):
    x: float
    y: float
    
    def distance_from_origin(self) -> float:
        return (self.x ** 2 + self.y ** 2) ** 0.5

point = Point(3, 4)
print(point.distance_from_origin())  # 5.0

Сложные структуры данных

4. Бинарное дерево поиска (BST)

from dataclasses import dataclass
from typing import Optional

@dataclass
class TreeNode:
    value: int
    left: Optional['TreeNode'] = None
    right: Optional['TreeNode'] = None

class BinarySearchTree:
    def __init__(self):
        self.root: Optional[TreeNode] = None
    
    def insert(self, value: int):
        """Вставить значение в BST"""
        if self.root is None:
            self.root = TreeNode(value)
        else:
            self._insert_recursive(self.root, value)
    
    def _insert_recursive(self, node: TreeNode, value: int):
        if value < node.value:
            if node.left is None:
                node.left = TreeNode(value)
            else:
                self._insert_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = TreeNode(value)
            else:
                self._insert_recursive(node.right, value)
    
    def search(self, value: int) -> bool:
        """Найти значение в дереве"""
        return self._search_recursive(self.root, value)
    
    def _search_recursive(self, node: Optional[TreeNode], value: int) -> bool:
        if node is None:
            return False
        if node.value == value:
            return True
        elif value < node.value:
            return self._search_recursive(node.left, value)
        else:
            return self._search_recursive(node.right, value)
    
    def inorder_traversal(self):
        """Обход дерева в порядке возрастания"""
        return list(self._inorder_recursive(self.root))
    
    def _inorder_recursive(self, node: Optional[TreeNode]):
        if node:
            yield from self._inorder_recursive(node.left)
            yield node.value
            yield from self._inorder_recursive(node.right)

# Использование
bst = BinarySearchTree()
for val in [50, 30, 70, 20, 40, 60, 80]:
    bst.insert(val)
print(bst.inorder_traversal())  # [20, 30, 40, 50, 60, 70, 80]

5. Граф (неориентированный)

from collections import defaultdict
from typing import List, Set

class Graph:
    def __init__(self):
        self.adjacency_list: dict[int, List[int]] = defaultdict(list)
    
    def add_edge(self, u: int, v: int):
        """Добавить ребро между узлами"""
        self.adjacency_list[u].append(v)
        self.adjacency_list[v].append(u)  # неориентированный граф
    
    def bfs(self, start: int) -> List[int]:
        """Поиск в ширину (BFS)"""
        visited: Set[int] = set()
        queue = [start]
        result = []
        
        while queue:
            vertex = queue.pop(0)
            if vertex not in visited:
                visited.add(vertex)
                result.append(vertex)
                queue.extend(self.adjacency_list[vertex])
        
        return result
    
    def dfs(self, start: int) -> List[int]:
        """Поиск в глубину (DFS)"""
        visited: Set[int] = set()
        result = []
        
        def _dfs(vertex: int):
            visited.add(vertex)
            result.append(vertex)
            for neighbor in self.adjacency_list[vertex]:
                if neighbor not in visited:
                    _dfs(neighbor)
        
        _dfs(start)
        return result

# Использование
graph = Graph()
for u, v in [(0, 1), (0, 2), (1, 3), (2, 3)]:
    graph.add_edge(u, v)
print(f"BFS: {graph.bfs(0)}")  # [0, 1, 2, 3]
print(f"DFS: {graph.dfs(0)}")  # [0, 1, 3, 2]

6. Приоритетная очередь (Heap)

import heapq
from dataclasses import dataclass

@dataclass
class Task:
    priority: int
    name: str
    
    def __lt__(self, other):
        return self.priority < other.priority

class PriorityQueue:
    def __init__(self):
        self._heap = []
    
    def enqueue(self, priority: int, name: str):
        """Добавить элемент с приоритетом"""
        task = Task(priority, name)
        heapq.heappush(self._heap, task)
    
    def dequeue(self) -> Task:
        """Извлечь элемент с минимальным приоритетом"""
        if not self._heap:
            raise IndexError("Очередь пуста")
        return heapq.heappop(self._heap)
    
    def is_empty(self) -> bool:
        return len(self._heap) == 0

# Использование
pq = PriorityQueue()
pq.enqueue(3, "низкий приоритет")
pq.enqueue(1, "высокий приоритет")
pq.enqueue(2, "средний приоритет")

while not pq.is_empty():
    task = pq.dequeue()
    print(f"{task.priority}: {task.name}")
# Выведет: 1: высокий приоритет, 2: средний приоритет, 3: низкий приоритет

Продвинутые техники

7. Использование slots для оптимизации памяти

class OptimizedNode:
    __slots__ = ['value', 'next']
    
    def __init__(self, value: int):
        self.value = value
        self.next = None

slots уменьшает потребление памяти, запрещая создание dict для каждого объекта.

8. Магические методы для кастомного поведения

class CustomList:
    def __init__(self, items: list):
        self._items = items
    
    def __len__(self):
        return len(self._items)
    
    def __getitem__(self, index):
        return self._items[index]
    
    def __setitem__(self, index, value):
        self._items[index] = value
    
    def __contains__(self, item):
        return item in self._items
    
    def __iter__(self):
        return iter(self._items)
    
    def __repr__(self):
        return f"CustomList({self._items})"

custom_list = CustomList([1, 2, 3])
print(len(custom_list))      # 3
print(custom_list[1])         # 2
print(2 in custom_list)       # True

Заключение

Python идеально подходит для создания пользовательских структур данных благодаря:

• Гибкости — можно создавать как простые, так и сложные структуры
• Выразительности — магические методы позволяют сделать код интуитивным
• Производительности — встроенные оптимизации и возможность использования slots
• Типобезопасности — type hints помогают избежать ошибок
• Готовым инструментам — dataclass, NamedTuple, heapq и другие

Создание собственных структур данных — это не только возможность, но и важный навык, позволяющий писать более эффективный и чистый код.