Двойно свързан списък: 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: Започнете да обхождате от началото на двойносвързания списък, докато до става null. След това свържете новия възел с до указател.
• Метод 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) Проверете дали следващият указател на текущия възел има стойността 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

Изтриване на главния възел

Необходимо е освобождаване на разпределена памет след всяко изтриване. В противен случай паметта за изтрития блок остава заета през цялото време на изпълнение на програмата и никое друго приложение не може да използва този сегмент от паметта.

Изтриване на опашката на двойносвързания списък

Тази операция е подобна на изтриването на главата. Вместо главата се премахва опашката. За да се идентифицира възел като опашка, се проверява дали следващият указател е null. След изтриване на опашката, паметта трябва да се освободи.

Тази операция е известна още като изтриване отзад.

Ето стъпките за това:

Стъпка 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) Присвояване на променлива изтриване на възел към съответстващия възел.

Стъпка 3) Свържете предишния възел на изтриване на възел към следващия си възел и зададе на следващия възел предишна указател към предишния възел.

Стъпка 4) Освободете паметта на изтриване на възел.

Ето псевдокода за търсене и изтриване на възел от свързан списък:

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. предишна Показателят е 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) преместване напред и премахване.
• История на браузъра: Навигацията напред и назад превърта свързания списък в двете посоки.
• Отмяна и повторение на стекове: Редактори и IDE track версии на документи с указатели „предишен“ и „следващ“.
• Деке: DoubleОпашките с край се изпращат и изскачат от двата края за време O(1).
• Музикални плейлисти: Предишно и следващо tracБутоните k разчитат на стрелки назад и напред.

Въпроси и Отговори