Las estructuras encadenadas en Python son el último bloque de FP2 y el que más peso tiene en el segundo parcial. La mayoría de la gente llega aquí con el concepto de nodo sin terminar de cuajar, entiende las palabras por separado pero no consigue visualizar cómo funciona la cadena entera.

En este artículo vamos desde el principio absoluto: qué son las LinkedList en Python, qué es un nodo de verdad, cómo se conectan, y cómo se implementa cada operación con su diagrama paso a paso.

Tabla de Contenidos

Antes de empezar — qué problema resuelven las estructuras encadenadas

Cuando usas una lista de Python [1, 2, 3, 4, 5], Python guarda todos los elementos en posiciones de memoria consecutivas, como una fila de casillas numeradas:

Posición:  [0]  [1]  [2]  [3]  [4]
Valor:      1    2    3    4    5

Eso tiene una ventaja enorme: acceder al elemento 3 es instantáneo porque Python calcula directamente su posición en memoria. Pero tiene un coste oculto: insertar o eliminar en el medio es caro, Python tiene que desplazar todos los elementos que vienen después.

Insertar 99 en posición 2:
Antes:  [1]  [2]  [3]  [4]  [5]
        ← desplazar todo →
Después: [1]  [2]  [99] [3]  [4]  [5]

Con un millón de elementos, insertar al principio significa mover un millón de valores en memoria.

Las estructuras encadenadas resuelven exactamente ese problema, insertar y eliminar en cualquier posición es siempre igual de rápido, sin mover nada. El coste que pagan por eso es que acceder a un elemento concreto requiere recorrer la lista desde el principio.

Lista de Python: acceso por índice rápido, inserción/borrado en medio lento
LinkedList:      acceso por índice lento, inserción/borrado en cualquier punto rápido

En FP2 no usamos LinkedList porque sea siempre mejor, la usamos para entender cómo se gestionan las referencias en memoria, que es la base de las estructuras de datos complejas.

Qué es un nodo — la unidad básica

Un nodo es la pieza más pequeña de una estructura encadenada. Cada nodo contiene exactamente dos cosas:

El valor que guarda (un número, una cadena, cualquier objeto)
Una referencia al siguiente nodo — o None si es el último

Nada más. Un nodo no sabe cuántos elementos hay en la lista. No sabe en qué posición está. Solo sabe su valor y quién viene después de él.

┌──────────┬──────────┐
│  valor   │siguiente │
│    10    │  ──────► │ → (apunta al siguiente nodo)
└──────────┴──────────┘

┌──────────┬──────────┐
│  valor   │siguiente │
│    10    │   None   │   (último nodo — no hay siguiente)
└──────────┴──────────┘

Por qué necesita su propia clase: porque es un objeto con dos atributos propios que tiene que existir de forma independiente en memoria. No es un número, no es una tupla, es un objeto que guarda un valor y sabe a quién apunta.

class Nodo:
    def __init__(self, valor, siguiente=None):
        self.valor = valor
        self.siguiente = siguiente

Solo eso. La clase Nodo tiene dos atributos: valor y siguiente. El parámetro siguiente tiene valor por defecto None porque cuando creas un nodo nuevo normalmente todavía no sabes quién viene después.

Puedes crear nodos y encadenarlos manualmente para ver cómo funciona:

# Crear tres nodos sueltos
nodo1 = Nodo(10)
nodo2 = Nodo(20)
nodo3 = Nodo(30)

# Encadenarlos a mano
nodo1.siguiente = nodo2
nodo2.siguiente = nodo3
# nodo3.siguiente sigue siendo None — es el último

print(nodo1.valor)              # → 10
print(nodo1.siguiente.valor)    # → 20
print(nodo1.siguiente.siguiente.valor)    # → 30
print(nodo1.siguiente.siguiente.siguiente)  # → None

nodo1              nodo2              nodo3
┌────┬────────┐   ┌────┬────────┐   ┌────┬──────┐
│ 10 │   ──────►  │ 20 │   ──────►  │ 30 │ None │
└────┴────────┘   └────┴────────┘   └────┴──────┘

Eso ya es una lista encadenada, tres nodos conectados en cadena. Solo falta envolverlos en una clase que gestione el conjunto.

