Как написать двусвязный список в питоне

5

Rukovodstvo

статьи и идеи для разработчиков программного обеспечения и веб-разработчиков.

Двусвязный список с примерами Python

Это третья статья в серии статей о реализации связанного списка в Python. В Части 1 [/ connected-lists-in-detail-with-python-examples-single-Linked-lists /] и Части 2 [/ sorting-and-merging-single-connected-list /] серии мы изучили отдельные связанный список в деталях. В этой статье мы начнем обсуждение двусвязного списка, который на самом деле является расширением односвязного списка. В односвязном списке каждый узел списка состоит из двух компонентов, фактическое значение узла

Время чтения: 12 мин.

Это третья статья в серии статей о реализации связанного списка в Python. В Части 1 и Части 2 этой серии мы подробно изучали односвязный список. В этой статье мы начнем обсуждение двусвязного списка, который на самом деле является расширением односвязного списка.

В односвязном списке каждый узел списка имеет два компонента: фактическое значение узла и ссылку на следующий узел в связанном списке. В двусвязном списке каждый узел имеет три компонента: значение узла, ссылку на предыдущий узел и ссылку на следующий узел. Для начального узла двусвязного списка ссылка на предыдущий узел равна нулю. Точно так же для последнего узла в двусвязном списке ссылка на следующий узел равна нулю.

Плюсы и минусы двусвязного списка

Ниже приведены некоторые плюсы и минусы двусвязного списка:

Плюсы

• В отличие от односвязного списка, двусвязный список можно перемещать и искать в обоих направлениях. Ссылка на следующий узел помогает в обходе узла в прямом направлении, в то время как ссылки на предыдущие узлы позволяют обход в обратном направлении.
• Основные операции, такие как вставка и удаление, легче реализовать в двусвязных списках, поскольку, в отличие от односвязных списков, нам не нужно переходить к узлу-предшественнику и сохранять его ссылку. Скорее, в двусвязном списке ссылка на узел-предшественник может быть получена из узла, который мы хотим удалить.

Минусы

• Одним из основных недостатков двусвязного списка является то, что вам нужно больше места в памяти для хранения одной дополнительной ссылки для каждого узла.
• Для выполнения операций вставки и удаления необходимо выполнить несколько дополнительных шагов.

Реализация двусвязного списка с помощью Python

В этом разделе мы увидим, как мы можем создать очень простой двусвязный список в Python. Если вы читали часть 1 и часть 2 этой серии статей, код должен быть довольно простым.

Как всегда, давайте сначала создадим класс для единственного узла в списке. Добавьте в свой файл следующий код:

В приведенном выше коде вы можете видеть, что мы создаем Node с тремя переменными-членами: item , nref и pref . item будет хранить фактические данные для узла. nref хранит ссылку на следующий узел, а pref сохраняет ссылку на предыдущий узел в двусвязном списке.

Затем нам нужно создать DoublyLinkedList , который содержит различные функции, связанные с двусвязным списком. Добавьте следующий код:

В этой статье мы продолжим добавлять функции к этому классу.

Вставка элементов в двусвязный список

В этом разделе мы увидим различные способы вставки элементов в двусвязный список.

Вставка элементов в пустой список

Самый простой способ вставить элемент в двусвязный список — это вставить элемент в пустой список. Следующий скрипт вставляет элемент в начало двусвязного списка:

В приведенном выше скрипте мы определяем метод insert_in_emptylist() . Сначала метод проверяет, имеет ли значение переменной self.start_node None или нет. Если переменная равна None , это означает, что список фактически пуст. Затем создается новый узел, и его значение инициализируется значением, переданным в качестве параметра параметра data функции insert_in_emptylist() . Наконец, значение self.start_node устанавливается на новый узел. В случае, если список не пустой, пользователю просто отображается сообщение о том, что список не пуст.

Добавьте метод insert_in_emptylist() в DoublyLinkedList вами ранее класс DoublyLinkedList.

Вставка элементов в начало

Чтобы вставить элемент в начало двусвязного списка, мы должны сначала проверить, является ли список пустым или нет. Если список пуст, мы можем просто использовать логику, определенную в insert_in_emptylist() для вставки элемента, поскольку в пустом списке первый элемент всегда находится в начале.

Иначе, если список не пустой, нам нужно выполнить три операции:

1. Для нового узла ссылка на следующий узел будет установлена на self.start_node .
2. Для self.start_node ссылка на предыдущий узел будет установлена на вновь вставленный узел.
3. Наконец, self.start_node станет вновь вставленным узлом.

Следующий скрипт вставляет элемент в начало двусвязного списка:

Добавьте метод insert_at_start() в DoublyLinkedList вами ранее класс DoublyLinkedList.

Вставка элементов в конец

Вставка элемента в конец двусвязного списка чем-то похожа на вставку элемента в начало. Сначала нам нужно проверить, пуст ли список. Если список пуст, мы можем просто использовать метод insert_in_emptylist() для вставки элемента. Если список уже содержит какой-то элемент, мы проходим по списку, пока ссылка на следующий узел не станет None . Когда ссылка на следующий узел становится None это означает, что текущий узел является последним узлом.

