Bezdepbonusu7Программирование: статьи и ответы

Алгоритмы

Структуры данных: основные виды, примеры на Python и как выбрать

Структуры данных - это способы хранения и организации значений в программе: массивы, списки, стеки, очереди, хеш-таблицы, деревья и графы. Разберём каждую простыми словами, покажем код на Python и сравним скорость основных операций.

Структуры данных: основные виды, примеры на Python и как выбрать
Содержание
  1. Что такое структуры данных
  2. Классификация: линейные и нелинейные
  3. Массив и список
  4. Стек: последним пришёл - первым ушёл
  5. Очередь: первым пришёл - первым ушёл
  6. Хеш-таблица: словарь и множество
  7. Дерево
  8. Граф
  9. Сложность операций и выбор структуры
  10. Частые вопросы

Что такое структуры данных

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

От выбора структуры зависит скорость программы и простота кода. Искать имя в неупорядоченном списке из миллиона записей долго, а в словаре практически мгновенно. Поэтому структуры данных изучают вместе с алгоритмами: одно без другого бесполезно.

Ниже разберём основные виды: массив и список, стек, очередь, хеш-таблицу (словарь и множество), дерево и граф. Примеры на Python, потому что в нём почти всё нужное есть из коробки.

Классификация: линейные и нелинейные

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

Отдельно выделяют ассоциативные структуры, где значение ищут не по номеру, а по ключу: словарь и множество. Они реализованы через хеш-таблицу.

СтруктураТипТипичное применение
Массив, списокЛинейнаяХранение последовательности, доступ по номеру
СтекЛинейнаяОтмена действий, разбор скобок, вызовы функций
ОчередьЛинейнаяЗадачи по порядку, обход в ширину
Хеш-таблицаАссоциативнаяПоиск по ключу, подсчёт, уникальные значения
ДеревоНелинейнаяФайловая система, иерархии, быстрый поиск
ГрафНелинейнаяКарты, соцсети, маршруты
Схема основных структур данных: стек, очередь, дерево
Стек, очередь и дерево: как расположены элементы

Массив и список

Массив хранит элементы подряд в памяти, поэтому обратиться к элементу по номеру можно мгновенно. Вставка в начало или середину дороже: все последующие элементы приходится сдвигать.

В Python роль массива играет список list. Он динамический: может расти и хранить значения разных типов. Подробнее о методах и срезах написано в статье про списки в Python.


nums = [10, 20, 30]
nums.append(40)        # добавить в конец - быстро
nums.insert(0, 5)      # вставка в начало - медленно, сдвигает всё
print(nums[2])         # доступ по индексу - быстро: 20
print(30 in nums)      # поиск перебором: True

Для компактного хранения чисел есть модуль array и библиотека NumPy, но для старта хватает обычного списка.

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

Стек: последним пришёл - первым ушёл

Стек работает как стопка тарелок: кладёте сверху и берёте сверху. Принцип называют LIFO. Так устроены кнопка "Назад" в браузере, отмена действия в редакторе и стек вызовов функций.


stack = []
stack.append("страница 1")
stack.append("страница 2")
stack.append("страница 3")
print(stack.pop())    # страница 3 - последняя добавленная
print(stack)          # ['страница 1', 'страница 2']

Список отлично подходит для стека, потому что append и pop с конца работают быстро. Подробный разбор есть в переводе про структуру данных стека и её применение.

Очередь: первым пришёл - первым ушёл

Очередь работает как в магазине: кто раньше встал, того раньше обслужат (FIFO). Её используют для обработки задач по порядку, печати документов, сообщений в брокерах.

Список для очереди не годится: удаление из начала сдвигает все элементы. Правильный выбор - collections.deque, где операции с обоих концов быстрые.


from collections import deque

queue = deque()
queue.append("задача A")
queue.append("задача B")
queue.append("задача C")
print(queue.popleft())   # задача A - вышла первой
print(len(queue))        # 2

Частая ошибка: делать очередь на обычном списке через pop(0). На маленьких данных незаметно, на сотнях тысяч элементов программа начинает заметно тормозить. Берите deque.

Хеш-таблица: словарь и множество

Хеш-таблица превращает ключ в число (хеш) и по нему сразу находит место хранения. Поэтому поиск, добавление и удаление в среднем занимают одинаковое короткое время независимо от размера. В Python это dict и set.


phones = {"Анна": "+7 900 111-11-11", "Борис": "+7 900 222-22-22"}
phones["Вера"] = "+7 900 333-33-33"
print(phones["Анна"])           # поиск по ключу
print("Борис" in phones)        # True

words = ["да", "нет", "да", "может", "нет", "да"]
counts = {}
for w in words:
    counts[w] = counts.get(w, 0) + 1
print(counts)                   # {'да': 3, 'нет': 2, 'может': 1}

