Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
В предыдущей статье, посвященной SkipList, некоторые студенты сообщили, что из-за отсутствия знаний и понимания связанных списков слишком сложно напрямую вникать в алгоритм. Кроме того, стек был представлен в предыдущей статье, поэтому в этот раз мы продолжаем тему линейной таблицы, давайте обсудим ее вместе.связанный список.
Связанный список является основой многих структур данных. Его главная особенность заключается в том, что он поддерживает быстрое удаление и вставку, поэтому он широко используется во многих сценариях, где данные часто меняются. И связанный списокСильная масштабируемость, поэтому его применение очень обширно, и существует множество связанных расширений и улучшенных версий. Сегодня мы собираемся представить вам двусторонний связанный список, также известный как двусвязный список, который является улучшенной версией обычного односвязного списка и часто используемого связанного списка.
Односвязный список
Связный список — это общая базовая структура данных, это линейный список, но он хранит данные не в линейном порядке, а хранит указатель (Pointer) на следующий узел в каждом узле. Вышеприведенное определение в Википедии.Мы можем понять два момента.Во-первых, связанный список состоит из нескольких узлов, и каждый узел хранит позицию следующего узла. Во-вторых, отдельные узлы связанного списка не сохраняются последовательно.
Давайте посмотрим на изображение ниже для лучшего понимания:
На приведенном выше рисунке показан односвязный список.Односторонний означает, что каждый узел имеет только один указатель на узел-преемник, а это означает, что связанный список имеет только одно направление обхода, поэтому он называется односвязным списком.
Добавления и удаления в связанных списках
У новичков может возникнуть головная боль при изучении связанных списков.По сравнению с прямым доступом к массивам, связанные списки должны проходить узлы, перемещая указатели, чтобы изменить содержимое узлов для завершения добавления и удаления, поэтому это не так интуитивно понятно, как массивы. Я пытался найти хороший пример для описания механизма работы связанного списка, пока не посмотрел фильм о шпионской войне и не обнаружил, что система шпионского контакта работает в виде связанного списка. Поэтому я решил взять шпионскую систему в качестве примера, чтобы показать, как работает связанный список.
Предположим, вы находитесь в Китайской Республикеглава армии, вы отвечаете за шпионскую связь. Для вашей безопасности вы и ваши людиодносторонний контактиз. То есть вы можете связаться только с одним из ваших подчиненных, и этот подчиненный затем свяжется с другими и, наконец, передаст секретный код цели. Предположим, ваше кодовое имя — A, ваш подчиненный — B, а подчиненный B — C, C для выполнения задачи. Этот механизм работал очень хорошо, пока однажды B не переместил место по загадочным причинам, в результате чего время контакта между A и B увеличилось. Чтобы решить эту проблему, вы решаете добавить нового человека, D, который отвечает за для связи между А и Б., чтобы ускорить контакт. Что вы должны сделать?
Из-за ограничений личности и соображений безопасности вам не известна конкретная информация о Б. Вы можете отправить сообщение только А, позволить А связаться с новым человеком D и сказать ему, как связаться с Б. Еще один момент, который следует отметить, заключается в том, что A должен дождаться, пока D успешно найдет B, прежде чем разорвать соединение с B. В противном случае, как только что-то случится с D, вся связь будет прервана.
Всю картинку рисуем следующим образом:
Сначала дайте D и B связаться, а затем отключите A и B. Но есть проблема, так как есть только один преемник A, и если A указывает на D, то позиция B будет потеряна. Поэтому нам нужно использовать временную переменную cur, чтобы сначала сохранить местоположение B, а затем позволить D указывать на этот cur. Но в Python нам не нужно быть такими хлопотными, используя метод присваивания с несколькими переменными в Python, мы можем сделать это с помощью одной строки кода.
код показывает, как показано ниже:
def add(pos, new_node):
new_node.next, pos.next = pos.next, new_node
Если через какое-то время B возвращается на прежнее место, D нам больше не нужен, что нам делать, чтобы удалить этот узел? Это очень просто, просто попросите D предоставить A последнюю контактную информацию B. Другими словами, пусть A пересекает D, чтобы указать на B.
Посмотрите на картинку:
def delete(pos):
pos.next = pos.next.next
Двусвязный список
После понимания односвязного списка двусвязный список также очень прост. Значение двунаправленности также очевидно: помимо записи положения последующих узлов, каждый узел также будетисточник записиРасположение узла. С помощью двустороннего указателя не только удобно получить исходный узел, но также можно легко выполнить ретроспективный обход и вставку заголовка всего связанного списка.
Помните, что мы представили в нашей предыдущей теме Pythondequeэта библиотека? С помощью deque мы можем реализовать очередь для добавления и удаления элементов в обоих направлениях.В сочетании с определением двусвязного списка легко обнаружить, что deque на самом деле является двусвязным списком, который сохраняет некоторые API. Другими словами, двухсторонняя очередь реализуется на основе двусвязного списка, точно так же, как стек реализуется на основе списка.
По сравнению с односвязным списком, поскольку у нас есть еще один указатель, его будет легче понять и реализовать, потому что то, что раньше делалось через последовательные связи и временные переменные, теперь можно легко реализовать через прямые указатели.
Ниже приведен код для добавления и удаления двусвязного списка:
def add(pos, new_node):
pos.next, new_node.next = new_node, pos.next
new_node.pre, new_node.next.pre = pos, new_node
def delete(pos):
pos.next = pos.next.next
# 这个时候pos.next已经更新
pos.next.pre = pos
Суммировать
Сам по себе двусвязный список не сложен, и изменений не так много, и он намного проще, чем представленный ранее SkipList. Я считаю, что даже новички могут справиться с этим, если они делают это сами. Когда я впервые узнал о структурах данных, я очень сопротивлялся использованию связанных списков, за исключением того, что я чувствовал, что адресация была громоздкой и требовало много времени для обхода всего связанного списка. Другая фундаментальная причина заключается в том, что написание связанных списков на C++ громоздко, и его легко реализовать.Утечки памяти и дикие указателипроблема. Так что я старался максимально использовать массивы как альтернативу, и даже какое-то время думал, что со снижением цены на память мы можем когда-нибудь отказаться от структуры связанных списков.
Только позже, когда я узнал об операционных системах, я нашел причину, по которой мне пришлось использовать связанные списки. Поскольку в операционной системепамять не является непрерывной, большая часть памяти разбросана. Когда мы создаем массив, мы фактически просим операционную систему запросить непрерывный участок памяти. Чем больше массив, на который мы обращаемся, тем больше будет этот кусок памяти. Очевидно, что чем больше память, тем сложнее на нее претендовать, потому что большая часть памяти разбита на множество фрагментов, и в случае нехватки ресурсов операционной системе нужно проделать большую работу по сбору фрагментов.
Связный список позволяет избежать этой проблемы, поскольку к нему обращаются с помощью указателей.Элементы в связанном списке разбросаны по всей памяти, разделяя нагрузку по потреблению памяти. Это также является причиной того, что связанные списки широко используются в области операционных систем.
Наконец, из-за нехватки места мы не разместили весь код. Студенты, которые хотят получить полный код двусвязного списка, могут подписаться на мою официальную учетную запись и ответить"Двусвязный список"Получать.
На сегодняшней статье все. Если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.