Singly Linked List

FácilPrioritaria

Colección lineal donde cada elemento apunta al siguiente.

¿Qué es una Singly Linked List?

Una Singly Linked List está compuesta por nodos, donde cada nodo contiene un valor y una referencia al siguiente nodo en la secuencia. A diferencia de un array, no se almacena en ubicaciones contiguas de memoria.

Analogía del Mundo Real

Imagina una cadena de trenes donde cada vagón (nodo) sabe cómo llegar al siguiente, pero no al anterior.
Si quieres llegar al último vagón, necesitas recorrerlos todos desde el primero.

Cómo Funciona Internamente una Singly Linked List

Cada nodo contiene:
- value: el dato almacenado.
- next: una referencia al siguiente nodo.
El primer nodo se llama head.
El último nodo tiene next = null.
Para insertar al inicio: crea un nuevo nodo y apunta su next al head actual.
Para eliminar el primer nodo: cambia el head al siguiente nodo.
Para acceder a un nodo intermedio, debes recorrer desde el head hasta llegar a la posición deseada.

Ejemplos de Código

// Definición del nodo
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// Definición de la Singly Linked List
class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Insertar al inicio
  prepend(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
  }

  // Agregar al final
  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }

  // Buscar un valor
  find(value) {
    let current = this.head;
    while (current) {
      if (current.value === value) return current;
      current = current.next;
    }
    return null;
  }

  // Eliminar el primer nodo
  removeHead() {
    if (this.head) this.head = this.head.next;
  }
}

Explicación Visual (🚧 En progreso)

Pronto disponible

Estamos trabajando en un video para explicar esta estructura de datos

Complejidad en Tiempo y Espacio

Operación	Promedio	Peor Escenario
Acceso	O(n)	O(n)
Búsqueda	O(n)	O(n)
Inserción	O(1)	O(1)
Eliminación	O(1)	O(1)

Donde n es el número de nodos en la lista.

El acceso aleatorio no es posible, ya que se debe recorrer desde el inicio.

Operaciones Comunes

.prepend(value)
Agrega un nodo al inicio de la lista
.append(value)
Agrega un nodo al final de la lista
.find(value)
Busca un nodo por su valor
.removeHead()
Elimina el primer nodo de la lista

Practica

Aplica lo que has aprendido

Reverse Linked List (Fácil)Merge Two Sorted Lists (Fácil)

Posts relacionados

Linked List en JS