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 .