Listas enlazadas en Java: implementación paso a paso

  cabeza
    │
    ▼
┌───────┐    ┌───────┐    ┌───────┐
│ "Ana" │───▶│ "Luis"│───▶│"María"│───▶ null
└───────┘    └───────┘    └───────┘
  nodo 1       nodo 2       nodo 3

Simple:       [A] ──▶ [B] ──▶ [C] ──▶ null

Doble:  null ◀── [A] ◀──▶ [B] ◀──▶ [C] ──▶ null

Circular:     [A] ──▶ [B] ──▶ [C] ──┐
               ▲                      │
               └──────────────────────┘

/**
 * Nodo genérico para una lista enlazada simple.
 * @param <T> Tipo de dato almacenado en el nodo
 */
public class Nodo<T> {
    private T dato;             // Información almacenada
    private Nodo<T> siguiente;  // Referencia al próximo nodo

    // Constructor: crea un nodo con dato y referencia al siguiente
    public Nodo(T dato, Nodo<T> siguiente) {
        this.dato = dato;
        this.siguiente = siguiente;
    }

    // Constructor: crea un nodo aislado (siguiente = null)
    public Nodo(T dato) {
        this(dato, null);
    }

    // --- Getters y Setters ---
    public T getDato()                    { return dato; }
    public void setDato(T dato)           { this.dato = dato; }
    public Nodo<T> getSiguiente()         { return siguiente; }
    public void setSiguiente(Nodo<T> sig) { this.siguiente = sig; }

    @Override
    public String toString() {
        return "Nodo{" + dato + "}";
    }
}

/**
 * Lista enlazada simple genérica.
 * Operaciones: insertar, eliminar, buscar, recorrer, invertir.
 */
public class ListaEnlazada<T> {
    private Nodo<T> cabeza;   // Primer nodo de la lista
    private int tamanio;       // Número de elementos

    public ListaEnlazada() {
        this.cabeza = null;
        this.tamanio = 0;
    }

    // ¿La lista está vacía?
    public boolean esVacia() {
        return cabeza == null;
    }

    // Número de elementos
    public int tamanio() {
        return tamanio;
    }

    // --- INSERCIÓN ---

    /** Inserta al inicio de la lista — O(1) */
    public void insertarInicio(T dato) {
        cabeza = new Nodo<>(dato, cabeza);
        tamanio++;
    }

    /** Inserta al final de la lista — O(n) */
    public void insertarFinal(T dato) {
        Nodo<T> nuevo = new Nodo<>(dato);
        if (esVacia()) {
            cabeza = nuevo;
        } else {
            Nodo<T> actual = cabeza;
            while (actual.getSiguiente() != null) {
                actual = actual.getSiguiente();
            }
            actual.setSiguiente(nuevo);
        }
        tamanio++;
    }

    /** Inserta en una posición específica (0-indexada) — O(n) */
    public void insertarEn(int posicion, T dato) {
        if (posicion < 0 || posicion > tamanio) {
            throw new IndexOutOfBoundsException(
                "Posición " + posicion + " fuera de rango [0, " + tamanio + "]");
        }
        if (posicion == 0) {
            insertarInicio(dato);
            return;
        }
        Nodo<T> actual = cabeza;
        for (int i = 0; i < posicion - 1; i++) {
            actual = actual.getSiguiente();
        }
        actual.setSiguiente(new Nodo<>(dato, actual.getSiguiente()));
        tamanio++;
    }

    // --- ELIMINACIÓN ---

    /** Elimina el primer nodo — O(1) */
    public T eliminarInicio() {
        if (esVacia()) {
            throw new RuntimeException("Lista vacía");
        }
        T dato = cabeza.getDato();
        cabeza = cabeza.getSiguiente();
        tamanio--;
        return dato;
    }

    /** Elimina el último nodo — O(n) */
    public T eliminarFinal() {
        if (esVacia()) {
            throw new RuntimeException("Lista vacía");
        }
        if (tamanio == 1) {
            return eliminarInicio();
        }
        Nodo<T> actual = cabeza;
        while (actual.getSiguiente().getSiguiente() != null) {
            actual = actual.getSiguiente();
        }
        T dato = actual.getSiguiente().getDato();
        actual.setSiguiente(null);
        tamanio--;
        return dato;
    }

    // --- BÚSQUEDA Y ACCESO ---

    /** Busca un dato y devuelve true si existe — O(n) */
    public boolean contiene(T dato) {
        Nodo<T> actual = cabeza;
        while (actual != null) {
            if (actual.getDato().equals(dato)) {
                return true;
            }
            actual = actual.getSiguiente();
        }
        return false;
    }

