Nodos
Cada elemento es un nodo con dos partes: el dato y la referencia al siguiente nodo.
Listas ligadas
Representación en memoria, listas con cabecera y listas dobles
Diego Ronaldo Sánchez Pichardo 219961
Gael Mateo Pérez Montejo 219957
Materia Estructura de datos
Docente Mateo Sánchez Méndez
Grupo K014
P2-Actividad colaborativa
11 de noviembre de 2026
¿Qué es una lista ligada?
Cabeza y fin
La lista se conoce por su primer nodo, la cabeza. El último apunta a None.
Dinámica
Crece y se reduce en tiempo de ejecución; no hay que reservar un tamaño fijo.
Es una estructura lineal: el orden lo dan los enlaces entre nodos, no la posición en memoria.
Los nodos están dispersos, los enlaces los unen
| Dirección | Dato | Siguiente |
|---|---|---|
| 0x1A0 | 12 | 0x3F8 |
| 0x1B8 | ocupado | otro programa |
| 0x2C4 | 41 | None |
| 0x310 | libre | |
| 0x3F8 | 27 | 0x2C4 |
cabeza = 0x1A0
120x1A0
270x3F8
410x2C4
None
Cada nodo se crea donde el sistema encuentre espacio libre. Para recorrer la lista se empieza en la cabeza y se sigue el campo siguiente hasta llegar a None.
Arreglo contiguo frente a lista ligada
Arreglo
120x100270x104410x108580x10C
- Casillas seguidas en memoria
- Acceso directo por índice en O(1)
- Insertar en medio obliga a desplazar elementos
- Tamaño reservado de antemano
Lista ligada
120x1A0270x3F8410x2C4580x0F0
- Nodos en cualquier lugar libre
- Acceso secuencial desde la cabeza en O(n)
- Insertar o eliminar solo cambia enlaces en O(1)
- Usa memoria extra para cada referencia
Insertar y eliminar es cambiar flechas
Insertar 20 después de 12
- Crear el nodo 20.
- nuevo.siguiente apunta a 27.
- 12.siguiente apunta al nuevo.
Eliminar 27
- Ubicar el nodo anterior, 12.
- 12.siguiente apunta a 41.
- El nodo 27 queda sin referencias y se libera.
Un nodo cabecera que siempre está
CABconteo = 3
12
27
41
None
Qué es
Un nodo especial al inicio que no guarda un dato de la lista. Puede guardar información como el número de nodos.
Ventaja
Insertar o eliminar al inicio es igual que en medio: siempre hay un nodo anterior y no hay que cambiar la cabeza.
Lista vacía
Nunca es None: es la cabecera sola, con siguiente igual a None. Así se evitan casos especiales en el código.
Lista circular con cabecera
El último nodo no apunta a None: regresa a la cabecera.
El recorrido termina cuando se vuelve a llegar a la cabecera, que funciona como centinela.
Sirve para procesos que dan vueltas, como turnos o una lista de reproducción.
Dos enlaces por nodo: anterior y siguiente
None
ant12sig
ant27sig
ant41sig
None
Recorrido
Se avanza con siguiente desde la cabeza y se regresa con anterior desde la cola.
Insertar entre A y B
nuevo.ant = A, nuevo.sig = B, A.sig = nuevo y B.ant = nuevo. Son cuatro enlaces.
Eliminar X
X.ant.sig = X.sig y X.sig.ant = X.ant. No hace falta buscar el nodo anterior.
Así lo programamos
class Nodo: def __init__(self, dato): self.dato = dato self.ant = None self.sig = None class ListaDoble: def __init__(self): self.cabeza = None self.cola = None
def agregar_final(self, dato): nuevo = Nodo(dato) if self.cabeza is None: self.cabeza = self.cola = nuevo else: nuevo.ant = self.cola self.cola.sig = nuevo self.cola = nuevo def recorrer_inverso(self): actual = self.cola while actual: print(actual.dato) actual = actual.ant
Lista doble en vivo
Hacia adelante:
Hacia atrás:
¿Cuál conviene usar?
| Arreglo | Lista simple | Lista con cabecera | Lista doble | |
|---|---|---|---|---|
| Enlaces por nodo | 0 | 1 | 1 y un nodo extra | 2 |
| Acceso al elemento i | O(1) | O(n) | O(n) | O(n) |
| Insertar al inicio | O(n) | O(1) | O(1) sin caso especial | O(1) |
| Eliminar un nodo conocido | O(n) | O(n), busca el anterior | O(n), busca el anterior | O(1) |
| Recorrido | Ambos sentidos | Solo adelante | Solo adelante | Ambos sentidos |
| Uso típico | Tablas fijas | Pilas y colas | Listas que cambian al inicio | Historial adelante y atrás |
Lo que nos llevamos
Referencias
Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. (2022). Introduction to algorithms (4.a ed.). MIT Press.
Goodrich, M. T., Tamassia, R. y Goldwasser, M. H. (2013). Data structures and algorithms in Python. Wiley.
Joyanes Aguilar, L. y Zahonero Martínez, I. (2008). Estructuras de datos en Java. McGraw-Hill.
Python Software Foundation. (2026). Documentación de Python 3. https://docs.python.org/es/3/
Gracias. ¿Preguntas?