Listas enlazadas: nodos y enlaces

Una lista enlazada es una serie de nodos, y cada nodo guarda un valor y un enlace al nodo siguiente. A diferencia de un array, sus nodos pueden estar en cualquier parte de la memoria, e insertar delante no desplaza nada.

Piensa en una línea de autobús: cada parada sabe cuál es la siguiente, aunque estén lejos unas de otras.

Para crear nodos usamos una clase, un molde para objetos que tienen los mismos campos. Node tiene dos: value, el dato, y next, el enlace.

Al crearlo, next vale None: todavía no apunta a nada. Para unir dos nodos, asignas el segundo al next del primero.

# Un nodo guarda un valor y un enlace al siguiente.
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

# Tres paradas de una línea de autobús, enlazadas.
a = Node("Plaza Mayor")
b = Node("Hospital")
c = Node("Universidad")
a.next = b
b.next = c

stop = a
while stop is not None:
    print(stop.value)
    stop = stop.next
# Crea Node("Estación") y enlázalo delante de a.

python3 -c "a = [1, 2]; b = a; b.append(3); print(a, a is b)"

python3 -c "n = {'value': 1, 'next': None}; m = {'value': 2, 'next': n}; print(m['next']['value'])"

Una lista enlazada solo conoce su cabeza. Para llegar al nodo número 100, sigues cien enlaces, uno tras otro.

No hay índice ni cuenta de posición: leer el elemento de la posición n cuesta n pasos. Es el precio de no necesitar un bloque seguido.

Para insertar delante, el nodo nuevo apunta a la cabeza vieja y pasa a ser la cabeza. Son dos asignaciones, sea cual sea la longitud.

Para insertar detrás de un nodo, primero haces que el nuevo apunte al siguiente, y después haces que el nodo apunte al nuevo. El orden importa: si lo inviertes, pierdes el resto de la lista.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

head = Node(30)
head.next = Node(40)

# Insertar delante: el nuevo apunta a la cabeza vieja.
new = Node(20)
new.next = head
head = new

# Insertar detrás de un nodo: se cambian dos enlaces.
after = Node(35)
after.next = head.next.next
head.next.next = after

stop = head
while stop is not None:
    print(stop.value)
    stop = stop.next

Para invertir una lista recorres sus nodos y haces que cada uno apunte al anterior. Necesitas tres nombres: previous, current y following.

En cada vuelta guardas following, giras el enlace de current hacia previous, y avanzas los dos nombres un nodo. Al final, previous es la nueva cabeza.

Escribe remove(head, value), que quita el primer nodo con ese valor y devuelve la cabeza. Hay dos casos: que sea la cabeza, o que esté más adentro.

Para el segundo caso necesitas mirar un nodo por detrás. Piensa por qué quitar un nodo es barato, pero encontrarlo no.