Структуры данных
Интерактивные визуализации структур данных - посмотрите, как каждая структура хранит и переупорядочивает свои данные.
Trie (Prefix Tree)Watch a trie share common prefixes as words are inserted character by character.Binary TreeSee a binary tree fill level by level, then get walked in-order.Binary Search TreeWatch a BST place each value left or right, then search by comparison.AVL TreeSee an AVL tree rebalance itself with rotations as it grows.Heap (Priority Queue)Watch a min-heap sift each new value up to keep the smallest on top.Linked ListWatch nodes link together and pointers rewire on insert, search, and delete.Hash TableSee keys hashed into buckets, with collisions resolved by chaining.Hash MapWatch key-value pairs hashed into buckets and looked up by key.Doubly Linked ListSee a list with forward and backward pointers link and relink both ways.StackPush and pop at one end only: the last value in is the first one out.QueueEnqueue at the rear, dequeue at the front: first in, first out.
Сравнение: Структуры данных
| Алгоритм | Доступ | Поиск | Вставка | Удаление |
|---|---|---|---|---|
| Trie (Prefix Tree) | O(m) | O(m) | O(m) | O(m) |
| Binary Tree | O(n) | O(n) | O(n) | O(n) |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(log n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) |
| Heap (Priority Queue) | O(1) | O(n) | O(log n) | O(log n) |
| Linked List | O(n) | O(n) | O(1) | O(1) |
| Hash Table | - | O(1) | O(1) | O(1) |
| Hash Map | - | O(1) | O(1) | O(1) |
| Doubly Linked List | O(n) | O(n) | O(1) | O(1) |
| Stack | O(n) | O(n) | O(1) | O(1) |
| Queue | O(n) | O(n) | O(1) | O(1) |