Listas Enlazadas

Introducción

Usamos las Listas Enlazadas para guardar una lista de objetos en secuencia,
pero a diferencia de los arrays, las linked lists pueden crecer o disminuir automáticamente.

Una linked list está compuesta por un grupo de nodos conectados uno tras otro.
Cada nodo tiene dos partes:

  1. El valor o dato que guarda.

  2. Una referencia (o dirección) hacia el siguiente nodo.

Por eso decimos que los nodos están enlazados (linked).
Al primero lo llamamos cabeza (head) y al último, cola (tail).

🧩 Idea general

Podemos imaginar una linked list como una cadena de cajas conectadas:


[ A | • ] → [ B | • ] → [ C | ∅ ]

Cada caja tiene un valor y una flecha (link) hacia la siguiente.
El último nodo apunta a null (∅), indicando el final de la lista.

⚙️ Complejidad de operaciones

🔍 Búsqueda

Si queremos saber si la lista contiene un número,
debemos recorrer todos los nodos, desde la cabeza hasta la cola.

En el peor caso, el valor buscado está en el último nodo →
la complejidad de tiempo es O(n).

📦 Acceso por índice

A diferencia de los arrays, donde los elementos están en posiciones contiguas,
en una linked list los nodos pueden estar dispersos en memoria.

Por eso no podemos acceder directamente por índice.
Hay que recorrer la lista hasta llegar al nodo deseado → O(n).

➕ Inserciones

Inserción al final

Si queremos agregar un nodo al final, necesitamos tener una referencia al último nodo.
Si ya la tenemos, la operación es O(1).
Si no, debemos recorrer toda la lista para encontrarlo → O(n).

Inserción al comienzo

Agregar un nodo al principio es muy rápido:
simplemente conectamos el nuevo nodo al antiguo primero y actualizamos la cabeza.
→ O(1).

Inserción en el medio

Primero debemos encontrar el nodo anterior, lo cual es O(n),
y luego actualizar los enlaces, lo cual es O(1).
En total: O(n).

❌ Eliminaciones

🧩 Actualización de enlaces al eliminar nodos

Antes de pasar al código en Java, haz una pausa y reflexiona sobre cómo se comportan los enlaces (links) cuando eliminamos nodos en una lista enlazada.

Toma una hoja y dibuja los siguientes tres escenarios:

  1. Eliminar el primer nodo (la cabeza):

    Imagina que tu lista empieza en head → [A|•] → [B|•] → [C|∅].

    ¿Qué debe ocurrir para que la lista siga conectada después de eliminar A?

    (Pista: el nuevo head debe apuntar al segundo nodo).

  2. Eliminar el último nodo (la cola):

    En la misma lista, ¿qué pasa si queremos borrar el nodo [C|∅]?

    ¿Qué enlace hay que cambiar?

    (Pista: el penúltimo nodo [B|•] debe apuntar ahora a null).

  3. Eliminar un nodo en el medio:

    Supón que quieres borrar el nodo [B|•].

    ¿Qué enlaces deben actualizarse para mantener la conexión entre A y C?

    (Pista: el next de A debe saltarse a C).

Para cada caso: - Dibuja el antes y el después de la lista.

  • Indica qué enlaces se modifican.

  • Calcula la complejidad temporal de la operación (O(1) o O(n)).

Este pequeño ejercicio es esencial para comprender cómo funcionan internamente las listas enlazadas.
Cuando empieces a implementarlas en Java, cada línea de código tendrá sentido si primero visualizas estos enlaces.

💡 Cuando termines…

Compara tus respuestas con los diagramas que aparecen a continuación.
Verás que:

  • Eliminar el primer nodo es una operación O(1).
  • Eliminar el último nodo requiere recorrer la lista → O(n).
  • Eliminar un nodo intermedio también implica un recorrido → O(n).

✅ Respuestas

1️⃣ Eliminar el primer nodo (la cabeza)

Antes:


head → [ A | • ] → [ B | • ] → [ C | ∅ ]

Después:


head → [ B | • ] → [ C | ∅ ]

Cambio: head = head.next
Complejidad: O(1)

2️⃣ Eliminar el último nodo (la cola)

Antes:


head → [ A | • ] → [ B | • ] → [ C | ∅ ]
↑
tail

Después:


head → [ A | • ] → [ B | ∅ ]
↑
tail

Cambio: penultimo.next = null; tail = penultimo
Complejidad: O(n) (hay que recorrer hasta el penúltimo nodo)

3️⃣ Eliminar un nodo en el medio

Antes:


head → [ A | • ] → [ B | • ] → [ C | ∅ ]

Después:


head → [ A | • ] ───→ [ C | ∅ ]
__**(salta B)**__/

Cambio: anterior.next = actual.next
Complejidad: O(n) (hay que encontrar el nodo y su anterior)

💬 En resumen

Operación Complejidad
Buscar elemento O(n)
Acceso por índice O(n)
Insertar al inicio O(1)
Insertar al final (sin tail) O(n)
Insertar en el medio O(n)
Eliminar al inicio O(1)
Eliminar al final O(n)
Eliminar en el medio O(n)

🧩 Próximo paso