Cómo se enlazan los nodos en memoria

Lo que en el diagrama ves como una flecha ──► es en realidad una referencia, la dirección de memoria donde está el siguiente nodo. Cuando haces nodo1.siguiente = nodo2 no estás copiando nodo2 dentro de nodo1, estás guardando en nodo1.siguiente la dirección donde está nodo2 en la memoria de Python.

Esto tiene una consecuencia importante: los nodos pueden estar en cualquier parte de la memoria, no tienen que ser posiciones consecutivas como en una lista de Python. Por eso insertar en el medio es tan barato: solo cambias a qué apuntan dos referencias, sin mover ningún dato.

Memoria RAM (ejemplo):
  posición 0x1000: nodo con valor 10, siguiente → 0x2500
  posición 0x2500: nodo con valor 20, siguiente → 0x0800
  posición 0x0800: nodo con valor 30, siguiente → None

Los nodos están dispersos en memoria — la cadena los une con referencias

La clase LinkedList — qué necesita

La clase LinkedList no guarda los elementos directamente, guarda una referencia al primer nodo de la cadena. A ese primer nodo se le llama cabeza (head o primero). Con esa sola referencia puedes llegar a cualquier elemento, siguiendo la cadena de siguiente en siguiente.

LinkedList
┌──────────┐
│ primero ─────► ┌────┬───┐   ┌────┬───┐   ┌────┬──────┐
└──────────┘     │ 10 │ ──────► 20 │ ──────► 30 │ None │
                 └────┴───┘   └────┴───┘   └────┴──────┘

Si la lista está vacía, primero vale None:

LinkedList
┌──────────┐
│ primero  │ → None
└──────────┘

class LinkedList:
    class Nodo:
        def __init__(self, valor, siguiente=None):
            self.valor = valor
            self.siguiente = siguiente

    def __init__(self):
        self.__primero = None
        self.__longitud = 0

Fíjate en que Nodo está dentro de LinkedList como clase anidada, en FP2 así es como aparece en el PDF. Es una clase interna porque los nodos son un detalle de implementación que no debería usarse desde fuera de la lista.

Operación 1 — Insertar al principio

Insertar al principio es la operación más sencilla y la más rápida. El proceso tiene siempre dos pasos:

Crear el nuevo nodo apuntando al actual primero
El nuevo nodo pasa a ser el primero

Antes de insertar 5:
primero ──► [10] ──► [20] ──► [30] ──► None

Paso 1 — crear nodo con siguiente = primero actual:
nuevo ──► [5] ──► [10] ──► [20] ──► [30] ──► None

Paso 2 — primero ahora apunta al nuevo nodo:
primero ──► [5] ──► [10] ──► [20] ──► [30] ──► None

El orden de los pasos importa mucho. Si primero actualizas primero y luego intentas conectar el nuevo nodo al siguiente, pierdes la referencia al resto de la lista. Primero conectas, luego actualizas.

def insertar_delante(self, valor):
    nuevo = self.Nodo(valor, self.__primero)  # paso 1: conectar al actual primero
    self.__primero = nuevo                    # paso 2: el nuevo es el primero
    self.__longitud += 1

O en una sola línea:

def insertar_delante(self, valor):
    self.__primero = self.Nodo(valor, self.__primero)
    self.__longitud += 1

Operación 2 — Insertar al final

Insertar al final requiere recorrer toda la lista hasta llegar al último nodo, el que tiene siguiente = None, y conectar el nuevo nodo ahí.

Antes de insertar 40 al final:
primero ──► [10] ──► [20] ──► [30] ──► None

Recorremos hasta el último nodo (el que tiene siguiente=None):
                              actual
primero ──► [10] ──► [20] ──► [30] ──► None

Conectamos el nuevo nodo:
primero ──► [10] ──► [20] ──► [30] ──► [40] ──► None

Hay un caso especial: si la lista está vacía, el nuevo nodo es directamente el primero.

def insertar_detras(self, valor):
    nuevo = self.Nodo(valor)

    if self.__primero is None:          # lista vacía — caso especial
        self.__primero = nuevo
    else:
        actual = self.__primero
        while actual.siguiente is not None:   # avanzar hasta el último
            actual = actual.siguiente
        actual.siguiente = nuevo         # conectar el nuevo al final
    self.__longitud += 1

