Dvojitě propojený seznam: C++, Python (Code Příklad)

Co je to dvojitě propojený seznam?

V dvojitě propojeném seznamu má každý uzel odkazy na předchozí i následující uzel. Každý uzel se skládá ze tří prvků: jeden obsahuje data a další dva jsou ukazatele na další a předchozí uzel. Tyto dva ukazatele pomáhají s pohybem vpřed nebo vzad od konkrétního uzlu.

Zde je základní struktura dvojitě propojeného seznamu.

Struktura dvojitě propojeného seznamu

Každý propojený seznam má úvodní a koncový uzel. Úvodní uzel nemá předchozí (předchozí ukazatel) uzel a koncový uzel nemá další uzel.

Zde jsou některé důležité pojmy pro dvojitě propojený seznam:

• Předchozí: Každý uzel je spojen se svým předchozím uzlem. Používá se jako ukazatel nebo odkaz.
• Další: Každý uzel je spojen se svým dalším uzlem. Používá se jako ukazatel nebo odkaz.
• Datum: Toto se používá k ukládání dat v uzlu. Data mohou obsahovat další Datové struktury uvnitř něj. Například řetězec, slovník, sada, hashmap a další struktury lze uložit do datového pole.

Zde je základní struktura jednoho uzlu v dvojitě propojeném seznamu:

Struktura uzlu ve dvojitě propojeném seznamu

Operadvojím propojením seznamu

Operace dvojitě propojeného seznamu zahrnují přidávání, mazání, vkládání a odebírání uzlů, stejně jako procházení seznamu shora dolů nebo zdola nahoru.

Zde je seznam operací, které lze implementovat na dvojitě propojeném seznamu:

• Vložení vpředu
• Vložení na konci nebo v posledním uzlu
• Vložení za uzel
• Vložení před uzel
• Smazání zepředu
• Vymazání z ocasu
• Vyhledejte a odstraňte uzel
• Traverz od hlavy k ocasu
• Traverz ocasu k hlavě

Implementace a pseudokód pro každou z těchto operací jsou uvedeny níže.

Vložení před dvojitě propojený seznam

Vložení na začátek znamená vytvoření uzlu v propojeném seznamu a jeho umístění na začátek seznamu.

Například existuje daný uzel 15Je třeba jej přidat jako hlavní uzel.

Při provádění této operace platí dvě důležité podmínky:

1. Nový uzel se stane hlavním uzlem, pokud je dvojitě propojený seznam prázdný.
2. Pokud již existuje hlavní uzel, předchozí hlavní uzel je nahrazen novým uzlem.

Zde je pseudokód pro tuto operaci:

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

Vložení do předního uzlu

Vložení na konec dvojitě propojeného seznamu

Vložení na konec znamená vytvoření uzlu v propojeném seznamu a jeho umístění na konec.

Tuto operaci provádějí dvě metody:

• Metoda 1: Začněte procházet od začátku dvojitě propojeného seznamu, dokud další se stane null. Poté propojte nový uzel s další ukazatel.
• Metoda 2: Vezměte poslední uzel dvojitě propojeného seznamu. Pak další Ukazatel posledního uzlu ukazuje na nový uzel. Nový uzel se stává koncovým uzlem.

Zde je pseudokód pro vložení na konci uzlu:

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

Vložení na konec propojeného seznamu

Vložení za uzel

Uvažujme existující dvojitě propojený seznam, jako je tento:

Cílem je vložit daný uzel, který bude propojen za uzel s hodnotou 12.

Krok 1) Projděte od začátku k poslednímu uzlu. Zkontrolujte, který uzel má hodnotu 12.

Krok 2) Vytvořte nový uzel a přiřaďte mu jako další ukazatel uzlu 12, další Uzel nového uzlu bude 15.

Zde je pseudokód pro vložení uzlu za uzel v dvojitě propojeném seznamu:

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

Vložení za uzel

Vložení před uzel

