Dubbellänkad lista: C++, Python (Code Exempel)

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: ett innehåller data, och de andra två är pekare till nästa och föregående nod. Dessa två pekare hjälper till att förflytta sig framåt eller bakåt från en viss nod.

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

Strukturen för en dubbellänkad lista

Varje länkad lista har en huvud- och en 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 innehålla andra Data struktur inuti den. Till exempel kan strängar, ordböcker, uppsättningar, hashmappar och andra strukturer lagras i datafältet.

Här är den grundläggande strukturen för en enskild nod i den dubbelt länkade listan:

Struktur för en nod i en dubbellänkad lista

Operationer av dubbelt länkad lista

Operationerna i en dubbellänkad lista inkluderar att lägga till, ta bort, infoga och ta bort noder, samt att gå igenom listan uppifrån och ner eller nerifrån och upp.

Här är en lista över operationer som kan implementeras på en dubbellänkad lista:

• Insättning framtill
• Insättning vid 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

Implementeringen och pseudokoden för var och en av dessa operationer följer nedan.

Infogning framför dubbellänkad lista

Insättning framför innebär att skapa en nod i den länkade listan och placera den i början av listan.

Till exempel finns det en given nod 15Den måste läggas till som huvudnod.

Två viktiga villkor gäller när denna operation utförs:

1. Den nya noden blir huvudnoden om den dubbelt länkade listan är tom.
2. Om det redan finns en head-nod ersätts den föregående head-noden med den nya noden.

Här är pseudokoden för den här operationen:

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

Insättning i främre noden

Infogning i slutet av dubbellänkad lista

Infogning i slutet innebär att skapa en nod i den länkade listan och placera den i svansen.

Två metoder utför denna operation:

• Metod 1: Börja gå från början av den dubbellänkade listan tills Nästa blir null. Länka sedan den nya noden med Nästa pekare.
• Metod 2: Ta den sista noden i den dubbelt länkade listan. Sedan, Nästa Pekaren för den sista noden pekar på den nya noden. Den nya noden blir den bakre noden.

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:
    ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead

Infogning i slutet av den länkade listan

Insättning efter en nod

Betrakta en befintlig dubbellänkad lista som följande:

Målet är att infoga en given nod som ska länkas efter noden med värdet 12.

Steg 1) Traversera 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 noden 12. De Nästa Noden för den nya noden blir 15.

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

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

Insättning efter en nod

Insättning före en nod

Den här operationen liknar infogning efter en nod. Ett specifikt nodvärde söks igenom, sedan skapas en ny nod och infogas före den sökta noden.

För att infoga en given nod 15 före noden 12, Följ dessa steg:

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.

Steg 3) Infoga den nya noden som Nästa noden för den aktuella noden.

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

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

Infoga en nod före en nod

Ta bort huvudet på den dubbellänkade listan

Huvudnoden i den dubbelt länkade listan har ingen tidigare nod. Så Nästa pekaren blir den nya huvudnoden när den nuvarande huvudnoden tas bort. Det krävs också att man frigör minnet som upptas av en borttagen 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 noden för den aktuella huvudnoden och gör föregående pekaren NULL. Detta kopplar bort den andra noden från den första noden.

Steg 3) Frigör minnet som upptogs 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

Tar bort huvudnoden

Det krävs att allokerat minne frigörs efter en borttagning. Annars förblir minnet för det borttagna blocket upptaget under hela programmets körtid, och ingen annan applikation kan använda det minnessegmentet.

Ta bort slutet av den dubbelt länkade listan

Denna operation liknar borttagning av huvudet. Istället för huvudet tas svansen bort. För att identifiera en nod som svansen, kontrollera om nästa pekare är null. Efter att svansen har tagits bort måste minnet frigöras.

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

Så här gör du:

Steg 1) Gå igenom tills den dubbelt länkade listans svansnod.

Steg 2) Tilldela en variabel eller pekare till svansnoden.

Steg 3) Ställ in Nästa pekaren till NULL och frigör minnet i 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
  ListHead.prev.next = NULL
  free memory(Tail)
  return head

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