unique = set(words)             # множество: без повторов
print(unique)

Ключом словаря может быть только неизменяемый объект: строка, число, кортеж. Список ключом быть не может. Множество удобно для проверки "есть ли значение", удаления дублей и операций пересечения и объединения.

В худшем случае при множестве коллизий операции замедляются до линейного времени, но с хорошей хеш-функцией такое встречается редко.

Дерево

Дерево состоит из узлов: у верхнего (корня) есть потомки, у тех свои, и так далее. Без циклов. Файловая система, структура HTML-страницы, оглавление - всё это деревья.

Популярный вариант - двоичное дерево поиска: у каждого узла не больше двух потомков, слева значения меньше, справа больше. Поиск в нём занимает время порядка логарифма от размера, если дерево сбалансировано.


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

def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

def inorder(node):                      # обход слева направо
    if node:
        yield from inorder(node.left)
        yield node.value
        yield from inorder(node.right)

root = None
for v in [8, 3, 10, 1, 6, 14]:
    root = insert(root, v)
print(list(inorder(root)))              # [1, 3, 6, 8, 10, 14]

Обход дерева слева направо выдаёт значения по возрастанию. Класс Node здесь - маленький пример объектно-ориентированного подхода: данные узла и связи хранятся в объекте.

Граф

Граф - набор вершин и рёбер между ними. Города и дороги, люди и дружба, страницы и ссылки. В отличие от дерева, здесь допустимы циклы, а рёбра могут быть направленными.

Самый простой способ хранить граф в Python - словарь, где ключ - вершина, а значение - список соседей. Для обхода в ширину нужна как раз очередь.


from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": [],
}

def bfs(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        v = queue.popleft()
        order.append(v)
        for neighbor in graph[v]:
            if neighbor not in seen:
                seen.add(neighbor)
                queue.append(neighbor)
    return order

print(bfs(graph, "A"))   # ['A', 'B', 'C', 'D']

Обратите внимание, что в одном алгоритме сразу три структуры: словарь для графа, множество для посещённых вершин и очередь для порядка обхода. Так и выглядит реальная работа со структурами данных.

Сложность операций и выбор структуры

Чтобы сравнивать структуры, используют нотацию Big O: она показывает, как растёт время операции с ростом данных. Подробно она объяснена в статье про нотацию Big O. Ниже типичные значения для встроенных типов Python по официальной таблице сложности (для словаря и множества приведены средние значения).

Операцияlistdequedictset
Доступ по индексу или ключуO(1)O(n) в серединеO(1)-
Добавление в конецO(1)O(1)O(1)O(1)
Вставка или удаление в началеO(n)O(1)--
Проверка "есть ли элемент"O(n)O(n)O(1)O(1)
Удаление по значению или ключуO(n)O(n)O(1)O(1)

Как выбирать на практике:

  • Нужен порядок и доступ по номеру - список.
  • Нужно часто брать из начала - deque.
  • Нужно быстро искать по ключу или подсчитывать - словарь.
  • Нужно убрать дубли или проверять принадлежность - множество.
  • Данные вложены друг в друга - дерево, а связи произвольные - граф.

Если хотите пойти дальше, посмотрите перевод про изучение структур данных и алгоритмов и обзор 10 алгоритмов, которые должен знать каждый разработчик.

Частые вопросы

Какие бывают основные структуры данных?

Массив и список, стек, очередь, хеш-таблица (словарь, множество), дерево и граф. Первые четыре линейные, дерево и граф нелинейные.

Чем отличается стек от очереди?

Стек работает по принципу LIFO: последний добавленный элемент выходит первым. Очередь работает по FIFO: первым выходит тот, кто пришёл раньше.

Что такое линейная структура данных?

Это структура, где элементы расположены последовательно, и у каждого есть не более одного предыдущего и одного следующего. Примеры: массив, список, стек, очередь.

Какие структуры данных есть в Python?

Встроенные: list, tuple, dict, set, frozenset. В модуле collections есть deque, Counter, defaultdict и другие, а очередь с приоритетом реализует модуль heapq.

Зачем знать структуры данных и алгоритмы?

Правильный выбор структуры ускоряет программу в десятки и сотни раз и упрощает код. Эти темы к тому же стандартно спрашивают на собеседованиях.

Что такое структура данных в базе данных?

Это другая область: схема таблиц, связи и индексы. Индексы в базах данных часто строятся на деревьях, поэтому знание структур данных помогает и там.

Список в Python - это массив или связный список?

Это динамический массив: элементы лежат в памяти подряд, доступ по индексу быстрый, а вставка в начало медленная.

Источники

Python

Похожие материалы

Версии программ и команды проверены на дату публикации. Если что-то изменилось, сверяйтесь с официальной документацией. Нашли неточность? Напишите на admin@bezdepbonusu7.win.