El while actual.siguiente is not None es el patrón de recorrido más importante de LinkedList, memorízalo porque aparece en casi todas las operaciones.

Operación 3 — Recorrer la lista

Recorrer la lista nodo a nodo siempre sigue el mismo patrón: empiezas en primero y avanzas con actual = actual.siguiente hasta que actual sea None.

primero ──► [10] ──► [20] ──► [30] ──► None
   actual=10 → actual=20 → actual=30 → actual=None → STOP

def __str__(self):
    """Muestra la lista como: 10 → 20 → 30 → None"""
    elementos = []
    actual = self.__primero
    while actual is not None:
        elementos.append(str(actual.valor))
        actual = actual.siguiente
    return ' → '.join(elementos) + ' → None'

def __len__(self):
    return self.__longitud

def __iter__(self):
    """Permite usar la lista en un for."""
    actual = self.__primero
    while actual is not None:
        valor = actual.valor
        actual = actual.siguiente
        yield valor

Fíjate en __iter__, guardamos actual.siguiente antes del yield porque el generador se pausa en yield y si alguien modifica la lista mientras la recorre podría haber problemas. Es el patrón seguro.

Operación 4 — Buscar un elemento

La búsqueda recorre la lista comparando cada valor hasta encontrar el elemento o llegar al final.

Buscar 20 en: [10] ──► [20] ──► [30] ──► None

actual=[10] → 10 != 20 → avanzar
actual=[20] → 20 == 20 → encontrado → devolver True (o el nodo)

def contiene(self, valor):
    """Devuelve True si el valor está en la lista."""
    actual = self.__primero
    while actual is not None:
        if actual.valor == valor:
            return True
        actual = actual.siguiente
    return False    # llegamos al final sin encontrarlo

Operación 5 — Eliminar un elemento

Eliminar es la operación que más cuesta visualizar. La clave es entender que para eliminar un nodo no necesitas borrarlo — solo necesitas que el nodo anterior deje de apuntar a él y apunte directamente al siguiente.

Eliminar 20 de: [10] ──► [20] ──► [30] ──► None

Antes:
[10].siguiente ──► [20]
[20].siguiente ──► [30]

Después de eliminar [20]:
[10].siguiente ──► [30]   ← saltamos el nodo 20

El nodo [20] sigue existiendo en memoria pero ya nadie apunta a él
Python lo eliminará automáticamente (garbage collector)

Hay tres casos que manejar:

Caso 1 — Eliminar el primero:

primero ──► [10] ──► [20] ──► [30] ──► None
                ↑
           eliminar este

primero ──► [20] ──► [30] ──► None

Caso 2 — Eliminar un nodo en el medio:

[10] ──► [20] ──► [30] ──► None
              ↑
         eliminar este

[10] ──► [30] ──► None

Caso 3 — Eliminar el último:

[10] ──► [20] ──► [30] ──► None
                       ↑
                  eliminar este

[10] ──► [20] ──► None

def eliminar(self, valor):
    """Elimina la primera ocurrencia del valor. Lanza ValueError si no existe."""

    if self.__primero is None:
        raise ValueError(f"{valor} no está en la lista")

    # Caso 1 — el valor está en el primer nodo
    if self.__primero.valor == valor:
        self.__primero = self.__primero.siguiente    # primero apunta al segundo
        self.__longitud -= 1
        return

    # Casos 2 y 3 — buscar el nodo ANTERIOR al que queremos eliminar
    anterior = self.__primero
    actual = self.__primero.siguiente

    while actual is not None:
        if actual.valor == valor:
            anterior.siguiente = actual.siguiente    # saltamos el nodo actual
            self.__longitud -= 1
            return
        anterior = actual
        actual = actual.siguiente

    raise ValueError(f"{valor} no está en la lista")

El patrón anterior / actual que avanza en pareja es la clave de la eliminación:

anterior ──► actual ──► siguiente
   [10]  ──►  [20] ──►   [30]

Si queremos eliminar actual (20):
anterior.siguiente = actual.siguiente
   [10].siguiente  =      [30]

