Как только что получивший диплом выпускника Flatiron School, я начал погружаться в огромный мир структур данных и алгоритмов, готовясь к собеседованию при приеме на работу. И есть ли лучший способ закрепить свежую информацию в своей голове, чем поделиться этими новообретенными знаниями в блоге? Ниже дается вводный обзор некоторых из наиболее распространенных структур данных, имеющихся в JavaScript; стеки, очереди, связанные списки, деревья, графики и хеш-таблицы. Я делаю ссылки на временную сложность выполнения операций с этими структурами данных, поэтому рекомендуется хотя бы вводное понимание Big O.
Структуры данных
Так что же такое структуры данных? Структуры данных - это способы организации, хранения и управления данными, чтобы компьютер мог использовать или изменять их наиболее эффективным образом. Другими словами, они представляют собой коллекции значений данных, отношений между данными и функций или операций, которые мы можем выполнять с данными. Структуры данных появляются повсюду, от очередей трафика до Интернета и человеческого мозга.
Стеки
Стеки - это линейные структуры данных, которые следуют шаблону «последний пришел - первым ушел» или «первым пришел - последний ушел» при определении порядка выполнения операций. Отличная визуализация этой концепции - стопка тарелок, которую можно найти в кафетерии. Чистые тарелки доставляются из кухни и кладутся наверх стопки. Первая тарелка, которую возьмет голодный посетитель, будет последней тарелкой, помещенной в стопку, то есть «последней пришла, первой уехала». Со временем, когда тарелки будут взяты, и мы приблизимся к основанию стопки, последняя тарелка, которую берет гость, будет первой тарелкой, которая будет помещена в стопку. Эта пластинка была «First In Last Out».
Со стеками выполняются две основные операции. Это push, добавление элемента в верхнюю часть стека, и pop, удаление элемента из верхней части стека. Поэтому элементы выталкиваются в порядке, обратном их перемещению. Временная сложность push и pop операций над стеками чрезвычайно благоприятна с временной сложностью O (1). Поскольку мы добавляем или удаляем только сверху, длина стека не имеет значения, и относительное время выполнения этой операции не меняется с увеличением длины стека.
Обычный стек, с которым столкнется каждый разработчик JavaScript, - это стек вызовов. Стек вызовов определяет порядок, в котором выполняются функции. Когда функция выполняется, она помещается в верхнюю часть стека вызовов, где остается до тех пор, пока не будет возвращено значение. Затем функция извлекается из стека вызовов, и выполняется следующая функция.
Очереди
Очереди представляют собой аналогичные линейные структуры данных, однако вместо того, чтобы следовать шаблону «последний вошел - первым ушел», следуйте порядку «первым пришел - первым ушел». Первый элемент, добавляемый в очередь, удаляется первым. Очереди можно легко смоделировать с помощью очереди или очереди в повседневной жизни, где первый клиент, который входит в очередь, является первым клиентом, которого обслуживают.
Операция enqueue используется для добавления элемента в конец очереди, в то время как dequeue удаляет элемент из начала очереди. Мы можем рассматривать очереди как массивы, где enqueue аналогичен unshift, а dequeue аналогичен pop. Глядя на временную сложность этих двух операций, обе они равны O (1), поскольку элемент либо удаляется спереди, либо добавляется сзади. Это не зависит от длины очереди.
Связанные списки
Связанные списки - это еще одна линейная структура данных, в которой элементы хранятся в последовательном, но не непрерывном порядке. Элементы связаны указателями, где первый элемент или узел - это голова, а последний - хвост. Каждый узел состоит из двух элементов: данных и ссылки на соседний узел. Если список пуст, заголовок является пустой ссылкой. Ниже приведен пример односвязного списка, где 2 - голова, а 8 - хвост. Мы можем «пройтись» по списку от 2 до 8.
В двусвязном списке соседние узлы также имеют указатели, указывающие на предыдущий узел, что позволяет нам «ходить» от головы к хвосту или назад от хвоста к голова.
Для связанных списков существует постоянная или временная сложность O (1) при вставке или удалении данных из списка. Указатели можно легко изменить, что делает эти операции достаточно эффективными. Временная сложность увеличивается до O (n) для операций доступа и поиска, аналогично для стеков и очередей, поскольку мы должны пройти через каждый узел (или элемент) и проверить его на соответствие желаемому значению. В худшем случае желаемое значение находится в конце списка (или стека, или очереди), и, таким образом, время, необходимое для выполнения этих операций, линейно масштабируется по мере роста списка.
Деревья
Деревья - это нелинейные структуры данных, чем-то похожие на связанные списки, в которых узлы связаны указателями, однако деревья содержат ссылки на несколько узлов в иерархической структуре. Типичным примером древовидной структуры данных является объектная модель документа (DOM).
Деревья можно охарактеризовать двумя основными свойствами:
- Один узел обозначается как корень (в приведенном выше примере узел HTML является корневым).
- Каждый узел (кроме корня) соединен указателем ровно с одним другим узлом в направлении родительский - ›дочерний.
У каждого узла может быть любое количество потомков. Узлы, не имеющие дочерних узлов, называются листьями или внешними узлами. Узлы, которые не являются листьями (у них есть дочерние узлы), являются внутренними узлами. Смежные узлы, принадлежащие одному родительскому узлу, являются одноуровневыми.
Двоичные деревья - это деревья, в которых все родительские узлы имеют только 2 дочерних элемента. Дочерний элемент слева должен иметь значение, равное или меньшее, чем значение родительского элемента, тогда как дочерний элемент справа должен иметь большее значение.
Операции поиска, выполняемые на двоичных деревьях, имеют временную сложность O (log (n)), поскольку половина дерева может игнорироваться при каждой итерации. Наименьшие и самые большие значения двоичных деревьев просто даны крайнему левому листу и крайнему правому листу соответственно.
Графики
В то время как узлы в деревьях должны иметь только одного родителя, графы представляют собой нелинейные структуры данных, в которых дочерние узлы могут иметь несколько родителей. Узлы соединены ребрами, которые могут быть направленными или ненаправленными, а также взвешенными или невзвешенными. Края, обладающие как направлением, так и весом, можно рассматривать как векторы. Интернет, возможно, является самым известным примером структуры данных графа. Графики также полезны для представления сетей, таких как схемные сети, социальные сети, нейронные сети и т. Д.
Хеш-таблицы
В хэш-таблицах данные хранятся ассоциативно, как и в словарной структуре с парами "ключ-значение". Мы можем определить расположение пар в памяти с помощью хеш-функций. Хеш-функции принимают ключ и возвращают адрес, в котором должна находиться пара. Коллизии возникают, когда несколько ключей указывают на один и тот же адрес. По мере увеличения размера таблицы столкновения становятся менее частыми.
Массивы могут использоваться для хранения пар ключ-значение в простых хэш-таблицах, где адреса находятся в целочисленной последовательности. Карты или объекты могут использоваться для представления хеш-таблиц с более сложным отображением адресов. Пара "ключ-значение" хэш-таблиц означает, что операции вставки, удаления и поиска могут выполняться с очень подходящей временной сложностью O (1). За эффективный поиск данных приходится платить. Отношения между парами ключ-значение и связь между ключами и их адресами приносят в жертву отношения между данными. Поэтому хеш-таблицы отлично подходят для извлечения данных, но не для хранения данных.
