Struttura dei dati: elenco a doppio collegamento

La lista doppiamente collegata è una variante della lista collegata in cui la navigazione è possibile in entrambi i modi, avanti e indietro facilmente rispetto alla lista singola collegata. Di seguito sono riportati i termini importanti per comprendere il concetto di lista doppiamente collegata.

  • Link - Ogni collegamento di un elenco collegato può memorizzare un dato chiamato elemento.

  • Next - Ogni collegamento di un elenco collegato contiene un collegamento al collegamento successivo denominato Avanti.

  • Prev - Ogni collegamento di un elenco collegato contiene un collegamento al collegamento precedente denominato Prec.

  • LinkedList - Un elenco collegato contiene il collegamento di connessione al primo collegamento denominato Primo e all'ultimo collegamento denominato Ultimo.

Rappresentazione di elenchi doppiamente collegati

Come per l'illustrazione sopra, di seguito sono riportati i punti importanti da considerare.

  • La lista doppiamente collegata contiene un elemento di collegamento chiamato primo e ultimo.

  • Ogni collegamento contiene uno o più campi dati e due campi di collegamento denominati successivo e precedente.

  • Ogni collegamento è collegato al collegamento successivo utilizzando il collegamento successivo.

  • Ogni collegamento è collegato al collegamento precedente utilizzando il collegamento precedente.

  • L'ultimo collegamento porta un collegamento come nullo per contrassegnare la fine dell'elenco.

Operazioni di base

Di seguito sono riportate le operazioni di base supportate da un elenco.

  • Insertion - Aggiunge un elemento all'inizio dell'elenco.

  • Deletion - Elimina un elemento all'inizio della lista.

  • Insert Last - Aggiunge un elemento alla fine dell'elenco.

  • Delete Last - Elimina un elemento dalla fine della lista.

  • Insert After - Aggiunge un elemento dopo un elemento dell'elenco.

  • Delete - Elimina un elemento dalla lista utilizzando il tasto.

  • Display forward - Visualizza l'elenco completo in avanti.

  • Display backward - Visualizza l'elenco completo in modo arretrato.

Operazione di inserimento

Il codice riportato di seguito illustra l'operazione di inserimento all'inizio di un elenco a doppio collegamento.

Esempio

//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;
}

Operazione di cancellazione

Il codice seguente mostra l'operazione di eliminazione all'inizio di un elenco a doppia connessione.

Esempio

//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;
}

Inserimento alla fine di un'operazione

Il codice riportato di seguito mostra l'operazione di inserimento nell'ultima posizione di un elenco a doppia connessione.

Esempio

//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;
}

Per vedere l'implementazione nel linguaggio di programmazione C, fare clic qui .