Saltar al contenido principal

Lista Enlazada Doble

Una lista enlazada doble es una estructura de datos lineal que extiende el concepto de la lista enlazada simple. Cada nodo contiene referencias tanto al siguiente nodo como al anterior, permitiendo un recorrido en ambas direcciones.

Características​

  1. Cada nodo contiene:
    • Un dato.
    • Una referencia al siguiente nodo (next).
    • Una referencia al nodo anterior (prev).
  2. Tiene dos puntos de referencia principales:
    • head: apunta al primer nodo.
    • tail: apunta al último nodo.

El primer nodo tiene su referencia prev = null y el último nodo tiene next = null.

Ventajas​

  • Permite recorrer la lista hacia adelante y hacia atrás.
  • Las operaciones de inserción y eliminación son más flexibles (no se requiere recorrer desde el inicio si tenemos un puntero al nodo).

Desventajas​

  • Ocupa más memoria (almacena dos referencias por nodo).
  • Mayor complejidad en la manipulación de punteros/referencias.

Complejidad de operaciones​

  • Acceso: O(n)O(n)
  • Inserción/Eliminación en extremos: O(1)O(1)
  • Inserción/Eliminación en posición intermedia: O(n)O(n)

Representación Visual​

Flujo de acciones​

Inserción al inicio​

  1. Verificar si la lista está vacía: Si head == null, se crea un nuevo nodo y tanto head como tail apuntan a él.
  2. Si la lista no está vacía:
    • Se crea un nuevo nodo.
    • Su puntero next apunta al nodo actual de head.
    • Se actualiza el puntero prev del nodo original de head para que apunte al nuevo nodo.
    • Finalmente, se asigna el nuevo nodo como head.

Inserción al final​

  1. Verificar si la lista está vacía: Si head == null, se crea un nuevo nodo y tanto head como tail apuntan a él.
  2. Si la lista no está vacía:
    • Se crea un nuevo nodo.
    • Se enlaza el puntero next del tail actual al nuevo nodo.
    • Se enlaza el puntero prev del nuevo nodo al tail actual.
    • Se actualiza el tail para que apunte al nuevo nodo.

Insertar en una posición especifica​

  1. Lista vacía: Si la lista está vacía (head == null), se crea un nodo y se asigna como head y tail.
  2. Posición inicial: Si pos <= 0, se llama a insertAtBeginning(data).
  3. Posición al final o más grande que el tamaño: Si pos >= tamaño, se llama a insertAtEnd(data).
  4. Posición intermedia:
    • Se recorre la lista hasta llegar a la posición anterior a pos (pos-1).
    • Se enlaza el nuevo nodo entre el nodo actual (current) y el siguiente.
    • Se actualizan los punteros next y prev de los nodos vecinos.

Eliminación​

  1. Lista vacía: Si head == null, no hay nada que eliminar.
  2. Eliminar la cabeza:
    1. Si el primer nodo contiene el dato:
      • Si es el único nodo (head == tail), se deja la lista vacía (head = tail = null).
      • Si hay más nodos, se mueve la cabeza al siguiente y se elimina el enlace al nodo previo (head.prev = null).
  3. Buscar el nodo:
    • Se recorre la lista desde head.next.
    • Si no se encuentra el dato, la función termina.
  4. Eliminar el nodo encontrado:
    • Si el nodo es el tail, se mueve la cola hacia atrás y se elimina el enlace al siguiente (tail.next = null).
    • Si está en el medio, se saltan los enlaces:
      1. current.prev.next = current.next
      2. current.next.prev = current.prev

Ejemplo Técnico​

DNode.java
/**
 * Node for doubly linked list
 */
class DNode<T> {
    private T data;
    private DNode<T> next;
    private DNode<T> prev;

    public DNode(T data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }

    public T getData() { return data; }
    public void setNext(DNode<T> next) { this.next = next; }
    public DNode<T> getNext() { return next; }
    public void setPrev(DNode<T> prev) { this.prev = prev; }
    public DNode<T> getPrev() { return prev; }
}
DoublyLinkedList.java
/**
 * Doubly linked list implementation
 */
public class DoublyLinkedList<T> {
    private DNode<T> head;
    private DNode<T> tail;
    private int size = 0;

    public void insertAtBeginning(T data) {
        DNode<T> newNode = new DNode<>(data);
        if (head == null) {
            head = tail = newNode;
        } else {
            newNode.setNext(head);
            head.setPrev(newNode);
            head = newNode;
        }
        size++;
    }

    public void insertAtEnd(T data) {
        DNode<T> newNode = new DNode<>(data);
        if (tail == null) {
            head = tail = newNode;
        } else {
            tail.setNext(newNode);
            newNode.setPrev(tail);
            tail = newNode;
        }
        size++;
    }

    public void insertAtPosition(int index, T data) {
        if (index <= 0) {
            insertAtBeginning(data);
            return;
        }
        if (index >= size) {
            insertAtEnd(data);
            return;
        }
        DNode<T> current = head;
        for (int i = 0; i < index - 1; i++) {
            current = current.getNext();
        }
        DNode<T> newNode = new DNode<>(data);
        newNode.setNext(current.getNext());
        newNode.setPrev(current);
        current.getNext().setPrev(newNode);
        current.setNext(newNode);
        size++;
    }

    public boolean delete(T data) {
        if (head == null) return false;

        if (head.getData().equals(data)) {
            head = head.getNext();
            if (head != null) head.setPrev(null);
            else tail = null;
            size--;
            return true;
        }

        DNode<T> current = head;
        while (current != null) {
            if (current.getData().equals(data)) {
                if (current.getNext() != null)
                    current.getNext().setPrev(current.getPrev());
                else tail = current.getPrev();

                if (current.getPrev() != null)
                    current.getPrev().setNext(current.getNext());
                size--;
                return true;
            }
            current = current.getNext();
        }
        return false;
    }

    public int length() { return size; }

    public String printForward() {
        StringBuilder sb = new StringBuilder();
        DNode<T> current = head;
        while (current != null) {
            sb.append(current.getData()).append(" <-> ");
            current = current.getNext();
        }
        return sb.append("null").toString();
    }

    public String printBackward() {
        StringBuilder sb = new StringBuilder();
        DNode<T> current = tail;
        while (current != null) {
            sb.append(current.getData()).append(" <-> ");
            current = current.getPrev();
        }
        return sb.append("null").toString();
    }
}

Aplicaciones Prácticas​

  • Navegadores web: Botones de atrás y adelante en el historial de navegación.
  • Edición de texto: Implementación de cursores que se mueven en ambas direcciones.
  • Sistemas de archivos: Permite recorrer directorios hacia adelante y atrás.
  • Algoritmos de caché (LRU): Eliminación rápida de nodos en ambas direcciones.

Referencias​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.
  • Weiss, M. A. (2020). Data Structures and Algorithm Analysis in Java (4th ed.). Pearson.
  • McDowell, G. (2016). Cracking the Coding Interview. CareerCup.
  • Python 3
  • Jest