Dubbellänkad lista: C++, Python (Kodexempel)

Vad är en dubbellänkad lista?

I en dubbellänkad lista har varje nod länkar till både föregående och nästa nod. Varje nod består av tre element: en innehåller data, och ytterligare två är nästa och föregående nods pekare. Dessa två pekare hjälper oss att gå framåt eller bakåt från en viss nod.

Här är den grundläggande strukturen för den dubbellänkade listan.

Varje länkad lista har en huvud- och svansnod. Huvudnoden har ingen "föregående" (föregående pekare) nod, och svansnoden har ingen "nästa" nod.

Här är några viktiga termer för en dubbellänkad lista:

• Föregående: Varje nod är länkad till sin tidigare nod. Den används som en pekare eller länk.
• Nästa: Varje nod är länkad till nästa nod. Den används som en pekare eller länk.
• Data: Detta används för att lagra data i en nod. "Data" kan hålla andra Data struktur innuti. Till exempel kan sträng, ordbok, uppsättning, hashmap, etc lagras i "Data".

Här är den grundläggande strukturen för en enda nod i den dubbellänkade listan:

Operationer av dubbelt länkad lista

Funktionerna för en dubbellänkad lista inkluderar att lägga till och ta bort noder, infoga och ta bort noder och gå igenom den länkade listan från toppen till botten.

Här är listan över operationer som vi kan implementera med den dubbellänkade listan:

• Insättning framtill
• Insättning i svansen eller sista noden
• Insättning efter en nod
• Infogning före en nod
• Radering framifrån
• Borttagning från svansen
• Sök och ta bort en nod
• Traversera huvud till svans
• Traversera svans mot huvud

Vi kommer att se implementeringen och pseudokoden för alla operationer ovan.

Infogning framför dubbellänkad lista

Insättning framför betyder att vi måste skapa en nod i den länkade listan och placera den i början av den länkade listan.

Till exempel finns det en given nod "15". Vi måste lägga till detta i huvudnoden.

Här är två viktiga villkor när du gör den här operationen:

1. Den nya noden kommer att vara huvudnoden om det inte finns någon nod i listan med dubbelt länkade.
2. Om det redan finns en huvudnod kommer det tidigare huvudet att ersättas av den nya noden.

Här är pseudokoden för denna operation:

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

Infogning i slutet av dubbellänkad lista

"Infoga i slutet" betyder att vi skapar en nod i den länkade listan och placerar den i slutet.

För att göra detta kan vi använda två metoder:

• Metod 1: Börja gå från huvudet på den dubbellänkade listan tills "nästa" blir null. Länka sedan den nya noden med "nästa".
• Metod 2: Ta den sista noden i listan med dubbelt länkade. Sedan kommer "nästa" nod för den sista noden att länka till den nya noden. Nu kommer den nya noden att vara svansnoden.

Här är pseudokoden för insättning vid svansnoden:

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

Insättning efter en nod

Låt oss säga att vi har en befintlig dubbellänkad lista som följande:

Vi vill infoga en given nod som kommer att länkas efter noden, som har värdet "12".

Här är stegen för detta:

Steg 1) Gå från huvudet till den sista noden. Kontrollera vilken nod som har värdet "12".

Steg 2) Skapa en ny nod och tilldela den som nästa pekare för nod "12". "Nästa" nod för den nya noden kommer att vara 15.

Här är pseudokoden för att infoga en nod efter en nod i dubbellänkad lista:

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

Infogning före en nod

Denna operation liknar mer "införandet efter en nod". Vi måste söka efter en specifik nods värde för att utföra detta. Sedan kommer vi att skapa en ny nod och infoga den före den sökta noden.

Låt oss säga att vi vill infoga en given nod "15" före noden "12". Så här är stegen för att göra det:

Steg 1) Gå igenom den länkade listan från huvudnoden till svansnoden.

Steg 2) Kontrollera om nästa pekare för den aktuella noden har värdet "12" eller inte.

Steg 3) Infoga den nya noden som "nästa" nod för den aktuella noden.

Här är pseudokoden för att infoga en nod före en nod i dubbel länkad lista:

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

Ta bort huvudet på den dubbellänkade listan

Huvudnoden i den dubbellänkade listan som inte har någon tidigare nod. Så nästa pekare blir den nya huvudnoden om vi vill ta bort huvudnoden. Vi måste också frigöra minnet som upptas av en nod samtidigt som vi tar bort en nod.

Här är stegen för att ta bort huvudnoden:

Steg 1) Tilldela en variabel till den aktuella huvudnoden.

Steg 2) Besök "nästa" nod för den aktuella huvudnoden och gör noden "föregående" (föregående pekare) som ''NULL". Det betyder att vi kopplar bort den andra noden från den första noden.

Steg 3) Frigör det upptagna minnet av den föregående huvudnoden.

Här är pseudokoden för att ta bort huvudet från en dubbellänkad lista:

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

Det är nödvändigt att radera det tilldelade minnet efter att ha utfört någon form av raderingsoperation. Annars kommer minnet för det raderade blocket att vara upptaget under hela programmets körtid. Ingen annan applikation kan använda det minnessegmentet.

Ta bort svansen på den dubbelt länkade listan.

Denna operation är ungefär samma sak som att ta bort huvudet. Här, istället för huvudet, måste vi ta bort svansen. För att identifiera en nod som en svansnod bör vi kontrollera om nästa pekare eller nästa nod är noll eller inte. Efter att ha tagit bort svansen måste vi frigöra minnet.

Denna operation är också känd som "radering från baksidan".

Här är stegen för att göra detta:

Steg 1) Traversera tills svansnoden på den dubbelt länkade listan.

