Listas enlazadas en Python: tutorial con ejemplos

Una lista enlazada es una estructura de datos clave para organizar y gestionar información. Contiene una serie de nodos almacenados en ubicaciones aleatorias de memoria, lo que favorece una gestión eficiente de memoria. Cada nodo en una lista enlazada tiene dos componentes principales: la parte de datos y una referencia al siguiente nodo de la secuencia.

Si a primera vista te parece un concepto complejo, ¡no te preocupes!

Vamos a desgranarlo desde los fundamentos para explicar qué son las listas enlazadas, por qué las usamos y las ventajas que ofrecen.

¿Por qué listas enlazadas?

Las listas enlazadas surgieron para superar varios inconvenientes de almacenar datos en listas y arrays convencionales, como se detalla a continuación:

Facilidad de inserción y borrado

En las listas, insertar o eliminar un elemento en cualquier posición que no sea el final obliga a desplazar todos los elementos posteriores. Este proceso tiene una complejidad temporal de O(n) y puede degradar el rendimiento, sobre todo a medida que crece el tamaño de la lista. Si aún no estás familiarizado con el funcionamiento o la implementación de las listas, puedes leer nuestro tutorial sobre listas en Python.

Las listas enlazadas, en cambio, funcionan de forma distinta. Almacenan los elementos en ubicaciones de memoria no contiguas y los conectan mediante punteros a los nodos siguientes. Gracias a esta estructura, pueden añadir o eliminar elementos en cualquier posición simplemente modificando los enlaces para incluir un nuevo elemento o saltar el que se elimina.

Una vez tienes una referencia directa al nodo en el punto de inserción o borrado, la operación es O(1). Aun así, encontrar esa posición requiere un recorrido O(n), por lo que el beneficio O(1) solo aplica cuando ya tienes un puntero al nodo relevante (por ejemplo, cuando trabajas en la cabeza de la lista).

Tamaño dinámico

Las listas de Python son arrays dinámicos, lo que ofrece flexibilidad para modificar su tamaño.

Sin embargo, este proceso implica operaciones complejas, como reasignar el array a un bloque de memoria más grande. Esta reasignación es ineficiente porque hay que copiar los elementos a un bloque nuevo, pudiendo reservar más espacio del necesario en ese momento.

En cambio, las listas enlazadas pueden crecer y reducirse dinámicamente sin necesidad de reasignaciones ni redimensionamientos. Por eso son preferibles en tareas que requieren mucha flexibilidad.

Eficiencia de memoria

Las listas reservan memoria para todos sus elementos en un bloque contiguo. Si una lista debe crecer más allá de su tamaño inicial, tiene que reservar un bloque contiguo mayor y copiar todos los elementos al nuevo bloque. Este proceso es costoso e ineficiente, especialmente en listas grandes. Por otro lado, si se sobreestima el tamaño inicial, se desperdicia memoria no utilizada.

En cambio, las listas enlazadas reservan memoria por elemento. Esto permite un mejor aprovechamiento, ya que la memoria para nuevos elementos se asigna conforme se añaden.

¿Cuándo deberías usar listas enlazadas?

Aunque las listas enlazadas aportan ventajas frente a listas y arrays, como tamaño dinámico y eficiencia de memoria, también tienen limitaciones. Como hay que almacenar punteros en cada elemento para referenciar el siguiente nodo, el consumo de memoria por elemento es mayor. Además, esta estructura no permite acceso directo: para acceder a un elemento hay que recorrer secuencialmente desde el inicio, lo que conlleva una búsqueda O(n).

La decisión entre usar una lista enlazada o un array depende de las necesidades de tu aplicación. Las listas enlazadas son especialmente útiles cuando:

• Necesitas insertar y eliminar elementos con frecuencia
• El tamaño de los datos es impredecible o cambia a menudo
• No es imprescindible el acceso directo a elementos
• El conjunto de datos contiene elementos o estructuras grandes

Tipos de listas enlazadas

Existen tres tipos de listas enlazadas, cada una con ventajas para distintos escenarios:

Listas simplemente enlazadas

Lista simplemente enlazada

Una lista simplemente enlazada es el tipo más sencillo: cada nodo contiene datos y una referencia al siguiente nodo de la secuencia. Solo se puede recorrer en una dirección, desde la cabeza (primer nodo) hasta la cola (último nodo).

Cada nodo en una lista simplemente enlazada suele tener dos partes:

• Datos: La información que almacena el nodo.
• Puntero siguiente: Una referencia al siguiente nodo. El puntero del último nodo suele ser null.

Como solo se pueden recorrer en una dirección, acceder a un elemento por valor o índice exige empezar en la cabeza e ir avanzando nodo a nodo hasta encontrarlo. Esta operación es O(n), por lo que es menos eficiente en listas grandes.

Insertar y eliminar un nodo al principio es muy eficiente: O(1). En cambio, hacerlo en medio o al final requiere recorrer la lista hasta ese punto, lo que es O(n).

Por su diseño, las listas simplemente enlazadas son útiles cuando la mayoría de operaciones ocurren al inicio de la lista.

Listas doblemente enlazadas