    /** Obtiene el dato en una posición — O(n) */
    public T obtener(int posicion) {
        if (posicion < 0 || posicion >= tamanio) {
            throw new IndexOutOfBoundsException(
                "Posición " + posicion + " fuera de rango [0, " + (tamanio - 1) + "]");
        }
        Nodo<T> actual = cabeza;
        for (int i = 0; i < posicion; i++) {
            actual = actual.getSiguiente();
        }
        return actual.getDato();
    }

    // --- UTILIDADES ---

    /** Invierte la lista in-place — O(n) */
    public void invertir() {
        Nodo<T> anterior = null;
        Nodo<T> actual = cabeza;
        while (actual != null) {
            Nodo<T> siguiente = actual.getSiguiente();
            actual.setSiguiente(anterior);
            anterior = actual;
            actual = siguiente;
        }
        cabeza = anterior;
    }

    /** Representación textual de la lista */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        Nodo<T> actual = cabeza;
        while (actual != null) {
            sb.append(actual.getDato());
            if (actual.getSiguiente() != null) {
                sb.append(" → ");
            }
            actual = actual.getSiguiente();
        }
        return sb.append("]").toString();
    }
}

public class DemoListaEnlazada {
    public static void main(String[] args) {
        ListaEnlazada<String> colores = new ListaEnlazada<>();

        // --- Inserción ---
        colores.insertarInicio("verde");         // [verde]
        colores.insertarInicio("rojo");          // [rojo → verde]
        colores.insertarFinal("azul");           // [rojo → verde → azul]
        colores.insertarEn(1, "amarillo");       // [rojo → amarillo → verde → azul]

        System.out.println("Lista: " + colores);
        System.out.println("Tamaño: " + colores.tamanio());

        // --- Búsqueda ---
        System.out.println("¿Contiene 'verde'? " + colores.contiene("verde"));
        System.out.println("Elemento en pos. 2: " + colores.obtener(2));

        // --- Eliminación ---
        String primero = colores.eliminarInicio();
        System.out.println("Eliminado inicio: " + primero);
        String ultimo = colores.eliminarFinal();
        System.out.println("Eliminado final: " + ultimo);
        System.out.println("Lista: " + colores);

        // --- Inversión ---
        colores.insertarFinal("naranja");
        colores.insertarFinal("morado");
        System.out.println("Antes de invertir: " + colores);
        colores.invertir();
        System.out.println("Después de invertir: " + colores);
    }
}
// Salida:
// Lista: [rojo → amarillo → verde → azul]
// Tamaño: 4
// ¿Contiene 'verde'? true
// Elemento en pos. 2: verde
// Eliminado inicio: rojo
// Eliminado final: azul
// Lista: [amarillo → verde]
// Antes de invertir: [amarillo → verde → naranja → morado]
// Después de invertir: [morado → naranja → verde → amarillo]

/**
 * Nodo para lista doblemente enlazada.
 */
public class NodoDoble<T> {
    private T dato;
    private NodoDoble<T> siguiente;
    private NodoDoble<T> anterior;

    public NodoDoble(T dato) {
        this.dato = dato;
        this.siguiente = null;
        this.anterior = null;
    }

    // Getters y setters
    public T getDato()                          { return dato; }
    public NodoDoble<T> getSiguiente()          { return siguiente; }
    public void setSiguiente(NodoDoble<T> sig)  { this.siguiente = sig; }
    public NodoDoble<T> getAnterior()           { return anterior; }
    public void setAnterior(NodoDoble<T> ant)   { this.anterior = ant; }
}

public class ListaDoble<T> {
    private NodoDoble<T> cabeza;
    private NodoDoble<T> cola;    // Referencia al último nodo
    private int tamanio;

    public ListaDoble() {
        cabeza = null;
        cola = null;
        tamanio = 0;
    }

    /** Inserta al inicio — O(1) */
    public void insertarInicio(T dato) {
        NodoDoble<T> nuevo = new NodoDoble<>(dato);
        if (cabeza == null) {
            cabeza = cola = nuevo;
        } else {
            nuevo.setSiguiente(cabeza);
            cabeza.setAnterior(nuevo);
            cabeza = nuevo;
        }
        tamanio++;
    }

    /** Inserta al final — O(1) gracias a la referencia 'cola' */
    public void insertarFinal(T dato) {
        NodoDoble<T> nuevo = new NodoDoble<>(dato);
        if (cola == null) {
            cabeza = cola = nuevo;
        } else {
            cola.setSiguiente(nuevo);
            nuevo.setAnterior(cola);
            cola = nuevo;
        }
        tamanio++;
    }