Resultado: [10] ──► [30]  (el [20] queda aislado)

La clase completa

class LinkedList:
    """Lista simplemente encadenada."""

    class Nodo:
        def __init__(self, valor, siguiente=None):
            self.valor = valor
            self.siguiente = siguiente

    def __init__(self):
        self.__primero = None
        self.__longitud = 0

    def insertar_delante(self, valor):
        """Inserta al principio en O(1)."""
        self.__primero = self.Nodo(valor, self.__primero)
        self.__longitud += 1

    def insertar_detras(self, valor):
        """Inserta al final en O(n)."""
        nuevo = self.Nodo(valor)
        if self.__primero is None:
            self.__primero = nuevo
        else:
            actual = self.__primero
            while actual.siguiente is not None:
                actual = actual.siguiente
            actual.siguiente = nuevo
        self.__longitud += 1

    def eliminar(self, valor):
        """Elimina la primera ocurrencia. Lanza ValueError si no existe."""
        if self.__primero is None:
            raise ValueError(f"{valor} no está en la lista")

        if self.__primero.valor == valor:
            self.__primero = self.__primero.siguiente
            self.__longitud -= 1
            return

        anterior = self.__primero
        actual = self.__primero.siguiente
        while actual is not None:
            if actual.valor == valor:
                anterior.siguiente = actual.siguiente
                self.__longitud -= 1
                return
            anterior = actual
            actual = actual.siguiente

        raise ValueError(f"{valor} no está en la lista")

    def contiene(self, valor):
        """Devuelve True si el valor está en la lista."""
        actual = self.__primero
        while actual is not None:
            if actual.valor == valor:
                return True
            actual = actual.siguiente
        return False

    def es_vacia(self):
        return self.__primero is None

    def __len__(self):
        return self.__longitud

    def __iter__(self):
        actual = self.__primero
        while actual is not None:
            valor = actual.valor
            actual = actual.siguiente
            yield valor

    def __str__(self):
        return ' → '.join(str(v) for v in self) + ' → None'

    def __repr__(self):
        return f'LinkedList({list(self)})'

    def __contains__(self, valor):
        return self.contiene(valor)

LinkedList vs lista de Python — cuándo usar cada una

                    Lista Python    LinkedList
─────────────────────────────────────────────
Acceso por índice:     O(1) ✓         O(n) ✗
Insertar al principio: O(n) ✗         O(1) ✓
Insertar al final:     O(1) ✓         O(n) ✗
Insertar en el medio:  O(n) ✗         O(1) ✓ (si ya tienes el nodo anterior)
Buscar un elemento:    O(n)           O(n)
Memoria:               más eficiente  menos eficiente (cada nodo tiene el puntero)

En FP2 la LinkedList no se usa porque sea mejor en todo, se usa para aprender a gestionar referencias y punteros, que es la base de árboles, grafos y otras estructuras que veremos en cursos posteriores.

Visualízalo con Python Tutor

Las LinkedList son donde Python Tutor más brilla de todo el curso, puedes ver exactamente cómo cada nodo apunta al siguiente y cómo las referencias cambian al insertar o eliminar. Ve a pythontutor.com y pega:

class Nodo:
    def __init__(self, valor, siguiente=None):
        self.valor = valor
        self.siguiente = siguiente

# Construir una lista de 3 nodos manualmente
n1 = Nodo(10)
n2 = Nodo(20)
n3 = Nodo(30)

n1.siguiente = n2
n2.siguiente = n3

# Recorrer
actual = n1
while actual is not None:
    print(actual.valor)
    actual = actual.siguiente

Ejecuta paso a paso y observa cómo actual va saltando de nodo en nodo siguiendo las flechas. Luego modifica el código para insertar un nodo nuevo entre n1 y n2, verás exactamente qué referencias cambian.

Resumen rápido

# NODO — la unidad básica
class Nodo:
    def __init__(self, valor, siguiente=None):
        self.valor = valor        # el dato
        self.siguiente = siguiente  # referencia al siguiente nodo o None

# ESTRUCTURA DE UNA LISTA ENCADENADA
# primero ──► [v1] ──► [v2] ──► [v3] ──► None
# Solo se guarda una referencia al primer nodo
# Para llegar a cualquier elemento hay que recorrer desde el principio