Предыдущая ссылка для нового узла устанавливается на последний узел, а следующая ссылка для последнего узла устанавливается на вновь вставленный узел. Сценарий для вставки элемента в последний узел выглядит следующим образом:

Добавьте метод insert_at_end() в DoublyLinkedList вами ранее класс DoublyLinkedList.

Вставка элемента после другого элемента

Чтобы вставить элемент после другого элемента, мы сначала проверяем, пуст ли список. Если список действительно пуст, мы просто отображаем сообщение о том, что «список пуст».

В противном случае мы перебираем все узлы двусвязного списка. В случае, если узел, после которого мы хотим вставить новый узел, не найден, мы отображаем сообщение пользователю о том, что элемент не найден. В противном случае, если узел найден, он выбирается, и мы выполняем четыре операции:

1. Установите предыдущую ссылку вновь вставленного узла на выбранный узел.
2. Установите следующую ссылку вновь вставленного узла на следующую ссылку выбранного.
3. Если выбранный узел не является последним узлом, установите предыдущую ссылку следующего узла после выбранного узла на вновь добавленный узел.
4. Наконец, установите следующую ссылку выбранного узла на вновь вставленный узел.

Скрипт для вставки элемента после другого элемента выглядит следующим образом:

Добавьте метод insert_after_item() в DoublyLinkedList вами ранее класс DoublyLinkedList.

Вставка элемента перед другим элементом

Чтобы вставить элемент перед другим элементом, мы сначала проверяем, пуст ли список. Если список действительно пуст, мы просто отображаем сообщение о том, что «список пуст».

В противном случае мы перебираем все узлы двусвязного списка. В случае, если узел, перед которым мы хотим вставить новый узел, не найден, мы отображаем сообщение пользователю, что элемент не найден. В противном случае, если узел найден, он выбирается, и мы выполняем четыре операции:

1. Установите следующую ссылку вновь вставленного узла на выбранный узел.
2. Установите предыдущую ссылку вновь вставленного узла на предыдущую ссылку выбранного.
3. Установите следующую ссылку узла, предшествующего выбранному узлу, на только что добавленный узел.
4. Наконец, установите предыдущую ссылку выбранного узла на вновь вставленный узел.

Сценарий для добавления элемента перед другим элементом в двусвязном списке выглядит следующим образом:

Добавьте метод insert_before_item() в DoublyLinkedList вами ранее класс DoublyLinkedList.

Обход двусвязного списка

Обход двусвязного списка очень похож на обход односвязного списка. Сценарий выглядит следующим образом:

Добавьте метод traverse_list() в DoublyLinkedList вами ранее класс DoublyLinkedList.

Удаление элементов из двусвязного списка

Как и вставка, существует несколько способов удаления элементов из двусвязного списка. В этом разделе мы рассмотрим некоторые из них.

Удаление элементов с самого начала

Самый простой способ удалить элемент из двусвязного списка — сначала. Для этого все, что вам нужно сделать, это установить значение начального узла на следующий узел, а затем установить для предыдущей ссылки начального узла значение « None . Однако, прежде чем мы это сделаем, нам нужно выполнить две проверки. Во-первых, нам нужно увидеть, пуст ли список. И затем мы должны увидеть, содержит ли список только один элемент или нет. Если список содержит только один элемент, мы можем просто установить для начального узла значение None . Следующий сценарий может использоваться для удаления элементов с начала двусвязного списка.

Добавьте метод delete_at_start() в DoublyLinkedList вами ранее класс DoublyLinkedList.

Удаление элементов с конца

Чтобы удалить элемент с конца, мы снова проверяем, пуст ли список или содержит ли список единственный элемент. Если список содержит единственный элемент, все, что нам нужно сделать, это установить для начального узла значение None . Если в списке более одного элемента, мы перебираем список до тех пор, пока не будет достигнут последний узел. Как только мы достигаем последнего узла, мы устанавливаем следующую ссылку узла, предшествующего последнему узлу, на None что фактически удаляет последний узел. Следующий скрипт можно использовать для удаления элемента с конца.

Добавьте метод delete_at_end() к DoublyLinkedList который вы создали ранее.

Удаление элементов по значению

Удаление элемента по значению — самая сложная из всех функций удаления в двусвязных списках, поскольку для удаления элемента по значению необходимо обработать несколько случаев. Давайте сначала посмотрим, как выглядит функция, а затем мы увидим объяснение отдельного фрагмента кода.

В приведенном выше скрипте мы создаем delete_element_by_value() которая принимает значение узла в качестве параметра и удаляет этот узел. В начале функции мы проверяем, пустой список или нет. Если список пуст, мы просто показываем пользователю, что список пуст.

Эта логика реализована в следующем фрагменте кода:

Затем мы проверяем, есть ли в списке единственный элемент и действительно ли этот элемент является элементом, который мы хотим удалить. Если единственным элементом является тот, который мы хотим удалить, мы просто устанавливаем для self.start_node значение None что означает, что теперь в списке не будет элемента. Если есть только один элемент, и это не тот элемент, который мы хотим удалить, мы просто отобразим сообщение о том, что удаляемый элемент не найден.

Следующий фрагмент кода реализует эту логику:

Затем мы обрабатываем случай, когда список имеет более одного элемента, но элемент, который нужно удалить, является первым элементом. В этом случае мы просто выполняем логику, написанную для метода delete_at_start() . Следующий фрагмент кода удаляет элемент с самого начала в случае нескольких элементов:

