10 типов структур данных, которые нужно знать + видео и упражнения

Автор оригинала: Beau Carnes
Екатерина Малахова, редактор-фрилансер, специально для блога Нетологии адаптировала статью Beau Carnes об основных типах структур данных.

«Плохие программисты думают о коде. Хорошие программисты думают о структурах данных и их взаимосвязях», — Линус Торвальдс, создатель Linux.

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

В этой статье я покажу вам 10 самых распространенных структур данных. Для каждой из них приведены видео и примеры их реализации на JavaScript. Чтобы вы смогли попрактиковаться, я также добавил несколько упражнений из бета-версии новой учебной программы freeCodeCamp.

Обратите внимание, что некоторые структуры данных включают временную сложность в нотации «большого О». Это относится не ко всем из них, так как иногда временная сложность зависит от реализации. Если вы хотите узнать больше о нотации «большого О», посмотрите это видео от Briana Marie.

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

Связные списки


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


Так устроен связный список

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

Основные операции в связном списке включают добавление, удаление и поиск элемента в списке.

Пример реализации на JavaScript

Временная сложность связного списка
╔═══════════╦═════════════════╦═══════════════╗
║ Алгоритм  ║Среднее значение ║ Худший случай ║
╠═══════════╬═════════════════╬═══════════════╣
║ Space     ║ O(n)            ║ O(n)          ║
║ Search    ║ O(n)            ║ O(n)          ║
║ Insert    ║ O(1)            ║ O(1)          ║
║ Delete    ║ O(1)            ║ O(1)          ║
╚═══════════╩═════════════════╩═══════════════╝


Упражнения от freeCodeCamp



Стеки


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

Стек организован по принципу LIFO (Last In First Out, «последним пришёл — первым вышел») . Это значит, что последний элемент, который вы добавили в стек, первым выйдет из него.


Так устроен стек

В стеках можно выполнять три операции: добавление элемента (push), удаление элемента (pop) и отображение содержимого стека (pip).

Пример реализации на JavaScript

Временная сложность стека
╔═══════════╦═════════════════╦═══════════════╗
║ Алгоритм  ║Среднее значение ║ Худший случай ║
╠═══════════╬═════════════════╬═══════════════╣
║ Space     ║ O(n)            ║ O(n)          ║
║ Search    ║ O(n)            ║ O(n)          ║
║ Insert    ║ O(1)            ║ O(1)          ║
║ Delete    ║ O(1)            ║ O(1)          ║
╚═══════════╩═════════════════╩═══════════════╝


Упражнения от freeCodeCamp



Очереди


Эту структуру можно представить как очередь в продуктовом магазине. Первым обслуживают того, кто пришёл в самом начале — всё как в жизни.


Так устроена очередь

Очередь устроена по принципу FIFO (First In First Out, «первый пришёл — первый вышел»). Это значит, что удалить элемент можно только после того, как были убраны все ранее добавленные элементы.

Очередь позволяет выполнять две основных операции: добавлять элементы в конец очереди (enqueue) и удалять первый элемент (dequeue).

Пример реализации на JavaScript

Временная сложность очереди
╔═══════════╦═════════════════╦═══════════════╗
║ Алгоритм  ║Среднее значение ║ Худший случай ║
╠═══════════╬═════════════════╬═══════════════╣
║ Space     ║ O(n)            ║ O(n)          ║
║ Search    ║ O(n)            ║ O(n)          ║
║ Insert    ║ O(1)            ║ O(1)          ║
║ Delete    ║ O(1)            ║ O(1)          ║
╚═══════════╩═════════════════╩═══════════════╝


Упражнения от freeCodeCamp



Множества



Так выглядит множество

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

  • Объединение комбинирует все элементы из двух разных множеств, превращая их в одно (без дубликатов).
  • Пересечение анализирует два множества и  создает еще одно из тех элементов, которые присутствуют в обоих изначальных множествах.
  • Разность выводит список элементов, которые есть в одном множестве, но отсутствуют в другом.
  • Подмножество выдает булево значение, которое показывает, включает ли одно множество все элементы другого множества.

Пример реализации на JavaScript


Упражнения от freeCodeCamp



Map


