Списки - это не просто массивы
Когда программисты видят слово «список», мы обычно сразу думаем «массив».
Массивы отлично подходят для хранения данных для итерации, но поскольку они имеют пронумерованные индексы, манипулирование элементами в массиве может быть дорогостоящим с точки зрения сложности времени и пространства.
Например, если мы хотим вставить новый элемент в 10-й индекс в массив из 100 элементов, нам нужно будет повторно проиндексировать остальные 90 элементов после вставки.
Если нам нужно работать со списком данных, который постоянно обновляется, мы можем использовать структуру данных, известную как связанный список. Связанный список можно представить себе как цепочку - это группа узлов с установленными заголовком, хвостом и длиной.
Каждый узел содержит значение и указатель на следующий узел в цепочке. Односвязные списки имеют указатели на следующий узел в списке, а двусвязные списки имеют указатели как на предыдущий, так и на следующий узел в цепочке.
Создание односвязного списка
(Рекомендую брать пример с Visualgo). Нам нужно создать классы для Node и для List. См. Ниже свойства каждого из них.
Чтобы манипулировать чем-либо в нашем связанном списке, нам нужно соблюдать три правила:
- Обязательно увеличивайте или уменьшайте длину списка при добавлении или удалении узлов.
- Убедитесь, что в списке есть правильная голова, хвосты и все узлы имеют точные указатели.
- При удалении убедитесь, что все указатели на удаленные узлы отключены, чтобы узел был правильно удален из памяти.
Нажать и снять
Когда мы добавляем узел к любой стороне списка, нам нужно убедиться, что заголовок и конец нашего списка верны.
Поскольку список с заголовком и концом одного узла является одним и тем же, нам необходимо учитывать этот случай в нашей реализации. Взгляните на закомментированный код ниже.
Поп и сдвиг
Когда мы удаляем узел с любой стороны списка, нам нужно учитывать еще две вещи - список, в котором остается один узел (потому что нам нужно убедиться, что наш хвост и голова точны), и пустой список (чтобы избежать ошибок времени выполнения).
Благодаря природе связанного списка у нас есть доступ к новому заголовку списка, просто проверяя указатель текущего заголовка.
Однако, когда мы выходим из списка, нам нужно пройти по списку, чтобы найти новый хвост. Я буду использовать вспомогательный метод, который мы сможем повторно использовать в последующих методах нашего класса под названием getNodeAtIndex.
Эта функция использует счетчик и выполняет итерацию по списку, пока мы не дойдем до индекса нужного нам узла. В этом случае нам понадобится предпоследний узел или длина списка минус два.
Получение и настройка
Поскольку мы уже реализовали метод get выше для использования в нашей реализации pop, все, что нам нужно сделать, это реализовать метод set.
Этот метод находит узел по указанному индексу и изменяет его значение на переданную переменную. Он также будет использовать наш метод получения. Нам просто нужно обработать случай, если узел не найден.
Вставка и удаление
Вставка и удаление элементов из связанных списков упрощается всеми предыдущими методами, которые мы только что написали. Нам нужно будет выполнить следующие действия:
- Проверьте, существует ли индекс в связанном списке (если нет, верните
false). - При удалении / добавлении в начале или в конце списка используйте уже написанные методы (больше не беспокойтесь о хвосте / голове!).
- Получите узлы до и после вставленного / удаленного узла и правильно назначьте их указатели.
Я включил полную реализацию в сущность GitHub внизу страницы вместе с методом печати наших узлов для тестирования.
Двусвязные списки
Двусвязные списки имеют аналогичную реализацию, но ссылки как на предыдущий, так и на следующий узлы в списке имеют некоторые преимущества и недостатки.
- Мы должны отслеживать оба указателя предыдущий и следующий и убедиться, что они правильно установлены при изменении списка.
- Поскольку у нас есть доступ к предыдущей ссылке на узел, нам больше не нужно перебирать список для метода
pop. - Двусвязные списки используют больше памяти на узел, поскольку они содержат два указателя, но это позволяет нам перемещаться по списку в обоих направлениях.
- Двусвязные списки имеют постоянное время для вставки и удаления в известной позиции, в то время как односвязные списки имеют линейное время.
