Двусвязный список: C++, Python (Code Пример)

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

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

Вот базовая структура двусвязного списка.

Структура двусвязного списка

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

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

• Предыдущая: Каждый узел связан со своим предыдущим узлом. Он используется как указатель или ссылка.
• Далее: Каждый узел связан со своим следующим узлом. Он используется как указатель или ссылка.
• Данные: Это используется для хранения данных в узле. Данные могут содержать и другую информацию. Структуры данных внутри него. Например, в поле данных могут храниться строки, словари, множества, хэш-карты и другие структуры.

Вот базовая структура отдельного узла в двусвязном списке:

Структура узла в двусвязном списке

Operaции двусвязного списка

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

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

• Вставка спереди
• Вставка в хвосте или последнем узле
• Вставка после узла
• Вставка перед узлом
• Удаление спереди
• Удаление из хвоста
• Найти и удалить узел
• Траверс голова к хвосту
• Траверс хвостом к голове

Ниже приведено описание реализации и псевдокод для каждой из этих операций.

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

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

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

При выполнении этой операции необходимо соблюдать два важных условия:

1. Новый узел становится головным узлом, если двусвязный список пуст.
2. Если головной узел уже существует, предыдущий головной узел заменяется новым.

Вот псевдокод для этой операции:

function insertAtFront(ListHead, value):
  newNode = Node()
  newNode.value = value
  ListHead.prev = newNode
  newNode.next = ListHead
  newNode.prev = NULL
  return ListHead

Вставка в передний узел

Вставка в конец двусвязного списка

Вставка в конец означает создание узла в связанном списке и размещение его в самом конце.

Для выполнения этой операции используются два метода:

• Метод 1: Начинайте обход с начала двусвязного списка до следующий становится нулевым. Затем свяжите новый узел с следующий указатель.
• Метод 2: Возьмите последний узел двусвязного списка. Затем... следующий Указатель последнего узла указывает на новый узел. Новый узел становится хвостовым узлом.

Вот псевдокод для вставки в хвостовой узел:

function insertAtTail(ListHead, value):
  newNode = Node()
  newNode.value = value
  newNode.next = NULL
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead

Вставка в конец связанного списка

Вставка после узла

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

Цель состоит в том, чтобы вставить заданный узел, который будет связан с узлом, имеющим определенное значение. 12.

Шаг 1) Пройдите от начала до конца узла. Проверьте, в каком узле находится значение. 12.

Шаг 2) Создайте новый узел и назначьте его в качестве указателя на следующий узел. 12, следующий Узел нового узла будет иметь номер 15.

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

function insertAfter(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Вставка после узла

Вставка перед узлом

Эта операция аналогична вставке после узла. Ищется определенное значение узла, затем создается новый узел и вставляется перед искомым узлом.

Вставить заданный узел 15 перед узлом 12, Следуй этим шагам:

Шаг 1) Перейдите по связанному списку от головного узла к хвостовому узлу.

Шаг 2) Проверьте, имеет ли указатель next текущего узла заданное значение. 12.

Шаг 3) Вставьте новый узел в качестве следующий узел текущего узла.

Вот псевдокод для вставки узла перед узлом в двусвязном списке:

function insertBefore(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.next.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Вставка узла перед узлом

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

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

Вот шаги для удаления головного узла:

Шаг 1) Назначьте переменную текущему головному узлу.

Шаг 2) Посетить следующий узел текущего головного узла и сделать Предыдущая Указатель NULL. Это отключает второй узел от первого.

Шаг 3) Освободите память, занятую предыдущим головным узлом.

Вот псевдокод для удаления заголовка из двусвязного списка:

function deleteHead(ListHead):
  PrevHead = ListHead
  ListHead = ListHead.next
  ListHead.prev = NULL
  PrevHead.next = NULL
  free memory(PrevHead)
  return ListHead

Удаление головного узла

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

Удалить хвост двусвязного списка

Эта операция аналогична удалению головы. Вместо головы удаляется хвост. Чтобы идентифицировать узел как хвост, проверьте, равен ли указатель next нулю. После удаления хвоста необходимо освободить память.

Эта операция также известна как удаление с обратной стороны.

Вот шаги, чтобы сделать это:

Шаг 1) Пройдите до конечного узла двусвязного списка.

Шаг 2) Назначьте переменную или указатель хвостовому узлу.

Шаг 3) Установить следующий Указатель на NULL и освобождение памяти хвостового узла.

Вот псевдокод для удаления хвостового узла:

function deleteTail(ListHead):
  head = ListHead
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  Tail = ListHead
  ListHead.prev.next = NULL
  free memory(Tail)
  return head

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

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

