Lección 10: Listas enlazadas
Imagina una búsqueda del tesoro: cada nota tiene un valor y una pista hacia la siguiente nota, y para llegar a la quinta hay que ir de una en una. Eso es una 'lista enlazada' (linked list): una cadena de 'nodos'. La ventaja: insertar o eliminar en el medio es O(1), solo redireccionas una pista. La d
Una lista enlazada es como una búsqueda del tesoro: cada nota tiene un valor y una pista de a dónde ir después. Para llegar a la quinta nota debes seguir las pistas una por una: no puedes saltar directo al medio como en un array, donde puedes llegar a cualquier lugar de inmediato.
- clase (class)
- Una plantilla para una pequeña caja con campos. class Node define una caja con dos campos: val (el valor) y next (un puntero al siguiente nodo). Node(1) crea una caja así, y self simplemente significa "esta caja".
- lista enlazada
- Una estructura de datos de nodos, cada uno con un valor y un puntero next al siguiente nodo; inserción/eliminación junto a un nodo conocido en O(1), pero acceso por posición en O(n).
- nodo (node)
- La pieza fundamental de una lista enlazada: un pequeño objeto con un valor (val) y un puntero (next) al siguiente nodo, o None al final.
- localidad de caché (cache locality)
- Cuán cerca en memoria se guardan datos que se usan juntos; un array contiguo es amigable con la caché, mientras que los nodos dispersos de una lista enlazada lo son menos.