# INSERTAR AL PRINCIPIO — O(1)
nuevo = Nodo(valor, primero)   # conectar al actual primero
primero = nuevo                 # el nuevo es ahora el primero

# INSERTAR AL FINAL — O(n)
actual = primero
while actual.siguiente is not None:   # avanzar hasta el último
    actual = actual.siguiente
actual.siguiente = Nodo(valor)        # conectar al final

# RECORRER — O(n)
actual = primero
while actual is not None:
    print(actual.valor)
    actual = actual.siguiente    # avanzar al siguiente

# ELIMINAR — O(n)
# Caso especial: eliminar el primero
primero = primero.siguiente

# Caso general: usar pareja anterior/actual
anterior = primero
actual = primero.siguiente
while actual is not None:
    if actual.valor == buscado:
        anterior.siguiente = actual.siguiente   # saltar el nodo
        break
    anterior = actual
    actual = actual.siguiente

# CUÁNDO USAR LinkedList vs lista de Python
# Lista Python  → acceso por índice, inserción al final, secuencias estables
# LinkedList    → muchas inserciones/borrados al principio, aprender estructuras

# ERRORES TÍPICOS
# 1. Actualizar primero antes de conectar el nuevo nodo → pierdes la lista
# 2. Olvidar el caso especial de lista vacía en insertar_detras
# 3. Olvidar el caso especial de eliminar el primer nodo
# 4. No guardar actual.siguiente antes de modificar anterior.siguiente

En el próximo artículo practicamos la LinkedList con programas reales, incluyendo cómo invertir una lista encadenada y cómo ordenar sus elementos.

Linked structures in Python — LinkedList from scratch without the mystery

Linked structures are the last FP2 block and the one that carries most weight in the second exam. Most people arrive here with the node concept not quite clicking, they understand the words separately but can’t visualise how the whole chain works. This article starts from absolute zero.

What problem do linked structures solve?

A Python list [1, 2, 3, 4, 5] stores elements in consecutive memory positions:

Position:  [0]  [1]  [2]  [3]  [4]
Value:      1    2    3    4    5

Accessing element 3 is instant, Python calculates its memory position directly. But inserting or deleting in the middle is expensive — Python has to shift every element that comes after.

Insert 99 at position 2:
Before:  [1]  [2]  [3]  [4]  [5]
         ← shift everything →
After:   [1]  [2]  [99] [3]  [4]  [5]

Linked structures solve exactly this, inserting and deleting anywhere is always equally fast, without moving anything. The trade-off: accessing a specific element requires traversing from the beginning.

Python list: fast index access, slow insert/delete in middle
LinkedList:  slow index access, fast insert/delete anywhere

What is a node — the basic unit

A node is the smallest piece of a linked structure. Each node contains exactly two things:

The value it stores
A reference to the next node — or None if it’s the last one

┌──────────┬──────────┐
│  value   │   next   │
│    10    │  ──────► │ → (points to next node)
└──────────┴──────────┘

┌──────────┬──────────┐
│  value   │   next   │
│    10    │   None   │   (last node — no next)
└──────────┴──────────┘

Why it needs its own class: it’s an object with two independent attributes that must exist separately in memory.

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

You can create and chain nodes manually:

n1 = Node(10)
n2 = Node(20)
n3 = Node(30)

n1.next_node = n2
n2.next_node = n3

print(n1.value)                              # → 10
print(n1.next_node.value)                    # → 20
print(n1.next_node.next_node.value)          # → 30
print(n1.next_node.next_node.next_node)      # → None

n1                 n2                 n3
┌────┬────────┐   ┌────┬────────┐   ┌────┬──────┐
│ 10 │   ──────►  │ 20 │   ──────►  │ 30 │ None │
└────┴────────┘   └────┴────────┘   └────┴──────┘

How nodes link in memory

The arrow ──► is a reference — the memory address where the next node lives. When you do n1.next_node = n2 you’re not copying n2 inside n1, you’re storing n2‘s memory address in n1.next_node. Nodes can live anywhere in memory, not in consecutive positions. That’s why insertion is cheap: you just change what two references point to, without moving any data.