Наконец, если список содержит несколько элементов и удаляемый элемент не является первым элементом, мы просматриваем все элементы в списке, кроме последнего, и смотрим, имеет ли какой-либо из узлов значение, соответствующее значению, которое нужно удалить. Если узел найден, выполняем следующие две операции:

1. Установите значение следующей ссылки предыдущего узла на следующую ссылку удаляемого узла.
2. Установите предыдущее значение следующего узла на предыдущую ссылку удаляемого узла.

Наконец, если удаляемый узел является последним узлом, для следующей ссылки узла, предшествующего последнему узлу, устанавливается значение « None . Следующий скрипт реализует эту логику:

Добавьте метод delete_element_by_value() DoublyLinkedList который вы создали ранее.

Переворачивание двусвязного списка

Чтобы перевернуть двусвязный список, вам в основном необходимо выполнить следующие операции:

1. Следующая ссылка начального узла должна иметь значение none, потому что первый узел станет последним узлом в обратном списке.
2. Для предыдущей ссылки последнего узла необходимо установить значение « None поскольку последний узел станет предыдущим узлом.
3. Следующие ссылки узлов (кроме первого и последнего узла) в исходном списке должны быть заменены предыдущими ссылками.

Сценарий обращения двусвязного списка выглядит следующим образом:

Добавьте метод reverse_linked_list() в DoublyLinkedList который вы создали ранее.

Тестирование функций двусвязного списка

В этом разделе мы протестируем двусвязные функции, которые мы создали в предыдущих разделах.

Сначала создадим объект класса DoublyLinkedList Выполните следующий скрипт:

Тестирование функций вставки

Давайте сначала протестируем функции вставки. Сначала мы добавим элементы в пустой список. Выполните следующий скрипт:

Теперь, если вы пройдете по списку, вы должны увидеть 50 как единственный элемент в списке, как показано ниже:

Теперь давайте добавим несколько элементов в начале. Выполните следующий скрипт:

Теперь, если вы пройдете по списку, вы должны увидеть следующие элементы в списке:

Чтобы добавить элементы в конце, выполните следующий скрипт:

Теперь, если вы пройдете по двусвязному списку, вы должны увидеть следующие элементы:

Вставим элемент после 50.

Теперь список должен выглядеть так:

Наконец, давайте добавим элемент перед пунктом 29.

Список на данный момент должен содержать следующие элементы:

Тестирование функций удаления

Давайте теперь протестируем функции удаления для элементов, которые мы вставили в последние разделы. Давайте сначала удалим элемент с самого начала.

Пункт 18 будет удален, и теперь список будет выглядеть так:

Точно так же следующий скрипт удаляет элемент из конца двусвязного списка:

Теперь при просмотре списка будут возвращены следующие элементы:

Наконец, вы также можете удалить элементы по значению с помощью функции delete_element_by_value() как показано ниже:

Если вы сейчас пройдете по списку, вы увидите, что элемент 65 будет удален из списка.

Проверка обратной функции

Наконец, давайте перевернем список с помощью функции reverse_linked_list() . Выполните следующий скрипт:

Теперь, если вы пройдете по списку, вы увидите перевернутый связанный список:

Заключение

Двусвязный список чрезвычайно полезен, особенно когда вам нужно выполнить множество операций вставки и удаления. Ссылки на предыдущий и следующий узлы позволяют очень легко вставлять и удалять новые элементы, не отслеживая предыдущий и следующий узлы.

В этой статье мы увидели, как двусвязный список может быть реализован с помощью Python. Мы также увидели различные способы выполнения операций вставки и удаления в двусвязном списке. Наконец, мы изучили, как перевернуть двусвязный список.

Реализация двусвязного списка в Python

В этой статье мы начнем обсуждение двусвязного списка Python, который на самом деле является расширением односвязного списка.

В односвязном списке каждый узел списка имеет два компонента: фактическое значение узла и ссылку на следующий узел в связанном списке. В двусвязном списке каждый узел имеет три компонента: значение узла, ссылку на предыдущий узел и ссылку на следующий узел. Для начального узла двусвязного списка ссылка на предыдущий узел равна нулю. Точно так же для последнего узла в двусвязном списке ссылка на следующий узел равна нулю.

Плюсы и минусы

Ниже приведены некоторые плюсы и минусы двусвязного списка:

• В отличие от односвязного списка, двусвязный список можно перемещать и искать в обоих направлениях. Ссылка на следующий узел помогает в обходе узла в прямом направлении, в то время как ссылки на предыдущие узлы позволяют обход в обратном направлении.
• Базовые операции, такие как вставка и удаление, легче реализовать в двусвязных списках, поскольку, в отличие от односвязных списков, нам не нужно переходить к узлу-предшественнику и сохранять его ссылку. Скорее, в двусвязном списке ссылка на узел-предшественник может быть получена из узла, который мы хотим удалить.

• Одним из основных недостатков двусвязного списка является то, что вам нужно больше места в памяти для хранения одной дополнительной ссылки для каждого узла.
• Для выполнения операций вставки и удаления необходимо выполнить несколько дополнительных шагов.

Реализация