En la siguiente clase implementaremos una Linked List en Java,
creando nuestra propia clase Node y manejando los enlaces manualmente.
Prepárate para encadenar ideas 🔗🐶

Ahora que ya comprendemos cómo funciona una lista enlazada — tanto usando LinkedList como construyendo nodos manuales — vamos a dar un paso más:

Construiremos nuestra propia clase LinkedList desde cero.

📋 Métodos implementados

Método Descripción
agregarAlInicio() Inserta al principio
agregarAlFinal() Inserta al final
indiceDe() Devuelve la posición del valor
contiene() Verifica si el valor existe
eliminarPrimero() Elimina el nodo inicial
eliminarUltimo() Elimina el nodo final

🧩 Convertir una lista enlazada en un arreglo

En algunos casos necesitamos pasar nuestra lista enlazada a un método que solo acepte un arreglo (array) de Java.

Por ejemplo, las funciones de la clase Arrays o métodos que esperan un int[].

Para eso, implementaremos el método toArray() dentro de nuestra clase ListaEnlazada.

💡 Idea principal

Queremos recorrer la lista, tomar el valor de cada nodo y copiarlo dentro de un nuevo arreglo de tamaño igual al de la lista.

Así, podremos trabajar con la estructura estándar de Java (int[]).

🧠 Paso a paso

  1. Creamos un arreglo del mismo tamaño que la lista.
  2. Recorremos los nodos desde el primero hasta el último.
  3. En cada paso, copiamos el valor del nodo al arreglo.
  4. Finalmente, retornamos el arreglo.

🧱 Código — método toArray()

public int[] toArray() {
    int[] array = new int[tamano];     // 1️⃣ Crear el arreglo con el tamaño actual
    var current = primero;             // 2️⃣ Iniciar desde el primer nodo
    int index = 0;                   // 3️⃣ Índice para el arreglo

    while (current != null) {        // 4️⃣ Recorrer la lista
        array[index++] = current.value; // Copiar valor y avanzar índice
        current = current.next;         // Mover al siguiente nodo
    }

    return array;                    // 5️⃣ Retornar el arreglo final
   }

🧪 Ejemplo de uso en Main.java

public class Main {
    public static void main(String[] args) {
        var list = new ListaEnlazada();
        list.addLast(10);
        list.addLast(20);
        list.addLast(30);

        int[] array = list.toArray();  // Convertir la lista en arreglo

        System.out.println(Arrays.toString(array));
    }
}

🖥️ Salida esperada

[10, 20, 30]

💭 Diferencias entre Arreglos y listas enlazadas

Una de las preguntas comunes en una entrevista de programación es sobre las diferencias entre los arrays y las listas enlazadas.
Debes poder explicar estas diferencias en términos de memoria requerida y complejidad temporal de las operaciones más comunes.

Los arrays, o más precisamente los arrays estáticos, tienen un tamaño fijo. Por lo tanto, si no sabemos de antemano cuántos objetos vamos a guardar, deberíamos usar arrays dinámicos o listas enlazadas.

💾 Memoria y espacio

Los arrays dinámicos crecen automáticamente (en Java, suelen duplicar su tamaño o aumentar en un 50 %) cuando se llenan.
Esto puede causar fragmentación o pérdida de memoria temporal, ya que se crea un nuevo array y se copian los elementos.

En cambio, las listas enlazadas usan solo la memoria que realmente necesitan.
Cada vez que agregamos un nuevo nodo, este ocupa exactamente el espacio requerido.
Sin embargo, cada nodo debe guardar además una referencia al siguiente nodo, lo cual implica un pequeño gasto adicional de memoria.

💡 Consejo:
Si sabes aproximadamente cuántos objetos vas a almacenar (por ejemplo, hasta 100), es mejor usar un array dinámico con esa capacidad inicial.
En Java, puedes hacerlo así:

var lista = new ArrayList<Integer>(100);

⚙️ Performance y complejidad temporal

El tiempo de ejecución depende de la operación que queramos realizar. Veamos cómo se comportan ambas estructuras:

Operación Array Estático/Dinámico Lista Enlazada
Acceso por índice O(1) (directo) O(n) (recorrido)
Búsqueda por valor O(n) O(n)
Inserción (al final o medio) O(n) (puede requerir copia) O(1) al inicio/fin
O(n) en posición intermedia
Eliminación O(n) (desplazar elementos) O(1) al inicio
O(n) en otro lugar

Como siempre he dicho: no existe la solución perfecta. Cada problema requiere un tipo diferente de estructura de datos.

Un buen programador no memoriza respuestas, sino que entiende el problema, piensa en múltiples soluciones, analiza ventajas y desventajas y elige la que mejor se adapte al escenario.

🗣️ Y eso es exactamente lo que un buen entrevistador quiere ver: tu capacidad para razonar, comparar, y tomar decisiones fundamentadas.

  • Usa arrays cuando necesites acceso rápido por índice o conozcas el tamaño aproximado.

  • Usa listas enlazadas cuando el número de elementos sea incierto o las inserciones/eliminaciones sean frecuentes.

En el próximo tema, exploraremos cómo optimizar las listas enlazadas mediante una doble referencia (listas doblemente enlazadas), para mejorar operaciones en ambos extremos.