Linked lists · Listas enlazadas
Nodes joined by links
- A linked list is a chain of nodes.
- Each node holds a piece of data and a link to the next node.
- The last node links to
None, which marks the end.
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.
A node is a small record
- We can store one node in a dictionary:
{"data": ..., "next": ...}. "data"holds the value;"next"holds the next node (orNone).- The first node is called the head of the list.
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"])
Walk the list
- Start at the head and follow each
"next"link. - Stop when you reach
None. - This visiting of every node is called traversal.
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"]
Why a linked list?
- You can insert or remove a node by changing links — no shifting of items.
- An array would have to move every item after the change.
- But a linked list has no index: to reach item 5 you must walk from the head.
¿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.
In Cambridge pseudocode
- The exam stores nodes in an array;
Nextis the index of the next node, andNULLmarks the end.
En pseudocódigo de Cambridge
- El examen almacena los nodos en un array;
Nextes el índice del siguiente nodo, yNULLmarca el final.
TYPE Node
DECLARE Data : INTEGER
DECLARE Next : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].Next
ENDWHILE
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - The last node points to
None.
Errores comunes
- Nunca pierda el puntero
head, de lo contrario toda la lista será inaccesible. - El último nodo apunta a
None.
Now you try
- A node is a dict
{"data": ..., "next": ...}. Follow"next"to walk the chain. - Press Check answer to test your code.
Ahora practique
- Un nodo es un dict
{"data": ..., "next": ...}. Siga"next"para recorrer la cadena. - Pulse Check answer para probar su código.
Nodes linked by pointers · Nodos enlazados por punteros
Each node points to the next; you insert/delete by re-linking. · Cada nodo apunta al siguiente; insertar/eliminar implica re-enlazar.
Build a linked list 1 → 2 → 3 using dictionaries. Make the three nodes, link each to the next, and point head at the first one. The last node's "next" must be None. · 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.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Walk the linked list starting at head and add up every node's "data". Store the total in total (the answer is 60). · Recorre la lista enlazada empezando por head y suma el "data" de cada nodo. Almacena el total en total (la respuesta es 60).
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Write length(head) that returns · retornos how many nodes are in the linked list. An empty list (head is None) has length 0. · Escribe length(head) que devuelva cuántos nodos hay en la lista enlazada. Una lista vacía (head es None) tiene longitud 0.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.