Datenstruktur - doppelt verknüpfte Liste

Doppelt verknüpfte Liste ist eine Variante der verknüpften Liste, bei der die Navigation auf beide Arten möglich ist, entweder vorwärts oder rückwärts im Vergleich zur einzelnen verknüpften Liste. Im Folgenden sind die wichtigen Begriffe aufgeführt, um das Konzept der doppelt verknüpften Liste zu verstehen.

  • Link - Jeder Link einer verknüpften Liste kann Daten speichern, die als Element bezeichnet werden.

  • Next - Jeder Link einer verknüpften Liste enthält einen Link zum nächsten Link namens Weiter.

  • Prev - Jeder Link einer verknüpften Liste enthält einen Link zum vorherigen Link namens Prev.

  • LinkedList - Eine verknüpfte Liste enthält den Verbindungslink zum ersten Link namens First und zum letzten Link Last.

Doppelt verknüpfte Listendarstellung

Gemäß der obigen Abbildung sind die folgenden wichtigen Punkte zu berücksichtigen.

  • Die doppelt verknüpfte Liste enthält ein Verknüpfungselement mit den Namen first und last.

  • Jede Verbindung enthält ein Datenfeld und zwei Verbindungsfelder, die als next und prev bezeichnet werden.

  • Jeder Link wird über seinen nächsten Link mit seinem nächsten Link verknüpft.

  • Jeder Link ist über seinen vorherigen Link mit seinem vorherigen Link verknüpft.

  • Der letzte Link enthält einen Link als null, um das Ende der Liste zu markieren.

Grundoperationen

Im Folgenden sind die grundlegenden Vorgänge aufgeführt, die von einer Liste unterstützt werden.

  • Insertion - Fügt am Anfang der Liste ein Element hinzu.

  • Deletion - Löscht ein Element am Anfang der Liste.

  • Insert Last - Fügt am Ende der Liste ein Element hinzu.

  • Delete Last - Löscht ein Element am Ende der Liste.

  • Insert After - Fügt ein Element nach einem Element der Liste hinzu.

  • Delete - Löscht mit dem Schlüssel ein Element aus der Liste.

  • Display forward - Zeigt die vollständige Liste vorwärts an.

  • Display backward - Zeigt die vollständige Liste rückwärts an.

Einfügevorgang

Der folgende Code demonstriert den Einfügevorgang am Anfang einer doppelt verknüpften Liste.

Beispiel

//insert link at the first location
void insertFirst(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;
	
   //point first to new first link
   head = link;
}

Löschvorgang

Der folgende Code demonstriert den Löschvorgang am Anfang einer doppelt verknüpften Liste.

Beispiel

//delete first item
struct node* deleteFirst() {

   //save reference to first link
   struct node *tempLink = head;
	
   //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
	
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

Einfügen am Ende einer Operation

Der folgende Code demonstriert den Einfügevorgang an der letzten Position einer doppelt verknüpften Liste.

Beispiel

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

Um die Implementierung in der Programmiersprache C zu sehen, klicken Sie bitte hier .