Den här operationen söker efter ett specifikt nodvärde och tar bort noden. En linjär sökning krävs eftersom den länkade listan är en linjär datastruktur. Efter borttagningen måste minnet frigöras.

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

Steg 1) Bläddra igenom den länkade listan från början tills nodvärdet är lika med sökobjektet.

Steg 2) Tilldela en variabel ta bort nod till den matchande noden.

Steg 3) Länka den föregående noden för ta bort nod till nästa nod och ställ in nästa nods föregående pekaren till föregående nod.

Steg 4) Frigör minnet av ta bort nod.

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

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

Sök och radera operation

Gå igenom en dubbellänkad lista framåt

När man går från huvudnoden itereras man över nästa nod tills NULL hittas. Värdet kan skrivas ut medan man går igenom varje nod. Här är stegen för att gå 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 noddata 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 NULL:
    print head.data
    head = head.next
  return ListHead

Returen är inte obligatorisk. Det är dock god praxis att returnera huvudnoden efter operationer.

Gå igenom en dubbellänkad lista bakifrån

Denna operation är den motsatta av traversen framifrån. Tillvägagångssättet är detsamma med en liten skillnad: nå slutpunkten först, gå sedan bakåt till huvudet med hjälp av föregående pekare.

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

Steg 1) Traversera tills svansnoden är nådd.

Steg 2) Från svansnoden, traversera med hjälp av föregående tills föregående nod är NULL. Den föregående pekaren är null för huvudnoden.

Steg 3) Skriv ut noddata vid varje iteration.

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

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

Skillnaden mellan enkel- och dubbellänkad lista

Den största skillnaden mellan en enkellänkad lista och en dubbellänkad lista är antalet länkar som varje nod innehåller.

Här är skillnaden mellan noderna i en enkellänkad lista och en dubbellänkad lista:

Dubbelt länkad lista in C++

Nedan finns en komplett C++ Implementering av en dubbellänkad lista med operationer för infoga, ta bort, sök och bläddra.

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

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

Dubbelt länkad lista in Python

Nedan finns en komplett Python Implementering av en dubbellänkad lista med hjälp av klasser för noder och själva listan.

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

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

Tidskomplexitet delas generellt in i tre typer: bästa tänkbara fall, genomsnittligt fall och värsta tänkbara fall.

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

1. Infogning vid huvud- eller svansnoden kostar O(1) eftersom ingen genomgång inom den länkade listan behövs. Huvud- och svansnoderna ger direkt åtkomst till huvud- och svansnoderna.
2. Borttagning vid början eller slutpunkten kostar O(1).
3. Att söka efter en nod kostar O(1) när målnoden är huvudnoden.

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

1. Insättning vid huvudet eller svansen kostar O(1).
2. Borttagning vid början eller slutpunkten kostar O(1).
3. Att söka efter en nod kostar O(n), eftersom målet kan finnas var som helst i listan. Här, n är det totala antalet noder.

Den värsta tänkbara tidskomplexiteten för den dubbelt länkade listan är densamma som för genomsnittsfallet.

Minneskomplexitet för dubbellänkade lista

Minneskomplexiteten är O(n), där n är det totala antalet noder. När den länkade listan implementeras måste minnet frigöras. Annars orsakar större länkade listor minnesläckor.

Tillämpningar av dubbellänkad lista

Dubbelt länkade listor driver flera verkliga datastrukturer eftersom dubbelriktad traversering förenklar många vanliga operationer.

• LRU-cache: Minst nyligen använda cacher använder en dubbellänkad lista med en hashkarta för O(1) flytt till fronten och utkastning.
• Webbläsarhistorik: Navigering framåt och bakåt leder den länkade listan i endera riktningen.
• Ångra och gör om staplar: Redaktörer och IDE:er track-dokumentversioner med föregående och nästa-pekare.
• Dekv: Double-slutade köer pushar och poppar från båda ändar i O(1)-tid.
• Musikspellistor: Föregående och nästa track-knapparna använder pekare framåt och bakåt.

Vanliga frågor