The LinkedList class

The LinkedList class doesn’t store elements directly, it stores a reference to the first node (head). With just that one reference you can reach any element by following the chain.

LinkedList
┌──────────┐
│  first  ──────► ┌────┬───┐   ┌────┬───┐   ┌────┬──────┐
└──────────┘      │ 10 │ ──────► 20 │ ──────► 30 │ None │
                  └────┴───┘   └────┴───┘   └────┴──────┘

Insert at front — O(1)

Before inserting 5:
first ──► [10] ──► [20] ──► [30] ──► None

Step 1 — create node pointing to current first:
new ──► [5] ──► [10] ──► [20] ──► [30] ──► None

Step 2 — first now points to new node:
first ──► [5] ──► [10] ──► [20] ──► [30] ──► None

def insert_front(self, value):
    self.__first = self.Node(value, self.__first)
    self.__length += 1

Insert at back — O(n)

Before inserting 40:
first ──► [10] ──► [20] ──► [30] ──► None

Traverse to last node (next_node=None):
                              current
first ──► [10] ──► [20] ──► [30] ──► None

Connect new node:
first ──► [10] ──► [20] ──► [30] ──► [40] ──► None

def insert_back(self, value):
    new = self.Node(value)
    if self.__first is None:
        self.__first = new
    else:
        current = self.__first
        while current.next_node is not None:
            current = current.next_node
        current.next_node = new
    self.__length += 1

Traverse — O(n)

first ──► [10] ──► [20] ──► [30] ──► None
current=10 → current=20 → current=30 → current=None → STOP

def __str__(self):
    return ' → '.join(str(v) for v in self) + ' → None'

def __iter__(self):
    current = self.__first
    while current is not None:
        value = current.value
        current = current.next_node
        yield value

Delete — O(n)

Delete 20 from: [10] ──► [20] ──► [30] ──► None

Before:  [10].next ──► [20],  [20].next ──► [30]
After:   [10].next ──► [30]   (we jump over [20])

Three cases:

Case 1 — delete first:
first ──► [10] ──► [20] ──► None
first = first.next_node
first ──► [20] ──► None

Case 2 — delete middle:
[10] ──► [20] ──► [30] ──► None
previous.next_node = current.next_node
[10] ──► [30] ──► None

Case 3 — delete last:
[10] ──► [20] ──► [30] ──► None
previous.next_node = None
[10] ──► [20] ──► None

def delete(self, value):
    if self.__first is None:
        raise ValueError(f"{value} not in list")

    if self.__first.value == value:
        self.__first = self.__first.next_node
        self.__length -= 1
        return

    previous = self.__first
    current = self.__first.next_node
    while current is not None:
        if current.value == value:
            previous.next_node = current.next_node
            self.__length -= 1
            return
        previous = current
        current = current.next_node

    raise ValueError(f"{value} not in list")

Complete class

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

    def __init__(self):
        self.__first = None
        self.__length = 0

    def insert_front(self, value):
        self.__first = self.Node(value, self.__first)
        self.__length += 1

    def insert_back(self, value):
        new = self.Node(value)
        if self.__first is None:
            self.__first = new
        else:
            current = self.__first
            while current.next_node is not None:
                current = current.next_node
            current.next_node = new
        self.__length += 1

    def delete(self, value):
        if self.__first is None:
            raise ValueError(f"{value} not in list")
        if self.__first.value == value:
            self.__first = self.__first.next_node
            self.__length -= 1
            return
        previous = self.__first
        current = self.__first.next_node
        while current is not None:
            if current.value == value:
                previous.next_node = current.next_node
                self.__length -= 1
                return
            previous = current
            current = current.next_node
        raise ValueError(f"{value} not in list")

    def contains(self, value):
        current = self.__first
        while current is not None:
            if current.value == value:
                return True
            current = current.next_node
        return False

    def is_empty(self):
        return self.__first is None

    def __len__(self):
        return self.__length

    def __iter__(self):
        current = self.__first
        while current is not None:
            value = current.value
            current = current.next_node
            yield value

    def __str__(self):
        return ' → '.join(str(v) for v in self) + ' → None'

    def __repr__(self):
        return f'LinkedList({list(self)})'

    def __contains__(self, value):
        return self.contains(value)

