Listas enlazadas

¿Qué es una lista enlazada?

Una lista enlazada es una estructura de datos lineal donde los elementos (nodos) no se almacenan en posiciones de memoria contiguas. En su lugar, cada nodo contiene datos y una referencia (puntero) al siguiente nodo. Esta estructura permite inserciones y eliminaciones eficientes.

A diferencia de los arrays, las listas enlazadas no requieren desplazar elementos al insertar o eliminar, lo que las hace ideales cuando hay modificaciones frecuentes.

Tipos de listas enlazadas

Implementación de lista enlazada simple

Clase Node

// Node class represents each element in the list
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

// Linked List class
class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  // Get the size of the list - O(1)
  getSize() {
    return this.size;
  }

  // Check if list is empty - O(1)
  isEmpty() {
    return this.size === 0;
  }
}

Insertar al inicio - O(1)

insertAtBeginning(data) {
  const newNode = new Node(data);
  
  // Point new node to current head
  newNode.next = this.head;
  
  // Update head to new node
  this.head = newNode;
  
  this.size++;
}

// Usage
const list = new LinkedList();
list.insertAtBeginning(3);  // List: 3
list.insertAtBeginning(2);  // List: 2 → 3
list.insertAtBeginning(1);  // List: 1 → 2 → 3

Insertar al final - O(n)

insertAtEnd(data) {
  const newNode = new Node(data);
  
  // If list is empty, new node becomes head
  if (this.isEmpty()) {
    this.head = newNode;
  } else {
    // Traverse to the end
    let current = this.head;
    while (current.next !== null) {
      current = current.next;
    }
    // Attach new node at the end
    current.next = newNode;
  }
  
  this.size++;
}

// Note: Can optimize to O(1) by maintaining a tail pointer

Insertar en posición - O(n)

insertAt(data, index) {
  if (index < 0 || index > this.size) {
    throw new Error('Invalid index');
  }
  
  // Insert at beginning
  if (index === 0) {
    this.insertAtBeginning(data);
    return;
  }
  
  const newNode = new Node(data);
  let current = this.head;
  
  // Traverse to position before insertion point
  for (let i = 0; i < index - 1; i++) {
    current = current.next;
  }
  
  // Insert new node
  newNode.next = current.next;
  current.next = newNode;
  
  this.size++;
}

Eliminar del inicio - O(1)

deleteFromBeginning() {
  if (this.isEmpty()) {
    throw new Error('List is empty');
  }
  
  // Move head to next node
  const deletedData = this.head.data;
  this.head = this.head.next;
  
  this.size--;
  return deletedData;
}

Eliminar del final - O(n)

deleteFromEnd() {
  if (this.isEmpty()) {
    throw new Error('List is empty');
  }
  
  // If only one node
  if (this.head.next === null) {
    const deletedData = this.head.data;
    this.head = null;
    this.size--;
    return deletedData;
  }
  
  // Traverse to second-to-last node
  let current = this.head;
  while (current.next.next !== null) {
    current = current.next;
  }
  
  const deletedData = current.next.data;
  current.next = null;
  
  this.size--;
  return deletedData;
}

Búsqueda - O(n)

search(data) {
  let current = this.head;
  let index = 0;
  
  while (current !== null) {
    if (current.data === data) {
      return index;
    }
    current = current.next;
    index++;
  }
  
  return -1;  // Not found
}

contains(data) {
  return this.search(data) !== -1;
}

Mostrar/Imprimir lista

print() {
  if (this.isEmpty()) {
    console.log('List is empty');
    return;
  }
  
  const values = [];
  let current = this.head;
  
  while (current !== null) {
    values.push(current.data);
    current = current.next;
  }
  
  console.log(values.join(' → '));
}

Implementación de lista doblemente enlazada

// Node for doubly linked list
class DoublyNode {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // Insert at beginning - O(1)
  insertAtBeginning(data) {
    const newNode = new DoublyNode(data);
    
    if (this.isEmpty()) {
      this.head = this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    
    this.size++;
  }

  // Insert at end - O(1) with tail pointer!
  insertAtEnd(data) {
    const newNode = new DoublyNode(data);
    
    if (this.isEmpty()) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    
    this.size++;
  }

  // Delete from beginning - O(1)
  deleteFromBeginning() {
    if (this.isEmpty()) {
      throw new Error('List is empty');
    }
    
    const deletedData = this.head.data;
    
    if (this.head === this.tail) {
      this.head = this.tail = null;
    } else {
      this.head = this.head.next;
      this.head.prev = null;
    }
    
    this.size--;
    return deletedData;
  }

  // Delete from end - O(1) with tail pointer!
  deleteFromEnd() {
    if (this.isEmpty()) {
      throw new Error('List is empty');
    }
    
    const deletedData = this.tail.data;
    
    if (this.head === this.tail) {
      this.head = this.tail = null;
    } else {
      this.tail = this.tail.prev;
      this.tail.next = null;
    }
    
    this.size--;
    return deletedData;
  }

  isEmpty() {
    return this.size === 0;
  }
}

Problemas comunes de listas enlazadas

1. Invertir una lista enlazada

function reverseList(head) {
  let prev = null;
  let current = head;
  
  while (current !== null) {
    // Save next node
    const nextNode = current.next;
    
    // Reverse the link
    current.next = prev;
    
    // Move pointers forward
    prev = current;
    current = nextNode;
  }
  
  return prev;  // New head
}

// Example: 1 → 2 → 3 → null becomes 3 → 2 → 1 → null

2. Detectar ciclo (Floyd)

function hasCycle(head) {
  let slow = head;
  let fast = head;
  
  while (fast !== null && fast.next !== null) {
    slow = slow.next;        // Move 1 step
    fast = fast.next.next;   // Move 2 steps
    
    if (slow === fast) {
      return true;  // Cycle detected
    }
  }
  
  return false;  // No cycle
}

// If there's a cycle, fast will eventually meet slow

3. Encontrar el elemento medio

function findMiddle(head) {
  let slow = head;
  let fast = head;
  
  while (fast !== null && fast.next !== null) {
    slow = slow.next;        // Move 1 step
    fast = fast.next.next;   // Move 2 steps
  }
  
  return slow;  // Slow will be at middle
}

// When fast reaches end, slow will be at middle

4. Unir dos listas ordenadas

function mergeSortedLists(l1, l2) {
  const dummy = new Node(0);
  let current = dummy;
  
  while (l1 !== null && l2 !== null) {
    if (l1.data < l2.data) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    current = current.next;
  }
  
  // Attach remaining nodes
  current.next = l1 !== null ? l1 : l2;
  
  return dummy.next;
}

5. Eliminar el n-ésimo nodo desde el final

function removeNthFromEnd(head, n) {
  const dummy = new Node(0);
  dummy.next = head;
  
  let first = dummy;
  let second = dummy;
  
  // Move first n+1 steps ahead
  for (let i = 0; i <= n; i++) {
    first = first.next;
  }
  
  // Move both until first reaches end
  while (first !== null) {
    first = first.next;
    second = second.next;
  }
  
  // Remove the nth node
  second.next = second.next.next;
  
  return dummy.next;
}

Resumen de complejidad temporal