Основы программирования структуры данных

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

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

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

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

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

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

В статье я привожу примеры реализации этих структур данных на 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).

Временная сложность стека ╔═══════════╦═════════════════╦═══════════════╗ ║ Алгоритм ║Среднее значение ║ Худший случай ║ ╠═══════════╬═════════════════╬═══════════════╣ ║ 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).

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

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

Множества

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

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

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

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

• Create a Set Class
• Remove from a Set
• Size of the Set
• Perform a Union on Two Sets
• Perform an Intersection on Two Sets of Data
• Perform a Difference on Two Sets of Data
• Perform a Subset Check on Two Sets of Data
• Create and Add to Sets in ES6
• Remove items from a set in ES6
• Use .has and .size on an ES6 Set
• Use Spread and Notes for ES5 Set() Integration

Map

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

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

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

Источник

Урок 3. Основы программирования. Основные структуры данных

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

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

Переменная

Представим, что память компьютера состоит из множества ячеек и каждая ячейка, куда мы сохраняем данные, имеет адрес. Этот адрес и фиксирует переменная. Она имеет название (имя переменной) и указывает, что именно хранится в памяти (значение переменной).

При обращении к ней, мы можем считывать и перезаписывать хранимую информацию. Это происходит так:

2. Присваиваем ей значение – указываем данные, которые необходимо сохранить в памяти компьютера.

3. Когда нам нужно использовать или указать эти данные, мы пишем не их, а имя переменной, которой они присвоены.

Правила создания имени переменной в JS

— Можно использовать любые буквы и цифры, символ подчеркивания «_».

— Нельзя начинать имя с цифры.

— Нельзя использовать знаки «-», «/», «#», «@».

— Нельзя использовать пробелы и табуляции.

— Заглавная буква имеет значение. Dogs и dogs – это разные переменные.

— Нельзя назвать переменную именем стандартной команды, которая есть в языке программирования. Например, нельзя создавать переменную с именем «typeof» в JS.

Переменные в JavaScript

Для объявления переменных в языке JavaScript используется слово let либо const.

Сonst – константа – используется для объявления переменных с теми значениями, которые должны оставаться неизменными на протяжении всей программы. Например, для объявления математических или физических постоянных. В остальных случаях используется слово let.

Справка! Для переменных предпочтительно применять глагол «объявить», а не «создать».

Объявим переменную с именем name:

Чтобы добавить значение используется специальный оператор присваивания – знак равенства «=»:

let name = 'Milhouse'; console.log(name);

В консоли увидим результат:

Имя name – это адрес ячеек, где хранится значение ‘Milhouse’. По имени переменной мы обращаемся к этим данным в разных частях программы. Простая переменная может иметь любой тип данных (число, строка, логическое значение).

Подробнее о типах данных мы рассказывали в Уроке 2.

Пример

Один из примеров использования переменных – это ввод и сохранение информации, которые вы производите каждый день.

Берём стандартную команду prompt() в JavaScript. Она выводит на экран диалоговое окно, в которое просит ввести какую-то информацию и нажать ОК. После ввода строки и нажатия ОК результат присваивается переменной. Если позже к этой переменной обратиться, то её значением будет информация, введённая пользователем.

Например, выполним команду prompt(), попросим пользователя ввести своё имя и сохраним результат в переменную под именем questionName:

let questionName = prompt('Как вас зовут?');

Введём имя «Сергей» и нажём ОК. Теперь попросим вывести в консоль значение переменной questionName:

Массив

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

Массив удобен, если одновременно необходимо хранить большое количество данных и иметь доступ к каждому элементу.

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

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

Каждому элементу массива присваивается индекс, благодаря которому получится напрямую обратиться к этому элементу.

Надеемся, вы помните из Урока 2, что индекс – это порядковый номер.

Во многих языках программирования, в том числе в JavaScript, элементы массива записываются в квадратных скобках через запятую. В зависимости от этого им присваивается индекс. Отсчёт ведётся с 0: первый элемент массива имеет индекс 0, следующий 1 и т. д.

Число индексов, которое придётся указать для того, чтобы «достать» значение какого-либо элемента, называется размерностью массива.

Пример на JavaScript

1. Создадим массив из двух элементов. Это происходит по аналогии с созданием переменных:

let productMiniList = ['lemonade', 'Cola'];

2. Теперь создадим массив, куда, помимо прочих элементов, включим и уже созданный массив:

let productList = ['apple', 'milk', 'cheese', productMiniList, 'tea'];

3. Чтобы достать apple из массива, необходимо написать имя массива и порядковый индекс нужного элемента в квадратных скобках:

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

Помимо массива встречаются и другие структуры данных: очереди, стеки, хэши, списки, таблицы и другие. Но на курсе «Основы программирования» мы их не рассматриваем.

Домашнее задание

Придумайте массив, состоящий из двух массивов и двух переменных, и напишите его на языке JavaScript.

Источник