В этом разделе мы увидим, как мы можем создать очень простой двусвязный список в Python. Если вы читали часть 1 и часть 2 этой серии статей, код должен быть довольно простым.

Как всегда, давайте сначала создадим класс для единственного узла в списке. Добавьте в свой файл следующий код:

В приведенном выше коде вы можете видеть, что мы создаем класс Node с тремя переменными-членами: item, nref и pref. Переменная item будет хранить фактические данные для узла. Nref хранит ссылку на следующий узел, а pref сохраняет ссылку на предыдущий узел в двусвязном списке.

Затем нам нужно создать класс DoublyLinkedList, который содержит различные функции, связанные с двусвязным списком Python. Добавьте следующий код:

В этой статье мы продолжим добавлять функции к этому классу.

Вставка элементов в пустой список

Самый простой способ вставить элемент в двусвязный список – это вставить элемент в пустой список. Следующий скрипт вставляет элемент в начало двусвязного списка:

В приведенном выше скрипте мы определяем метод insert_in_emptylist(). Сначала метод проверяет, имеет ли значение переменной self.start_node значение None или нет. Если переменная равна None, это означает, что список фактически пуст.

Затем создается новый узел, и его значение инициализируется значением, переданным в качестве параметра данных функции insert_in_emptylist(). Наконец, значение переменной self.start_node устанавливается на новый узел. В случае, если список не пустой, пользователю просто отображается сообщение о том, что список не пуст.

Добавьте метод insert_in_emptylist() в созданный вами ранее класс DoublyLinkedList.

Вставка элементов в начало

Чтобы вставить элемент в начало двусвязного списка, мы должны сначала проверить, является ли список пустым или нет. Если список пуст, мы можем просто использовать логику, определенную в insert_in_emptylist(), для вставки элемента, поскольку в пустом списке первый элемент всегда находится в начале.

1. Для нового узла ссылка на следующий узел будет установлена на self.start_node.
2. Для self.start_node ссылка на предыдущий узел будет установлена на вновь вставленный узел.
3. Наконец, self.start_node станет вновь вставленным узлом.

Следующий скрипт вставляет элемент в начало двусвязного списка:

Добавьте метод insert_at_start() в созданный вами ранее класс DoublyLinkedList.

Вставка элементов в конец

Вставка элемента в конец двусвязного списка чем-то похожа на вставку элемента в начало. Сначала нам нужно проверить, пуст ли список. Если список пуст, мы можем просто использовать метод insert_in_emptylist() для вставки элемента. Если список уже содержит какой-то элемент, мы проходим по списку, пока ссылка на следующий узел не станет None. Когда ссылка на следующий узел становится None, это означает, что текущий узел является последним узлом.

Предыдущая ссылка для нового узла устанавливается на последний узел, а следующая ссылка для последнего узла устанавливается на вновь вставленный узел. Скрипт для вставки элемента в последний узел выглядит следующим образом:

Добавьте метод insert_at_end() в созданный вами ранее класс DoublyLinkedList.

Вставка элемента после другого элемента

Чтобы вставить элемент после другого элемента, мы сначала проверяем, пуст ли список. Если список действительно пуст, мы просто отображаем сообщение о том, что «список пуст».

1. Установите предыдущую ссылку вновь вставленного узла на выбранный узел.
2. Установите следующую ссылку вновь вставленного узла на следующую ссылку выбранного.
3. Если выбранный узел не является последним узлом, установите предыдущую ссылку следующего узла после выбранного узла на вновь добавленный узел.
4. Наконец, установите следующую ссылку выбранного узла на вновь вставленный узел.

Скрипт для вставки элемента после другого элемента выглядит следующим образом:

Добавьте метод insert_after_item() в созданный вами ранее класс DoublyLinkedList.

Как вставить элемент перед другим элементом

Чтобы вставить элемент перед другим элементом, мы сначала проверяем, пуст ли список. Если список действительно пуст, мы просто отображаем сообщение о том, что «список пуст».

1. Установите следующую ссылку вновь вставленного узла на выбранный узел.
2. Установите предыдущую ссылку вновь вставленного узла на предыдущую ссылку выбранного.
3. Установите следующую ссылку узла, предшествующего выбранному узлу, на только что добавленный узел.
4. Наконец, установите предыдущую ссылку выбранного узла на вновь вставленный узел.

Скрипт для добавления элемента перед другим элементом в двусвязном списке выглядит следующим образом:

Добавьте метод insert_before_item() в созданный вами ранее класс DoublyLinkedList.

Обход двусвязного списка

Обход двусвязного списка очень похож на обход односвязного списка. Скрипт выглядит следующим образом:

Добавьте метод traverse_list() в созданный вами ранее класс DoublyLinkedList.

Удаление элементов из двусвязного списка

Как и вставка, существует несколько способов удаления элементов из двусвязного списка. В этом разделе мы рассмотрим некоторые из них.

Удаление элементов с самого начала

Самый простой способ удалить элемент из двусвязного списка – сначала. Для этого все, что вам нужно сделать, это установить значение начального узла на следующий, а затем установить для предыдущей ссылки начального узла значение «None». Однако, прежде чем мы это сделаем, нам нужно выполнить две проверки. Во-первых, нам нужно увидеть, пуст ли список.

