В Python типовые структуры данных можно реализовать как встроенными средствами, так и с помощью сторонних библиотек. Вот подробный разбор:

1. Связные списки (Linked Lists)

Односвязный список

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
        
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    
    def prepend(self, data):
        """Добавление в начало"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    def delete(self, key):
        """Удаление узла по значению"""
        current = self.head
        
        # Если удаляем голову
        if current and current.data == key:
            self.head = current.next
            current = None
            return
        
        prev = None
        while current and current.data != key:
            prev = current
            current = current.next
        
        if current is None:
            return
        
        prev.next = current.next
        current = None
    
    def display(self):
        """Вывод списка"""
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        return " -> ".join(map(str, elements))

# Использование
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.prepend(0)
print(ll.display())  # 0 -> 1 -> 2
ll.delete(1)
print(ll.display())  # 0 -> 2

Двусвязный список

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def append(self, data):
        new_node = DNode(data)
        if not self.head:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

2. Стеки (Stacks)

Реализация на списке

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()
        return None
    
    def peek(self):
        """Просмотр верхнего элемента без удаления"""
        if not self.is_empty():
            return self.items[-1]
        return None
    
    def is_empty(self):
        """Проверка на пустоту"""
        return len(self.items) == 0
    
    def size(self):
        """Размер стека"""
        return len(self.items)

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

3. Очереди (Queues)

Обычная очередь

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        """Добавление в очередь"""
        self.items.append(item)
    
    def dequeue(self):
        """Удаление из очереди"""
        if not self.is_empty():
            return self.items.popleft()
        return None
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

Круговая очередь (Circular Queue)

class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = self.rear = -1
    
    def enqueue(self, item):
        if self.is_full():
            raise Exception("Queue is full")
        
        if self.is_empty():
            self.front = self.rear = 0
        else:
            self.rear = (self.rear + 1) % self.capacity
        
        self.queue[self.rear] = item
    
    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        
        item = self.queue[self.front]
        
        if self.front == self.rear:
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacity
        
        return item
    
    def is_empty(self):
        return self.front == -1
    
    def is_full(self):
        return (self.rear + 1) % self.capacity == self.front

4. Деревья (Trees)

Бинарное дерево

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

class BinaryTree:
    def __init__(self, root_value):
        self.root = TreeNode(root_value)
    
    def insert(self, value):
        """Вставка значения в дерево"""
        self._insert_recursive(self.root, value)
    
    def _insert_recursive(self, node, value):
        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):
        """Поиск значения в дереве"""
        return self._search_recursive(self.root, value)
    
    def _search_recursive(self, node, value):
        if node is None or node.value == value:
            return node
        
        if value < node.value:
            return self._search_recursive(node.left, value)
        return self._search_recursive(node.right, value)
    
    # Обходы дерева
    def inorder_traversal(self, node):
        """Центрированный обход (left-root-right)"""
        if node:
            self.inorder_traversal(node.left)
            print(node.value, end=" ")
            self.inorder_traversal(node.right)
    
    def preorder_traversal(self, node):
        """Прямой обход (root-left-right)"""
        if node:
            print(node.value, end=" ")
            self.preorder_traversal(node.left)
            self.preorder_traversal(node.right)

5. Графы (Graphs)

Список смежности

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v, directed=False):
        """Добавление ребра между вершинами u и v"""
        self.graph[u].append(v)
        if not directed:
            self.graph[v].append(u)
    
    def bfs(self, start):
        """Поиск в ширину"""
        visited = set()
        queue = deque([start])
        visited.add(start)
        
        while queue:
            vertex = queue.popleft()
            print(vertex, end=" ")
            
            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
    
    def dfs(self, start):
        """Поиск в глубину (итеративный)"""
        visited = set()
        stack = [start]
        
        while stack:
            vertex = stack.pop()
            if vertex not in visited:
                print(vertex, end=" ")
                visited.add(vertex)
                stack.extend(reversed(self.graph[vertex]))
    
    def dfs_recursive(self, vertex, visited=None):
        """Поиск в глубину (рекурсивный)"""
        if visited is None:
            visited = set()
        
        visited.add(vertex)
        print(vertex, end=" ")
        
        for neighbor in self.graph[vertex]:
            if neighbor not in visited:
                self.dfs_recursive(neighbor, visited)

# Использование
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)

print("BFS traversal:")
g.bfs(0)  # 0 1 2 3

print("\nDFS traversal:")
g.dfs(0)  # 0 1 2 3

Матрица смежности

class GraphMatrix:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
    
    def add_edge(self, u, v, weight=1, directed=False):
        self.matrix[u][v] = weight
        if not directed:
            self.matrix[v][u] = weight
    
    def display(self):
        for row in self.matrix:
            print(row)

6. Куча (Heap)

import heapq

# Встроенная реализация (min-heap)
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heapq.heappop(heap))  # 3 (минимальный элемент)

# Кастомная реализация
class MinHeap:
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i - 1) // 2
    
    def left_child(self, i):
        return 2 * i + 1
    
    def right_child(self, i):
        return 2 * i + 2
    
    def insert(self, key):
        self.heap.append(key)
        self._heapify_up(len(self.heap) - 1)
    
    def _heapify_up(self, i):
        while i > 0 and self.heap[self.parent(i)] > self.heap[i]:
            self.heap[i], self.heap[self.parent(i)] = \
                self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)
    
    def extract_min(self):
        if len(self.heap) == 0:
            return None
        
        root = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self._heapify_down(0)
        return root
    
    def _heapify_down(self, i):
        smallest = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
        
        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self._heapify_down(smallest)

7. Хеш-таблицы (Hash Tables)

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def _hash_function(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        hash_key = self._hash_function(key)
        bucket = self.table[hash_key]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        
        bucket.append((key, value))
    
    def get(self, key):
        hash_key = self._hash_function(key)
        bucket = self.table[hash_key]
        
        for k, v in bucket:
            if k == key:
                return v
        
        raise KeyError(f"Key {key} not found")
    
    def delete(self, key):
        hash_key = self._hash_function(key)
        bucket = self.table[hash_key]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                return
        
        raise KeyError(f"Key {key} not found")

# Использование
ht = HashTable()
ht.insert("apple", 5)
ht.insert("banana", 7)
print(ht.get("apple"))  # 5
ht.insert("apple", 10)  # Обновление
print(ht.get("apple"))  # 10

Основные принципы работы:

Для связанных списков:

1. Динамическое выделение памяти - каждый узел создается отдельно
2. Указатели/ссылки - узлы связаны через указатели на следующий/предыдущий элемент
3. Вставка/удаление O(1) в начало/конец (если есть указатель на конец)

Для графов:

1. Список смежности - эффективен для разреженных графов
2. Матрица смежности - эффективна для плотных графов
3. Обходы BFS/DFS - базовые алгоритмы для работы с графами

Для деревьев:

1. Рекурсивная структура - каждое поддерево само является деревом
2. Балансировка - важна для поддержания эффективности операций
3. Обходы - разные порядки (in-order, pre-order, post-order) для разных задач

Общие рекомендации:

1. Используйте встроенные коллекции (list, deque, heapq) когда возможно
2. Реализуйте кастомные структуры только при необходимости специфического поведения
3. Учитывайте временную и пространственную сложность операций
4. Для продакшен-кода предпочитайте библиотеки типа networkx для графов