С примерами на JavaScript
Все мы слышали о важности знания своих структур данных для собеседований с разработчиками. Если вы относительный новичок в информатике и программировании, это может показаться непонятным. Каждая структура данных хранит информацию в определенном формате. Различные структуры подходят для разных операций, поэтому в зависимости от конечной цели программист выберет наиболее подходящую структуру данных на основе эффективности и простоты.
Вы, вероятно, уже использовали множество структур данных в программировании, причем более абстрактно в повседневной жизни. Попробуйте найти книгу в библиотеке по ее десятичному числу Дьюи. Вы используете хеш-таблицу. Как насчет того, чтобы перечислить продукты, которые вам нужно купить? Есть массив. Когда вы нажимаете кнопку "Назад" в браузере, вы как будто указываете на предыдущий узел связанного списка. И поиск в файлах на вашем компьютере? Это дерево.
В этом посте я обрисую четыре основных структуры данных - массив, хеш-таблицу, связанный список и дерево - и покажу примеры простых алгоритмов. Этот список ни в коем случае не является исчерпывающим, и, безусловно, необходимо знать о других структурах данных, но я считаю, что эти четыре - отличное место для начала.
Множество
Массив, вероятно, является первой структурой данных, которую вы усвоили в процессе программирования. Это легко визуализировать, и с ним весело работать. Массив - это список элементов в указанном порядке. Каждый элемент соответствует индексу, причем первый элемент находится под индексом 0. У следующих элементов индексы увеличиваются на 1.
Ниже я создаю массив, объявляя переменную и устанавливая для нее список элементов, заключенных в квадратные скобки, и объединяю элементы массива в строку.
Хеш-таблица
Хэш-таблица состоит из пар ключ: значение, где каждый ключ уникален и указывает на связанное с ним значение. Ключ преобразуется в целое число с помощью некоторой хеш-функции и сохраняется.
Объект в JavaScript - это пример хеш-таблицы. Подобно массиву, я создаю его ниже, объявив переменную и установив для нее пары ключ: значение, окруженные фигурными скобками. Выполняемый алгоритм представляет собой перечисление ключей в объекте.
Связанный список
Связанный список, как и массив, представляет собой серию элементов. Однако вместо того, чтобы хранить в последовательном пространстве памяти, элементы можно хранить где угодно, и каждый элемент отслеживает свои собственные данные и следующий элемент в строке. Связанные списки могут быть односвязными, каждый элемент указывает только на элемент перед ним (как показано выше), или двойными, причем каждый элемент указывает как спереди, так и сзади. Чтобы создать связанный список, потребуется немного больше работы, поэтому я сначала покажу это.
Отметим, что Node и LinkedList не являются специальными или зарезервированными словами, поэтому мы могли бы так же легко называть наши классы Blob вместо Node и Fiddlesticks вместо LinkedList. Важна основная структура того, как эти экземпляры класса соединяются, а не то, как мы их называем. Попробуйте ответить, чтобы подтвердить.
Ниже я нахожу длину связанного списка.
Дерево
Дерево состоит из узлов, соединенных ребрами. Узел будет иметь одного родителя (кроме корневого узла) и может иметь одного или нескольких дочерних узлов. На рисунке выше показан особый тип дерева, называемый деревом двоичного поиска. В BTS каждый узел имеет максимум два дочерних элемента, а дочерний элемент слева меньше дочернего элемента справа. Это позволяет повысить эффективность алгоритмов поиска. Как и в случае со связанными списками, нам нужно немного поработать, чтобы настроить наше дерево.
Еще раз помните, что имена классов здесь не важны. Важно то, как мы соединяем данные, хранящиеся в экземплярах каждого класса. В приведенном ниже алгоритме я нахожу наименьшее целое число в дереве.
Список структур данных выходит за рамки этих четырех, и на них стоит потратить время. По мере того, как вы знакомитесь с большим количеством структур данных, вы увидите сходства и совпадения между ними.
