Линейные и нелинейные структуры данных: разница, примеры, таблица

Что такое линейная структура данных и чем она отличается от нелинейной. Массив, список, стек, очередь, дерево, граф: примеры на Python, таблица сложности операций и как выбрать.

12 мин чтенияструктуры данных · алгоритмы · python

Коротко

ЛинейныеНелинейные
Как связаны элементыЦепочкой: у каждого один сосед слева и один справаСетью: у элемента может быть несколько соседей
ОбходОдин проход от начала до концаНужен алгоритм: DFS, BFS и их вариации
ПримерыМассив, связный список, стек, очередь, декДерево, куча, граф, хеш-таблица
Типичные задачиХранить последовательность, порядок обработкиИерархии, связи, быстрый поиск
  • Линейная структура данных — та, где элементы выстроены в одну последовательность: у каждого, кроме крайних, ровно один предыдущий и один следующий.
  • Нелинейная — та, где у элемента может быть несколько «следующих»: потомки в дереве, соседи в графе.
  • Деление говорит о логике связей, а не о том, как данные лежат в памяти. Куча — дерево, но хранится в обычном массиве.
  • Линейная не значит медленная, нелинейная не значит быстрая. Выбирают по операциям, которые нужны чаще всего.

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

Представьте очередь в поликлинике. У каждого человека есть тот, кто стоит перед ним, и тот, кто стоит за ним. Первый и последний — исключения: у первого никого впереди, у последнего никого сзади. Это и есть линейность.

Формально линейная структура данных обладает тремя свойствами:

  1. Есть единственный первый элемент и единственный последний.
  2. У каждого элемента не больше одного предшественника и не больше одного последователя.
  3. Все элементы можно обойти за один проход, никуда не возвращаясь.

Третье свойство — самый простой практический тест. Если структуру можно пройти одним циклом 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]

Сильная сторона — доступ по индексу за O(1)O(1). Слабая — вставка и удаление в начале или середине за O(n)O(n): приходится двигать хвост.

Подробнее: массив как структура данных. Питоновский 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

Картина обратная массиву. Вставить или удалить узел, когда уже стоишь рядом с ним, — O(1)O(1): достаточно переставить ссылки. Зато добраться до пятого элемента можно только через первые четыре, так что доступ по номеру — O(n)O(n).

Подробнее: список как структура данных и двусвязный список, где у узла есть ссылка ещё и на предыдущий.

Стек

Стопка тарелок: кладём сверху и снимаем сверху. Принцип 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) стоит O(n)O(n), потому что сдвигает все оставшиеся элементы. Очереди нужны для обхода в ширину, планировщиков задач, буферов сообщений.

Подробнее: очередь как структура данных.

Дек

Двусторонняя очередь: добавлять и удалять можно с обоих концов, и всё за O(1)O(1). Дек умеет быть и стеком, и очередью сразу.

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

В сбалансированном дереве поиск, вставка и удаление занимают O(log⁡n)O(\log n). Если дерево выродилось в «палку» (вставляли уже отсортированные числа), всё деградирует до O(n)O(n) — по сути, получается связный список.

Подробнее: дерево как структура данных, бинарное дерево поиска, префиксное дерево.

Куча