Tato operace je podobná vkládání za uzel. Vyhledá se specifická hodnota uzlu, poté se vytvoří nový uzel a vloží se před hledaný uzel.

Vložení daného uzlu 15 před uzlem 12, Následuj tyto kroky:

Krok 1) Projděte propojený seznam od hlavního uzlu k koncovému uzlu.

Krok 2) Zkontroluje, zda má další ukazatel aktuálního uzlu hodnotu 12.

Krok 3) Vložte nový uzel jako další uzel aktuálního uzlu.

Zde je pseudokód pro vložení uzlu před uzel v dvojitě propojeném seznamu:

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

Vložení uzlu před uzel

Odstranění hlavičky dvojitě propojeného seznamu

Hlavní uzel v dvojitě propojeném seznamu nemá žádný předchozí uzel. Takže další Ukazatel se stane novým hlavním uzlem, když je aktuální hlava odstraněna. Je také nutné uvolnit paměť obsazenou odstraněným uzlem.

Zde jsou kroky pro odstranění hlavního uzlu:

Krok 1) Přiřaďte proměnnou aktuálnímu hlavnímu uzlu.

Krok 2) Navštivte další uzlu aktuálního hlavního uzlu a proveďte předchozí ukazatel NULL. Tím se odpojí druhý uzel od prvního uzlu.

Krok 3) Uvolněte paměť obsazenou předchozím hlavním uzlem.

Zde je pseudokód pro odstranění hlavičky z dvojitě propojeného seznamu:

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

Odstranění hlavního uzlu

Po jakémkoli smazání je nutné uvolnit alokovanou paměť. Jinak zůstane paměť pro smazaný blok obsazená po celou dobu běhu programu a žádná jiná aplikace nemůže tento segment paměti použít.

Odstranění konce dvojitě propojeného seznamu

Tato operace je podobná odstranění hlavičky. Místo hlavičky se odstraní konec. Pro identifikaci uzlu jako konce je nutné zkontrolovat, zda je další ukazatel nulový. Po odstranění konce je nutné uvolnit paměť.

Tato operace je také známá jako smazání zezadu.

Zde jsou kroky, jak to provést:

Krok 1) Procházejte až k koncovému uzlu dvojitě propojeného seznamu.

Krok 2) Přiřaďte proměnnou nebo ukazatel koncovému uzlu.

Krok 3) Nastav další ukazatel na NULL a uvolní paměť koncového uzlu.

Zde je pseudokód pro odstranění koncového uzlu:

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

Vyhledání a odstranění uzlu z dvojitě propojeného seznamu

Tato operace vyhledává konkrétní hodnotu uzlu a tento uzel odstraňuje. Lineární vyhledávání je vyžadováno, protože propojený seznam je lineární datová struktura. Po odstranění musí být paměť uvolněna.

Zde jsou kroky pro vyhledání a odstranění uzlu v dvojitě propojeném seznamu:

Krok 1) Procházejte propojeným seznamem od začátku, dokud se hodnota uzlu nerovná hledané položce.

Krok 2) Přiřadit proměnnou deleteNode k odpovídajícímu uzlu.

Krok 3) Propojit předchozí uzel deleteNode k jeho dalšímu uzlu a nastavit další uzel předchozí ukazatel na předchozí uzel.

Krok 4) Osvoboďte paměť deleteNode.

Zde je pseudokód pro vyhledávání a mazání uzlu ze spojitého seznamu:

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

Operace vyhledávání a mazání

Procházení dvojitě propojeného seznamu zpředu

Procházení od hlavního uzlu iteruje přes další uzel, dokud není nalezena hodnota NULL. Při procházení každého uzlu lze vytisknout hodnotu. Zde jsou kroky pro procházení vpřed:

Krok 1) Přiřaďte ukazatel nebo proměnnou aktuálnímu hlavnímu uzlu.

Krok 2) Iterujte k dalšímu uzlu v záhlaví, dokud nedosáhnete hodnoty NULL.