Вот шаги для поиска и удаления узла в двусвязном списке:

Шаг 1) Пройдите по связанному списку от начала до конца, пока значение узла не совпадет со значением искомого элемента.

Шаг 2) Присвойте переменную deleteNode к соответствующему узлу.

Шаг 3) Свяжите предыдущий узел deleteNode к следующему узлу и установить следующий узел Предыдущая указатель на предыдущий узел.

Шаг 4) Освободите память о deleteNode.

Вот псевдокод для поиска и удаления узла из связанного списка:

function searchAndDelete(ListHead, searchItem):
  head = ListHead
  while head.value not equals searchItem:
    head = head.next
  deleteNode = head
  head.prev.next = head.next
  if head.next is not NULL:
    head.next.prev = head.prev
  free memory(deleteNode)
  return ListHead

Операция поиска и удаления

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

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

Шаг 1) Назначьте указатель или переменную текущему головному узлу.

Шаг 2) Продолжайте итерацию до следующего узла в головной части, пока не получите NULL.

Шаг 3) Выводите данные узла на каждой итерации.

Шаг 4) Верните головной узел.

Вот псевдокод для обхода двусвязного списка с начала:

function traverseFromFront(ListHead):
  head = ListHead
  while head not equals NULL:
    print head.data
    head = head.next
  return ListHead

Возврат не является обязательным. Однако возврат головного узла после завершения операций — это хорошая практика.

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

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

Вот шаги для обхода двусвязного списка с конца:

Шаг 1) Двигайтесь до достижения хвостового узла.

Шаг 2) Начиная от хвостового узла, выполните траверсирование, используя Предыдущая до тех пор, пока предыдущий узел не станет NULL. Предыдущая Указатель для головного узла равен нулю.

Шаг 3) На каждой итерации выводите данные узла.

Вот псевдокод для обхода с задней стороны:

function traverseFromBack(ListHead):
  head = ListHead
  while head.next is not NULL:
    head = head.next
  tail = head
  while tail is not NULL:
    print tail.value
    tail = tail.prev
  return ListHead

Разница между односвязным и двусвязным списком

Основное различие между односвязным и двусвязным списком заключается в количестве связей, которые содержит каждый узел.

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

Двусвязный список в C++

Ниже представлен полный C++ Реализация двусвязного списка с операциями вставки, удаления, поиска и обхода.

