Автор оригинала: Pankaj Kumar.
Список вдвойне связан в Python – сделал легко
Вдвойне связанный список – это структура данных, которая используется для хранения списков. Это очень похоже на связанные списки, но с несколькими дополнительными функциями. В этом уроке мы обсудим, какой вдвочно связан список, мы будем реализовать его в Python и увидеть его вывод.
Предварительный реквизит: связанный список
Прежде чем перейти к вдвойне связанным спискам, нам нужно обсудить, какие связанные списки есть.
Связанный список, как следует наименование, представляет собой список, в котором элементы списка связаны с другими элементами списка в определенном виде. Точный способ связанных элементов отличается различными типами связанных списков.
Наиболее распространенным связным списком является «односторонний список» или просто «связанный список», в этом каждый элемент ссылается на следующий элемент в списке. Итак, чтобы получить доступ к 10-м пункту, нам нужно сначала получить доступ к 9-м пункту, потому что он ссылается на 10-й элемент. И как только мы получим доступ к 10-м пункту, он позволит нам получить доступ к 11-м пункту через ссылку, который имеет 10-й элемент.
Каждый элемент в связанном списке называется узлом. В одиночном списке каждый узел имеет две части. Первая часть хранит данные узла, а вторая часть хранит ссылку на следующий узел.
Теперь давайте посмотрим на вдвойне связанные списки.
Что такое вдвойне связанный список?
Вдвойне связанный список также является списком, в котором узлы подключены через ссылки, но в этом случае каждый узел ссылается на следующий элемент, а также предыдущий элемент. Итак, как только мы получим доступ к 10-м узлу, мы можем получить доступ к 9-м узлу и 11-м узлу и получить доступ к конкретному узлу, нам нужно будет получить доступ к узлу перед ним или узлом после него.
Как мы делаем это, это то, что у каждого узла есть три части. Первая часть – это фактические данные, которые будут сохранены, вторая часть – это ссылка на предыдущий узел в списке, и третью часть – это ссылка на следующий узел в списке.
Преимущество наличия двух звеньев заключается в том, что он делает такие операции, как присоединение и удаление намного проще и быстрее, чем отдельно связанный список.
Чтобы визуализировать, вдвойне связанный список выглядит что-то подобное:
В приведенном выше примере вы можете видеть, что в связанном списке есть четыре элемента/узла. Каждый узел имеет некоторые данные или контент, и каждый узел/ссылки на следующий и предыдущий узел списка. Предыдущая ссылка первого узла и следующая ссылка последнего узла не указывает на что-то, поэтому они хранят Нет (в случае питона).
Чтобы запустить, глава списка указывает на первый узел в списке, а список хвостов указывает на последний узел в списке. Таким образом, первые и последние узлы прямо доступны через них. Для достижения других узлов мы либо проходим через голову или хвост, а затем впоследствии доступа к следующим или предыдущим узлам соответственно, пока мы не достигнем цели.
Реализация вдвойне связанного списка в Python
Создание вдвойне связанного списка очень проста. Мы должны создать два класса, один класс для узлов и другой класс, который создаст связанный список с использованием узлов, созданных первым классом.
1. Класс: узел
Для класса узла у нас есть только три члена в классе. Один для хранения данных, один для хранения следующего узла и один для предыдущего узла.
Определение класса будет выглядеть что-то подобное:
class Node:
def __init__(self, data = None):
self.data = data
self.next = None
self.previous = None
Здесь, изначально узлы не указывают на любой другой узел, и он может или не может иметь данные в зависимости от того, как он был создан.
2. Класс: вдвойне связанный список
Этот класс будет содержать гораздо больше, чем класс узла. Он будет содержать узлу головного узла, узел хвоста, количество элементов в списке и многие необходимые методы, такие как метод вставки новых узлов, удаляют существующие узлы, поиск существующих узлов и распечатайте список.
Класс будет выглядеть что-то подобное:
class DLL:
def __init__(self):
self.head = None
self.tail = None
self.count = 0
def __repr__(self):
string = ""
if(self.head == None):
string += "Doubly Linked List Empty"
return string
string += f"Doubly Linked List:\n{self.head.data}"
start = self.head.next
while(start != None):
string += f" -> {start.data}"
start = start.next
return string
def append(self, data):
if self.head == None:
self.head = Node(data)
self.tail = self.head
self.count += 1
return
self.tail.next = Node(data)
self.tail.next.previous = self.tail
self.tail = self.tail.next
self.count += 1
def insert(self, data, index):
if (index > self.count) | (index < 0):
raise ValueError(f"Index out of range: {index}, size: {self.count}")
if(index == self.count):
self.append(data)
return
if(index == 0):
self.head.previous = Node(data)
self.head.previous.next = self.head
self.head = self.head.previous
self.count += 1
return
start = self.head
for _ in range(index):
start = start.next
start.previous.next = Node(data)
start.previous.next.previous = start.previous
start.previous.next.next = start
start.previous = start.previous.next
self.count += 1
return
def remove(self, index):
if (index >= self.count) | (index < 0):
raise ValueError(f"Index out of range: {index}, size: {self.count}")
if index == 0:
self.head = self.head.next
self.head.previous = None
self.count -= 1
return
if index == (self.count - 1):
self.tail = self.tail.previous
self.tail.next = None
self.count -= 1
return
start = self.head
for i in range(index):
start = start.next
start.previous.next, start.next.previous = start.next, start.previous
self.count -= 1
return
def index(self, data):
start = self.head
for i in range(self.count):
if(start.data == data):
return i
start = start.next
return None
def size(self):
return self.count
def display(self):
print(self)
Вышеуказанный класс имеет много членов, давайте обсудим их один за другим.
3. Метод __init__
В конструкторе мы объявляем три переменных. голова и хвост инициализируются с Нет , что означает, что в списке нет переменных в списке, и поэтому Считать также инициализируется с 0 Отказ
4. Метод __repr__
Метод __REPR__ вернет строку, которая распечатает связанный список. Таким образом, либо список пуста, в этом случае мы распечатаем это, либо список не пусто, поэтому мы распечатаем данные в каждом узле один за другим.
5. Способ добавления и вставки
Мы можем либо добавить, либо вставлять узлы в указанном положении в этой реализации. Чтобы добавить, мы проверим, будет ли список пустым, если так, то голова и хвост может указывать на новый узел. В противном случае мы сделаем последний узел Следующий Укажите на новый узел, затем сделайте новый узел предыдущий Укажите на последний узел, и, наконец, сделайте хвост указать на новый узел.
Чтобы вставить в указанную позицию, если положение находится в конце, то мы просто добавляем узел, в противном случае, если позиция находится в начале, то мы делаем первый узел предыдущий Укажите на новый узел, затем сделайте новый узел Следующий Укажите на первый узел, и, наконец, мы делаем голова указать на новый узел.
Если указанная позиция находится в середине, то мы сначала доберемся до этой позиции, сделайте Следующий из узла до этой позиции указывают на новый узел, затем сделайте новый узел предыдущий Укажите на узел перед этой позицией, затем сделайте новый узел Следующий Укажите на узел в этой позиции и, наконец, мы делаем предыдущий узла в этом положении указывают на новый узел.
Мы также проверяем, если данный индекс действителен или нет, а если нет, мы можем поднять ValueError Отказ Кроме того, мы увеличиваем Считать После каждой успешной вставки операции.
6. Способ удаления
Чтобы удалить элемент, который мы должны указывать, где элемент должен быть удален. Если указанный индекс вне диапазона, мы поднимаем ValueError Отказ Если индекс 0, мы снимаем первый элемент, чтобы сделать это, мы делаем голова указать на второй узел. Если голова Это ноль, это означает, что список сейчас пусто, если нет, то мы должны сделать новый голова ‘s предыдущий магазин Нет Отказ
Точно так же, если индекс один меньше, чем размер списка, это означает, что мы должны удалить последний элемент, поэтому мы делаем хвост Укажите на второй последний узел, а затем сделайте новый хвост ‘s Следующий магазин Нет Отказ
Если индекс где-то посередине, мы впервые достигли этой позиции, а затем сделайте Следующий у узла до этой позиции указывают на узел после этого положения, и, наконец, сделайте предыдущий узема после этого положения указывают на узел перед этой позицией.
В удалении мы сделаем только узел недоступным из списка, и фактический процесс удаления его из памяти остается в модуле сборки мусора Python.
7. Метод индекса, размера и отображения.
индекс Метод используется для поиска элемента в списке, мы проходим весь список в зависимости от размера списка и вернуть индекс, если мы найдем цель. Если нет, мы вернемся Нет Отказ
Размер Метод возвращает значение Считать Член класса, который хранит количество элементов в списке.
И Дисплей Метод печатает объект, который вызывает __repr__ Метод и возвращенная строка напечатаны на экран.
Выход
После выполнения нескольких утверждений в классе здесь вывод:
Заключение
В этом руководстве мы изучали вдвойне связанные списки и внедрили его в Python. Мы начали с понимания работы по отдельно связанным списком, то мы обсудили, как вдвойне связанный список отличается. Мы написали код для структуры данных в Python и обсудили, как работает каждый метод, и, наконец, мы рассмотрим вывод кода.
Я надеюсь, что у вас было отличное время обучения, и увидимся в следующем руководстве.