Krok 3) Vytiskněte data uzlu v každé iteraci.

Krok 4) Vraťte hlavový uzel.

Zde je pseudokód pro procházení dvojitě propojeného seznamu zepředu:

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

Návrat není povinný. Vrácení hlavního uzlu po operacích je však dobrým postupem.

Procházení dvojitě propojeným seznamem odzadu

Tato operace je inverzní k traverzu zepředu. Přístup je stejný s jedním malým rozdílem: nejprve dosáhněte koncového uzlu a poté se vraťte zpět k vrcholu pomocí předchozí ukazatel.

Zde jsou kroky pro procházení dvojitě propojeným seznamem zezadu:

Krok 1) Pohybujte se, dokud nedosáhnete koncového uzlu.

Krok 2) Z koncového uzlu proveďte traverz pomocí předchozí dokud předchozí uzel nedosáhne hodnoty NULL. předchozí Ukazatel pro hlavní uzel je null.

Krok 3) V každé iteraci vytiskněte data uzlu.

Zde je pseudokód pro procházení zezadu:

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

Rozdíl mezi jednoduchou a dvojitou vazbou seznamu

Hlavní rozdíl mezi jednoduchou a dvojitou vazbou seznamu je počet vazeb, které každý uzel obsahuje.

Zde je rozdíl mezi uzly jednoduše propojeného seznamu a dvojitě propojeného seznamu:

Dvojitě propojený seznam v C++

Níže je uveden kompletní C++ Implementace dvojitě propojeného seznamu s operacemi vkládání, mazání, vyhledávání a procházení.

#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);
}

Výstup

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

Dvojitě propojený seznam v Python

Níže je uveden kompletní Python implementace dvojitě propojeného seznamu s využitím tříd pro uzly a samotného seznamu.

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()

Výstup

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

Složitost dvojitě propojeného seznamu

Časová složitost se obecně dělí na tři typy: nejlepší případ, průměrný případ a nejhorší případ.

Časová složitost v nejlepším případě pro Double Linked List:

1. Vložení na začátku nebo na konci seznamu stojí O(1), protože není nutné procházet seznamem. Ukazatele na začátku a na konci seznamu umožňují přímý přístup k těmto uzlům.
2. Vymazání na začátku nebo na konci řetězce stojí O(1).
3. Hledání uzlu stojí O(1), pokud je cílový uzel hlavním uzlem.

Časová složitost v průměrném případě pro Double Linked List:

1. Vložení na začátku nebo na konci stojí O(1).
2. Vymazání na začátku nebo na konci řetězce stojí O(1).
3. Hledání uzlu stojí O(n), protože cíl se může nacházet kdekoli v seznamu. Zde, n je celkový počet uzlů.

Časová složitost dvojitě propojeného seznamu v nejhorším případě je stejná jako v průměrném případě.

Paměťová složitost Double Linked List

Složitost paměti je O(n), kde n je celkový počet uzlů. Při implementaci propojeného seznamu je nutné uvolnit paměť. Jinak větší propojené seznamy způsobují úniky paměti.

Aplikace dvojitě propojených seznamů

Dvojitě propojené seznamy jsou základem několika reálných datových struktur, protože obousměrné procházení zjednodušuje mnoho běžných operací.

• Mezipaměť LRU: Mezipaměti Least-Recently-Used používají dvojitě propojený seznam s hash mapou pro přesun na začátek a vyřazení O(1).
• Historie prohlížeče: Navigace zpět a vpřed prochází propojeným seznamem v obou směrech.
• Vrácení a opakování akcí v hromádkách: Editory a IDE track verzí dokumentů s ukazateli na předchozí a další.
• Deque: DoubleFronty s koncovými konci se v čase O(1) odesílají a odesílají z obou konců.
• Hudební playlisty: Předchozí a další tracTlačítka k se spoléhají na ukazatele vpřed a vzad.

Nejčastější dotazy