Структуры данных в JavaScript
Скорее всего, вы пришли к этой статье, потому что ваша подготовка к интервью завела вас в кроличью нору LeetCode. Связанные списки — излюбленное средство многих интервьюеров для проверки понимания интервьюируемыми основных структур данных, а также ваших навыков решения проблем. Независимо от того, немного ли вы заржавели в школе или впервые сталкиваетесь со связанными списками, сначала их может быть немного сложно понять.
Как и в большинстве задач, полезно начать с диаграммы. Связанный список — это линейная структура данных, которую можно рассматривать как цепочку, где каждая ссылка в цепочке связана со следующей ссылкой. В связанном списке каждое звено в цепочке будет представлено как узел.
В односвязном списке каждый узел содержит некоторые данные, а затем указатель на следующий узел. Для двусвязного списка также будет указатель на предыдущий узел. Первый узел в списке обычно называется головным, а указатель next конечного узла ни на что не ссылается. Когда эта диаграмма построена, пришло время начать кодирование односвязного списка в JavaScript.
Кодирование класса узла
Поскольку односвязный список состоит из множества заметок, имеет смысл создать класс Node таким образом, чтобы новый узел можно было легко и последовательно создавать. При создании нового узла данные, которые он будет содержать, должны быть известны, но следующий узел может быть неизвестен.
Класс узла двусвязного списка будет очень похож на рис. 2, но с дополнительным свойством previous, которое также будет инициализировано значением null, поскольку оно может быть неизвестно или может быть головным узлом.
Создание односвязного списка
С написанным классом узла мы можем погрузиться в построение односвязного списка. Предположим, у нас есть массив, в котором каждый элемент представляет данные, которые должны храниться в узле, а следующий элемент должен быть следующим узлом. Элемент с нулевым индексом будет главой этого связанного списка.
Приведенная выше функция сначала проверяет два пограничных случая, когда либо не создается узел, либо создается только один узел. Затем код for перебирает оставшийся массив, создавая узел для данных каждого элемента, а затем добавляет свойство next к предыдущему узлу. После этого возвращается заголовок списка, поскольку теперь он указывает на следующий узел, который указывает на следующий узел, и так далее, пока свойство next последнего узла не укажет на null.
Дополнительные замечания
Хотя в этой статье не рассказывается, как вставить или удалить узел в существующем связанном списке, ее стоит кратко обсудить. Поскольку связанный список не индексируется, любая вставка или удаление узла должна начинаться с головного узла, а затем переходить через последующие узлы, пока не будет найдено желаемое местоположение. Отсюда необходимо обновить свойство next предыдущего узла, чтобы оно указывало на соответствующий узел. Более подробное обсуждение см. в следующей статье из серии Структуры данных в JavaScript: Редактирование односвязного списка.
Я уверен, что я не первый, кто рекомендует Cracking the Coding Interview, но если вы изучаете структуры данных и алгоритмы для интервью, это отличный ресурс.
