Clase Node y construcción de listas
Defina un dataclass Node, construya listas enlazando nodos manualmente y escriba helpers de insert/delete/print para visualizar los cambios en los punteros.
Clase Node y construcción de listas es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué es una lista enlazada?
Una lista enlazada es una secuencia de nodos en la que cada nodo almacena un valor y un puntero al nodo siguiente. A diferencia de los arrays, los nodos están dispersos en la memoria: no existe acceso O(1) basado en índices. A cambio, se obtiene inserción y eliminación O(1) en cualquier posición conocida, sin desplazar elementos.
En Python representamos cada nodo con una clase pequeña que contiene val y next. Encadenar los nodos forma la lista; el next del último nodo es None para indicar el final.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build: 1 -> 2 -> 3 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
# Traverse and print
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None')Crear listas a partir de arrays
En las entrevistas, a menudo le darán una lista y le pedirán que construya su equivalente como lista enlazada, o al contrario. Conviene memorizar las funciones auxiliares build y to_list: build encadena nodos a partir de un array y to_list recorre la lista para recopilar los valores y facilitar la verificación.
Crear una lista enlazada a partir de n elementos requiere un tiempo de O(n) y un espacio de O(n). Utilizar un nodo de cabecera ficticio simplifica los casos límite en los que el primer nodo puede cambiar.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
head = build([1, 2, 3, 4, 5])
print(to_list(head)) # [1, 2, 3, 4, 5]Insertar al principio y al final
Insertar un nodo nuevo en la cabecera es O(1): cree el nodo, haga que su next apunte a la cabecera anterior y devuelva el nodo nuevo como cabecera. Insertar en la cola requiere recorrer la lista hasta el último nodo (O(n)) y enlazar después el nodo nuevo.
Utilizar un nodo de cabecera ficticia elimina el caso especial de una lista vacía en ambas inserciones, porque dummy.next siempre es la cabecera real.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_head(head, val):
return ListNode(val, head) # O(1)
def insert_tail(head, val):
new_node = ListNode(val)
if not head:
return new_node
curr = head
while curr.next:
curr = curr.next
curr.next = new_node
return head
head = None
for v in [1, 2, 3]:
head = insert_tail(head, v)
head = insert_head(head, 0)
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None') # 0 -> 1 -> 2 -> 3 -> NoneEliminar un nodo por valor
Para eliminar el primer nodo con un valor determinado, mantenga un puntero prev una posición detrás de curr. Cuando curr.val == target, establezca prev.next = curr.next para saltarse el nodo. Una cabecera ficticia resulta especialmente útil aquí porque elimina el caso especial de eliminar el nodo que es la cabecera real: prev siempre puede comenzar en la cabecera ficticia.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_val(head, target):
dummy = ListNode(0)
dummy.next = head
prev, curr = dummy, head
while curr:
if curr.val == target:
prev.next = curr.next
break
prev, curr = curr, curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
head = None
for v in [1, 2, 3, 2, 4]:
dummy2 = ListNode(v)
dummy2.next = head
head = dummy2 # build in reverse for speed
head = delete_val(head, 2)
print(to_list(head))Visualizar los cambios en los punteros
Un error común es perder de vista un nodo al actualizar los punteros. Guarde siempre next antes de sobrescribirlo: saved = curr.next y, después, reasígnelo. Dibuje la lista como cajas conectadas mediante flechas y simule en papel cada actualización de punteros antes de programar. Este enfoque visual evita errores accidentales de puntero nulo durante las entrevistas.
Recuerde que, en Python, reasignar curr.next no afecta al propio curr, pero perder la referencia a curr.next antes de guardarla significa que ya no podrá recorrer la lista hacia delante.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Demonstrate safe pointer update
def swap_first_two(head):
if not head or not head.next:
return head
first = head
second = head.next
# Save third before losing the reference
third = second.next
# Rewire
second.next = first
first.next = third
return second
from functools import reduce
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = swap_first_two(nodes[0])
curr = head
while curr:
print(curr.val, end=' ')
curr = curr.next
# 2 1 3 4Listas enlazadas simples frente a dobles
Una lista enlazada simple almacena únicamente un puntero next; el recorrido es unidireccional. Una lista doblemente enlazada almacena tanto prev como next, lo que permite recorrerla hacia atrás en O(1) y eliminar en O(1) cuando se dispone de una referencia directa al nodo (sin necesidad del bucle que mantiene el puntero prev).
collections.deque de Python está implementado como una lista doblemente enlazada, por lo que admite appendleft y popleft en O(1). En las entrevistas implementará listas enlazadas simples; las listas doblemente enlazadas aparecen en el diseño de cachés LRU.
class DLNode:
def __init__(self, val=0):
self.val = val
self.prev = None
self.next = None
# Build doubly linked: 1 <-> 2 <-> 3
a, b, c = DLNode(1), DLNode(2), DLNode(3)
a.next = b; b.prev = a
b.next = c; c.prev = b
# Traverse forward
curr = a
while curr:
print(curr.val, end=' <-> ')
curr = curr.next
print('None')
# Traverse backward from c
curr = c
while curr:
print(curr.val, end=' <-> ')
curr = curr.prev
print('None')Funciones auxiliares para longitud, cola e impresión
Tres funciones auxiliares que debería tener preparadas para cualquier entrevista sobre listas enlazadas: length(head) cuenta los nodos en O(n), tail(head) devuelve el último nodo en O(n) y print_list(head) da formato a la lista para depurarla. Tenerlas listas le permite centrarse en el algoritmo principal en lugar de volver a implementar la lógica auxiliar.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def length(head):
count = 0
while head:
count += 1
head = head.next
return count
def tail(head):
while head and head.next:
head = head.next
return head
def print_list(head):
parts = []
while head:
parts.append(str(head.val))
head = head.next
print(' -> '.join(parts) + ' -> None')
# Build and test
nodes = [ListNode(i) for i in [10, 20, 30, 40]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = nodes[0]
print('Length:', length(head))
print('Tail:', tail(head).val)
print_list(head)Configurar dos punteros en listas enlazadas
La técnica de los dos punteros es tan importante para las listas enlazadas como para los arrays, pero los punteros son nodos de la lista enlazada en lugar de índices. Entre las configuraciones habituales se encuentran un puntero lento y uno rápido (el rápido avanza al doble de velocidad) para encontrar puntos medios y detectar ciclos, y un par de predecesor y actual para eliminar e invertir.
Inicialice siempre ambos punteros de forma explícita y compruebe con cuidado la terminación por valor nulo: fast and fast.next evita errores de puntero nulo cuando fast está cerca del final.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Find middle node using slow-fast pointers
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length, returns second of two middle nodes
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
print(find_middle(nodes[0]).val) # 3 (middle of 1->2->3->4->5)El patrón de la cabecera ficticia
El patrón de la cabecera ficticia (nodo centinela) es uno de los trucos más útiles en los problemas de listas enlazadas. Al anteponer un nodo ficticio con valor 0, nunca tendrá que tratar de forma especial una lista vacía ni un cambio en la cabecera real. El resultado siempre es dummy.next. Este patrón aparece al fusionar listas ordenadas, eliminar el nodo n desde el final, particionar una lista y en muchos otros problemas.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Remove all nodes with val == target (may include head)
def remove_all(head, target):
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next:
if curr.next.val == target:
curr.next = curr.next.next # skip the node
else:
curr = curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
nodes = [ListNode(v) for v in [1, 2, 6, 3, 4, 5, 6]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = remove_all(nodes[0], 6)
print(to_list(head)) # [1, 2, 3, 4, 5]Complejidad temporal y espacial
La mayoría de las operaciones con listas enlazadas tienen estas complejidades. Acceso por índice: O(n), porque debe recorrer la lista desde la cabecera. Insertar o eliminar en un nodo conocido: O(1), porque solo hay que volver a enlazar los punteros. Insertar o eliminar en la posición k: O(k), porque primero hay que recorrer la lista. Búsqueda: O(n), en el peor caso se recorre toda la lista. El espacio es O(1) para todas las operaciones in situ (sin contar estructuras de datos adicionales).
Compárelo con los arrays: ofrecen acceso O(1), pero insertar o eliminar cuesta O(n) debido al desplazamiento. Las listas enlazadas son mejores cuando las inserciones y eliminaciones en posiciones arbitrarias son frecuentes.
Consejos para entrevistas sobre listas enlazadas
Antes de escribir código para una lista enlazada, dibuje visualmente la lista con cajas y flechas. Confirme en voz alta los casos límite: lista vacía, un solo nodo y longitud par frente a impar. Utilice una cabecera ficticia para simplificar las condiciones de los límites. Compruebe siempre if not head al principio. Después de programar, siga el recorrido de su solución sobre una lista de tres nodos para detectar errores de punteros antes que el entrevistador.
La mayoría de los errores en listas enlazadas procede de una de estas tres causas: olvidar guardar next antes de sobrescribirlo, cometer un error de posición en la condición de terminación o no gestionar el caso límite en el que cambia la cabecera; el nodo ficticio elimina por completo la tercera causa.
Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Repaso de la lección
En esta lección ha aprendido que: una lista enlazada se construye a partir de objetos Node con los campos val y next, el patrón de la cabecera ficticia elimina los casos límite en los que cambia la cabecera y la configuración de dos punteros lento-rápido es la base para encontrar puntos medios y detectar ciclos. A continuación abordaremos cómo invertir una lista enlazada, uno de los problemas de punteros más habituales en las entrevistas.
Preguntas frecuentes
¿La lección «Clase Node y construcción de listas» es gratis?
Sí — el texto completo de «Clase Node y construcción de listas» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Clase Node y construcción de listas»?
Defina un dataclass Node, construya listas enlazando nodos manualmente y escriba helpers de insert/delete/print para visualizar los cambios en los punteros. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «Clase Node y construcción de listas»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Clase Node y construcción de listas
- Inversión de una lista enlazada
- Detección de ciclos con el algoritmo de Floyd
- Combinar, dividir y encontrar el enésimo elemento desde el final