LinkedList vs Python list

                    Python list    LinkedList
──────────────────────────────────────────────
Index access:          O(1) ✓        O(n) ✗
Insert at front:       O(n) ✗        O(1) ✓
Insert at back:        O(1) ✓        O(n) ✗
Insert in middle:      O(n) ✗        O(1) ✓ (if you have the previous node)
Search:                O(n)          O(n)
Memory:                more efficient  less efficient

Quick summary

# NODE — basic unit
class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next_node = next_node    # reference or None

# LINKED LIST STRUCTURE
# first ──► [v1] ──► [v2] ──► [v3] ──► None
# Only stores reference to first node

# INSERT AT FRONT — O(1)
new = Node(value, first)    # connect to current first
first = new                  # new is now first

# INSERT AT BACK — O(n)
current = first
while current.next_node is not None:
    current = current.next_node
current.next_node = Node(value)

# TRAVERSE — O(n)
current = first
while current is not None:
    print(current.value)
    current = current.next_node

# DELETE — O(n)
# Special case: delete first
first = first.next_node
# General case: previous/current pair
previous = first
current = first.next_node
while current is not None:
    if current.value == target:
        previous.next_node = current.next_node    # jump over node
        break
    previous = current
    current = current.next_node

# COMMON MISTAKES
# 1. Updating first before connecting new node → lose the list
# 2. Forgetting empty list special case in insert_back
# 3. Forgetting first node special case in delete
# 4. Not saving next reference before modifying previous.next_node

Estructuras encadenadas en Python — LinkedList desde cero sin misterio

Tabla de Contenidos

Antes de empezar — qué problema resuelven las estructuras encadenadas

Qué es un nodo — la unidad básica

Cómo se enlazan los nodos en memoria

La clase LinkedList — qué necesita

Operación 1 — Insertar al principio

Operación 2 — Insertar al final

Operación 3 — Recorrer la lista

Operación 4 — Buscar un elemento

Operación 5 — Eliminar un elemento

Caso 1 — Eliminar el primero:

Caso 2 — Eliminar un nodo en el medio:

Caso 3 — Eliminar el último:

La clase completa

LinkedList vs lista de Python — cuándo usar cada una

Visualízalo con Python Tutor

Resumen rápido

Linked structures in Python — LinkedList from scratch without the mystery

What problem do linked structures solve?

What is a node — the basic unit

How nodes link in memory

The LinkedList class

Insert at front — O(1)

Insert at back — O(n)

Traverse — O(n)

Delete — O(n)

Complete class

LinkedList vs Python list

Quick summary

Clases en Python — objetos, encapsulamiento y métodos mágicos desde cero

Operadores en Python — práctica real con 3 programas en VS Code

Iteradores y generadores en Python — cómo funciona el for por dentro

Condicionales en Python — ejercicios con solución y chuletario completo

Herencia y polimorfismo en Python — super(), override y clases abstractas

Bucles en Python — ponlos a prueba con estos ejercicios

2 comentarios

Deja una respuesta Cancelar la respuesta

Tabla de Contenidos

Antes de empezar — qué problema resuelven las estructuras encadenadas

Qué es un nodo — la unidad básica

Cómo se enlazan los nodos en memoria

La clase LinkedList — qué necesita

Operación 1 — Insertar al principio

Operación 2 — Insertar al final

Operación 3 — Recorrer la lista

Operación 4 — Buscar un elemento

Operación 5 — Eliminar un elemento

Caso 1 — Eliminar el primero:

Caso 2 — Eliminar un nodo en el medio:

Caso 3 — Eliminar el último:

La clase completa

LinkedList vs lista de Python — cuándo usar cada una

Visualízalo con Python Tutor

Resumen rápido

Linked structures in Python — LinkedList from scratch without the mystery

What problem do linked structures solve?

What is a node — the basic unit

How nodes link in memory

The LinkedList class

Insert at front — O(1)

Insert at back — O(n)

Traverse — O(n)

Delete — O(n)

Complete class

LinkedList vs Python list

Quick summary

Publicaciones Similares

2 comentarios

Deja una respuesta Cancelar la respuesta