Map — это структура, которая хранит данные в парах ключ/значение, где каждый ключ уникален. Иногда её также называют ассоциативным массивом или словарём. Map часто используют для быстрого поиска данных. Она позволяет делать следующие вещи:

  • добавлять пары в коллекцию;
  • удалять пары из коллекции;
  • изменять существующей пары;
  • искать значение, связанное с определенным ключом.



Так устроена структура map

Пример реализации на JavaScript



Упражнения от freeCodeCamp




Хэш-таблицы





Так работают хэш-таблица и хэш-функция

Хэш-таблица — это похожая на Map структура, которая содержит пары ключ/значение. Она использует хэш-функцию для вычисления индекса в массиве из блоков данных, чтобы найти желаемое значение.

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

Таким образом, когда вы вводите пару ключ/значение в хэш-таблицу, ключ проходит через хэш-функцию и превращается в число. В дальнейшем это число используется как фактический ключ, который соответствует определенному значению. Когда вы снова введёте тот же ключ, хэш-функция обработает его и вернет такой же числовой результат. Затем этот результат будет использован для поиска связанного значения. Такой подход заметно сокращает среднее время поиска.

Пример реализации на JavaScript

Временная сложность хэш-таблицы
╔═══════════╦═════════════════╦═══════════════╗
║ Алгоритм  ║Среднее значение ║ Худший случай ║
╠═══════════╬═════════════════╬═══════════════╣
║ Space     ║ O(n)            ║ O(n)          ║
║ Search    ║ O(1)            ║ O(n)          ║
║ Insert    ║ O(1)            ║ O(n)          ║
║ Delete    ║ O(1)            ║ O(n)          ║
╚═══════════╩═════════════════╩═══════════════╝


Упражнения от freeCodeCamp



Двоичное дерево поиска




Двоичное дерево поиска

Дерево — это структура данных, состоящая из узлов. Ей присущи следующие свойства:

  • Каждое дерево имеет корневой узел (вверху).
  • Корневой узел имеет ноль или более дочерних узлов.
  • Каждый дочерний узел имеет ноль или более дочерних узлов, и так далее.

У двоичного дерева поиска есть два дополнительных свойства:

  • Каждый узел имеет до двух дочерних узлов (потомков).
  • Каждый узел меньше своих потомков справа, а его потомки слева меньше его самого.

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

Пример реализации на JavaScript

Временная сложность двоичного дерева поиска 
╔═══════════╦═════════════════╦══════════════╗
║ Алгоритм  ║Среднее значение ║Худший случай ║
╠═══════════╬═════════════════╬══════════════╣
║ Space     ║ O(n)            ║ O(n)         ║
║ Search    ║ O(log n)        ║ O(n)         ║
║ Insert    ║ O(log n)        ║ O(n)         ║
║ Delete    ║ O(log n)        ║ O(n)         ║
╚═══════════╩═════════════════╩══════════════╝



Упражнения от freeCodeCamp



Префиксное дерево


Префиксное (нагруженное) дерево — это разновидность дерева поиска. Оно хранит данные в метках, каждая из которых представляет собой узел на дереве. Такие структуры часто используют, чтобы хранить слова и выполнять быстрый поиск по ним — например, для функции автозаполнения.



Так устроено префиксное дерево

Каждый узел в языковом префиксном дереве содержит одну букву слова. Чтобы составить слово, нужно следовать по ветвям дерева, проходя по одной букве за раз. Дерево начинает ветвиться, когда порядок букв отличается от других имеющихся в нем слов или когда слово заканчивается. Каждый узел содержит букву (данные) и булево значение, которое указывает, является ли он последним в слове.

Посмотрите на иллюстрацию и попробуйте составить слова. Всегда начинайте с корневого узла вверху и спускайтесь вниз. Это дерево содержит следующие слова: ball, bat, doll, do, dork, dorm, send, sense.

Пример реализации на JavaScript


Упражнения от freeCodeCamp



Двоичная куча


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


Так устроены минимальная и максимальная кучи

Двоичная куча может быть минимальной или максимальной. В максимальной куче ключ любого узла всегда больше ключей его потомков или равен им. В минимальной куче всё устроено наоборот: ключ любого узла меньше ключей его потомков или равен им.

Порядок уровней в двоичной куче важен, в отличие от порядка узлов на одном и том же уровне. На иллюстрации видно, что в минимальной куче на третьем уровне значения идут не по порядку: 10, 6 и 12.