Lista doblemente enlazada

Una desventaja de las listas simplemente enlazadas es que solo se pueden recorrer en una dirección, sin posibilidad de volver al nodo anterior. Esta restricción limita operaciones que requieren navegación bidireccional.

Las listas doblemente enlazadas resuelven este problema incorporando un puntero adicional en cada nodo, lo que permite recorrer la lista en ambos sentidos. Cada nodo contiene tres elementos: los datos, un puntero al siguiente nodo y un puntero al anterior.

Listas circulares

Lista circular

Las listas circulares son una variante en la que el último nodo apunta de nuevo al primero, creando una estructura cíclica. A diferencia de las listas simple y doblemente enlazadas que hemos visto, aquí la lista no termina: vuelve a empezar.

Su naturaleza cíclica las hace ideales para escenarios donde hay que iterar continuamente, como juegos de mesa que pasan del último jugador al primero, o algoritmos como la planificación round-robin.

Resumen de complejidad temporal

Una comparativa rápida entre listas enlazadas y listas de Python:

La idea principal: las listas enlazadas ganan en inserciones y borrados en la cabeza (O(1)), pero pierden en casi todo lo demás. Si no vas a añadir o quitar elementos con frecuencia al principio, probablemente te convenga más una lista de Python.

Cómo crear una lista enlazada en Python

Ahora que ya sabes qué son, por qué las usamos y sus variantes, vamos a implementarlas en Python. El cuaderno de este tutorial está disponible en este cuaderno de DataLab; si haces una copia, podrás editar y ejecutar el código. Es una gran opción si encuentras problemas al ejecutarlo en tu equipo.

Inicializar un nodo

Como vimos, un nodo es un elemento de la lista enlazada que almacena datos y una referencia al siguiente nodo. Así puedes definir un nodo en Python:

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

    def __repr__(self):
        return f"Node({self.data})"

Este código inicializa un nodo realizando dos acciones principales: al atributo "data" se le asigna el valor que representa la información del nodo. El atributo "next" representa la dirección del siguiente nodo y se establece en None para indicar que aún no enlaza con ningún otro. A medida que añadamos nodos, este atributo se actualizará para apuntar al siguiente.

Crear la clase de la lista enlazada

Después, creamos la clase de la lista enlazada. Aquí encapsularemos las operaciones para gestionar los nodos, como inserción y borrado. Empezamos inicializando la lista:

class LinkedList:
    def __init__(self):
        self.head = None  # Initialize head as None

Al establecer self.head en None, indicamos que la lista está vacía inicialmente y no hay nodos a los que apuntar. Ahora vamos a poblarla insertando nuevos nodos.

Insertar un nodo nuevo al principio

Dentro de la clase LinkedList, añadimos un método para crear un nodo nuevo y colocarlo al inicio:

    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)  # Create a new node 
        new_node.next = self.head  # Next for new node becomes the   current head
        self.head = new_node  # Head now points to the new node

Cada vez que llamas a este método, se crea un nodo con los datos que indiques. Su puntero siguiente se establece en la cabeza actual, colocándolo delante de los nodos existentes. Por último, la cabeza de la lista pasa a ser el nuevo nodo.

Vamos a poblar la lista con una serie de palabras para entender mejor la inserción. Para ello, primero creamos un método para recorrer e imprimir el contenido:

    def printList(self):
        temp = self.head # Start from the head of the list
        while temp:
            print(temp.data,end=' ') # Print the data in the current node
            temp = temp.next # Move to the next node
        print()  # Ensures the output is followed by a new line

Este método imprime el contenido de nuestra lista enlazada. Ahora usemos los métodos definidos para poblarla con las palabras: "the quick brown fox".

if __name__ == '__main__':
    # Create a new LinkedList instance
    llist = LinkedList()

    # Insert each letter at the beginning using the method we created
    llist.insertAtBeginning('fox') 
    llist.insertAtBeginning('brown') 
    llist.insertAtBeginning('quick')  
    llist.insertAtBeginning('the')  

    # Now 'the' is the head of the list, followed by 'quick', then 'brown' and 'fox'

    # Print the list
    llist.printList()

Estas líneas deberían mostrar el siguiente resultado:

"the quick brown fox"

Insertar un nodo nuevo al final

Ahora crearemos un método llamado insertAtEnd dentro de la clase LinkedList para añadir un nodo al final. Si la lista está vacía, el nuevo nodo se convertirá en la cabeza. En caso contrario, se añadirá al último nodo actual. Veámoslo en la práctica:

    def insertAtEnd(self, new_data):
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

El método empieza creando un nuevo nodo. Después comprueba si la lista está vacía; de ser así, asigna el nuevo nodo como cabeza. Si no, recorre la lista hasta el último nodo y establece su puntero siguiente al nuevo nodo.

Incluye este método en la clase LinkedList y úsalo para añadir una palabra al final. Para ello, modifica tu función principal así:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list
    llist.printList()

Observa que simplemente hemos llamado a insertAtEnd para que la palabra "jumps" aparezca al final de la lista. El código debería producir:

"the quick brown fox jumps"

Eliminar un nodo del principio

