Связанные списки для занятого инженера
Аудитория
Эту статью может прочитать любой инженер, даже не знакомый со связными списками. Тем не менее, я бы сказал, что это будет наиболее полезно для тех, у кого есть хотя бы мимолетное понимание, и может послужить напоминанием об основных моментах.
Аргумент
В отличие от Деревьев, которые представляют собой иерархическую структуру данных, связанные списки являются линейными. Существует два типа связанных списков: односвязные списки и двусвязные списки.
В односвязном списке каждый узел имеет значение (представленное A, B и C выше), а также указатель на следующий узел (представленный стрелкой). Конечный узел в списке будет указывать на null. Двусвязный список аналогичен, за исключением того, что есть два указателя: один на узел впереди, а другой на узел позади.
Ниже представлена простая реализация Java.
Обычно мы представляем весь список, используя первый узел (часто называемый заголовком). Затем мы можем перемещаться по списку с помощью указателей.
Поскольку нам нужно пройти по всему списку, чтобы найти элемент, время поиска равно O(n). Вставка и удаление немного отличаются.
- Если нам дан узел и нам нужно вставить после него, то наша сложность равна
O(1). - Если нам дан узел, который нам нужно удалить, то сложность односвязного списка равна
O(n), тогда как в двусвязном списке -O(1). Это похоже на то, как в односвязном списке нам нужно вернуться через узлы, чтобы найти предыдущий узел до того, который мы хотели бы удалить. - Если нам нужно найти узел, который нужно вставить или удалить, то во всех случаях сложность составляет
O(n).
Давайте подробнее остановимся на этом.
Вставка в односвязный / двусвязный список
Для односвязного списка есть два основных случая: вставка в середине списка и вставка в начале. Вставка в конец списка следует той же логике, что и вставка в середине, но «следующий» узел - это null.
Верхняя диаграмма представляет собой вставку в середину односвязного списка. Мы добавляем узел New между B и C. Для этого нам нужно указать следующий указатель B на New, затем следующий указатель New на C. Затем стирается указатель между B и C, представленный пунктирной линией.
Нижняя часть диаграммы представляет собой вставку в начале списка. Нам нужно переназначить головку, чтобы она стала нашим новым узлом, теперь указатель должен указывать на предыдущую головку.
Давайте закодируем это. Мы хотели бы иметь односвязный список с двумя методами: addAtHead и addAtIndex.
Двусвязный список немного отличается, теперь нам нужно позаботиться о двух указателях.
Первые два случая аналогичны односвязному списку. В первом мы указываем следующий указатель предыдущего узла на наш новый узел, а затем возвращаем предыдущий указатель нашего нового узла. Точно так же то, что изначально было следующим узлом, будет указано нашим новым узлом и, в свою очередь, будет указывать на него обратно.
Чтобы вставить в голову, нам нужно направить нашу предыдущую голову назад на наш новый узел, а наш новый узел вперед на предыдущую голову.
Чтобы вставить в хвост, нам нужно указать наш новый узел обратно на предыдущий хвост, а предыдущий хвост - вперед, на наш новый узел. Это отличается от односвязного списка, поскольку мы должны осознавать null отсутствие концепции предыдущего указателя.
Давайте теперь закодируем это. Мы хотели бы иметь двусвязный список с тремя методами: addAtHead, addAtIndex и addAtTail.
Удаление из односвязного / двусвязного списка
Разобравшись с прошивкой, переходим к удалению.
Если мы удаляем в центре списка, то нам нужно указать предыдущий узел на следующий узел и удалить указатель с узла для удаления. Если мы удаляем в голове, нам нужно удалить указатель с текущей головы и переместить голову к следующему узлу.
Давайте запрограммируем это. На этот раз у нас будет только один метод, deleteAtIndex.
Для удаления двусвязного списка нам нужно рассмотреть больше указателей.
В первом случае мы удаляем из середины очереди. Нам нужно указать предыдущий узел на следующий узел и наоборот.
В случае, когда мы удаляем из заголовка очереди, нам нужно удалить все указатели на узел и от узла для удаления, а затем переместить заголовок на следующий узел.
В финальном сценарии мы должны сделать то же самое, хотя нас больше не волнует голова.
Проблемы с указателем
Когда я вижу проблему с использованием связанных списков, я думаю, что это «указатели». Использование двух указателей в связанном списке и перебор с разной скоростью - это решение по крайней мере двух проблем: поиск цикла в связанном списке и расширение, поиск начала цикла.
Первоначальная проблема решается путем отправки двух указателей через связанный список, один перемещается на один шаг за раз, а следующий перемещается на два шага за раз. Если указатель находит конец списка, цикла нет. Если указатели встречаются, значит, есть.
Поиск начала цикла немного сложнее. Это требует, чтобы мы сначала нашли место, где узлы сталкиваются (как раньше), затем вернули один указатель на начало списка, продолжая повторять другой.
Последняя проблема, которую мы решим, - это перевернуть связанный список. Мы можем сделать это, перебирая наш список, указывая текущий узел на предыдущий, а затем перемещая голову. Визуальное представление ниже.
Это воплощено в кодированном решении ниже.
Вывод
В заключение мы представили, исследовали и реализовали связанные списки, решая множество проблем.
