Фундаментальные структуры данных
Всем привет! Сегодня речь пойдет о фундаментальных структурах данных, которые я изучил на очередном курсе Высшей школы программирования Сергея Бобровского. Эта статья будет некой шпаргалкой, куда можно будет заглянуть и увидеть основные особенности некоторых базовых типов данных.
Связанный список
Первой структурой данных, показанной на курсе, был связанный список, ниже представлена схема его устройства.
Всё довольно просто. У нас есть набор узлов (Node), которые содержат какое-то значение (число, строка или ещё что-то) и ссылку на другой узел. Первый и последний узлы списка называются HEAD и TAIL соответственно. Для реализации такого списка нам нужно два класса: Node, который описывает узел и LinkedList, определяющий наш список.
Как видно из схемы, перемещаться по узлам мы можем только вперёд.
Преимущества
- Очень быстрая операция вставки/удаления элемента, для вставки узла в середину нам достаточно изменить всего 2 ссылки.
- Элементы могут храниться в различных областях памяти. Список легко меняет свой размер.
- Легко выделить часть списка, просто изменив поля HEAD и TAIL.
Недостатки
- Чтобы обратиться к элементу необходимо перебрать всех его предшественников.
- Время доступа к узлам больше чем в массиве, так как они хранятся в разных областях памяти.
- Можно двигаться лишь в одном направлении.
Двунаправленный cвязанный список
Эта структура данных убирает один из недостатков связанного списка: возможность движения только в одном направлении. Её устройство представлено ниже.
На схеме видно, что это тот же связанный список, однако его элементы содержат ссылки не только на следующий, но и на предыдущий узел. Плюсы и минусы этой структуры, по сравнению с массивами, такие же как и у связанного списка, кроме движения в одном направлении. Однако, стоит сказать, чем отличаются два вида этих связанных списков: очевидный минус “разностороннего” собрата нашего связанного списка в том, что узлы первого требуют больше памяти, ибо хранят в себе 2 ссылки, а не 1. Впрочем, такое устройство списка повышает эффективность некоторых операций, например, удаления. А о возможности передвигаться по списку в двух направлениях было сказано ранее.
Динамический массив
Это улучшенный массив, который умеет изменять свой размер автоматически. Сравним эту структуру данных с нашими связанными списками.
Преимущества
- Есть возможность обратиться к элементу по индексу.
- Элементы хранятся последовательно, они попадают в кэш процессора при обращении к массиву и обрабатываются быстрее.
- Массив занимает меньше памяти, так как с элементами не нужно хранить ссылки на “соседей”.
Недостатки
- Долгие процедуры вставки и удаления. Нам нужно сдвигать все последующие элементы на 1 вправо при вставке, либо влево - при удалении.
- Затратная процедура изменения размера массива.
Стек
Стек работает по принципу LIFO (Last In First Out) последний пришёл, первый ушёл. Саму структуру можно представить как стакан, в который кладут объекты. Ниже представлено его схематичное изображение.
Мы можем положить элемент в стек, либо же вытащить его из стека, также, часто реализуют возможность просто посмотреть что находится наверху, без удаления объекта. На схеме 4 изображения стека, цифра на объекте означает каким по счёту элемент был добавлен в хранилище. На первых 3-х изображениях мы добавляем элементы в стек, а на последнем изображении объект вытаскивается из стека. Как видим, исчез объект, который попал в хранилище последним.
Для хранения стека можно использовать различные структуры данных, например динамический массив или связанный список.
Очередь
Очередь работает так же как и обычная человеческая очередь в магазине или где-то ещё. Здесь соблюдается принцип FIFO (First In First Out) первый пришёл, первый ушёл. Мы можем добавить элемент в один конец очереди и извлечь его из другого конца.
Для хранения очереди, как и для стека, можно использовать различные структуры данных.
Двусторонняя очередь
Можно сказать, что это совмещение очереди и стека. Здесь есть 2 входа и 2 выхода. Значит, что элементы спокойно можно добавлять в начало и конец списка. Точно также мы можем извлекать объекты с любого конца очереди. Скорость работы двусторонней очереди может сильно зависеть от того, что мы выберем хвостом, а что головой. Это справедливо если мы реализуем такую очередь на основе массива (ведь добавление в конец происходит быстро, а вот с началом нужно возиться, передвигая все элементы массива вправо). Использование двунаправленного списка для реализации этой очереди не несёт подобных трудностей, и операции вставки/ удаления крайних элементов выполняются за одинаковое количество времени.
Упорядоченный список
Название говорит само за себя, это список, элементы которого расположены в определённом порядке, например по возрастанию.
Хорошо когда данные сразу отсортированы, потому что процедура сортировки крайне затратна по ресурсам. А чтобы элементы не пришлось сортировать, нам следует использовать упорядоченный список, который сам ставит элемент в нужное место.
Хэш-таблица
Что такое хэш-функция или просто хэш? Если говорить просто, то это некий алгоритм, преобразующий данные. А хэш-таблица - это вместилище данных, преобразованных с помощью хэш-функции. Ниже представлена схема хэш-таблицы.
Есть некий объект (например строка), который мы пропускаем через хэш-функцию (для строки можно складывать коды символов и брать остаток от деления полученной суммы на количество слотов в таблице), она проводит какие-то операции над нашей строкой и выдаёт номер слота, куда её следует поместить.
Что это даёт нам на практике? Скорость: хэширование позволяет очень быстро узнать, где индекс интересующего нас элемента в таблице. Однако не всё так просто, чем больше различных значений необходимо хранить в таблице, и чем меньше в ней слотов, тем выше вероятность возникновения коллизий (ситуация, когда хэш-функция для разных объектов выдаёт один и тот же номер слота). Подбор оптимальной хэш-функции позволяет максимально сократить количество коллизий, но не убрать их. Для решения данной проблемы есть несколько методов разрешения коллизий. Вот пара самых популярных: можно просто ставить элемент, при возникновении коллизии, в следующий свободный слот; А можно сделать так, чтобы в слоте хэш-таблицы хранился список, а когда хэш-функция определяет очередной элемент в занятый слот - добавлять этот объект в список.
Ассоциативный массив
В некоторых кругах известный под именем “Словарь”. Хранит данные в формате ключ-значение. Особенность ключей в том, что ими может быть что угодно и они должны быть уникальны. Для реализации этой структуры данных неплохо подходит хэш-таблица, главное чтобы количество коллизий было в разумных пределах. Берём 2 массива, для ключей и значений, хэш-функция распределяет ключи в первом массиве, а значения во втором массиве записываются в слот, номер которого равен номеру слота соответствующего ключа. В отличие от хэш-таблицы ассоциативный массив не ограничен по размеру, количество ключей для него берётся с гарантированным запасом под конкретную задачу, либо просто используется динамический массив. Кроме хэш-таблицы, для реализации словаря, можно использовать и упорядоченный массив, например, если результатом работы хэш-функции является множество коллизий. Такой массив будет хранить объекты с двумя полями: ключ и значение.
Множество
Это неупорядоченное хранилище данных, элементы которого уникальны. Особенность множества заключается в высокой скорости проверки принадлежности к нему элемента.
Кэш
Это своего рода хэш-таблица, применяемая когда количество элементов гораздо меньше количества значений. В таких случаях хэш-таблица быстро заполняется и возникает необходимость избавиться от неактуальных элементов, чтобы дать возможность попасть в таблицу новым значениям. Существуют различные схемы вытеснения неактуальных значений, например мы можем просто удалять элемент, который попал в кэш раньше всех.
Получается, что в кэше хранятся самые востребованные элементы, его размещают в наиболее быстрой памяти (оперативная или кэш процессора) чтобы максимально увеличить скорость работы программы.
Заключение
В данной статье рассмотрены базовые структуры данных, изучаемые на 1-м курсе по алгоритмам в школе Сергея Бобровского. Единственная вещь, которую я не затронул тут - фильтр Блюма.
Мою исполнение этих структур данных на языке Java можно посмотреть здесь, наборы методов определены заданиями курса, так же как и некоторые особенности реализации.
Понимание принципов работы и устройства структур данных позволит Вам повысить качество своих программ, ведь правильно подобранная хранилище данных позволяет многократно упростить работу и повысить быстродействие приложения. Также, не обязательно использовать эти структуры по отдельности, есть случаи, когда их комбинация окажется более выгодным решением и повысит эффективность того или иного продукта.
Ну а на этом всё, спасибо за внимание!
-
Типы данных