Steg 2) Tilldela en variabel eller pekare till svansnoden.

Steg 3) Gör "nästa" nod som NULL och frigör minnet från svansnoden.

Här är pseudokoden för att ta bort svansnoden:

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

Sök och ta bort en nod från dubbellänkad lista

Denna operation låter oss söka efter en specifik noddata och ta bort den noden. Vi måste utföra en linjär sökning eftersom den länkade listan är en linjär datastruktur. Efter radering måste vi också frigöra minnet.

Här är stegen för att söka och ta bort en nod i den dubbellänkade listan:

Steg 1) Gå igenom den länkade listan från huvudet tills nodens värde är lika med sökobjektet.

Steg 2) Tilldela en variabel "deleteNode" till den matchade noden.

Steg 3) Tilldela den föregående noden för "deleteNode" till nästa nod.

Steg 4) Frigör minnet av "deleteNode"

Här är pseudokoden för att söka och ta bort en nod från en länkad lista:

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

Gå igenom en dubbellänkad lista framifrån

Att gå från huvudnoden och iterera över nästa nod tills vi hittar "NULL". När vi korsar varje nod kan vi skriva ut nodens värde. Här är stegen för att korsa framifrån (riktning framåt):

Steg 1) Tilldela en pekare eller variabel till den aktuella huvudnoden.

Steg 2) Iterera till nästa nod i huvudet tills du får "NULL"

Steg 3) Skriv ut nodens data i varje iteration.

Steg 4) Returnera huvudnoden.

Här är pseudokoden för att gå igenom en dubbellänkad lista framifrån:

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

Här är returen inte obligatorisk. Men det är en bra praxis att returnera huvudnoden efter operationerna.

Gå igenom en dubbelt länkad lista bakifrån

Denna operation är inversen av traversen framifrån. Tillvägagångssättet är detsamma med lite skillnad. Vi måste gå till ändnoden och sedan färdas från ändnoden till den främre noden.

Här är stegen för att gå igenom en dubbellänkad lista från baksidan:

Steg 1) Traversera tills vi når svansnoden.

Steg 2) Från svansnoden kommer vi att korsa tills vi får den föregående noden som "NULL". "Prev" (föregående pekare) kommer att vara noll för huvudnoden

Steg 3) Vid varje iteration kommer vi att skriva ut noddata.

Här är pseudokoden för att korsa bakifrån:

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

Skillnad mellan enkel- och dubbellänkad lista

Den största skillnaden mellan Singly och Double Linked-listan är antalet länkar.

Här är skillnaden mellan noderna i en enkellänkad lista och den dubbellänkade listans nodstruktur:

Fält	Enkelt länkad lista	Dubbelt länkad lista
Structure	Enkelt länkad lista har ett datafält och en länk till nästa nod.	Dubbellänkad lista har ett datafält och två länkar. En för föregående nod och en annan för nästa nod.
Traversal	Den kan bara gå från huvud till svans.	Den kan gå både framåt och bakåt.
Minne	Upptar mindre minne.	Den upptar mer minne än en enskilt länkad lista.
Tillgänglighet	Singly Linked Lists är mindre effektiva eftersom de bara använder en länk till nästa nod. Det finns ingen länk till föregående nod.	Dubbellänkade listor är mer effektiva än enkellänkade listor.

Dubbelt länkad lista in 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);
}

Produktion

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

Dubbelt länkad lista in 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()

Produktion

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

Komplexiteten hos dubbellänkade lista

I allmänhet är tidskomplexitet indelad i tre typer.

De är:

1. Bästa fall
2. Genomsnittligt fall
3. Värsta fall

Tidskomplexitet i bästa fall för dubbellänkad lista:

1. Insättning i huvudet eller svansen kommer att kosta O(1). Eftersom vi inte behöver gå in i den länkade listan. Huvudet och svanspekaren kan ge oss tillgång till huvud- och svansnoden med O(1) tidskomplexitet.
2. Radering vid huvudet eller svansen kommer att kosta O(1).
3. Att söka en nod kommer att ha tidskomplexiteten O(1). Eftersom målnoden kan vara huvudnoden.

Tidskomplexitet i det genomsnittliga fallet för dubbellänkad lista:

1. Insättning vid huvudet eller svansen kommer att ha samma tidskomplexitet som kostnaden O(1).
2. Borttagning vid huvudet eller svansen kommer att ha samma tidskomplexitet som kostnaden O(1).
3. Att söka i en nod kommer att ha tidskomplexiteten O(n). Eftersom sökobjektet kan finnas var som helst mellan den länkade listan. Här är "n" den totala noden som finns i den länkade listan.

Den värsta tänkbara tidskomplexiteten för den dubbellänkade listan kommer att vara densamma som genomsnittsfallet.

Minneskomplexitet för dubbellänkade lista

Minneskomplexitet är O(n), där "n" är det totala antalet noder. När vi implementerar den länkade listan måste vi frigöra minnet som vi använde. Annars, för en större länkad lista, kommer det att orsaka minnesläckor.

Sammanfattning

• En länkad lista är en slags linjär datastruktur, en samling data representerad på ett linjärt sätt.
• En dubbellänkad lista är en typ av länkad lista där en nod har länkar till både föregående och nästa nod.
• Dubbellänkad lista innehåller alla operationer som att lägga till en nod, ta bort en nod, infoga en nod efter eller före en annan nod och gå igenom den länkade listan från topp till svans.
• Dubbellänkad lista har ett datafält och två länkar. En för föregående nod och en annan för nästa nod.
• Komplexiteten av dubbelt länkad lista bästa fall, genomsnittligt fall
• Och i värsta fall.