Como Hacer Una Lista Doblemente Enlazada En C++

¡Hola, futuros programadores! Vamos a sumergirnos en el fascinante mundo de las Listas Doblemente Enlazadas en C++. No te preocupes, lo haremos paso a paso.

¿Qué es una Lista Enlazada?

Imagina una cadena de papel. Cada eslabón (un trozo de papel) contiene información y está conectado al siguiente eslabón. Eso es básicamente una Lista Enlazada. Cada "eslabón" en programación se llama Nodo. Cada nodo guarda un dato y una dirección que apunta al siguiente nodo.

Ahora, piensa que cada eslabón, además de conectarse al siguiente, ¡se conecta también al anterior! Eso es una Lista Doblemente Enlazada. Tenemos información, un puntero al siguiente nodo y un puntero al nodo anterior. ¡Más conexiones, más flexibilidad!

Definiendo el Nodo

Primero, necesitamos definir cómo será nuestro Nodo. Usaremos una estructura (struct) en C++ para ello. Una estructura es como un "molde" para crear objetos.

Aquí está el código:
struct Nodo {
  int data;
  Nodo* siguiente;
  Nodo* anterior;
};

Vamos a desglosarlo. int data; es el dato que guardará nuestro nodo. Podría ser un número entero, una cadena de texto, o incluso otro objeto. Nodo* siguiente; es un puntero (una dirección de memoria) al siguiente nodo en la lista. Nodo* anterior; es un puntero al nodo anterior.

Creando la Lista

Ahora, vamos a crear nuestra Lista Doblemente Enlazada. Necesitamos mantener un registro del primer nodo (cabeza) y del último nodo (cola) de la lista.

Aquí el código para iniciar la lista:
Nodo* cabeza = NULL;
Nodo* cola = NULL;

Inicializamos cabeza y cola a NULL, que significa que la lista está vacía.

Insertando un Nodo

La parte interesante: ¡insertar datos en nuestra lista! Vamos a insertar al final de la lista (append). Así agregaremos un nuevo elemento a la cola.

El código para insertar al final se vería así:
void insertarAlFinal(int valor) {
  Nodo* nuevoNodo = new Nodo();
  nuevoNodo->data = valor;
  nuevoNodo->siguiente = NULL;

  if (cabeza == NULL) {
    nuevoNodo->anterior = NULL;
    cabeza = nuevoNodo;
    cola = nuevoNodo;
  } else {
    nuevoNodo->anterior = cola;
    cola->siguiente = nuevoNodo;
    cola = nuevoNodo;
  }
}

Analicemos este código. Nodo* nuevoNodo = new Nodo(); crea un nuevo nodo. nuevoNodo->data = valor; asigna el valor al campo de datos. nuevoNodo->siguiente = NULL; El siguiente nodo es nulo por defecto. Si la lista está vacía (cabeza == NULL), el nuevo nodo se convierte en la cabeza y la cola. Si no está vacía, conectamos el nuevo nodo a la cola actual y lo convertimos en la nueva cola.

Recorriendo la Lista

Podemos recorrer la lista desde la cabeza hasta la cola, o viceversa. Esto es gracias a los punteros siguiente y anterior.

Para imprimir los datos desde la cabeza a la cola:
void imprimirLista() {
  Nodo* actual = cabeza;
  while (actual != NULL) {
    std::cout << actual->data << " ";
    actual = actual->siguiente;
  }
  std::cout << std::endl;
}

Esto empieza en la cabeza y sigue el puntero siguiente hasta llegar al final de la lista (donde siguiente es NULL).

Eliminando un Nodo

Finalmente, veamos cómo eliminar un nodo. Esto requiere un poco de cuidado para no romper la lista.

Código para eliminar un nodo (necesitamos un valor para ubicarlo):
void eliminarNodo(int valor) {
  Nodo* actual = cabeza;
  while (actual != NULL) {
    if (actual->data == valor) {
      if (actual->anterior != NULL) {
        actual->anterior->siguiente = actual->siguiente;
      } else {
        cabeza = actual->siguiente;
      }
      if (actual->siguiente != NULL) {
        actual->siguiente->anterior = actual->anterior;
      } else {
        cola = actual->anterior;
      }
      delete actual;
      return;
    }
    actual = actual->siguiente;
  }
}

Localizamos el nodo a eliminar. Luego, actualizamos los punteros siguiente y anterior de los nodos vecinos. Por último, liberamos la memoria que ocupaba el nodo eliminado con delete actual;.

¡Felicidades! Ahora conoces los fundamentos de las Listas Doblemente Enlazadas en C++. ¡Practica y experimenta para dominar este concepto!