И затем мы должны увидеть, содержит ли список только один элемент или нет. Если список содержит только один элемент, мы можем просто установить для начального узла значение None. Следующий скрипт может использоваться для удаления элементов с начала двусвязного списка.

Добавьте метод delete_at_start() к классу DoublyLinkedList, который вы создали ранее.

Удаление элементов с конца

Чтобы удалить элемент с конца, мы снова проверяем, пуст ли список или содержит ли список единственный элемент. Если список содержит единственный элемент, все, что нам нужно сделать, это установить для начального узла значение None. Если в списке более одного элемента, мы перебираем список до тех пор, пока не будет достигнут последний узел.

Как только мы достигаем последнего узла, мы устанавливаем следующую ссылку узла, предшествующего последнему, на None, что фактически удаляет последний узел. Следующий скрипт можно использовать для удаления элемента с конца.

Добавьте метод delete_at_end() к классу DoublyLinkedList, который вы создали ранее.

Удаление элементов по значению

Удаление элемента по значению – самая сложная из всех функций удаления в двусвязных списках, поскольку для удаления элемента по значению необходимо обработать несколько случаев. Давайте сначала посмотрим, как выглядит функция, а затем мы увидим объяснение отдельного фрагмента кода.

В приведенном выше скрипте мы создаем функцию delete_element_by_value(), которая принимает значение узла в качестве параметра и удаляет этот узел. В начале функции мы проверяем, пустой список или нет. Если список пуст, мы просто показываем пользователю, что список пуст.

Эта логика реализована в следующем фрагменте кода:

Затем мы проверяем, есть ли в списке единственный элемент и действительно ли этот элемент является элементом, который мы хотим удалить. Если единственным элементом является тот, который мы хотим удалить, мы просто устанавливаем для self.start_node значение None, что означает, что теперь в списке не будет элемента.

Если есть только один элемент, и это не тот элемент, который мы хотим удалить, мы просто отобразим сообщение о том, что удаляемый элемент не найден.

Следующий фрагмент кода реализует эту логику:

Затем мы обрабатываем случай, когда список имеет более одного элемента, но элемент, который нужно удалить, является первым элементом. В этом случае мы просто выполняем логику, написанную для метода delete_at_start(). Следующий фрагмент кода удаляет элемент с самого начала в случае нескольких элементов:

1. Установите значение следующей ссылки предыдущего узла на следующую ссылку удаляемого узла.
2. Установите предыдущее значение следующего узла на предыдущую ссылку удаляемого узла.

Наконец, если удаляемый узел является последним узлом, для следующей ссылки узла, предшествующего последнему узлу, устанавливается значение «None». Следующий скрипт реализует эту логику:

Добавьте метод delete_element_by_value() к классу DoublyLinkedList, который вы создали ранее.

Переворачивание списка

1. Следующая ссылка начального узла должна иметь значение none, потому что первый узел станет последним узлом в обратном списке.
2. Для предыдущей ссылки последнего узла необходимо установить значение «None», поскольку последний узел станет предыдущим узлом.
3. Следующие ссылки узлов (кроме первого и последнего узла) в исходном списке должны быть заменены предыдущими ссылками.

Скрипт обращения двусвязного списка выглядит следующим образом:

Добавьте метод reverse_linked_list() в созданный вами ранее класс DoublyLinkedList.

Тестирование функций двусвязного списка

Сначала создадим объект класса DoublyLinkedList. Выполните следующий скрипт:

Тестирование функций вставки

Давайте сначала протестируем функции вставки. Сначала мы добавим элементы в пустой список. Выполните следующий скрипт:

Теперь, если вы пройдете по списку, вы должны увидеть 50 как единственный элемент в списке, как показано ниже:

Теперь давайте добавим несколько элементов в начале. Выполните следующий скрипт:

Теперь, если вы пройдете по списку, вы должны увидеть следующие элементы в списке:

Чтобы добавить элементы в конце, выполните следующий скрипт:

Теперь, если вы пройдете по двусвязному списку, вы должны увидеть следующие элементы:

Вставим элемент после 50.

Теперь список должен выглядеть так:

Наконец, давайте добавим элемент перед пунктом 29.

Список на данный момент должен содержать следующие элементы:

Тестирование функций удаления

Давайте теперь протестируем функции удаления для элементов, которые мы вставили в последние разделы. Давайте сначала удалим элемент с самого начала.

Пункт 18 будет удален, и теперь список будет выглядеть так:

Точно так же следующий скрипт удаляет элемент из конца двусвязного списка:

Теперь при просмотре списка будут возвращены следующие элементы:

Наконец, вы также можете удалить элементы по значению, используя функцию delete_element_by_value(), как показано ниже:

Если вы сейчас пройдете по списку, вы увидите, что элемент 65 будет удален из списка.

Проверка обратной функции

Наконец, давайте перевернем список с помощью функции reverse_linked_list(). Выполните следующий скрипт:

Теперь, если вы пройдете по списку, вы увидите перевернутый связанный список:

Заключение

Двусвязный список чрезвычайно полезен, особенно когда вам нужно выполнить множество операций вставки и удаления. Ссылки на предыдущий и следующий узлы позволяют очень легко вставлять и удалять новые элементы, не отслеживая предыдущий и следующий узлы.