    /** Elimina un nodo específico — O(1) si se conoce la referencia */
    public void eliminarNodo(NodoDoble<T> nodo) {
        if (nodo == null) return;
        if (nodo.getAnterior() != null) {
            nodo.getAnterior().setSiguiente(nodo.getSiguiente());
        } else {
            cabeza = nodo.getSiguiente(); // era la cabeza
        }
        if (nodo.getSiguiente() != null) {
            nodo.getSiguiente().setAnterior(nodo.getAnterior());
        } else {
            cola = nodo.getAnterior();    // era la cola
        }
        tamanio--;
    }

    /** Recorre de inicio a fin */
    public String recorrerAdelante() {
        StringBuilder sb = new StringBuilder("[");
        NodoDoble<T> actual = cabeza;
        while (actual != null) {
            sb.append(actual.getDato());
            if (actual.getSiguiente() != null) sb.append(" ↔ ");
            actual = actual.getSiguiente();
        }
        return sb.append("]").toString();
    }

    /** Recorre de fin a inicio */
    public String recorrerAtras() {
        StringBuilder sb = new StringBuilder("[");
        NodoDoble<T> actual = cola;
        while (actual != null) {
            sb.append(actual.getDato());
            if (actual.getAnterior() != null) sb.append(" ↔ ");
            actual = actual.getAnterior();
        }
        return sb.append("]").toString();
    }
}

/**
 * Lista circular simple.
 * El último nodo siempre apunta al primero.
 */
public class ListaCircular<T> {
    private Nodo<T> ultimo;   // Referencia al último nodo
    private int tamanio;

    public ListaCircular() {
        ultimo = null;
        tamanio = 0;
    }

    /** Inserta al inicio (después de último, antes del primero) — O(1) */
    public void insertarInicio(T dato) {
        Nodo<T> nuevo = new Nodo<>(dato);
        if (ultimo == null) {
            ultimo = nuevo;
            nuevo.setSiguiente(nuevo);  // Apunta a sí mismo
        } else {
            nuevo.setSiguiente(ultimo.getSiguiente());  // nuevo → primero
            ultimo.setSiguiente(nuevo);                  // ultimo → nuevo
        }
        tamanio++;
    }

    /** Inserta al final — O(1) */
    public void insertarFinal(T dato) {
        insertarInicio(dato);
        ultimo = ultimo.getSiguiente();  // El nuevo pasa a ser el último
    }

    /** Recorrido completo (una vuelta) */
    @Override
    public String toString() {
        if (ultimo == null) return "[]";
        StringBuilder sb = new StringBuilder("[");
        Nodo<T> actual = ultimo.getSiguiente(); // Empieza en el primero
        do {
            sb.append(actual.getDato());
            actual = actual.getSiguiente();
            if (actual != ultimo.getSiguiente()) sb.append(" → ");
        } while (actual != ultimo.getSiguiente());
        return sb.append("] (circular)").toString();
    }
}

import java.util.LinkedList;

public class DemoLinkedListAPI {
    public static void main(String[] args) {
        LinkedList<String> ciudades = new LinkedList<>();

        // --- Como List ---
        ciudades.add("Madrid");            // Inserta al final
        ciudades.add("Barcelona");
        ciudades.addFirst("Sevilla");      // Inserta al inicio
        ciudades.add(1, "Valencia");       // Inserta en posición 1

        System.out.println("Lista: " + ciudades);
        // [Sevilla, Valencia, Madrid, Barcelona]

        // --- Como Deque (doble cola) ---
        ciudades.offerFirst("Bilbao");     // Inserta al inicio
        ciudades.offerLast("Málaga");      // Inserta al final
        System.out.println("Primero: " + ciudades.peekFirst());  // Bilbao
        System.out.println("Último: " + ciudades.peekLast());    // Málaga

        // --- Eliminación ---
        ciudades.removeFirst();            // Elimina Bilbao
        ciudades.removeLast();             // Elimina Málaga
        ciudades.remove("Madrid");         // Elimina Madrid por valor

        // --- Recorrido con for-each ---
        System.out.println("Ciudades restantes:");
        for (String ciudad : ciudades) {
            System.out.println("  • " + ciudad);
        }

        // --- Búsqueda ---
        System.out.println("¿Contiene Valencia? " + ciudades.contains("Valencia"));
        System.out.println("Índice de Barcelona: " + ciudades.indexOf("Barcelona"));
    }
}
// Salida:
// Lista: [Sevilla, Valencia, Madrid, Barcelona]
// Primero: Bilbao
// Último: Málaga
// Ciudades restantes:
//   • Sevilla
//   • Valencia
//   • Barcelona
// ¿Contiene Valencia? true
// Índice de Barcelona: 2

