Listas enlazadas
Nodos unidos por enlaces
- Una lista enlazada es una cadena de nodos.
- Cada nodo contiene un trozo de datos y un enlace al siguiente nodo.
- El último nodo enlacea a
None, lo cual marca el final.
Un nodo es un pequeño registro
- Podemos almacenar un nodo en un diccionario:
{"data": ..., "next": ...}. "data"contiene el valor;"next"contiene el siguiente nodo (oNone).- El primer nodo se denomina cabeza de la lista.
second = {"data": "b", "next": None}
first = {"data": "a", "next": second}
print(first["data"])
print(first["next"]["data"])
Recorrer la lista
- Comience en la cabeza y siga cada enlace
"next". - Deténgase cuando llegue a
None. - A esta visita de cada nodo se le llama recorrido.
head = {"data": 1, "next": {"data": 2, "next": None}}
node = head
while node is not None:
print(node["data"])
node = node["next"]
¿Por qué usar una lista enlazada?
- Puede insertar o eliminar un nodo cambiando los enlaces, sin necesidad de desplazar elementos.
- Un array tendría que mover todos los elementos posteriores al cambio.
- Sin embargo, una lista enlazada no tiene índice: para acceder al elemento 5 debe recorrer desde la cabeza.
En pseudocódigo de Cambridge
- El examen almacena los nodos en un array;
NextIndexes el índice del siguiente nodo, yNULLmarca el final.
TYPE Node
DECLARE Data : INTEGER
DECLARE NextIndex : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].NextIndex
ENDWHILE
Errores comunes
- Nunca pierda el puntero
head, de lo contrario toda la lista será inaccesible. - El último nodo apunta a
None.
Ahora tú prueban
- Un nodo es un dict
{"data": ..., "next": ...}. Siga"next"para recorrer la cadena. - Pulsa Check answer para probar tu código.
Nodos enlazados por punteros
Cada nodo apunta al siguiente; insertar/eliminar implica re-enlazar.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Construye una lista enlazada 1 → 2 → 3 usando diccionarios. Crea los tres nodos, enlaza cada uno al siguiente y señala head hacia el primero. El "next" del último nodo debe ser None.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Recorre la lista enlazada empezando por head y suma el "data" de cada nodo. Almacena el total en total (la respuesta es 60).
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Escribe length(head) que devuelva cuántos nodos hay en la lista enlazada. Una lista vacía (head es None) tiene longitud 0.
Haz clic en Ejecutar para ver la salida aquí.