Дерево, в котором родитель всегда не больше своих потомков (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 — минимум лежит в нулевой ячейке

Кучу используют как очередь с приоритетом: достать самый важный элемент — O(log⁡n)O(\log n), подсмотреть его — O(1)O(1).

Подробнее: бинарная куча.

Граф

Самая общая структура: вершины и рёбра между ними, без ограничений. Связей может быть сколько угодно, возможны циклы, «главной» вершины нет. Дорожная сеть, друзья в соцсети, зависимости между пакетами — графы.

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 — главное отличие обхода графа от обхода дерева. В дереве до узла ведёт один путь, в графе — много, и без пометок обход будет ходить по кругу.

Дерево — частный случай графа: связный граф без циклов. А связный список — частный случай дерева, где у каждого узла один потомок. Так что линейные структуры в каком-то смысле вложены в нелинейные.

Подробнее: граф как структура данных.

Хеш-таблица

Хранит пары «ключ — значение» и находит значение по ключу в среднем за O(1)O(1). В Python это dict и set.

ages = {'Аня': 25, 'Борис': 31} ages['Вика'] = 28 print(ages['Борис']) # 31 — без перебора всех записей print('Глеб' in ages) # False

Хеш-таблицу обычно относят к нелинейным структурам, и вот почему: между её элементами нет отношения «предыдущий — следующий». Место элемента определяет хеш-функция от ключа, а не соседи. Но случай пограничный: внутри это массив корзин, и в части учебников хеш-таблицы выносят в отдельную группу. Если спросят на экзамене — назовите нелинейной и объясните почему, этого достаточно.

Подробнее: как устроена хеш-таблица.

Логическая линейность и физическая

Здесь путаются чаще всего. «Линейная» описывает то, как элементы связаны по смыслу, а не как они разложены в памяти.

СтруктураЛогическиВ памяти
МассивЛинейнаяПодряд, одним куском
Связный списокЛинейнаяУзлы разбросаны, связаны ссылками
Бинарная кучаНелинейнаяПодряд, в обычном массиве
Дерево на узлахНелинейнаяУзлы разбросаны, связаны ссылками

Связный список разбросан по памяти как попало, но он линейный: у каждого узла один следующий. Куча лежит в массиве ячейка к ячейке, но она нелинейная: у элемента с индексом i два потомка — с индексами 2i + 1 и 2i + 2.

Отсюда же следует, что одну и ту же логическую структуру можно реализовать по-разному. Стек — на массиве или на списке. Граф — списками смежности или матрицей. Классификация «линейная / нелинейная» от реализации не меняется.

Сравнительная таблица операций

Сложность указана в нотации «O большое». Если она вам пока незнакома, начните с разбора Big O.

СтруктураТипДоступ по индексуПоиск значенияВставкаУдаление
Массив (динамический)ЛинейнаяO(1)O(1)O(n)O(n)O(n)O(n), в конец O(1)O(1) ¹O(n)O(n), с конца O(1)O(1)
Связный списокЛинейнаяO(n)O(n)O(n)O(n)O(1)O(1) ²O(1)O(1) ²
СтекЛинейная——O(1)O(1) на вершинуO(1)O(1) с вершины
ОчередьЛинейная——O(1)O(1) в конецO(1)O(1) из начала
ДекЛинейная——O(1)O(1) с любого концаO(1)O(1) с любого конца
Хеш-таблицаНелинейная—O(1)O(1) в среднемO(1)O(1) в среднемO(1)O(1) в среднем
Сбалансированное дерево поискаНелинейная—O(log⁡n)O(\log n)O(log⁡n)O(\log n)O(log⁡n)O(\log n)
Бинарная кучаНелинейная—O(n)O(n), минимум O(1)O(1)O(log⁡n)O(\log n)O(log⁡n)O(\log n) для минимума
Граф (списки смежности)Нелинейная—O(V+E)O(V + E)O(1)O(1) вершина или реброO(V+E)O(V + E) вершина

¹ Амортизированно: изредка массив расширяется и копирует все элементы.

² Если уже есть ссылка на нужное место. В односвязном списке для удаления нужен ещё и предыдущий узел. Поиск самого места — O(n)O(n).

Прочерк означает, что операция для структуры не предусмотрена. У стека нет «достать третий снизу» — если она вам нужна, вам нужен не стек.

Пара оговорок к таблице. У хеш-таблицы худший случай — O(n)O(n), когда много ключей попало в одну корзину. У несбалансированного дерева поиска — тоже O(n)O(n). В графе VV — число вершин, EE — число рёбер.

Насколько это заметно на практике

Разница между O(n)O(n) и O(1)O(1) — не теория. Проверим, есть ли число в списке и в множестве из 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 внутри цикла превращает решение в O(n2)O(n^2). Замена списка на set возвращает O(n)O(n).
  • Связный список в прикладном коде нужен редко. Его теоретический плюс — вставка за O(1)O(1) — работает, только если ссылка на место уже есть. Обычно её приходится искать за O(n)O(n).
  • Структуры комбинируют. LRU-кеш — это хеш-таблица плюс двусвязный список. Алгоритм Дейкстры — граф плюс куча. Обход графа в ширину — граф плюс очередь плюс множество.

Частые ошибки и заблуждения

«Линейная структура — это та, что работает за линейное время». Нет. Слово «линейная» здесь про форму связей, а не про O(n)O(n). Доступ по индексу в массиве — O(1)O(1), хотя массив линейный. Поиск в куче — O(n)O(n), хотя куча нелинейная.

«Нелинейные структуры всегда быстрее». Быстрее на тех операциях, под которые они заточены. Дерево поиска ищет за O(log⁡n)O(\log n), но получить «элемент номер 500» в нём без дополнительных ухищрений нельзя, а в массиве — мгновенно.

«Связный список нелинейный, потому что узлы разбросаны по памяти». Расположение в памяти не важно. Важно, что у каждого узла один следующий.

«Стек и очередь — это отдельные способы хранения». Это абстракции: правила, в каком порядке можно класть и доставать элементы. Хранить их можно и в массиве, и в списке.

Очередь на list.pop(0). Работает правильно, но медленно: каждое извлечение — O(n)O(n). Используйте collections.deque.

Обход графа без множества посещённых. На дереве такой код работает, на графе с циклом — зависает.

Где это спрашивают

На экзамене или зачёте вопрос звучит прямо: «дайте определение линейной структуры данных, приведите примеры». Достаточно определения через «один предшественник — один последователь» и списка из раздела выше.

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

  • Чем массив отличается от связного списка и когда что выбрать?
  • На чём реализовать очередь, чтобы обе операции были за O(1)O(1)?
  • Почему куча хранится в массиве, если это дерево?
  • Чем дерево отличается от графа?
  • Какую структуру вы взяли в решении и почему не другую?

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

Что запомнить

  • Линейная структура: элементы стоят в цепочку, обход одним проходом. Массив, связный список, стек, очередь, дек.
  • Нелинейная структура: у элемента несколько связей, для обхода нужен DFS или BFS. Дерево, куча, граф, хеш-таблица.
  • Классификация говорит о логике связей, а не о памяти и не о скорости.
  • Выбирайте структуру по самой частой операции — таблица сложности выше в помощь.

Потренироваться в спокойной обстановке

Все задачи

Читать дальше

Все статьи
Алгоритмы и структуры данныхОчередь (queue): структура данных FIFO, операции и реализация на PythonОчередь как структура данных простыми словами: принцип FIFO, операции за O(1), почему list.pop(0) медленный, collections.deque, кольцевая очередь и применение в BFS и планировщиках.Алгоритмы и структуры данныхГраф как структура данных: матрица смежности, список смежности и список рёбер на PythonЧто такое граф в программировании: вершины и рёбра, ориентированный, неориентированный и взвешенный граф. Три представления графа в памяти с кодом на Python и сравнением по памяти и скорости.Алгоритмы и структуры данныхБинарное дерево: что это, виды, листья, полное и сбалансированное деревоБинарное дерево простыми словами: корень, узлы и листья, высота, виды деревьев (строгое, полное, совершенное, сбалансированное, вырожденное) и построение на Python с рабочим кодом.