В этой статье мы увидели, как двусвязный список может быть реализован с помощью Python. Мы также увидели различные способы выполнения операций вставки и удаления в двусвязном списке. Наконец, мы изучили, как перевернуть двусвязный список.

Doubly Linked List in Python – Made Easy

A doubly linked list is a data structure that is used to store lists. It is very similar to linked lists but with a few extra features. In this tutorial, we will discuss what a doubly-linked list is, we will implement it in python and see it’s output.

Pre-Requisite: Linked List

Before we move on to doubly linked lists, we need to discuss what linked lists are.

A linked list, as the name suggests, is a list in which the list items are linked to other list items in a particular way. The exact way the items are linked differs in different types of linked lists.

The most common linked list is the “singly linked list” or simply, “linked list”, in this, each item links to the next item in the list. So, to access the 10th item, we need to first access the 9th item because it links to the 10th item. And once we access the 10th item, it will allow us to access the 11th item through the link that the 10th item has.

Each item in a linked list is called a node. In a singly linked list, each node has two parts. The first part stores the data of the node, and the second part stores the link to the next node.

Now let us look at doubly linked lists.

What is a Doubly Linked List?

A doubly linked list is also a list in which the nodes are connected through links, but in this case, each node links to the next item as well as the previous item. So, once we have accessed the 10th node, we can access the 9th node and the 11th node, and to access a particular node, we will need to access either the node before it or the node after it.

The way we do this is that each node has three parts. The first part is the actual data to be stored, the second part is the link to the previous node in the list, and the third part is the link to the next node in the list.

The benefit of having two links is that it makes operations such as appending and deleting much easier and faster than a singly linked list.

To visualize, a doubly linked list looks something like this:

Doubly Linked List Representation

In the above example, you can see that there are four items/nodes in the linked list. Each node has some data or content, and each node points/links to the next and the previous node of the list. The first node’s previous link and the last node’s next link do not point to anything, so they store None (in the case of python).

To start, a list head points to the first node in the list, and a list tail points to the last node in the list. So the first and last nodes are directly accessible through them. To reach the other nodes, we either go through the head or the tail and then subsequently access the next or previous nodes respectively till we reach the target.

Implementing a Doubly Linked List in Python

Creating a doubly linked list is very straightforward. We have to create two classes, one class for nodes and the other class that will create the linked list using the nodes created by the first class.

1. Class: Node

For the node class, we only have three members in the class. One to store data, one to store the next node, and one for the previous node.

The class definition will look something like this:

Here, initially, the nodes don’t point to any other node, and it may or may not have data depending on how it was created.

2. Class: Doubly Linked List

This class will contain much more than the node class. It will contain the head node, the tail node, the number of items in the list, and many necessary methods like the method to insert new nodes, delete existing nodes, search the existing nodes, and print the list.

The class will look something like this:

The above class has many members, let us discuss them one by one.

3. The __init__ method

In the constructor, we are declaring three variables. head and tail are initialized with None , which means there are no variables in the list at the beginning, and so the count is also initialized with 0 .

4. The __repr__ method

The __repr__ method will return the string that will print the linked list. So either the list is empty, in which case we print that, or the list is not empty, so we print the data in each node one by one.

5. The append and insert method

We can either append or insert nodes at a specified position in this implementation. To append, we will check if the list is empty, if so then the head and tail can point to the new node. Otherwise, we will make the last node’s next point to the new node, then make the new node’s previous point to the last node, and finally, make the tail point to the new node.

To insert at a specified position, if the position is at the end, then we just append the node, otherwise, if the position is at the beginning, then we make the first node’s previous point to the new node, then make the new node’s next point to the first node, and finally, we make the head point to the new node.

If the position specified is in the middle, then we first reach that position, make the next of the node before that position point to the new node, then make the new node’s previous point to the node before that position, then make the new node’s next point to the node at that position, and finally, we make the previous of the node at that position point to the new node.

We also check if the given index is valid or not, and if not, we can raise a ValueError . Also, we increment the count after every successful insert operation.

6. The remove method

To remove an item we must specify where the item is to be removed from. If the specified index is out of range, we raise a ValueError . If the index is 0, we are removing the first item, to do this, we make the head point to the second node. If the head is null, it means that the list is now empty, if not, then we have to make the new head ‘s previous store None .

Similarly, if the index is one less than the size of the list, it means we have to remove the last item, so we make the tail point to the second-last node and then make the new tail ‘s next store None .

If the index is somewhere in the middle, we first reach that position, then make the next of the node before that position point to the node after that position, and finally, make the previous of the node after that position point to the node before that position.

In removal, we are only making the node inaccessible from the list, and the actual process of removing it from memory is left to the garbage collection module of Python.

7. The index , size , and display method.

The index method is used to search for an item in the list, we go through the entire list based on the list size and return the index if we find the target. If not, we return None .

The size method returns the value of the count member of the class, which stores the number of items in the list.

And the display method prints the object, which calls the __repr__ method and the returned string is printed to the screen.

The Output

After executing multiple statements on the class, here is the output:

Example illustrating initialization, append method, and insert method.

Example illustrating remove method, index method, size method, and display method.

Conclusion

