Я недавно закончил учебный курс по программированию. К концу я чувствую себя комфортно, создавая веб-приложение от идеи до завершения. Однако я знаю, что в моих знаниях есть пробелы. Во время моего первого пробного технического интервью мне сразу же задали вопросы о структурах данных. В учебной программе, которую я закончил, явно не рассматривались структуры данных. Я смог логически разобраться с некоторыми вопросами, но теперь я трачу время, чтобы заполнить эти знания для себя и сделать обзор для любых других выпускников, которые сталкиваются с подобным опытом.
СТРУКТУРЫ ДАННЫХ
Структуры данных - это способы организации данных таким образом, чтобы их можно было эффективно использовать, принимая во внимание пространственную и временную сложность различных задач.
В этом посте предполагается, что если вы читаете это, вы уже знакомы с примитивными структурами данных, и сосредоточитесь на непримитивных структурах данных, начиная с простых упорядоченных списков.
МАССИВЫ
Массив - это упорядоченный набор элементов, каждый со своим индексом. Каждый элемент сам по себе может быть значением, массивом или объектом. Элементы массива хранятся в непрерывных ячейках памяти.
Поскольку положение каждого элемента может быть вычислено напрямую, нет необходимости перемещаться по структуре данных для доступа к конкретному элементу, который является частью того, что делает массив одним из наиболее эффективных способов хранения и доступа к последовательности значений или для хранения набора данных с похожими элементами.
Преимущества и использование:
Просто создать и использовать.
Итерация по массивам выполняется быстрее по сравнению с другими структурами данных.
Большие наборы данных можно хранить в массиве вместо объявления множества переменных, что может улучшить читаемость кода.
Массивы можно использовать для хранения данных более чем в одном измерении.
Они являются фундаментальным строительным блоком для сложных структур данных и могут использоваться для реализации других структур.
Недостатки:
Во многих языках, если вы хотите использовать массив, вы должны знать количество элементов, которые вы хотите сохранить при его объявлении. После того, как он был объявлен, невозможно добавить дополнительные элементы.
СТЕКИ
Стек - это линейная структура. Вставка или удаление любых элементов происходит наверху стека. Он следует шаблону «последний пришел - первым ушел» (LIFO).
Примером стека является история вашего браузера. Если вы нажмете кнопку «Назад», вы не захотите попасть на сайт, который вы посетили на прошлой неделе или в прошлом месяце; вы хотите увидеть последний добавленный элемент или последний посещенный веб-сайт, который, к счастью, находится в верхней части стека.
В основном есть три операции, которые вы можете выполнять со стеками. Вы можете добавить (протолкнуть) элемент в стек, удалить (вытолкнуть) элемент из стека или отобразить (взглянуть наверх) содержимое стека.
Преимущества
Память может выделяться динамически, в отличие от массива.
Чтение и запись переменных стека очень быстро и легко.
Недостатки
Негибкость. Большая часть памяти, которая нужна людям, расположена не в последовательном или хронологическом порядке, поэтому, если вы не ищете элемент на вершине стека, компьютер должен пройти путь от последнего набора информации к нужному вам, перемещая через стек.
ОЧЕРЕДИ
Как и стеки, очереди представляют собой последовательные линейные структуры. Однако очереди обрабатывают элементы в том порядке, в котором они были введены. Очередь следует правилу «первым пришел - первым ушел» (FIFO).
Очереди можно использовать для планирования задач ЦП или там, где может быть получено большое количество запросов, для хранения каждого запроса, который должен быть обработан, в том порядке, в котором он был получен.
Преимущества
Память может выделяться динамически, в отличие от массива.
Обеспечивает обработку самых старых данных в первую очередь.
Низкое время работы.
Недостатки
Гибкость. Предназначен только для поиска самого старого элемента.
СВЯЗАННЫЕ СПИСКИ
Связанные списки - это линейные структуры данных, которые используют систему ссылок, а не индекс или позицию элемента в строке. Они состоят из элементов, хранящихся в узлах, каждый из которых содержит указатель (ссылку) на следующий узел, от головы до конца.
Метафора для этого может быть охотой за мусором, где каждый предмет включает подсказку, которая указывает вам на следующий.
Если какие-либо элементы заменены местами, указатели необходимо будет сбросить, чтобы связанный список оставался неразрывным. Точно так же, если новый элемент добавляется в первую позицию, необходимо установить заголовок на новый элемент и добавить указатель, который направляет на следующий элемент, который ранее был заголовком.
Так зачем беспокоиться?
Преимущества и использование
Связанные списки легче и эффективнее реструктурировать.
Элементы можно вставлять в связанные списки на неопределенное время, в то время как массив может либо заполняться, либо требовать изменения размера.
Лучше всего использовать, когда данные необходимо быстро добавить или удалить из неизвестных мест.
Недостатки
В то время как массивы допускают произвольный доступ, связанные списки допускают только последовательный доступ к элементам, что делает их непригодными для приложений, которым требуется возможность поиска элемента по его индексу.
Они используют больше памяти, чем массив.
Перебирать список назад неэффективно.
ДЕРЕВЬЯ
Деревья - это нелинейные структуры данных, которые в основном используются для представления иерархических отношений.
Подобно связному списку, узел содержит как элементы данных, так и указатели, обозначающие его отношение к непосредственным узлам.
Корень содержит ссылки на все элементы, расположенные непосредственно под ним, которые известны как его «дочерние узлы».
Распространенным типом дерева является двоичное дерево поиска, которое используется для простого поиска хранимых данных. Эти поисковые операции очень эффективны, но должны соответствовать очень строгим правилам.
Преимущества и использование
Отлично подходит для хранения иерархических данных.
Быстрые и легкие операции вставки и удаления.
Динамический размер.
По деревьям легче искать, чем по связанным спискам. В деревьях двоичного поиска поиск выполняется очень быстро, при худшем поведении.
Может использоваться для поиска кратчайшего пути в сети.
Недостатки
Дочерние узлы не содержат никакой информации о своих родительских узлах.
Переставлять узлы медленно.
Хеш-таблицы в большинстве случаев работают быстрее.
ГРАФИКИ
Графики используются для представления сетей. Это может включать, среди прочего, социальные сети или поток вычислений.
В социальной сети каждая вершина может представлять одного человека и содержать данные об этом человеке.
Графики могут быть неориентированными, как на диаграмме выше, или направленными.
В ориентированном графе ребра являются направленными. Примером этого является веб-сайт, где вершины представляют веб-страницы, а направленные ребра представляют собой ссылки с одной страницы на другую.
Графы чаще всего представлены либо матрицей смежности, либо списком смежности, в зависимости от ситуации.
Преимущества
Способен моделировать разнообразное количество предметов и может допускать любое количество ребер от каждого узла.
Их можно использовать для поиска кратчайших путей.
Они упрощают работу с большими данными.
Недостатки
Необходимо выбрать представление, основанное на задаче, с каждым из которых есть компромиссы.
Матрицы смежности имеют большую сложность памяти.
Списки смежности не позволяют быстро определить, присутствует ли данное ребро в графе.
ХЕШ-ТАБЛИЦА
В хеш-таблицах данные хранятся ассоциативно. Данные хранятся в формате массива, причем каждое значение данных имеет собственное уникальное значение индекса.
В хеш-таблице используется хеш-функция для создания индекса, в который должен быть вставлен или расположен элемент.
Действия, выполняемые с хеш-таблицей, - это поиск, вставка и удаление.
Преимущества
Доступ к данным с известным индексом очень быстрый, независимо от размера данных.
Недостатки
Есть момент, когда хеш-таблица становится слишком полной, и таблица должна быть увеличена, что может привести к нежелательному поведению.
Могут возникнуть коллизии, требующие обработки ошибок.
БОЛЬШЕ РЕСУРСОВ
Для получения дополнительной информации о структурах данных см. Обзор структур данных на сайте GeeksforGeeks.
Для получения дополнительной информации о деревьях я нашел полезным Структуры данных 101: глубокое погружение в деревья с помощью Java Аманды Фосетт.
Для получения дополнительной информации о графах и их представлениях см. Graph Data Structures от baeldung.
БЛАГОДАРНОСТЬ!
Я постоянно совершенствуюсь. Если у вас есть исправления или отзывы, я буду рад узнать и внести исправления.
