Линейные и нелинейные структуры данных: разница, примеры, таблица
Что такое линейная структура данных и чем она отличается от нелинейной. Массив, список, стек, очередь, дерево, граф: примеры на Python, таблица сложности операций и как выбрать.
Коротко
| Линейные | Нелинейные | |
|---|---|---|
| Как связаны элементы | Цепочкой: у каждого один сосед слева и один справа | Сетью: у элемента может быть несколько соседей |
| Обход | Один проход от начала до конца | Нужен алгоритм: DFS, BFS и их вариации |
| Примеры | Массив, связный список, стек, очередь, дек | Дерево, куча, граф, хеш-таблица |
| Типичные задачи | Хранить последовательность, порядок обработки | Иерархии, связи, быстрый поиск |
- Линейная структура данных — та, где элементы выстроены в одну последовательность: у каждого, кроме крайних, ровно один предыдущий и один следующий.
- Нелинейная — та, где у элемента может быть несколько «следующих»: потомки в дереве, соседи в графе.
- Деление говорит о логике связей, а не о том, как данные лежат в памяти. Куча — дерево, но хранится в обычном массиве.
- Линейная не значит медленная, нелинейная не значит быстрая. Выбирают по операциям, которые нужны чаще всего.
Что такое линейная структура данных
Представьте очередь в поликлинике. У каждого человека есть тот, кто стоит перед ним, и тот, кто стоит за ним. Первый и последний — исключения: у первого никого впереди, у последнего никого сзади. Это и есть линейность.
Формально линейная структура данных обладает тремя свойствами:
- Есть единственный первый элемент и единственный последний.
- У каждого элемента не больше одного предшественника и не больше одного последователя.
- Все элементы можно обойти за один проход, никуда не возвращаясь.
Третье свойство — самый простой практический тест. Если структуру можно пройти одним циклом for без рекурсии и без пометок «здесь я уже был», она линейная.
nums = [10, 20, 30, 40] for x in nums: # один проход, ни один элемент не пропущен print(x, end=' ') # 10 20 30 40
Что такое нелинейная структура данных
Теперь представьте не очередь, а схему метро или оргструктуру компании. У начальника отдела пять подчинённых — кто из них «следующий»? У станции три пересадки — куда идти дальше? Единственного ответа нет, и именно поэтому структура нелинейная.
В нелинейной структуре у элемента может быть несколько последователей, а иногда и несколько предшественников. Обычным циклом её не обойти: на каждой развилке нужно решить, куда пойти сначала и как не забыть про остальные ветки.
tree = { 'value': 1, 'children': [ {'value': 2, 'children': []}, {'value': 3, 'children': [{'value': 4, 'children': []}]}, ], } def walk(node): print(node['value'], end=' ') for child in node['children']: # развилка: куда идти дальше? walk(child) walk(tree) # 1 2 3 4
Здесь уже понадобилась рекурсия. Она запоминает, в какую ветку мы ещё не заходили. Кстати, запоминает с помощью стека вызовов — то есть нелинейную структуру мы обходим, опираясь на линейную.
Линейные структуры данных: примеры
Массив
Элементы лежат в памяти подряд, каждый доступен по номеру. Это самая простая и самая быстрая структура для чтения: адрес элемента вычисляется по формуле, без перебора.
temps = [18, 21, 19, 23] print(temps[2]) # 19 — сразу, без перебора temps.append(25) # в конец — быстро temps.insert(0, 15) # в начало — сдвигает все элементы print(temps) # [15, 18, 21, 19, 23, 25]
Сильная сторона — доступ по индексу за . Слабая — вставка и удаление в начале или середине за : приходится двигать хвост.
Подробнее: массив как структура данных. Питоновский list — это динамический массив, который сам увеличивает ёмкость, когда место заканчивается.
Связный список
Элементы разбросаны по памяти, и каждый хранит ссылку на следующий. Порядок задают ссылки, а не расположение в памяти.
class Node: def __init__(self, value, next=None): self.value = value self.next = next head = Node(1, Node(2, Node(3))) # 1 -> 2 -> 3 head = Node(0, head) # вставка в начало за O(1) node = head while node: # обход — только по ссылкам, по порядку print(node.value, end=' ') # 0 1 2 3 node = node.next
Картина обратная массиву. Вставить или удалить узел, когда уже стоишь рядом с ним, — : достаточно переставить ссылки. Зато добраться до пятого элемента можно только через первые четыре, так что доступ по номеру — .
Подробнее: список как структура данных и двусвязный список, где у узла есть ссылка ещё и на предыдущий.
Стек
Стопка тарелок: кладём сверху и снимаем сверху. Принцип LIFO — last in, first out, «последним пришёл, первым ушёл».
stack = [] stack.append('a') stack.append('b') stack.append('c') print(stack.pop()) # c — последним пришёл, первым ушёл print(stack[-1]) # b — посмотреть вершину, не снимая
Стек — это не способ хранения, а ограничение доступа: работать можно только с вершиной. Внутри обычно массив или связный список. На стеке держатся вызовы функций, отмена действий в редакторе, проверка скобок, обход в глубину.
Подробнее: стек как структура данных.
Очередь
Очередь в кассу: добавляем в конец, забираем из начала. Принцип FIFO — first in, first out.
from collections import deque queue = deque() queue.append('первый') queue.append('второй') queue.append('третий') print(queue.popleft()) # первый — кто раньше пришёл, тот раньше ушёл
Обратите внимание: очередь сделана на deque, а не на list. У списка pop(0) стоит , потому что сдвигает все оставшиеся элементы. Очереди нужны для обхода в ширину, планировщиков задач, буферов сообщений.
Подробнее: очередь как структура данных.
Дек
Двусторонняя очередь: добавлять и удалять можно с обоих концов, и всё за . Дек умеет быть и стеком, и очередью сразу.
window = deque([1, 2, 3]) window.appendleft(0) window.pop() print(window) # deque([0, 1, 2])
Подробнее: дек и зачем он нужен.
Нелинейные структуры данных: примеры
Дерево
Иерархия: есть корень, у каждого узла — потомки, у каждого узла, кроме корня, ровно один родитель. Циклов нет. Файловая система, DOM-дерево страницы, структура JSON — всё это деревья.
Самая частая разновидность на собеседованиях — бинарное дерево поиска. В нём слева от узла лежат значения меньше, справа — больше. Поэтому при поиске на каждом шаге половину дерева можно отбросить.
class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right # 8 # / \ # 3 10 # / \ # 1 6 root = TreeNode(8, TreeNode(3, TreeNode(1), TreeNode(6)), TreeNode(10)) def contains(node, target): while node: if target == node.value: return True node = node.left if target < node.value else node.right return False print(contains(root, 6)) # True print(contains(root, 7)) # False
В сбалансированном дереве поиск, вставка и удаление занимают . Если дерево выродилось в «палку» (вставляли уже отсортированные числа), всё деградирует до — по сути, получается связный список.
Подробнее: дерево как структура данных, бинарное дерево поиска, префиксное дерево.
Куча
Дерево, в котором родитель всегда не больше своих потомков (min-куча) или не меньше (max-куча). Про порядок между соседними ветками куча ничего не обещает — зато минимум всегда лежит в корне.
import heapq tasks = [5, 1, 8, 3] heapq.heapify(tasks) # теперь это куча, хотя тип — обычный list print(heapq.heappop(tasks)) # 1 — всегда минимум heapq.heappush(tasks, 2) print(tasks[0]) # 2 — минимум лежит в нулевой ячейке
Кучу используют как очередь с приоритетом: достать самый важный элемент — , подсмотреть его — .
Подробнее: бинарная куча.
Граф
Самая общая структура: вершины и рёбра между ними, без ограничений. Связей может быть сколько угодно, возможны циклы, «главной» вершины нет. Дорожная сеть, друзья в соцсети, зависимости между пакетами — графы.
from collections import deque graph = { 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C'], } def bfs(start): seen = {start} queue = deque([start]) order = [] while queue: node = queue.popleft() order.append(node) for neighbor in graph[node]: if neighbor not in seen: # без этого зациклимся на A-B-D-C-A seen.add(neighbor) queue.append(neighbor) return order print(bfs('A')) # ['A', 'B', 'C', 'D']
Множество seen — главное отличие обхода графа от обхода дерева. В дереве до узла ведёт один путь, в графе — много, и без пометок обход будет ходить по кругу.
Дерево — частный случай графа: связный граф без циклов. А связный список — частный случай дерева, где у каждого узла один потомок. Так что линейные структуры в каком-то смысле вложены в нелинейные.
Подробнее: граф как структура данных.
Хеш-таблица
Хранит пары «ключ — значение» и находит значение по ключу в среднем за . В Python это dict и set.
ages = {'Аня': 25, 'Борис': 31} ages['Вика'] = 28 print(ages['Борис']) # 31 — без перебора всех записей print('Глеб' in ages) # False
Хеш-таблицу обычно относят к нелинейным структурам, и вот почему: между её элементами нет отношения «предыдущий — следующий». Место элемента определяет хеш-функция от ключа, а не соседи. Но случай пограничный: внутри это массив корзин, и в части учебников хеш-таблицы выносят в отдельную группу. Если спросят на экзамене — назовите нелинейной и объясните почему, этого достаточно.
Подробнее: как устроена хеш-таблица.
Логическая линейность и физическая
Здесь путаются чаще всего. «Линейная» описывает то, как элементы связаны по смыслу, а не как они разложены в памяти.
| Структура | Логически | В памяти |
|---|---|---|
| Массив | Линейная | Подряд, одним куском |
| Связный список | Линейная | Узлы разбросаны, связаны ссылками |
| Бинарная куча | Нелинейная | Подряд, в обычном массиве |
| Дерево на узлах | Нелинейная | Узлы разбросаны, связаны ссылками |
Связный список разбросан по памяти как попало, но он линейный: у каждого узла один следующий. Куча лежит в массиве ячейка к ячейке, но она нелинейная: у элемента с индексом i два потомка — с индексами 2i + 1 и 2i + 2.
Отсюда же следует, что одну и ту же логическую структуру можно реализовать по-разному. Стек — на массиве или на списке. Граф — списками смежности или матрицей. Классификация «линейная / нелинейная» от реализации не меняется.
Сравнительная таблица операций
Сложность указана в нотации «O большое». Если она вам пока незнакома, начните с разбора Big O.
| Структура | Тип | Доступ по индексу | Поиск значения | Вставка | Удаление |
|---|---|---|---|---|---|
| Массив (динамический) | Линейная | , в конец ¹ | , с конца | ||
| Связный список | Линейная | ² | ² | ||
| Стек | Линейная | — | — | на вершину | с вершины |
| Очередь | Линейная | — | — | в конец | из начала |
| Дек | Линейная | — | — | с любого конца | с любого конца |
| Хеш-таблица | Нелинейная | — | в среднем | в среднем | в среднем |
| Сбалансированное дерево поиска | Нелинейная | — | |||
| Бинарная куча | Нелинейная | — | , минимум | для минимума | |
| Граф (списки смежности) | Нелинейная | — | вершина или ребро | вершина |
¹ Амортизированно: изредка массив расширяется и копирует все элементы.
² Если уже есть ссылка на нужное место. В односвязном списке для удаления нужен ещё и предыдущий узел. Поиск самого места — .
Прочерк означает, что операция для структуры не предусмотрена. У стека нет «достать третий снизу» — если она вам нужна, вам нужен не стек.
Пара оговорок к таблице. У хеш-таблицы худший случай — , когда много ключей попало в одну корзину. У несбалансированного дерева поиска — тоже . В графе — число вершин, — число рёбер.
Насколько это заметно на практике
Разница между и — не теория. Проверим, есть ли число в списке и в множестве из 100 000 элементов:
import timeit data = list(range(100_000)) as_set = set(data) print(timeit.timeit(lambda: 99_999 in data, number=100)) print(timeit.timeit(lambda: 99_999 in as_set, number=100))
На моём ноутбуке первая строка печатает около 0,05 секунды, вторая — меньше 0,00001. Разница в тысячи раз, и с ростом данных она только увеличивается. Точные цифры у вас будут другими, порядок — тот же.
Как выбрать структуру данных
Не начинайте с вопроса «линейная или нелинейная». Начните с вопроса «что я буду делать с данными чаще всего».
| Что нужно | Что взять |
|---|---|
| Хранить по порядку, читать по номеру | Массив |
| Часто вставлять и удалять в середине, имея ссылку на узел | Связный список |
| Обрабатывать в обратном порядке, откатывать назад | Стек |
| Обрабатывать в порядке поступления | Очередь |
| Работать с обоими концами | Дек |
| Быстро проверять «есть ли такой элемент», искать по ключу | Хеш-таблица |
| Держать данные отсортированными и искать по диапазону | Сбалансированное дерево поиска |
| Постоянно доставать минимум или максимум | Куча |
| Описать иерархию: папки, категории, комментарии | Дерево |
| Описать произвольные связи: маршруты, зависимости | Граф |
Несколько практических правил:
- По умолчанию берите массив. В Python это
list. Он компактен, дружит с кешем процессора и на небольших данных обгоняет «правильные» структуры даже там, где проигрывает по асимптотике. - Поиск по значению в цикле — сигнал взять хеш-таблицу. Строчка
if x in some_listвнутри цикла превращает решение в . Замена списка наsetвозвращает . - Связный список в прикладном коде нужен редко. Его теоретический плюс — вставка за — работает, только если ссылка на место уже есть. Обычно её приходится искать за .
- Структуры комбинируют. LRU-кеш — это хеш-таблица плюс двусвязный список. Алгоритм Дейкстры — граф плюс куча. Обход графа в ширину — граф плюс очередь плюс множество.
Частые ошибки и заблуждения
«Линейная структура — это та, что работает за линейное время». Нет. Слово «линейная» здесь про форму связей, а не про . Доступ по индексу в массиве — , хотя массив линейный. Поиск в куче — , хотя куча нелинейная.
«Нелинейные структуры всегда быстрее». Быстрее на тех операциях, под которые они заточены. Дерево поиска ищет за , но получить «элемент номер 500» в нём без дополнительных ухищрений нельзя, а в массиве — мгновенно.
«Связный список нелинейный, потому что узлы разбросаны по памяти». Расположение в памяти не важно. Важно, что у каждого узла один следующий.
«Стек и очередь — это отдельные способы хранения». Это абстракции: правила, в каком порядке можно класть и доставать элементы. Хранить их можно и в массиве, и в списке.
Очередь на list.pop(0). Работает правильно, но медленно: каждое извлечение — . Используйте collections.deque.
Обход графа без множества посещённых. На дереве такой код работает, на графе с циклом — зависает.
Где это спрашивают
На экзамене или зачёте вопрос звучит прямо: «дайте определение линейной структуры данных, приведите примеры». Достаточно определения через «один предшественник — один последователь» и списка из раздела выше.
На собеседовании напрямую так спрашивают редко, чаще на позициях стажёра и джуна. Зато тема всплывает в уточняющих вопросах:
- Чем массив отличается от связного списка и когда что выбрать?
- На чём реализовать очередь, чтобы обе операции были за ?
- Почему куча хранится в массиве, если это дерево?
- Чем дерево отличается от графа?
- Какую структуру вы взяли в решении и почему не другую?
Последний вопрос — главный. В большинстве алгоритмических задач полдела — выбрать структуру: стек для скобок, хеш-таблицу для поиска пары, очередь для кратчайшего пути. Обзор всех структур с картой, что учить в каком порядке, — в статье структуры данных: обзор.
Что запомнить
- Линейная структура: элементы стоят в цепочку, обход одним проходом. Массив, связный список, стек, очередь, дек.
- Нелинейная структура: у элемента несколько связей, для обхода нужен DFS или BFS. Дерево, куча, граф, хеш-таблица.
- Классификация говорит о логике связей, а не о памяти и не о скорости.
- Выбирайте структуру по самой частой операции — таблица сложности выше в помощь.