Пример реализации на JavaScript


Временная сложность двоичной кучи
╔═══════════╦══════════════════╦═══════════════╗
║ Алгоритм  ║ Среднее значение ║ Худший случай ║
╠═══════════╬══════════════════╬═══════════════╣
║ Space     ║ O(n)             ║ O(n)          ║
║ Search    ║ O(n)             ║ O(n)          ║
║ Insert    ║ O(1)             ║ O(log n)      ║
║ Delete    ║ O(log n)         ║ O(log n)      ║
║ Peek      ║ O(1)             ║ O(1)          ║
╚═══════════╩══════════════════╩═══════════════╝

Упражнения от freeCodeCamp



Граф


Графы — это совокупности узлов (вершин) и связей между ними (рёбер). Также их называют сетями.

По такому принципу устроены социальные сети: узлы — это люди, а рёбра — их отношения.



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

Чаще всего граф изображают в каком-либо из двух видов: это может быть список смежности или матрица смежности.


Граф в виде матрицы смежности

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

Матрица смежности — это сетка с числами, где каждый ряд или колонка соответствуют отдельному узлу в графе. На пересечении ряда и колонки находится число, которое указывает на наличие связи. Нули означают, что она отсутствует; единицы — что связь есть. Чтобы обозначить вес каждой связи, используют числа больше единицы.

Существуют специальные алгоритмы для просмотра рёбер и вершин в графах — так называемые алгоритмы обхода. К их основным типам относят поиск в ширину (breadth-first search) и в глубину (depth-first search). Как вариант, с их помощью можно определить, насколько близко к корневому узлу находятся те или иные вершины графа. В видео ниже показано, как на JavaScript выполнить поиск в ширину.

Пример реализации на JavaScript

Временная сложность списка смежности (графа) 
╔═══════════════╦════════════╗
║   Алгоритм    ║    Время   ║
╠═══════════════╬════════════╣
║ Storage       ║ O(|V|+|E|) ║
║ Add Vertex    ║ O(1)       ║
║ Add Edge      ║ O(1)       ║
║ Remove Vertex ║ O(|V|+|E|) ║
║ Remove Edge   ║ O(|E|)     ║
║ Query         ║ O(|V|)     ║
╚═══════════════╩════════════╝



Упражнения от freeCodeCamp



Узнать больше


Если до этого вы никогда не сталкивались с алгоритмами или структурами данных, и у вас нет какой-либо подготовки в области ИТ, лучше всего подойдет книга Grokking Algorithms. В ней материал подан доступно и с забавными иллюстрациями (их автор — ведущий разработчик в Etsy), в том числе и по некоторым структурам данных, которые мы рассмотрели в этой статье.

От редакции Нетологии


Нетология проводит набор на курсы по Big Data:

1. Программа «Big Data: основы работы с большими массивами данных»

Для кого: инженеры, программисты, аналитики, маркетологи — все, кто только начинает вникать в технологию Big Data.

  • введение в историю и основы технологии;
  • способы сбора больших данных;
  • типы данных;
  • основные и продвинутые методы анализа больших данных;
  • основы программирования, архитектуры хранения и обработки для работы с большими массивами данных.

Формат занятий: онлайн.

Подробности по ссылке → http://netolo.gy/dJd

2. Программа «Data Scientist»

Для кого: специалисты, работающие или собирающиеся работать с Big Data, а также те, кто планирует построить карьеру в области Data Science. Для обучения необходимо владеть как минимум одним из языков программирования (желательно Python) и помнить программу по математике старших классов (а лучше вуза).

Темы курса:

  • экспресс-обучение основным инструментам, Hadoop, кластерные вычисления;
  • деревья решений, метод k-ближайших соседей, логистическая регрессия, кластеризация;
  • уменьшение размерности данных, методы декомпозиции, спрямляющие пространства;
  • введение в рекомендательные системы;
  • распознавание изображений, машинное зрение, нейросети;
  • обработка текста, дистрибутивная семантика, чатботы;
  • временные ряды, модели ARMA/ARIMA, сложные модели прогнозирования.

Формат занятий: офлайн, г. Москва, центр Digital October. Преподают специалисты из Yandex Data Factory, Ростелеком, «Сбербанк-Технологии», Microsoft, OWOX, Clever DATA, МТС.

