Структура данных и связанные списки
Я отправился в путешествие по информатике с тех пор, как закончил свой Bootcamp. Я думаю, что важно знать, что вы используете при написании кода. Приятно знать, когда использовать массив, а когда использовать хеш-таблицу - две темы, которые я затронул в предыдущих блогах.
Со статическими массивами у нас есть только определенный объем данных или памяти, которые можно разместить рядом друг с другом. Однако динамические массивы и статические массивы могут увеличивать объем своей памяти и удваиваться. Однако удвоение массива будет иметь проблему с производительностью O (n). Мы также помним вставку или удаление в массиве любого элемента, который не является первым или последним, равным O (n). Почему? Что ж, нам нужно будет перебрать остальные элементы после вставки или удаления и переместить индексы.
Хеш-таблицы могут хранить что-то в памяти в любом месте, а это означает, что нам не нужно беспокоиться о вставке или удалении, поскольку нам не нужно перемещать индексы, поэтому мы имеем Большое О из О (1). Однако компромисс…. хеш-таблицы неупорядочены!
Так…. связанные списки, где они находятся. Помните, в прошлом блоге мы говорили, что решение проблемы коллизий для хэш-таблиц может быть решено с помощью связанных списков.
Эта таблица часто используется для объяснения хеш-таблиц в других статьях, я много видел ее, особенно когда сам изучал и исследовал хеш-таблицы… но никто толком не объяснил, что происходит после столкновения (после красного числа). Это может быть в другом их блоге, поэтому я не буду судить! Но я считаю, что хорошо знать, что делает ваша структура данных, даже если вам не нужно ее использовать. Итак, давайте объясним это.
Связанные списки фактически не встроены в Javascript, если вы не создадите их самостоятельно. Они чаще встречаются в языках нижнего уровня, таких как Java, где вы также должны знать и управлять своим пространством памяти / сборкой мусора! Так что же такое связанный список?
Как определено geeksforgeeks, «связанный список - это линейная структура данных, в которой элементы не хранятся в непрерывных ячейках памяти. Элементы в связанном списке связаны с помощью указателей, как показано на изображении ниже:
Проще говоря, связанный список состоит из узлов, каждый из которых содержит поле данных и ссылку (ссылку) на следующий узел в списке ».
В этом блоге мы обсудим один из двух типов связанных списков: односвязные списки. Двусвязные списки мы обсудим в следующем блоге.
Односвязный список содержит набор узлов. Узлы состоят из двух частей: значения (показаны как данные ниже) и указателя.
Первый узел называется головой, а последний узел - хвостом. Связанные списки также называются завершающимися нулем, то есть последний узел просто указывает на Null!
Visualgo - отличный визуальный ученик, который привлек мое внимание благодаря Удеми и Master the Coding Interview: Data Structures and Algorithms. Поиграйте с хеш-таблицами, массивами и связанными списками, невероятно информативно и интересно наблюдать за происходящим в визуальной перспективе.
Вам может быть интересно, в чем разница между связными списками и массивами? Большая разница в том, что элементы массива находятся рядом друг с другом в памяти, тогда как элементы связанного списка разбросаны. Компьютеры обычно имеют систему кэширования, что означает, что чтение из последовательной памяти происходит быстрее, чем чтение из разрозненной памяти. Таким образом, итерация по связному списку может быть медленнее, чем итерация по массиву, даже если они оба равны O (n)… однако вставка и удаление выполняются намного быстрее. Что касается хеш-таблиц, единственное преимущество связанных списков состоит в том, что, хотя данные разбросаны, существует некоторая форма порядка. Если вы посмотрите на диаграмму выше, каждый узел указывает на следующий узел. Чтобы вы лучше понимали «Большой О», взгляните на эту таблицу.
Теперь вы, возможно, смотрите на удаление односвязного списка и задаетесь вопросом, почему это O (1) ... Здесь очень хорошее обсуждение переполнения стека → https://stackoverflow.com/questions/14048143/why-is -удаление-в-односвязном-списке-o1 .
Давайте перейдем к следующей части изучения связанных списков. Указатель! Или на диаграмме ранее стрелку.
Я создал здесь указатель. mySecondFavouriteObject имеет ссылку на объект. Таким образом, указатель является ссылкой на область памяти. Мы не копируем myFavouriteObject в другое место в памяти. Когда мы смотрим на нашу оперативную память, есть только одна запись для {name: «JimBob»}. Оба myFavouriteObject и mySecondFavouriteObject указывают на {name: «JimBob»}. Если вы не совсем понимаете это, не волнуйтесь, воспользуйтесь иллюстрацией ниже.
Итак, это возвращает {name: ‘Jimbob’} с цифрой 1 или 2 после него… что это доказывает? Итак, следуйте следующему фрагменту кода ниже, чтобы убедиться, что оба объекта просто указывают на один и тот же {name: ‘Jimbob’} в памяти.
Название меняется для обоих! Это сработает, если вместо этого вы также измените mySecondFavouriteObject.name.
Последний тест: удалим myFavouriteObject и посмотрим, сохраняет ли mySecondFavouriteObject пару ключ / значение.
Следует еще сохранить ссылку!
Это должно дать вам лучшее понимание того, как работает единый связанный список.
Затем создайте свой собственный связанный список в Javascript. Итак, мы понимаем концепцию того, чем должен быть единый связанный список, но как мы его спроектируем, с простыми добавками и добавлениями.
Во-первых, нам нужно создать начало связанного списка, которое является головным узлом (который также будет хвостовым узлом для первой записи данных).
Итак, это должно быть достаточно очевидным. Но мы передаем нашему классу connectedList значение, конструктор создает первый узел, используя переданное значение, его указатель (следующий) затем устанавливается в значение null, так как конец единственного связанного списка должен указывать на null.
Теперь у нас есть начало связанного списка, давайте создадим методы добавления и добавления.
Здесь много чего происходит, но все это довольно стандартные методы и классы. Мы просто создаем функцию-метод с именем append, которая принимает значение. Это используется для создания нового узла, который будет в конце нашего единого связанного списка, поэтому мы знаем, что этот узел должен указывать на ноль.
Затем мы устанавливаем наш текущий последний узел так, чтобы он указывал на создаваемый newNode, и делаем наш newNode хвостом!
Посмотрим, сможете ли вы выяснить метод добавления, поскольку он довольно похож!
Единственная реальная разница здесь в том, что наше следующее значение должно быть установлено на текущий головной узел, прежде чем мы изменим наш newNode на заголовок связанного списка!
Я не выполнял вставку или удаление, но попробуйте сами. Я узнал большую часть этих знаний через Удеми и собеседование Master the Coding. Поистине, все разбито.
