Резюме

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

Элементы массива хранятся в памяти последовательно. Благодаря этому значение элемента по определенному индексу всегда можно получить за константное время. Добавление элемента в массив тоже происходит за $O(1)$. Операции поиска и удаления в худшем случае требуют $O(n$) операций.

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

Элементы связного списка в памяти компьютера в общем случае располагаются в произвольных местах. Итерация по элементам связного списка более медленная, чем итерация по элементам массива. Добавление и удаление элемента выполняются за $O(1)$. На поиск элемента в худшем случае понадобиться $O(n)$ операций.

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

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