Eliminar el primer nodo es sencillo: basta con hacer que la cabeza apunte al segundo nodo. Así, el primero deja de formar parte de la lista. Para ello, añade este método en la clase LinkedList:

def deleteFromBeginning(self):
    if self.head is None:
        return "The list is empty" # If the list is empty, return this string
    self.head = self.head.next  # Otherwise, remove the head by making the next node the new head

Eliminar un nodo del final

Para eliminar el último nodo, hay que recorrer la lista hasta el penúltimo y poner su puntero siguiente a None. De este modo, el último deja de pertenecer a la lista. Copia y pega el siguiente método en tu clase LinkedList:

def deleteFromEnd(self):
    if self.head is None:
        return "The list is empty" 
    if self.head.next is None:
        self.head = None  # If there's only one node, remove the head by making it None
        return
    temp = self.head
    while temp.next.next:  # Otherwise, go to the second-last node
        temp = temp.next
    temp.next = None  # Remove the last node by setting the next pointer of the second-last node to None

Este método primero comprueba si la lista está vacía y devuelve un mensaje si lo está. Si la lista solo tiene un nodo, se elimina. En listas con varios nodos, localiza el penúltimo y actualiza su referencia siguiente a None.

Actualicemos ahora la función principal para borrar elementos al inicio y al final:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from the beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()

Este código imprimirá la lista antes y después del borrado, mostrando cómo funcionan las operaciones de inserción y eliminación. Deberías ver esta salida:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox

Buscar un valor concreto en la lista enlazada

La última operación que veremos es la búsqueda de un valor concreto. Para ello, el método empieza en la cabeza y recorre cada nodo comprobando si sus datos coinciden con el valor buscado. Aquí tienes una implementación práctica:

def search(self, value):
    current = self.head  # Start with the head of the list
    position = 0  # Counter to keep track of the position
    while current: # Traverse the list
        if current.data == value: # Compare the list's data to the search value
            return f"Value '{value}' found at position {position}" # Print the value if a match is found
        current = current.next
        position += 1
    return f"Value '{value}' not found in the list" 

Para buscar valores en la lista que hemos creado, actualiza tu función principal para incluir el método de búsqueda que acabamos de añadir:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

   # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()
    
        # Search for 'quick' and 'lazy' in the list
    print(llist.search('quick'))  # Expected to find
    print(llist.search('lazy'))   # Expected not to find

Este código producirá la siguiente salida:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox 
Value 'quick' found at position 0
Value 'lazy' not found in the list

La palabra "quick" se ha localizado correctamente porque está en la primera posición de la lista. En cambio, "lazy" no forma parte de la lista, por eso no se encuentra.

Reflexiones finales

¡Enhorabuena por llegar hasta aquí! Ahora tienes una base sólida sobre las listas enlazadas: su estructura, tipos, cómo añadir y eliminar elementos y cómo recorrerlas.

Pero el viaje no acaba aquí. Las listas enlazadas son solo la puerta de entrada al mundo de las estructuras de datos y los algoritmos. Aquí tienes algunos posibles próximos pasos para profundizar:

Crea tu propio proyecto

Explora aplicaciones prácticas integrando listas enlazadas en un proyecto de programación o ciencia de datos. Se usan para desarrollar sistemas de archivos, construir tablas hash e incluso crear sistemas de navegación GPS y juegos de mesa. Para empezar con tus propios proyectos, echa un vistazo a nuestros proyectos de ciencia de datos gratuitos y guiados, donde aprenderás a resolver problemas reales en Python, R y SQL.

Aprende sobre estructuras de datos y algoritmos

Aprender otras estructuras como árboles, pilas y colas es el siguiente paso natural desde las listas enlazadas. Se basan en los mismos principios y te ayudan a resolver un abanico más amplio de problemas de forma eficiente. Por ejemplo, los árboles y los árboles binarios de búsqueda amplían el concepto de lista enlazada a una forma jerárquica, permitiendo que cada nodo se conecte con múltiples elementos.

Si estos conceptos te suenan lejanos, ¡tranquilo! Datacamp tiene un curso completo de estructuras de datos y algoritmos en Python que los explica en detalle. Primero verás pilas, árboles, tablas hash, colas y grafos. Después aprenderás algoritmos de búsqueda y ordenación, que te ayudarán a programar y resolver problemas con más eficiencia.

Explora conceptos avanzados de listas enlazadas

En este tutorial hemos implementado listas simplemente enlazadas, con operaciones como inserción, borrado y recorrido.

Puedes ir un paso más allá aprendiendo a implementar listas doblemente enlazadas y circulares. Las skip lists son otra extensión que permite acelerar las búsquedas facilitando accesos más rápidos a los elementos.

Conocer estas estructuras avanzadas llevará tus habilidades técnicas al siguiente nivel y mejorará tu capacidad de programación, preparándote para retos más complejos en ciencia de datos, desarrollo de software e ingeniería de machine learning.

Si prefieres una introducción más amigable antes de abordar estos temas, explora nuestro itinerario de habilidades Python Programming. Ofrece una serie de cursos con los fundamentos del lenguaje.