Двозв'язаний список: C++, Python (Приклад коду)

Що таке двозв’язаний список?

У подвійно зв’язаному списку кожен вузол має посилання як на попередній, так і на наступний вузол. Кожен вузол складається з трьох елементів: один зберігає дані, а ще два є покажчиками на наступний і попередній вузол. Ці два покажчики допомагають нам рухатися вперед або назад від певного вузла.

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

Кожен пов’язаний список має головний і хвіст вузол. Головний вузол не має «попереднього» (попереднього вказівника) вузла, а хвостовий вузол не має «наступного» вузла.

Ось кілька важливих термінів для подвійно зв’язаного списку:

Попередня: Кожен вузол пов’язаний зі своїм попереднім вузлом. Він використовується як вказівник або посилання.
далі: Кожен вузол пов’язаний зі своїм наступним вузлом. Він використовується як вказівник або посилання.
дата: Це використовується для зберігання даних у вузлі. «Дані» можуть містити інші Структури даних всередині нього. Наприклад, рядок, словник, набір, хеш-карта тощо можна зберігати в «Даних».

Ось базова структура одного вузла в подвійно зв’язаному списку:

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

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

Операції з подвійно зв’язаним списком включають додавання та видалення вузлів, вставлення та видалення вузлів, а також обхід зв’язаного списку зверху вниз.

Ось список операцій, які ми можемо реалізувати за допомогою подвійно зв’язаного списку:

Вставка спереду
Вставка в хвіст або останній вузол
Вставка після вузла
Вставка перед вузлом
Видалення спереду
Видалення з хвоста
Пошук і видалення вузла
Перехід голова до хвоста
Поперечний хвіст до голови

Ми побачимо реалізацію та псевдокод для всіх операцій вище.

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

Вставка попереду означає, що нам потрібно створити вузол у зв’язаному списку та розмістити його на початку зв’язаного списку.

Наприклад, є заданий вузол «15». Нам потрібно додати це до головного вузла.

Ось дві важливі умови під час виконання цієї операції:

Новий вузол буде головним, якщо немає жодного вузла в двозв’язаному списку.
Якщо вже є головний вузол, попередній головний вузол буде замінено новим вузлом.

Ось псевдокод для цієї операції:

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:
	then 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
	then List = ListHead.next
  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
	then List = ListHead.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.next
  ListHead.next = NULL
  free memory( Tail )
  return head

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

Ця операція дозволяє нам шукати певні дані вузла та видаляти цей вузол. Нам потрібно виконати лінійний пошук, оскільки пов’язаний список є лінійною структурою даних. Після видалення нам також потрібно звільнити пам'ять.

Ось кроки для пошуку та видалення вузла в подвійно зв’язаному списку:

Крок 1) Переходьте по пов’язаному списку від заголовка, доки значення вузла не зрівняється з елементом пошуку.

Крок 2) Призначте змінну «deleteNode» відповідному вузлу.

Крок 3) Призначте попередній вузол “deleteNode” наступному вузлу.

Крок 4) Звільніть пам'ять «deleteNode»

Ось псевдокод для пошуку та видалення вузла зі зв’язаного списку:

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

Пошук і видалення Operaції — Операція пошуку та видалення

Огляд двозв’язаного списку вперед

Для переходу від головного вузла та переходу до наступного вузла, поки не знайдемо «NULL». Переходячи по кожному вузлу, ми можемо вивести значення вузла. Ось кроки для переміщення спереду (напрямок вперед):

Крок 1) Призначте вказівник або змінну поточному головному вузлу.

Крок 2) Перейдіть до наступного вузла голови, доки не отримаєте «NULL»

Крок 3) Друк даних вузла в кожній ітерації.

Крок 4) Повернути головний вузол.

Ось псевдокод для обходу двозв’язаного списку спереду:

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

Тут повернення не є обов'язковим. Але повернути головний вузол після операції – хороша практика.

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

Ця операція є зворотною ходу спереду. Підхід той самий з невеликою різницею. Ми повинні пройти до кінцевого вузла, а потім пройти від кінцевого вузла до переднього вузла.

Ось кроки для обходу двозв’язаного списку ззаду:

Крок 1) Переходьте, поки не досягнете хвостового вузла.

