Lista enlazada
Última actualización
Una lista enlazada almacena una secuencia como una cadena de nodos, donde cada nodo guarda un valor y un puntero al siguiente nodo. A diferencia de un arreglo, los nodos no son contiguos en memoria: sigues los punteros next para recorrer la lista. Pulsa reproducir arriba para ver cómo se enlazan nodos al principio y al final, cómo se busca un valor recorriendo la cadena y cómo se elimina un nodo reconectando un puntero.
Insertar o eliminar al principio es O(1) porque solo reapuntas la cabeza. Llegar a una posición en el medio o al final es O(n) porque primero debes recorrer hasta allí. Ese compromiso -extremos baratos, sin acceso aleatorio- es lo que distingue a una lista enlazada de un arreglo.
Complejidad temporal
| Operación | Complejidad | Notas |
|---|---|---|
| Insertar al principio | O(1) | Reapuntar la cabeza |
| Insertar al final | O(n) | Recorrer primero hasta el final (O(1) con un puntero al final) |
| Buscar | O(n) | Seguir los punteros next |
| Eliminar la cabeza | O(1) | Reapuntar la cabeza más allá de ella |
| Acceso por índice | O(n) | Sin acceso aleatorio |
Lista enlazada vs arreglo
| Aspecto | Lista enlazada | Arreglo |
|---|---|---|
| Memoria | Nodos dispersos + punteros | Bloque contiguo |
| Acceso aleatorio | O(n) | O(1) |
| Insertar/eliminar al frente | O(1) | O(n) (desplazamiento) |
| Amigabilidad con la caché | Mala | Buena |
Ejemplo resuelto
Construir la lista [10, 20], anteponer 5 y luego eliminar 20:
| Paso | Estructura | Acción |
|---|---|---|
| Inicio | head -> null | Lista vacía |
| Insertar al principio 10 | head -> 10 -> null | Reapuntar la cabeza a un nuevo nodo cuyo next es la cabeza anterior (null) |
| Insertar al final 20 | head -> 10 -> 20 -> null | Recorrer hasta el nodo 10, poner su next en un nuevo nodo 20 |
| Insertar al principio 5 | head -> 5 -> 10 -> 20 -> null | El nuevo nodo 5 apunta a la antigua cabeza 10; la cabeza ahora apunta a 5 |
| Eliminar 20 | head -> 5 -> 10 -> null | Recorrer hasta 10, poner su next de 20 a null; el nodo 20 queda desenlazado |
Cuándo usar una lista enlazada
| Úsala cuando | Evítala cuando |
|---|---|
| Insertas o eliminas en los extremos (o en un nodo que ya tienes) mucho más de lo que indexas | Necesitas acceso aleatorio rápido por posición (indexación O(1)) |
| El tamaño cambia mucho y no quieres coste de redimensionar/copiar | Recorres bucles ajustados donde la localidad de caché domina el rendimiento |
| Estás construyendo una cola, una pila o una lista de adyacencia | La memoria es escasa: cada nodo paga un puntero extra por elemento |
| Necesitas referencias estables a nodos que sobreviven a inserciones en otros lugares | Mayormente lees y rara vez modificas, así que un arreglo es más simple y rápido |
Código de Linked List
Una implementación limpia y ejecutable de Linked List en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Linked List en Python
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.next = None5
6
7class LinkedList:8 def __init__(self):9 self.head = None10
11 def append(self, value):12 node = Node(value)13 if self.head is None:14 self.head = node15 return16 current = self.head17 while current.next:18 current = current.next19 current.next = node20
21 def find(self, value):22 current = self.head23 while current:24 if current.value == value:25 return True26 current = current.next27 return False28
29 def delete(self, value):30 # Re-link the previous node around the match31 current, prev = self.head, None32 while current:33 if current.value == value:34 if prev is None:35 self.head = current.next36 else:37 prev.next = current.next38 return True39 prev, current = current, current.next40 return False41
42 def __str__(self):43 values, current = [], self.head44 while current:45 values.append(str(current.value))46 current = current.next47 return " -> ".join(values) + " -> None"48
49
50lst = LinkedList()51for value in [3, 7, 1, 9]:52 lst.append(value)53
54print("List: ", lst)55print("find(7): ", lst.find(7))56lst.delete(1)57print("After delete(1):", lst)Código de Linked List en JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.next = null;5 }6}7
8class LinkedList {9 constructor() {10 this.head = null;11 }12
13 append(value) {14 const node = new Node(value);15 if (!this.head) {16 this.head = node;17 return;18 }19 let current = this.head;20 while (current.next) current = current.next;21 current.next = node;22 }23
24 find(value) {25 for (let n = this.head; n; n = n.next) {26 if (n.value === value) return n;27 }28 return null;29 }30
31 delete(value) {32 if (!this.head) return false;33 if (this.head.value === value) {34 this.head = this.head.next;35 return true;36 }37 // Walk to the node just before the one to remove38 for (let n = this.head; n.next; n = n.next) {39 if (n.next.value === value) {40 n.next = n.next.next;41 return true;42 }43 }44 return false;45 }46
47 toArray() {48 const out = [];49 for (let n = this.head; n; n = n.next) out.push(n.value);50 return out;51 }52}53
54const list = new LinkedList();55for (const value of [10, 20, 30, 40]) list.append(value);56console.log("List:", list.toArray().join(" -> "));57console.log("find(30):", list.find(30) !== null);58list.delete(20);59console.log("After delete(20):", list.toArray().join(" -> "));Código de Linked List en Java
Java
1public class Main {2 static class Node {3 int value;4 Node next;5 Node(int value) { this.value = value; }6 }7
8 static Node head;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = node; return; }13 Node cur = head;14 while (cur.next != null) cur = cur.next;15 cur.next = node;16 }17
18 static boolean find(int value) {19 for (Node cur = head; cur != null; cur = cur.next) {20 if (cur.value == value) return true;21 }22 return false;23 }24
25 // Unlink the first node holding value26 static void delete(int value) {27 if (head == null) return;28 if (head.value == value) { head = head.next; return; }29 Node cur = head;30 while (cur.next != null && cur.next.value != value) cur = cur.next;31 if (cur.next != null) cur.next = cur.next.next;32 }33
34 static void print() {35 StringBuilder sb = new StringBuilder();36 for (Node cur = head; cur != null; cur = cur.next) {37 sb.append(cur.value).append(" -> ");38 }39 System.out.println(sb.append("null"));40 }41
42 public static void main(String[] args) {43 append(3); append(7); append(1); append(9);44 print();45 System.out.println("find 7: " + find(7));46 delete(7);47 print();48 System.out.println("find 7: " + find(7));49 }50}Código de Linked List en C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* next = nullptr;6 explicit Node(int v) : value(v) {}7};8
9struct LinkedList {10 Node* head = nullptr;11
12 void append(int value) {13 Node* node = new Node(value);14 if (head == nullptr) {15 head = node;16 return;17 }18 Node* cur = head;19 while (cur->next != nullptr) cur = cur->next;20 cur->next = node;21 }22
23 bool find(int value) const {24 for (Node* cur = head; cur != nullptr; cur = cur->next) {25 if (cur->value == value) return true;26 }27 return false;28 }29
30 void remove(int value) {31 if (head == nullptr) return;32 if (head->value == value) { // removing the head is a special case33 Node* old = head;34 head = head->next;35 delete old;36 return;37 }38 for (Node* cur = head; cur->next != nullptr; cur = cur->next) {39 if (cur->next->value == value) {40 Node* old = cur->next;41 cur->next = old->next;42 delete old;43 return;44 }45 }46 }47
48 void print() const {49 for (Node* cur = head; cur != nullptr; cur = cur->next) {50 std::cout << cur->value << " -> ";51 }52 std::cout << "null\n";53 }54};55
56int main() {57 LinkedList list;58 for (int value : {10, 20, 30, 40}) list.append(value);59 list.print();60 std::cout << std::boolalpha << "find(30): " << list.find(30) << "\n";61 list.remove(20);62 list.remove(10);63 list.print();64 return 0;65}Código de Linked List en C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* next;8} Node;9
10Node* head = NULL;11
12void append(int value) {13 Node* node = malloc(sizeof(Node));14 node->value = value;15 node->next = NULL;16 if (head == NULL) {17 head = node;18 return;19 }20 Node* cur = head;21 while (cur->next != NULL) cur = cur->next;22 cur->next = node;23}24
25bool find(int value) {26 for (Node* cur = head; cur != NULL; cur = cur->next) {27 if (cur->value == value) return true;28 }29 return false;30}31
32void deleteValue(int value) {33 if (head == NULL) return;34 if (head->value == value) { // removing the head is a special case35 Node* old = head;36 head = head->next;37 free(old);38 return;39 }40 for (Node* cur = head; cur->next != NULL; cur = cur->next) {41 if (cur->next->value == value) {42 Node* old = cur->next;43 cur->next = old->next;44 free(old);45 return;46 }47 }48}49
50void printList(void) {51 for (Node* cur = head; cur != NULL; cur = cur->next) {52 printf("%d -> ", cur->value);53 }54 printf("NULL\n");55}56
57int main(void) {58 int values[] = {10, 20, 30, 40};59 for (int i = 0; i < 4; i++) append(values[i]);60 printList();61 printf("find(30): %s\n", find(30) ? "true" : "false");62 deleteValue(20);63 deleteValue(10);64 printList();65 return 0;66}Preguntas frecuentes sobre listas enlazadas
¿Cuál es la diferencia entre una lista enlazada y un arreglo?
Un arreglo almacena los elementos en un único bloque contiguo, lo que da acceso aleatorio
O(1) pero inserciones/eliminaciones O(n) que desplazan elementos. Una lista enlazada almacena nodos en cualquier lugar de la memoria conectados por punteros, lo que da inserciones/eliminaciones O(1) en una posición conocida pero acceso O(n) ya que debes recorrer la cadena.¿Cuándo debería usar una lista enlazada?
Las listas enlazadas brillan cuando insertas o eliminas con frecuencia en los extremos (o en un nodo del que ya tienes una referencia) y rara vez necesitas acceso aleatorio, por ejemplo colas, pilas, listas de adyacencia y cachés LRU. Si necesitas acceso indexado rápido, un arreglo o arreglo dinámico suele ser mejor.
¿Cuál es la complejidad temporal de una lista enlazada?
Insertar o eliminar en la cabeza es
O(1). Buscar, o llegar al final sin un puntero al final, es O(n) porque sigues los punteros next uno por uno. No hay acceso aleatorio O(1): indexar en una lista enlazada es O(n).¿Cuál es la diferencia entre una lista simplemente enlazada y una doblemente enlazada?
Una lista simplemente enlazada almacena solo un puntero
next por nodo, así que puedes recorrer en una dirección y eliminar un nodo requiere una referencia a su predecesor. Una lista doblemente enlazada añade un puntero prev, permitiendo el recorrido hacia atrás y la eliminación O(1) de un nodo que ya tienes, a costa de un puntero extra por nodo y más gestión en cada inserción y eliminación.¿Por qué insertar al final es O(n) si insertar al principio es O(1)?
Insertar al principio solo reconecta el puntero
head, que es trabajo constante. Llegar al final significa seguir los punteros next desde la cabeza hasta el extremo, lo cual es O(n). Mantener un puntero tail separado hace que la inserción al final también sea O(1), por lo que las listas del mundo real a menudo rastrean ambos extremos.¿Tienen las listas enlazadas inserción O(1) en todas partes?
No, esa es una idea equivocada común. La inserción en sí es
O(1) solo una vez que ya tienes un puntero al nodo después del cual insertas. Encontrar esa posición por valor o índice sigue costando O(n) porque debes recorrer la cadena para llegar allí.Recursos relacionados
Más visualizaciones
