Estructura de datos: lista doblemente vinculada
La lista doblemente enlazada es una variación de la lista enlazada en la que la navegación es posible en ambas formas, ya sea hacia adelante o hacia atrás fácilmente en comparación con la lista enlazada única. A continuación se presentan los términos importantes para comprender el concepto de lista doblemente enlazada.
Link - Cada enlace de una lista enlazada puede almacenar un dato llamado elemento.
Next - Cada enlace de una lista enlazada contiene un enlace al siguiente enlace llamado Siguiente.
Prev - Cada enlace de una lista enlazada contiene un enlace al enlace anterior llamado Prev.
LinkedList - Una lista vinculada contiene el enlace de conexión al primer enlace llamado Primero y al último enlace llamado Último.
Representación de lista doblemente enlazada
Según la ilustración anterior, los siguientes son los puntos importantes que deben considerarse.
La lista doblemente enlazada contiene un elemento de enlace llamado primero y último.
Cada enlace lleva un campo de datos y dos campos de enlace llamados siguiente y anterior.
Cada enlace está vinculado con su siguiente enlace utilizando su siguiente enlace.
Cada enlace está vinculado con su enlace anterior utilizando su enlace anterior.
El último enlace lleva un enlace como nulo para marcar el final de la lista.
Operaciones básicas
A continuación se muestran las operaciones básicas respaldadas por una lista.
Insertion - Agrega un elemento al principio de la lista.
Deletion - Elimina un elemento al principio de la lista.
Insert Last - Agrega un elemento al final de la lista.
Delete Last - Elimina un elemento del final de la lista.
Insert After - Agrega un elemento después de un elemento de la lista.
Delete - Elimina un elemento de la lista con la tecla.
Display forward - Muestra la lista completa de forma progresiva.
Display backward - Muestra la lista completa al revés.
Operación de inserción
El siguiente código demuestra la operación de inserción al comienzo de una lista doblemente enlazada.
Ejemplo
//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;
}Operación de eliminación
El siguiente código demuestra la operación de eliminación al comienzo de una lista doblemente vinculada.
Ejemplo
//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;
}Inserción al final de una operación
El siguiente código demuestra la operación de inserción en la última posición de una lista doblemente enlazada.
Ejemplo
//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;
}Para ver la implementación en lenguaje de programación C, haga clic aquí .