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

Co je to dvojitě propojený seznam?

Ve 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 dalšího a předchozího uzlu. Tyto dva ukazatele nám pomáhají jít vpřed nebo vzad od určitého uzlu.

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

Každý propojený seznam má hlavní a koncový uzel. Uzel Head nemá žádný uzel „předchozí“ (předchozí ukazatel) a koncový uzel nemá žádný uzel „další“.

Zde je několik důležitých výrazů pro seznam s dvojitým odkazem:

• 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: To se používá k ukládání dat v uzlu. „Data“ mohou obsahovat jiné Datové struktury uvnitř toho. Do „Data“ lze uložit například řetězec, slovník, sadu, hashmap atd.

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

Operadvojím propojením seznamu

Operace dvojitě propojeného seznamu zahrnují přidávání a odstraňování uzlů, vkládání a odebírání uzlů a procházení propojeného seznamu shora dolů.

Zde je seznam operací, které můžeme implementovat pomocí dvojitě propojeného seznamu:

• Vložení vpředu
• Vložení do ocasu nebo posledního 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ě

Uvidíme implementaci a pseudokód pro všechny operace výše.

Vložení před seznam Double Linked List

Vložení vpřed znamená, že musíme vytvořit uzel v propojeném seznamu a umístit jej na začátek propojeného seznamu.

Například existuje daný uzel „15“. Musíme to přidat do hlavního uzlu.

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

1. Nový uzel bude hlavním uzlem, pokud v seznamu s dvojitým propojením žádný uzel není.
2. Pokud již existuje hlavní uzel, předchozí uzel bude 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í na konec dvojitě propojeného seznamu

„Vložení na konec“ znamená, že vytvoříme uzel v propojeném seznamu a umístíme jej na konec.

K tomu můžeme použít dvě metody:

• Metoda 1: Začněte procházet od začátku seznamu dvojitě propojených položek, dokud se „další“ nestane nulovým. Poté propojte nový uzel s „dalším“.
• Metoda 2: Vezměte poslední uzel seznamu Dvojitě propojený. Potom se „další“ uzel posledního uzlu propojí s novým uzlem. Nyní bude nový uzel koncový uzel.

Zde je pseudokód pro vložení do koncového uzlu:

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

Vložení za uzel

Řekněme, že máme existující dvojitě propojený seznam, jako je tento:

Chceme vložit daný uzel, který bude připojen za uzel, který má hodnotu „12“.

Zde je postup:

Krok 1) Traverz od hlavy k poslednímu uzlu. Zkontrolujte, který uzel má hodnotu „12“.

Krok 2) Vytvořte nový uzel a přiřaďte jej jako další ukazatel uzlu „12“. „Další“ uzel nového uzlu bude 15.

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

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

Vložení před uzel

Tato operace je více podobná „vložení za uzel“. Abychom to provedli, musíme vyhledat hodnotu konkrétního uzlu. Poté vytvoříme nový uzel a vložíme jej před hledaný uzel.

Řekněme, že chceme vložit daný uzel „15“ před uzel „12“. Zde jsou kroky, jak to udělat:

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

Krok 2) Zkontrolujte, zda má další ukazatel aktuálního uzlu hodnotu „12“ nebo ne.

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

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

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

Odstraňte hlavičku dvojitě propojeného seznamu

Hlavní uzel ve dvojitě propojeném seznamu, který nemá žádný předchozí uzel. Pokud tedy chceme hlavní uzel odstranit, dalším ukazatelem bude nový hlavní uzel. Při mazání uzlu také potřebujeme uvolnit paměť obsazenou 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ší“ uzel aktuálního hlavního uzlu a uzel „předchozí“ (předchozí ukazatel) nastavte na „NULL“. To znamená, že odpojujeme druhý uzel od prvního uzlu.

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

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

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

Po provedení jakékoli operace odstranění je nutné alokovanou paměť smazat. Jinak po celou dobu běhu programu zůstane paměť pro smazaný blok obsazená. Žádná jiná aplikace nemůže tento segment paměti použít.

Odstraňte konec dvojitě propojeného seznamu.

Tato operace je něco podobného jako vymazání hlavy. Zde místo hlavy musíme odstranit ocas. Abychom identifikovali uzel jako koncový uzel, měli bychom zkontrolovat, zda je další ukazatel nebo další uzel prázdný nebo ne. Po smazání ocasu potřebujeme uvolnit paměť.

Tato operace je také známá jako „vymazání zezadu“.

Postupujte takto:

Krok 1) Projděte až do koncového uzlu dvojitě propojeného seznamu.

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

Krok 3) Udělejte „další“ uzel jako NULL a uvolněte paměť koncového uzlu.

Zde je pseudokód pro smazání koncového uzlu:

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

Vyhledejte a odstraňte uzel ze seznamu s dvojitým propojením