#include<iostream>
using namespace std;
struct node{
  int data;
  struct node *next;
  struct node *prev;
};
void insertFront(node* &listHead, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  if(listHead != NULL){
    listHead->prev = newNode;
    newNode->next = listHead;
  }
  listHead = newNode;
  cout<<"Added "<<value<<" at the front"<<endl;
}
void insertEnd(node* &listHead, int value){
  if(listHead == NULL){
    insertFront(listHead, value);
    return;
  }
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL){
    head = head->next;
  }
  head->next = newNode;
  newNode->prev = head;
  cout<<"Added "<<value<<" at the end"<<endl;
}
void insertAfter(node* &listHead, int searchValue, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL && head->data != searchValue){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  newNode->prev = head;
  if(newNode->next != NULL){
    newNode->next->prev = newNode;
  }
  cout<<"Inserted "<<value<<" after node "<<searchValue<<endl;
}
void insertBefore(node* &listHead, int searchValue, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL && head->next->data != searchValue){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  newNode->prev = head;
  if(newNode->next != NULL){
    newNode->next->prev = newNode;
  }
  cout<<"Inserted "<<value<<" before node "<<searchValue<<endl;
}
void traverseFromFront(node *listHead){
  node* head = listHead;
  cout<<"Traversal from head:\t";
  while(head != NULL){
    cout<<head->data<<"\t";
    head = head->next;
  }
  cout<<endl;
}
void traverseFromEnd(node *listHead){
  node* head = listHead;
  cout<<"Traversal from tail:\t";
  while(head->next != NULL){
    head = head->next;
  }
  node *tail = head;
  while(tail != NULL){
    cout<<tail->data<<"\t";
    tail = tail->prev;
  }
  cout<<endl;
}
void searchAndDelete(node **listHead, int searchItem){
  node* head = (*listHead);
  while(head != NULL && head->data != searchItem){
    head = head->next;
  }
  if(*listHead == NULL || head == NULL) return;
  if((*listHead)->data == head->data){
    *listHead = head->next;
  }
  if(head->next != NULL){
    head->next->prev = head->prev;
  }
  if(head->prev != NULL){
    head->prev->next = head->next;
  }
  free(head);
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
int main(){
  node *head = NULL;
  insertFront(head, 5);
  insertFront(head, 6);
  insertFront(head, 7);
  insertEnd(head, 9);
  insertEnd(head, 10);
  insertAfter(head, 5, 11);
  insertBefore(head, 5, 20);
  traverseFromFront(head);
  traverseFromEnd(head);
  searchAndDelete(&head, 7);
  traverseFromFront(head);
  traverseFromEnd(head);
}

Результат

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversal from head:    7  6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6  7
Deleted Node    7
Traversal from head:    6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6

Двусвязный список в Python

Ниже представлен полный Python Реализация двусвязного списка с использованием классов для узлов и самого списка.

class Node:
  def __init__(self, data=None, prev=None, next=None):
    self.data = data
    self.next = next
    self.prev = prev
class DoublyLinkedList:
  def __init__(self):
    self.head = None
  def insertFront(self, val):
    newNode = Node(data=val)
    newNode.next = self.head
    if self.head is not None:
      self.head.prev = newNode
    self.head = newNode
    print("Added {} at the front".format(val))
  def insertEnd(self, val):
    newNode = Node(data=val)
    if self.head is None:
      self.head = newNode
      print("Added {} at the end".format(val))
      return
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    newNode.prev = temp
    print("Added {} at the end".format(val))
  def traverseFromFront(self):
    temp = self.head
    print("Traversing from head:\t", end="")
    while temp is not None:
      print("{}\t".format(temp.data), end="")
      temp = temp.next
    print()
  def traverseFromEnd(self):
    temp = self.head
    print("Traversing from tail:\t", end="")
    while temp.next is not None:
      temp = temp.next
    tail = temp
    while tail is not None:
      print("{}\t".format(tail.data), end="")
      tail = tail.prev
    print()
  def insertAfter(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp
    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} after node {}".format(value, searchItem))
  def insertBefore(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp
    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} before node {}".format(value, searchItem))
  def searchAndDelete(self, searchItem):
    temp = self.head
    while temp is not None and temp.data != searchItem:
      temp = temp.next
    if self.head is None or temp is None:
      return
    if self.head.data == temp.data:
      self.head = temp.next
    if temp.next is not None:
      temp.next.prev = temp.prev
    if temp.prev is not None:
      temp.prev.next = temp.next
    print("Deleted Node\t{}".format(searchItem))
doublyLinkedList = DoublyLinkedList()
doublyLinkedList.insertFront(5)
doublyLinkedList.insertFront(6)
doublyLinkedList.insertFront(7)
doublyLinkedList.insertEnd(9)
doublyLinkedList.insertEnd(10)
doublyLinkedList.insertAfter(5, 11)
doublyLinkedList.insertBefore(5, 20)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
doublyLinkedList.searchAndDelete(7)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()

Результат

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversing from head:   7  6  20  5  11  9  10
Traversing from tail:   10  9  11  5  20  6  7
Deleted Node    7
Traversing from head:   6  20  5  11  9  10
Traversing from tail:   10  9  11  5  20  6

Сложность двусвязного списка

Временная сложность обычно делится на три типа: наилучший случай, средний случай и наихудший случай.

Временная сложность в лучшем случае для двусвязного списка:

1. Вставка в начало или конец списка стоит O(1), поскольку обход внутри связанного списка не требуется. Указатели на начало и конец списка обеспечивают прямой доступ к узлам начала и конца списка.
2. Удаление в начале или в конце обходится в O(1).
3. Поиск узла обходится за O(1), если целевой узел является головным узлом.

Временная сложность в среднем случае для двусвязного списка:

1. Вставка в начало или конец стоит O(1).
2. Удаление в начале или в конце обходится в O(1).
3. Поиск узла обходится за O(n), поскольку целевой узел может находиться в любом месте списка. Здесь, n общее количество узлов.

Наихудшая временная сложность двусвязного списка совпадает со средней.

Сложность памяти двусвязного списка

Сложность по памяти составляет O(n), где n — это общее количество узлов. При реализации связанного списка необходимо освободить память. В противном случае, большие связанные списки приводят к утечкам памяти.

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

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

• LRU-кэш: В кэшах с наименьшим количеством недавно использованных элементов используется двусвязный список с хеш-картой для перемещения в начало списка и вытеснения за время O(1).
• История браузера: Навигация «Назад» и «Вперед» позволяет перемещаться по связанному списку в любом направлении.
• Стеки отмены и повтора: Редакторы и интегрированные среды разработки track версий документа с указателями prev и next.
• Deque: DoubleВ очередях с двумя концами операции добавления и извлечения предметов выполняются за время O(1).
• Музыкальные плейлисты: Предыдущий и следующий tracКнопки k используют указатели назад и вперед.

Часто задаваемые вопросы (FAQ)