In this tutorial, we studied Doubly Linked Lists and implemented it in Python. We started by understanding the working of a singly linked list, then we discussed how a doubly linked list is different. We wrote the code for the data structure in python and discussed how each method is working, and finally we reviewed the output of the code.

Doubly Linked List with Python Examples

This is the third article in the series of articles on implementing linked list with Python. In Part 1 and Part 2 of the series we studied single linked list in detail. In this article, we will start our discussion about doubly linked list, which is actually an extension of single linked list.

In single linked list each node of the list has two components, the actual value of the node and the reference to the next node in the linked list. In the doubly linked list, each node has three components: the value of the node, the reference to the previous node, and the reference to the next node. For the start node of the doubly linked list, the reference to the previous node is null. Similarly, for the last node in the doubly linked list, the reference to next node is null.

Pros and Cons of a Doubly Linked List

Following are some of the pros and cons of a doubly linked list:

• Unlike a single linked list, the doubly linked list can be traversed and searched in both directions. The reference to the next node helps in traversing the node in the forward direction while the references to the previous nodes allow traversal in the backward direction.
• Basic operations such as insertion and deletion are easier to implement in the doubly linked lists since, unlike single linked lists, we do not need to traverse to the predecessor node and store its reference. Rather, in a doubly linked list the reference of the predecessor node can be retrieved from the node that we want to delete.

• One of the major drawbacks of the doubly linked list is that you need more memory space to store one extra reference for each node.
• A few additional steps are required to be performed in order to perform insertion and deletion operations.

Implementing the Doubly Linked List with Python

In this section, we will see how we can create a very simple doubly linked list in Python. If you have read Part 1 and Part 2 of this series of articles, the code should be pretty straight-forward.

As always, let's first create a class for the single node in the list. Add the following code to your file:

You can see in the above code, we create a Node class with three member variables: item , nref , and pref . The item variable will store the actual data for the node. The nref stores the reference to the next node, while pref stores the reference to the previous node in the doubly linked list.

Next, we need to create the DoublyLinkedList class, which contains different doubly linked list related functions. Add the following code:

Throughout this article we will keep adding functions to this class.

Inserting Items in Doubly Linked List

In this section, we will see the different ways of inserting items in a doubly linked list.

Inserting Items in Empty List

The easiest way to insert an item in a doubly linked list is to insert an item in the empty list. The following script inserts an element at the start of the doubly linked list:

In the script above, we define a method insert_in_emptylist() . The method first checks whether the self.start_node variable is None or not. If the variable is None , it means that the list is actually empty. Next, a new node is created and its value is initialized by the value passed as a parameter to the data parameter of the insert_in_emptylist() function. Finally, the value of self.start_node variable is set to the new node. In case if the list is not empty, a message is simply displayed to the user that the list is not empty.

Add the insert_in_emptylist() method to the DoublyLinkedList class that you created earlier.

Inserting Items at the Start

To insert an item at the beginning of the doubly linked list, we have to first check whether the list is empty or not. If the list is empty, we can simply use the logic defined in the insert_in_emptylist() to insert the element since in an empty list, the first element is always at the start.

Else, if the list is not empty, we need to perform three operations:

1. For the new node, the reference to the next node will be set to self.start_node .
2. For the self.start_node the reference to the previous node will be set to the newly inserted node.
3. Finally, the self.start_node will become the newly inserted node.

The following script inserts an item at the start of the doubly linked list:

Add the insert_at_start() method to the DoublyLinkedList class that you created earlier.

Inserting Items at the End

Inserting an element at the end of the doubly linked list is somewhat similar to inserting an element at the start. At first, we need to check if the list is empty. If the list is empty then we can simply use the insert_in_emptylist() method to insert the element. If the list already contains some element, we traverse through the list until the reference to the next node becomes None . When the next node reference becomes None it means that the current node is the last node.

The previous reference for the new node is set to the last node, and the next reference for the last node is set to the newly inserted node. The script for inserting an item at the last node is as follows:

Add the insert_at_end() method to the DoublyLinkedList class that you created earlier.

Inserting Item after another Item

To insert an item after another item, we first check whether or not the list is empty. If the list is actually empty, we simply display the message that the "list is empty".

Otherwise we iterate through all the nodes in the doubly linked list. In case if the node after which we want to insert the new node is not found, we display the message to the user that the item is not found. Else if the node is found, it is selected and we perform four operations:

1. Set the previous reference of the newly inserted node to the selected node.
2. Set the next reference of the newly inserted node to the next reference of the selected.
3. If the selected node is not the last node, set the previous reference of the next node after the selected node to the newly added node.
4. Finally, set the next reference of the selected node to the newly inserted node.

The script for inserting item after another item is as follows:

Add the insert_after_item() method to the DoublyLinkedList class that you created earlier.

Inserting Item before another Item

To insert an item before another item, we first check whether or not the list is empty. If the list is actually empty, we simply display the message that the "list is empty".

Otherwise we iterate through all the nodes in the doubly linked list. In case if the node before which we want to insert the new node is not found, we display the message to the user that the item is not found. Else if the node is found, it is selected and we perform four operations:

1. Set the next reference of the newly inserted node to the selected node.
2. Set the previous reference of the newly inserted node to the previous reference of the selected.
3. Set the next reference of the node previous to the selected node, to the newly added node.
4. Finally, set the previous reference of the selected node to the newly inserted node.

