Estructura de datos - Lista doblemente enlazada
La lista doblemente enlazada (Doubly Linked List) es una extensión de la lista simplemente enlazada. Cada nodo, además de apuntar al siguiente nodo, guarda adicionalmente un puntero al nodo anterior, formando así una estructura encadenada accesible en ambas direcciones.
Estructura y características de la lista doblemente enlazada
struct Node { int data; struct Node* prev; struct Node* next; };
prev apunta al nodo anterior | data almacena los datos | next apunta al nodo siguiente
Ventaja principal: se puede eliminar directamente cualquier nodo (sin necesidad de guardar el predecesor) y admite recorrido bidireccional
Como se muestra en la figura anterior, cada nodo de la lista doblemente enlazada tieneprevynextdos punteros.
En el lenguaje C, la definición del nodo de una lista doblemente enlazada es la siguiente:
Ejemplo
int data; /* Campo de datos */
struct Node* prev; /* Puntero predecesor: apunta al nodo anterior */
struct Node* next; /* Puntero sucesor: apunta al nodo siguiente */
};
En comparación con la lista simplemente enlazada, la mayor ventaja de la lista doblemente enlazada es que se puede acceder directamente a su predecesor y sucesor desde cualquier nodo, lo que hace que la operación de eliminación ya no necesite guardar una referencia adicional al nodo predecesor.
En la lista simplemente enlazada, para eliminar un nodo específico es necesario conocer su nodo predecesor para poder ajustar los punteros. En la lista doblemente enlazada, dado que cada nodo guarda por sí mismo el puntero prev, la operación de eliminación se puede completar directamente.
Operaciones básicas
Operación de inserción
La inserción en una lista doblemente enlazada requiere ajustar simultáneamente los punteros prev/next del nuevo nodo, así como los punteros de su nodo predecesor y sucesor, involucrando en total cuatro ajustes de punteros.
Ejemplo
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
/* Crear un nuevo nodo */
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
/* Insertar un nodo al inicio Pasos: el next del nuevo nodo apunta al nodo cabecera original, y el prev del nodo cabecera original apunta al nuevo nodo */
/* El nuevo nodo se convierte en el nuevo nodo cabecera */
struct Node* insertAtHead(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head != NULL) {
newNode->next = head;
head->prev = newNode;
}
return newNode; /* Insertar un nuevo nodo después de un nodo especificado Se necesitan operar 4 punteros: 1-2: prev y next del nuevo nodo 3: prev del nodo sucesor (si existe) 4: next del nodo predecesor */
}
/* El next del nuevo nodo apunta al sucesor original */
/* El prev del nuevo nodo apunta al predecesor */
/* El prev del sucesor original apunta al nuevo nodo */
/* El next del predecesor apunta al nuevo nodo */
Operación de eliminación
void insertAfter(struct Node* prevNode, int value) {
if (prevNode == NULL) return;
struct Node* newNode = createNode(value);
newNode->next = prevNode->next; Ejemplo
newNode->prev = prevNode; /* Eliminar el nodo especificado (no es necesario conocer el nodo predecesor, esta es la mayor ventaja de la lista doblemente enlazada) Pasos: conectar los nodos anterior y posterior entre sí, omitir el nodo actual y luego liberar el nodo actual */
if (prevNode->next != NULL) {
prevNode->next->prev = newNode; /* Si el nodo eliminado es el nodo cabecera, actualizar el puntero de cabecera */
}
prevNode->next = newNode; /* Hacer que el next del nodo predecesor apunte al nodo sucesor */
}
Operación de eliminación
Ejemplo
La lista doblemente enlazada admite dos formas de recorrido: hacia adelante y hacia atrás.
void deleteNode(struct Node** headRef, struct Node* del) {
if (*headRef == NULL || del == NULL) return;
Ejemplo
if (*headRef == del) {
*headRef = del->next;
}
/* Recorrido hacia adelante: desde head, en la dirección de next */
if (del->prev != NULL) {
del->prev->next = del->next;
}
"Recorrido hacia adelante: "
if (del->next != NULL) {
del->next->prev = del->prev;
}
free(del); /* Recorrido hacia atrás: desde tail, en la dirección de prev Primero es necesario encontrar el nodo final */
}
Operación de recorrido (bidireccional)
/* Desde la cola, regresar a la cabecera en la dirección de prev */
Ejemplo
/* Construir la lista enlazada: 10 <-> 20 <-> 30 */
void traverseForward(struct Node* head) {
printf(/* Salida: Recorrido hacia adelante: 10 20 30 */);
struct Node* cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
/* Salida: Recorrido hacia atrás: 30 20 10 */
Lista doblemente enlazada vs Lista simplemente enlazada
void traverseBackward(struct Node* head) {
if (head == NULL) return;
Dimensión de comparación
struct Node* cur = head;
while (cur->next != NULL) {
cur = cur->next;
}
Lista simplemente enlazada
printf(Lista doblemente enlazada);
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->prev;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
Estructura del nodo
head = insertAtHead(head, 30);
head = insertAtHead(head, 20);
head = insertAtHead(head, 10);
traverseForward(head); Memoria adicional por nodo
traverseBackward(head); 8 bytes (sistema de 64 bits)
return 0;
}
Lista doblemente enlazada vs Lista simplemente enlazada
| Recorrido hacia adelante | Compatible | Compatible |
|---|---|---|
| Recorrido hacia atrás | data + next | data + prev + next |
| No compatible | Compatible | Eliminación de nodo |
| Se necesita conocer el nodo predecesor | No se necesita predecesor, se puede eliminar directamente | Operación de inserción |
| Ajustar 1~2 punteros | Ajustar 4 punteros | Otras extensiones |
| IA pensando... | Estructura de datos – Lista enlazada | Estructura de datos – Lista circular |
| Lista de notas | Haz clic para compartir notas | ¡La nota debe ser una extensión del contenido de este artículo! Puedes hacer clic aquí para enviar un artículo Cómo obtener el código de invitación de registro Antes de compartir notas debes iniciar sesión. |