Подробности по ссылке.
Нетология
89,00
Университет интернет-профессий
Поделиться публикацией

Комментарии 29

    +9
    Хеш-таблица это вроде одна из реализаций ассоциативного массива (словаря). Почему ее выделили в отдельную структуру данных? Тогда уж надо было сказать что возможны и другие реализации ассоциативных массивов (красно-черные деревья и прочие деревья поиска).
      0
      Ну если на то пошло, сама реализация ассоциативного массива это дерево.
      Я так понял пост просто перечисляет наиболее встречаемые сущности организации данных под общепринятыми наименованиями.
      +10

      Всё вперемешку. Ужас.
      Очередь и стек — самостоятельные структуры данных? Ничего, что их можно реализовать и поверх массива, и поверх списка — с разными свойствами соответственно?
      Мапа, сет, дерево, хэш-таблица на одном уровне? "Раньше я думал, что Карл Маркс и Фридрих Энгельс — муж и жена, а теперь я знаю, что это четыре разных человека" :-)


      Рано вам кого-то учить.

        0
        Без сарказма, а расскажите чем будут отличаться свойства очереди и стека реализованные поверх массива? Поверх списка мне все понятно, а вот по массиву сходу не очевидно. При добавлении и удалении элементов будут постоянные реаллокации массива, что плохо, но возрастет скорость итерирования объектов (а очередь и стек не про итерирование).
          +1
          1. Не будет выделений/освобождений в куче на каждый чих — существенный выигрыш. И вообще нет кучи мелких кусочков памяти, выделенных в куче, всё лежит локально (и удобно попадает в кэш проца для задач, где стек используется активно)
          2. Если не выделить сразу сколько надо памяти — иногда (например, при каждом удвоении размера массива) придётся реаллоцировать, тут мы проиграем (в среднем быстродействие всё равно выше, чем у списка, но иногда операция добавления элемента может оказаться долгой — в некоторых задачах это неприемлемо)

          В общем, редко когда имеет смысл делать очередь или стек на списке.


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

            0
            Спасибо, здорово.
            Из той же серии, массивы предпочтительнее списков в играх для хранения объектов, потому что создание\удаление объектов на сцене редкая операция, а итерация по ним происходит каждый кадр понесколько раз.
              0

              Из смешного по теме: в C# класс List — на самом деле массив, реальный список — LinkedList. Вот до такой степени MS верит в преимущество массивов в большинстве случаев.

                +1

                LinkedList ― это конкретно «связный список».


                Просто «список», без уточнений ― это абстрактная упорядоченная коллекция нефиксированного размера, которая реализована может быть как угодно. Когда термин «список» встречается в описании какого-нибудь алгоритма, если нет уточнений, лучше его именно так абстрактно и понимать.

                  0

                  Ну да, просто после STL и прочих библиотек, в которых list == linked list, это было непривычно.
                  А учитывая, что явно указана сложность Item[i] как O[1] — это не абстрактная реализация списка, а именно аналог std::vector.

          0
          Здравствуйте. Уточните, что есть реализация «поверх массива/списка», как для начинающего?
            +2

            Глядите. Очередь/стек — это не конкретная структура, а объект, реализующий две операции: положить в очередь (push) и взять из очереди (pull). Для очереди порядок выдаются объекты в том же порядке — FIFO (First In First Out), для стека в обратном — LIFO (Last In First Out). Ну, есть ещё очередь с приоритетами — это когда первым выдаёт объект с наивысшим приоритетом.
            Итого, если мы сделали нечто, умеющее правильно выполнять эти операции — это очередь :-)


            Варианты реализации (на примере LIFO очереди):


            1. Связный список. Ну, тут всё просто: push добавляет объект к концу списка, pull берёт из начала (и выкидывает этот объект из списка). Сложность обеих операций O(1), но надо выделять память на каждый push.
            2. Массив. Если ограничить длину очереди — поверх массива делается кольцевой буфер: указатели на "голову" и "хвост" очереди.
              • push — кладём элемент на место, куда указывает хвост, сдвигаем указатель на 1 элемент направо (возвращаясь к началу массива, если перешли за конец).
              • pull — берём элемент из места, куда указывает голова, сдвигаем голову на 1 направо (опять же "закольцевав" движение)
              • Сложность обеих операций опять же O(1), но нет выделения памяти на каждый чих — работает быстрее.
            3. В варианте 2 размер ограничен, если нужен неограниченный — при заполнении массива увеличиваем его — точнее, выделяем новый и копируем туда все данные. Удобно увеличивать размер ровно в два раза, тогда получаем амортизированную сложность (т.е. в среднем по куче операций) опять же O(1), но вот в худшем случае (когда увеличиваем массив) уже O(n).

            Ну, можно придумать ещё кучу других реализаций, но это самые распространённые.

          –2

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

            +2
            Я правильно понял, что, если не считать отдельных переменных, есть 10 типов данных: массив со ссылками и массив со ссылками на массивы?
            (особенно тщательно офигел от «заземления» «связного списка»… Я за свою трудовую биографию, кроме того, что был программистом, еще был и чуть-чуть энергетиком с группой допуска… Заземление связного списка — это сильно!
            Я бы не додумался. Надо изучить электричество тщательно. Вдруг заземление, которое возводится в абсолют энергетиками, это действительно просто нулевой указатель?..)
              +1
              Уважаемые программисты, пишите код ответственно. Всегда заземляйте ваши структуры данных!
              +2
              Это же копия статьи . Разве так было можно здесь? :\
                0
                Как так, сложность поиска для связного списка O(n), а удаления O(1)? Магия однако
                  +1
                  Удаление не требует поиска в общем случае.
                    0
                    Под «удалением» понимается, что мы уже имеем указатель на удаляемый элемент, его не нужно искать.
                      0
                      Спасибо, понял что под Insert/Delete имелись ввиду сами операции…
                      Просто может где-нибудь сноску сделать что для того что-бы что-то удалить нужно это найти еще, а если вставлять то пройтись по всему списку сначала.
                      Извиняюсь за конфуз.
                        0

                        Если список связан только в одну сторону, как в примере, удалить элемент за О(1) можно только имея заранее приготовленную ссылку на предыдущий элемент (под итератором, к примеру). Если для удаления есть только ссылка на текущий элемент, взятая со стороны — или надо иметь двустороннюю связь, или удаляется за О(n), так как нам реально нужен предыдущий элемент списка.

                          0
                          Не обязательно. Вот такой, например, вариант удаления элемента из односвязного списка за O(1):
                          // Предполагается, что список имеет вид
                          // struct node {
                          //     node* next;
                          //     std::unique_ptr<data> data;
                          // };
                          // 
                          // Последний элемент списка имеет поле next == nullptr
                          // В конце списка может быть не более одного "мусорного" элемента с полем data == nullptr - он ничего не означает и с логической точки зрения элементом списка не является
                          
                          // Единственный аргумент - удаляемый элемент списка
                          void erase(node& to_delete) {
                              if (to_delete.next == nullptr) {
                                  // Нужно удалить последний элемент - превращаем себя в sentinel
                                  to_delete.data = nullptr;
                              } else {
                                  // Общий случай - перемещаем следующий элемент в себя, после чего уничтожаем следующий
                                  to_delete.data = std::move(to_delete.next->data);
                                  to_delete.next = to_delete.next->next;
                                  delete to_delete.next;
                              }
                          }
                          
                    +2
                    Материал сложный для начинающих.
                    А для не начинающих слишком раздражительно детская подача материалами, с попытками смехуечности и вот этого вот.
                      0
                      Почему это insert в двоичную кучу O(1)? Когда вы вставляете элемент в кучу, потом еще нужно привести кучу к каноническому виду (вставка может нарушить правила формирования кучи), так что сложность логарифмическая
                        +1
                        Я, видимо, один такой, но мне в таких статьях всегда не хватает примеров. Видишь вот такую задачу — хватай вот такую структуру данных, она идеально для этого подойдёт.
                        • НЛО прилетело и опубликовало эту надпись здесь
                            0
                            А откуда автор может знать, где применять?
                            У вас есть задача, вы знаете структуры данных — решаете какую лучше применить.
                            Автор ваших задач не знает. А абстрактное — «префиксное дерево удобно для словарей» — не имеет ценности.
                            • НЛО прилетело и опубликовало эту надпись здесь
                                +1
                                Знаете структуру, знаете особенности — умеете применять. Ценность вполне очевидная
                        • НЛО прилетело и опубликовало эту надпись здесь

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                          Самое читаемое