The script for adding item before another item in a doubly linked list is as follows:

Add the insert_before_item() method to the DoublyLinkedList class that you created earlier.

Traversing a Doubly Linked List

Traversing a doubly linked list is very similar to traversing a single linked list. The script is as follows:

Add the traverse_list() method to the DoublyLinkedList class that you created earlier.

Deleting Elements from Doubly Linked List

Like insertion, there can be multiple ways to delete elements from a doubly linked list. In this section, we will review some of them.

Deleting Elements from the Start

The easiest way to delete an element from a doubly linked list is from the start. To do so, all you have to do is set the value of the start node to the next node and then set the previous reference of the start node to None . However before we do that we need to perform two checks. First, we need to see if the list is empty. And then we have to see if the list contains only one element or not. If the list contains only one element then we can simply set the start node to None . The following script can be used to delete elements from the start of the doubly linked list.

Add the delete_at_start() method to the DoublyLinkedList class that you created earlier.

Deleting Elements from the End

To delete the element from the end, we again check if the list is empty or if the list contains a single element. If the list contains a single element, all we have to do is to set the start node to None . If the list has more than one element, we iterate through the list until the last node is reached. Once we reach the last node, we set the next reference of the node previous to the last node, to None which actually removes the last node. The following script can be used to delete the element from the end.

Add the delete_at_end() method to the DoublyLinkedList class that you created earlier.

Deleting Elements by Value

Deleting an element by value is the trickiest of all the deletion functions in doubly linked lists since several cases have to be handled in order to remove an element by value. Let's first see how the function looks like and then we will see the explanation of the individual piece of code.

In the above script we create delete_element_by_value() function that takes the node value as parameter and deletes that node. At the beginining of the function we check if the list is empty or not. If the list is empty we simply display the user that the list is empty.

This logic is implemented in the following piece of code:

Next, we check if the list has a single element and that element is actually the element we want to delete. If the only element is the one that we want to delete, we simply set the self.start_node to None which means that the list will now have no item. If there is only one item and that is not the item that we want to delete, we will simply display the message that item to be deleted is not found.

Free eBook: Git Essentials

Check out our hands-on, practical guide to learning Git, with best-practices, industry-accepted standards, and included cheat sheet. Stop Googling Git commands and actually learn it!

The following piece of code implements this logic:

Next, we handle the case where the list has more than one items but the item to be deleted is the first item. In that case we simply execute the logic that we wrote for the method delete_at_start() . The following piece of code deletes an element from the start in case of multiple items:

Finally, if the list contains multiple items and the item to be deleted is not the first item, we traverse all the elements in the list except the last one and see if any of the nodes has the value that matches the value be deleted. If the node is found, we perform the following two operations:

1. Set the value of the next reference of the previous node to the next reference of the node to be deleted.
2. Set the previous value of the next node to the previous reference of the node to be deleted.

Finally, if the node to be deleted is the last node, the next reference of the node previous to the last node is set to None . The following script implements this logic:

Add the delete_element_by_value() method to the DoublyLinkedList class that you created earlier.

Reversing a Doubly Linked List

To reverse a doubly linked list, you basically have to perform the following operations:

1. The next reference of the start node should be set none because the first node will become the last node in the reversed list.
2. The previous reference of the last node should be set to None since the last node will become the previous node.
3. The next references of the nodes (except the first and last node) in the original list should be swapped with the previous references.

The script for reversing a doubly linked list is as follows:

Add the reverse_linked_list() method to the DoublyLinkedList class that you created earlier.

Testing Doubly Linked List Functions

In this section, we will test the doubly linked functions that we created in the previous sections.

Let's first create the object of the DoublyLinkedList class. Execute the following script:

Testing Insertion Functions

Let's test the insertion functions first. We'll first add elements in the empty list. Execute the following script:

Now if you traverse the list, you should see 50 as the only element in the list as shown below:

Now let's add a few elements at the start. Execute the following script:

Now if you traverse the list, you should see the following elements in the list:

To add the elements at the end, execute the following script:

Now if you traverse the doubly linked list, you should see the following elements:

Let's insert an element after 50.

Now the list should look like this:

Finally, let's add an element before item 29.

The list at this point of time, should contain the following elements:

Testing Deletion Functions

Let's now test the deletion functions on the items that we inserted in the last sections. Let's first delete an element from the start.

Item 18 will be removed and the list will now look like this:

Similarly, the following script deletes the element from the end of the doubly linked list:

Traversing the list now will return the following items:

Finally, you can also delete the elements by value using the delete_element_by_value() function as shown below:

If you traverse the list now, you will see that item 65 will be deleted from the list.

Testing Reverse Function

Finally, let's reverse the list using the reverse_linked_list() function. Execute the following script:

Now if you traverse the list, you will see the reversed linked list:

Conclusion

The doubly linked list is extremely useful specifically when you have to perform lots of inserts and delete operations. The links to the previous and next nodes make it very easy to insert and delete new elements without keeping track of the previous and next nodes.

In this article, we saw how doubly linked list can be implemented with Python. We also saw different ways to perform insert and delete operations on doubly linked list. Finally we studied how to reverse a doubly linked list.