import java.util.LinkedList;
import java.util.Iterator;

/**
 * Sistema de gestión de tareas con prioridad.
 * Utiliza LinkedList de la API de Java para demostrar
 * inserción ordenada, eliminación y recorrido.
 */
public class GestorTareas {

    // Clase interna: representa una tarea
    static class Tarea implements Comparable<Tarea> {
        private String nombre;
        private int prioridad;   // 1 = máxima, 5 = mínima
        private boolean completada;

        public Tarea(String nombre, int prioridad) {
            this.nombre = nombre;
            this.prioridad = prioridad;
            this.completada = false;
        }

        public void completar() { this.completada = true; }

        @Override
        public int compareTo(Tarea otra) {
            return Integer.compare(this.prioridad, otra.prioridad);
        }

        @Override
        public String toString() {
            String estado = completada ? "✓" : "○";
            return String.format("[%s] P%d: %s", estado, prioridad, nombre);
        }
    }

    private LinkedList<Tarea> tareas = new LinkedList<>();

    /** Inserta tarea manteniendo orden por prioridad */
    public void agregarTarea(String nombre, int prioridad) {
        Tarea nueva = new Tarea(nombre, prioridad);
        int posicion = 0;
        for (Tarea t : tareas) {
            if (nueva.compareTo(t) < 0) break;
            posicion++;
        }
        tareas.add(posicion, nueva);
        System.out.println("+ Añadida: " + nueva);
    }

    /** Completa la tarea de mayor prioridad (primera) */
    public void completarSiguiente() {
        if (tareas.isEmpty()) {
            System.out.println("No hay tareas pendientes.");
            return;
        }
        Tarea t = tareas.getFirst();
        t.completar();
        System.out.println("Completada: " + t);
        tareas.removeFirst();
    }

    /** Elimina todas las tareas completadas */
    public void limpiarCompletadas() {
        Iterator<Tarea> it = tareas.iterator();
        int eliminadas = 0;
        while (it.hasNext()) {
            if (it.next().completada) {
                it.remove();
                eliminadas++;
            }
        }
        System.out.println("Limpiadas " + eliminadas + " tareas completadas.");
    }

    /** Muestra el estado actual */
    public void mostrarTareas() {
        System.out.println("\n=== Tareas pendientes (" + tareas.size() + ") ===");
        if (tareas.isEmpty()) {
            System.out.println("  (ninguna)");
        } else {
            for (Tarea t : tareas) {
                System.out.println("  " + t);
            }
        }
        System.out.println();
    }

    // --- Programa principal ---
    public static void main(String[] args) {
        GestorTareas gestor = new GestorTareas();

        // Inserción ordenada por prioridad
        gestor.agregarTarea("Corregir bug crítico en producción", 1);
        gestor.agregarTarea("Escribir documentación del API", 3);
        gestor.agregarTarea("Actualizar dependencias Maven", 4);
        gestor.agregarTarea("Revisar pull request del equipo", 2);
        gestor.agregarTarea("Preparar demo para el cliente", 1);

        gestor.mostrarTareas();

        // Completar las dos tareas más urgentes
        gestor.completarSiguiente();
        gestor.completarSiguiente();

        gestor.mostrarTareas();
    }
}
// Salida:
// + Añadida: [○] P1: Corregir bug crítico en producción
// + Añadida: [○] P3: Escribir documentación del API
// + Añadida: [○] P4: Actualizar dependencias Maven
// + Añadida: [○] P2: Revisar pull request del equipo
// + Añadida: [○] P1: Preparar demo para el cliente
//
// === Tareas pendientes (5) ===
//   [○] P1: Corregir bug crítico en producción
//   [○] P1: Preparar demo para el cliente
//   [○] P2: Revisar pull request del equipo
//   [○] P3: Escribir documentación del API
//   [○] P4: Actualizar dependencias Maven
//
// Completada: [✓] P1: Corregir bug crítico en producción
// Completada: [✓] P1: Preparar demo para el cliente
//
// === Tareas pendientes (3) ===
//   [○] P2: Revisar pull request del equipo
//   [○] P3: Escribir documentación del API
//   [○] P4: Actualizar dependencias Maven