Двозв'язаний список: 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

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

Звільнення виділеної пам'яті після будь-якого видалення є обов'язковим. В іншому випадку пам'ять для видаленого блоку залишатиметься зайнятою протягом усього часу виконання програми, і жодна інша програма не зможе використовувати цей сегмент пам'яті.

Видалити хвіст подвійно зв'язаного списку

Ця операція схожа на видалення голови. Замість голови видаляється хвіст. Щоб ідентифікувати вузол як хвіст, перевірте, чи є наступний вказівник нульовим. Після видалення хвоста пам'ять необхідно звільнити.

Ця операція також відома як видалення зі спини.

Ось кроки, як це зробити:

Крок 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. Попередня Вказівник для головного вузла має значення 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: Кеші Least-Recently-Used використовують подвійно зв'язаний список з хеш-картою для O(1) переміщення на початок та вилучення.
• Історія браузера: Навігація назад і вперед дозволяє переміщатися по зв'язаному списку в будь-якому напрямку.
• Скасування та повторення стеків: Редактори та IDE track версій документів з покажчиками на попередній та наступний.
• Деке: DoubleЧерги з кінцями надсилають та виштовхують дані з обох кінців за час O(1).
• Музичні плейлисти: Попередній та наступний tracКнопки k залежать від вказівників назад та вперед.

Поширені запитання