Tato operace nám umožňuje vyhledat konkrétní data uzlu a tento uzel odstranit. Musíme provést lineární vyhledávání, protože propojený seznam je lineární datová struktura. Po smazání musíme také uvolnit paměť.

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

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

Krok 2) Přiřaďte proměnnou „deleteNode“ k odpovídajícímu uzlu.

Krok 3) Přiřaďte předchozí uzel „deleteNode“ dalšímu uzlu.

Krok 4) Uvolněte paměť „deleteNode“

Zde je pseudokód pro vyhledávání a smazání uzlu z propojeného seznamu:

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

Procházet dvojitě propojený seznam odpředu

Procházet z hlavního uzlu a iterovat přes další uzel, dokud nenajdeme „NULL“. Při procházení každého uzlu můžeme vytisknout hodnotu uzlu. Zde jsou kroky pro přecházení zepředu (směr 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 hlavy, dokud nedostanete „NULL“

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

Krok 4) Vraťte hlavový uzel.

Zde je pseudokód pro procházení seznamu s dvojitým odkazem zepředu:

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

Zde není vrácení povinné. Je ale dobrým zvykem po operacích hlavovou uzlinu vrátit.

Procházejte dvojitě propojený seznam zezadu

Tato operace je inverzní k traverzu zepředu. Přístup je stejný s malým rozdílem. Musíme traverzovat ke koncovému uzlu a pak traverzovat z koncového uzlu k přednímu uzlu.

Zde jsou kroky pro procházení dvojitě propojeného seznamu zezadu:

Krok 1) Traverzujte, dokud nedosáhneme ocasního uzlu.

Krok 2) Z koncového uzlu budeme procházet, dokud nezískáme předchozí uzel jako „NULL“. „Předchozí“ (předchozí ukazatel) bude mít pro hlavní uzel hodnotu null

Krok 3) Při každé iteraci vytiskneme data uzlu.

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

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

Rozdíl mezi Jednotlivě a Dvojitě propojeným seznamem

Hlavním rozdílem mezi seznamem Singly a Double Linked je počet odkazů.

Zde je rozdíl mezi uzly Jednotně propojeného seznamu a strukturou uzlů Dvojitě propojeného seznamu:

Pole	Jednotlivě propojený seznam	Dvojitě propojený seznam
Struktura	Jednotlivě propojený seznam má jedno datové pole a jeden odkaz na další uzel.	Dvojitě propojený seznam má jedno datové pole a dva odkazy. Jeden pro předchozí uzel a druhý pro další uzel.
Traverz	Může přecházet pouze od hlavy k ocasu.	Může se pohybovat vpřed i vzad.
Memory	Zabírá méně paměti.	Zabírá více paměti než jednotlivě propojený seznam.
Přístupnost	Jednotlivě propojené seznamy jsou méně efektivní, protože používají pouze jeden odkaz na další uzel. Neexistuje žádný odkaz na předchozí uzel.	Dvojitě propojené seznamy jsou efektivnější než jednotlivé propojené seznamy.

Dvojitě propojený seznam v 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);
}

Výstup

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

Dvojitě propojený seznam v 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()

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.

Jedná se o:

1. Nejlepší případ
2. Průměrný případ
3. Nejhorší případ

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

1. Vložení do hlavy nebo paty bude stát O(1). Protože nepotřebujeme procházet uvnitř propojeného seznamu. Ukazatel hlavy a ocasu nám může poskytnout přístup k uzlu hlavy a ocasu s časovou složitostí O(1).
2. Smazání hlavy nebo paty bude stát O(1).
3. Hledání uzlu bude mít časovou složitost O(1). Protože cílový uzel může být hlavní uzel.

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

1. Vložení na hlavu nebo konec bude mít časovou složitost nákladů O(1).
2. Vypuštění na začátku nebo na konci bude mít časovou složitost nákladů O(1).
3. Hledání uzlu bude mít časovou složitost O(n). Protože hledaná položka může být umístěna kdekoli mezi propojeným seznamem. Zde je „n“ celkový uzel přítomný v propojeném seznamu.

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

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 musíme uvolnit paměť, kterou jsme použili. V opačném případě u většího propojeného seznamu způsobí úniky paměti.

Shrnutí

• Propojený seznam je druh lineární datové struktury, kolekce dat reprezentovaných lineárním způsobem.
• Dvojitě propojený seznam je typ propojeného seznamu, kde má uzel propojení s předchozím i následujícím uzlem.
• Dvojitě propojený seznam obsahuje všechny operace, jako je přidání uzlu, odstranění uzlu, vložení uzlu za nebo před jiný uzel a procházení propojeným seznamem od začátku k konci.
• Dvojitě propojený seznam má jedno datové pole a dva odkazy. Jeden pro předchozí uzel a druhý pro další uzel.
• Složitost dvojitě propojeného seznamu Nejlepší případ, průměrný případ
• A nejhorší případ.