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

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

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

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

Плюсы

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

Минусы

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

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

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

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

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

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

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

 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_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 станет вновь вставленным узлом.

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

 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() в DoublyLinkedList вами ранее класс DoublyLinkedList.

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

Вставка элемента в конец двусвязного списка чем-то похожа на вставку элемента в начало. Сначала нам нужно проверить, пуст ли список. Если список пуст, мы можем просто использовать метод insert_in_emptylist() для вставки элемента. Если список уже содержит какой-то элемент, мы проходим по списку, пока ссылка на следующий узел не станет 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() в DoublyLinkedList вами ранее класс DoublyLinkedList.

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

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

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

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

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

 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() в DoublyLinkedList вами ранее класс DoublyLinkedList.

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

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

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

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

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

 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() в DoublyLinkedList вами ранее класс DoublyLinkedList.

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

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

 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() в DoublyLinkedList вами ранее класс DoublyLinkedList.

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

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

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

Самый простой способ удалить элемент из двусвязного списка - сначала. Для этого все, что вам нужно сделать, это установить значение начального узла на следующий узел, а затем установить для предыдущей ссылки начального узла значение « 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() в DoublyLinkedList вами ранее класс DoublyLinkedList.

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

Чтобы удалить элемент с конца, мы снова проверяем, пуст ли список или содержит ли список единственный элемент. Если список содержит единственный элемент, все, что нам нужно сделать, это установить для начального узла значение 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() к DoublyLinkedList который вы создали ранее.

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

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

 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 

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

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

Наконец, если удаляемый узел является последним узлом, для следующей ссылки узла, предшествующего последнему узлу, устанавливается значение « 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() DoublyLinkedList который вы создали ранее.

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

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

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

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

 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() 

Выход:

 50 

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

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

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

 18 
 5 
 10 
 50 

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

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

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

 18 
 5 
 10 
 50 
 29 
 39 
 49 

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

 new_linked_list.insert_after_item(50, 65) 

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

 18 
 5 
 10 
 50 
 65 
 29 
 39 
 49 

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

 new_linked_list.insert_before_item(29, 100) 

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

 18 
 5 
 10 
 50 
 65 
 100 
 29 
 39 
 49 

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

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

 new_linked_list.delete_at_start() 

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

 5 
 10 
 50 
 65 
 100 
 29 
 39 
 49 

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

 new_linked_list.delete_at_end() 

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

 5 
 10 
 50 
 65 
 100 
 29 
 39 

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

 new_linked_list.delete_element_by_value(65) 

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

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

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

 new_linked_list.reverse_linked_list() 

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

 39 
 29 
 100 
 50 
 10 
 5 

Заключение

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

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