Крок 2) Від хвостового вузла ми будемо переходити, поки не отримаємо попередній вузол як «NULL». «Попередній» (попередній покажчик) буде нульовим для головного вузла

Крок 3) На кожній ітерації ми будемо друкувати дані вузла.

Ось псевдокод для проходження ззаду:

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

Різниця між однозв’язаним і двозв’язаним списком

Основна відмінність між однозв’язаним і подвійним списком полягає в кількості посилань.

Ось різниця між структурою вузлів однозв’язаного списку та двозв’язаного списку:

Поле	Однозв'язаний список	Двозв’язаний список
Структура	Однозв'язаний список має одне поле даних і одне посилання на наступний вузол.	Двозв’язаний список має одне поле даних і два посилання. Один для попереднього вузла, інший для наступного вузла.
Обхід	Він може проходити лише від голови до хвоста.	Він може рухатися як вперед, так і назад.
пам'ять	Займає менше пам'яті.	Він займає більше пам’яті, ніж однозв’язаний список.
Доступність	Однозв’язані списки менш ефективні, оскільки використовують лише одне посилання на наступний вузол. Немає посилання на попередній вузол.	Двозв’язані списки ефективніші, ніж однозв’язані списки.

Двозв'язаний список в 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);
  }
  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 = new 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 = new node();
  head = listHead;	
  cout<<"Traversal from head:\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 = new node();
  head = (*listHead);
  while(head->next!=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;
  return;
  }
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
Aded 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 head:    10      9       11      5       20      6       7
Deleted Node    7
Traversal from head:    6        20      5       11      9       10
Traversal from head:    10      9       11      5       20      6

Двозв'язаний список в 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.insertFront(val)
    
    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:
      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 is not 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 is not 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.next is not None and temp.data is not searchItem:
      temp = temp.next
    
    if self.head is None or temp is None:
      return

    if self.head.data is 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))
    return

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

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

Загалом часова складність поділяється на три види.

До них відносяться:

Найкращий випадок
Середній випадок
Найгірший випадок

Часова складність у найкращому випадку для двозв’язаного списку:

Вставка в голову або хвіст коштуватиме O(1). Оскільки нам не потрібно переходити всередину пов’язаного списку. Покажчик голови та хвоста може надати нам доступ до головного та хвостового вузлів із складністю часу O(1).
Видалення в голові чи хвості коштуватиме O(1).
Час пошуку вузла складе O(1). Оскільки цільовий вузол може бути головним вузлом.

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

Вставка в голові чи хвості матиме часову складність вартості O(1).
Видалення в голові чи хвості матиме часову складність вартості O(1).
Час пошуку вузла складе O(n). Тому що пошуковий елемент може перебувати будь-де між пов’язаним списком. Тут «n» — загальна кількість вузлів у пов’язаному списку.

Найгірша часова складність подвійнозв’язаного списку буде такою ж, як і середній випадок.

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

Складність пам’яті дорівнює O(n), де «n» — загальна кількість вузлів. Під час реалізації пов’язаного списку ми повинні звільнити пам’ять, яку ми використовували. Інакше, для більшого зв’язаного списку, це призведе до витоку пам’яті.

Підсумки

Зв’язаний список — це свого роду лінійна структура даних, сукупність даних, представлених у лінійному порядку.
Двозв’язаний список — це тип зв’язаного списку, де вузол має зв’язки як з попереднім, так і з наступним вузлом.
Двозв’язаний список містить усі операції, такі як додавання вузла, видалення вузла, вставлення вузла після або перед іншим вузлом і обхід зв’язаного списку від початку до кінця.
Двозв’язаний список має одне поле даних і два посилання. Один для попереднього вузла, інший для наступного вузла.
Складність двозв’язаного списку Найкращий випадок, середній випадок
І найгірший випадок.

Вам може сподобатися:

Що таке двозв’язаний список?

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

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

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

СТАТТІ ПО ТЕМІ

Вставка після вузла

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

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

Видаліть хвіст двозв’язаного списку.

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

Огляд двозв’язаного списку вперед

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

Різниця між однозв’язаним і двозв’язаним списком

Двозв'язаний список в C++

Вихід

Двозв'язаний список в Python

Вихід

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

Підсумки