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

Автор оригинала: Usman Malik.

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

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

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

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

Плюсы

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

Аферы

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

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

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

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

class Node:
    def __init__(self, data):
        self.item = data
        self.nref = None
        self.pref = None

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

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

class DoublyLinkedList:
    def __init__(self):
        self.start_node = None

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

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

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

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

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

 def insert_in_emptylist(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
        else:
            print("list is not empty")

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

Добавьте метод insert_in_empty list() в созданный ранее класс Double Linked List .

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

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

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

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

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

    def insert_at_start(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
            print("node inserted")
            return
        new_node = Node(data)
        new_node.nref = self.start_node
        self.start_node.pref = new_node
        self.start_node = new_node

Добавьте метод insert_at_start() в класс Double Linked List , созданный ранее.

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

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

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

    def insert_at_end(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
            return
        n = self.start_node
        while n.nref is not None:
            n = n.nref
        new_node = Node(data)
        n.nref = new_node
        new_node.pref = n

Добавьте метод insert_at_end() в класс Double Linked List , созданный ранее.

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

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

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

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

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

    def insert_after_item(self, x, data):
        if self.start_node is None:
            print("List is empty")
            return
        else:
            n = self.start_node
            while n is not None:
                if n.item == x:
                    break
                n = n.nref
            if n is None:
                print("item not in the list")
            else:
                new_node = Node(data)
                new_node.pref = n
                new_node.nref = n.nref
                if n.nref is not None:
                    n.nref.prev = new_node
                n.nref = new_node

Добавьте метод insert_after_item() в класс Double Linked List , созданный ранее.

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

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

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

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

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

    def insert_before_item(self, x, data):
        if self.start_node is None:
            print("List is empty")
            return
        else:
            n = self.start_node
            while n is not None:
                if n.item == x:
                    break
                n = n.nref
            if n is None:
                print("item not in the list")
            else:
                new_node = Node(data)
                new_node.nref = n
                new_node.pref = n.pref
                if n.pref is not None:
                    n.pref.nref = new_node
                n.pref = new_node

Добавьте метод insert_before_item() в класс Double Linked List , созданный ранее.

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

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

    def traverse_list(self):
        if self.start_node is None:
            print("List has no element")
            return
        else:
            n = self.start_node
            while n is not None:
                print(n.item , " ")
                n = n.nref

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

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

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

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

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

   def delete_at_start(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        if self.start_node.nref is None:
            self.start_node = None
            return
        self.start_node = self.start_node.nref
        self.start_prev = None;

Добавьте метод delete_at_start() в класс Double Linked List , созданный ранее.

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

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

    def delete_at_end(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        if self.start_node.nref is None:
            self.start_node = None
            return
        n = self.start_node
        while n.nref is not None:
            n = n.nref
        n.pref.nref = None

Добавьте метод delete_at_end() в класс Double Linked List , созданный ранее.

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

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

    def delete_element_by_value(self, x):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        if self.start_node.nref is None:
            if self.start_node.item == x:
                self.start_node = None
            else:
                print("Item not found")
            return 

        if self.start_node.item == x:
            self.start_node = self.start_node.nref
            self.start_node.pref = None
            return

        n = self.start_node
        while n.nref is not None:
            if n.item == x:
                break;
            n = n.nref
        if n.nref is not None:
            n.pref.nref = n.nref
            n.nref.pref = n.pref
        else:
            if n.item == x:
                n.pref.nref = None
            else:
                print("Element not found")

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

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

        if self.start_node is None:
            print("The list has no element to delete")
            return

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

Следующая часть кода реализует эту логику:

        if self.start_node.nref is None:
            if self.start_node.item == x:
                self.start_node = None
            else:
                print("Item not found")
            return

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

        if self.start_node.item == x:
            self.start_node = self.start_node.nref
            self.start_node.pref = None
            return

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

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

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

        n = self.start_node
        while n.nref is not None:
            if n.item == x:
                break;
            n = n.nref
        if n.nref is not None:
            n.pref.nref = n.nref
            n.nref.pref = n.pref
        else:
            if n.item == x:
                n.pref.nref = None
            else:
                print("Element not found")

Добавьте метод delete_element_by_value() в класс Double Linked List , созданный ранее.

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

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

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

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

    def reverse_linked_list(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        p = self.start_node
        q = p.nref
        p.nref = None
        p.pref = q
        while q is not None:
            q.pref = q.nref
            q.nref = p
            p = q
            q = q.pref
        self.start_node = p

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

Тестирование Функций Двусвязного Списка

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

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

new_linked_list = DoublyLinkedList()

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

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

new_linked_list.insert_in_emptylist(50)

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

new_linked_list.traverse_list()

Выход:

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

new_linked_list.insert_at_start(10)
new_linked_list.insert_at_start(5)
new_linked_list.insert_at_start(18)

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

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

new_linked_list.insert_at_end(29)
new_linked_list.insert_at_end(39)
new_linked_list.insert_at_end(49)

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

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

new_linked_list.insert_after_item(50, 65)

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

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

new_linked_list.insert_before_item(29, 100)

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

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

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

new_linked_list.delete_at_start()

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

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

new_linked_list.delete_at_end()

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

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

new_linked_list.delete_element_by_value(65)

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

Тестирование Обратной Функции

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

new_linked_list.reverse_linked_list()

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

Вывод

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

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