Структура данных — это способ организации и хранения данных в памяти, чтобы они были эффективно доступны и модифицируемы. Абстрактный тип данных (ADT) — это логическая модель — операции и их поведение — независимо от способа реализации.
ADT описывает, операции существуют; структура данных определяет, они хранятся и как быстро работают.
ADT: Stack → push, pop, peek (LIFO behavior)
Implementations: → array-backed OR linked-list-backed
ADT: List → get(i), insert, remove
Implementations: → dynamic array OR linked list
# Both satisfy the "Stack" ADT, but have different cost profiles
stack = [] # list-backed stack
stack.append(10) # push -> amortized O(1)
top = stack[-1] # peek -> O(1)
stack.pop() # pop -> O(1)
| Аспект | Вопрос для рассмотрения |
|---|---|
| Характер доступа | Случайный доступ или последовательный? |
| Мутации | Частые вставки/удаления в середине? |
| Упорядочение | Отсортировано, FIFO, LIFO или нет? |
| Поиск | По индексу или по ключу? |
Правильный выбор — это тот, чьи стандартные операции дешевы для вашей рабочей нагрузки.
Выбор неправильной структуры превращает операцию O(1) в O(n), что может замедлить код в тысячи раз при масштабировании.
Рассуждение в терминах ADT позволяет вам сначала учитывать поведение, а затем менять реализации позже, не переписывая вызывающий код.