Listas enlazadas en Python: Tutorial con ejemplos

Una lista enlazada es una estructura de datos que desempeña un papel crucial en la organización y gestión de datos. Contiene una serie de nodos que se almacenan en ubicaciones aleatorias de la memoria, lo que permite una gestión eficaz de la memoria. Cada nodo de una lista enlazada contiene dos componentes principales: la parte de datos y una referencia al siguiente nodo de la secuencia.

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

Vamos a desglosarlo hasta sus fundamentos para explicar qué son las listas enlazadas, por qué las utilizamos y las ventajas únicas que ofrecen.

¿Por qué listas enlazadas?

Las listas enlazadas se crearon para superar varios inconvenientes asociados al almacenamiento de datos en listas y matrices normales, como se indica a continuación:

Facilidad de inserción y supresión

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

Las listas enlazadas, sin embargo, funcionan de forma diferente. Almacenan elementos en varias ubicaciones de memoria no contiguas y los conectan mediante punteros a nodos posteriores. Esta estructura permite que las listas enlazadas añadan o eliminen elementos en cualquier posición, simplemente modificando los enlaces para incluir un elemento nuevo o pasar por alto el eliminado.

Una vez que se identifica la posición del elemento y se tiene acceso directo al punto de inserción o supresión, se pueden añadir o eliminar nodos en tiempo O(1).

Tamaño dinámico

Las listas de Python son matrices dinámicas, lo que significa que ofrecen la flexibilidad de modificar el tamaño.

Sin embargo, este proceso implica una serie de operaciones complejas, incluida la reasignación de la matriz a un nuevo bloque de memoria más grande. Esta reasignación es ineficaz, ya que los elementos se copian en un nuevo bloque, pudiendo asignar más espacio del inmediatamente necesario.

En cambio, las listas enlazadas pueden crecer y decrecer dinámicamente sin necesidad de reasignación o redimensionamiento. Esto las convierte en una opción preferible para tareas que requieren una gran flexibilidad.

Eficiencia de la memoria

Las listas asignan memoria para todos sus elementos en un bloque contiguo. Si una lista necesita crecer más allá de su tamaño inicial, debe asignar un nuevo bloque más grande de memoria contigua y luego copiar todos los elementos existentes en este nuevo bloque. Este proceso lleva mucho tiempo y es ineficaz, sobre todo para listas grandes. Por otra parte, si se sobreestima el tamaño inicial de la lista, se desperdicia la memoria no utilizada.

En cambio, las listas enlazadas asignan memoria a cada elemento por separado. Esta estructura permite una mejor utilización de la memoria, ya que la memoria para los nuevos elementos puede asignarse a medida que se añaden.

¿Cuándo debes utilizar listas enlazadas?

Aunque las listas enlazadas ofrecen ciertas ventajas sobre las listas y matrices normales, como el tamaño dinámico y la eficiencia en memoria, también tienen sus limitaciones. Como hay que almacenar punteros para cada elemento para referenciar el siguiente nodo, el uso de memoria por elemento es mayor cuando se utilizan listas enlazadas. Además, esta estructura de datos no permite el acceso directo a los datos. Acceder a un elemento requiere un recorrido secuencial desde el principio de la lista, lo que da lugar a una complejidad de tiempo de búsqueda O(n).

La elección entre utilizar una lista enlazada o una matriz depende de las necesidades específicas de la aplicación. Las listas enlazadas son más útiles cuando

• Necesitas insertar y eliminar con frecuencia muchos elementos
• El tamaño de los datos es impredecible o puede cambiar con frecuencia
• El acceso directo a los elementos no es un requisito
• El conjunto de datos contiene elementos o estructuras grandes

Tipos de listas enlazadas

Hay tres tipos de listas enlazadas, cada una de las cuales ofrece ventajas únicas para distintos escenarios. Estos tipos son:

Listas simples

Lista unívoca

Una lista enlazada simple es el tipo más sencillo de lista enlazada, en la que cada nodo contiene algunos datos y una referencia al siguiente nodo de la secuencia. Sólo pueden recorrerse en una única dirección: de la cabeza (el primer nodo) a la cola (el último nodo).

Cada nodo de una lista con un solo enlace suele constar de dos partes:

• Data: La información real almacenada en el nodo.
• Siguiente Puntero: Una referencia al siguiente nodo. El siguiente puntero del último nodo suele ser nulo.

Como estas estructuras de datos sólo pueden recorrerse en una única dirección, para acceder a un elemento concreto por valor o índice hay que empezar por la cabecera y recorrer secuencialmente los nodos hasta encontrar el nodo deseado. Esta operación tiene una complejidad temporal de O(n), por lo que es menos eficaz para listas grandes.

Insertar y eliminar un nodo al principio de una lista de un solo enlace es muy eficaz, con una complejidad temporal de O(1). Sin embargo, la inserción y la eliminación en el medio o al final requieren recorrer la lista hasta ese punto, lo que conlleva una complejidad temporal O(n).

El diseño de las listas simples las convierte en una estructura de datos útil cuando se realizan operaciones que tienen lugar al principio de la lista.

Listas doblemente enlazadas

Lista doblemente enlazada

Una desventaja de las listas con un solo enlace es que sólo podemos recorrerlas en una dirección y no podemos iterar hacia el nodo anterior si es necesario. Esta restricción limita nuestra capacidad para realizar operaciones que requieran una navegación bidireccional.

Las listas doblemente enlazadas resuelven este problema incorporando un puntero adicional dentro de cada nodo, lo que garantiza que la lista pueda recorrerse en ambas direcciones. Cada nodo de una lista doblemente enlazada contiene tres elementos: los datos, un puntero al nodo siguiente y un puntero al nodo anterior.

Listas enlazadas circulares

Lista enlazada circular

Las listas enlazadas circulares son una forma especializada de lista enlazada en la que el último nodo apunta de nuevo al primer nodo, creando una estructura circular. Esto significa que, a diferencia de las listas simple y doblemente enlazadas que hemos visto hasta ahora, la lista enlazada circular no termina, sino que hace un bucle.

La naturaleza cíclica de las listas enlazadas circulares las hace ideales para situaciones en las que hay que hacer un bucle continuo, como los juegos de mesa que hacen un bucle desde el último jugador hasta el primero, o en algoritmos informáticos como la programación por turnos.

Cómo crear una lista enlazada en Python

Ahora que ya sabemos qué son las listas enlazadas, por qué las utilizamos y sus variaciones, procedamos a implementar estas estructuras de datos en Python. El cuaderno de este tutorial también está disponible en este cuaderno de DataLab; si creas una copia podrás editar y ejecutar el código. ¡Esta es una gran opción si te encuentras con algún problema al ejecutar el código por tu cuenta!

Inicializar un nodo

Como aprendimos anteriormente, un nodo es un elemento de la lista enlazada que almacena datos y una referencia al siguiente nodo de la secuencia. He aquí cómo puedes definir un nodo en Python:

class Node:
    def __init__(self, data):
        self.data = data  # Assigns the given data to the node
        self.next = None  # Initialize the next attribute to null

El código anterior inicializa un nodo realizando dos acciones principales: Al atributo "datos" del nodo se le asigna un valor que representa la información real que debe contener el nodo. El atributo "siguiente" representa la dirección del siguiente nodo. Actualmente está definido como Ninguno, lo que significa que no enlaza con ningún otro nodo de la lista. A medida que sigamos añadiendo nuevos nodos a la lista enlazada, este atributo se actualizará para apuntar al nodo siguiente.

Crear una clase de lista enlazada

A continuación, tenemos que crear la clase Lista enlazada. Esto encapsulará todas las operaciones de gestión de los nodos, como la inserción y la eliminación. Empezaremos por inicializar la lista enlazada:

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

Al establecer self.head como Ninguno, estamos afirmando que la lista enlazada está inicialmente vacía y que no hay nodos en la lista a los que apuntar. Ahora procederemos a poblar la lista insertando nuevos nodos.

Insertar un nuevo nodo al principio de una lista enlazada

Dentro de la clase LinkedList, vamos a añadir un método para crear un nuevo nodo y colocarlo al principio de la lista:

    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 llames al método anterior, se creará un nuevo nodo con los datos que hayas especificado. El puntero siguiente de este nuevo nodo se establece en la cabeza actual de la lista, lo que colocará este nodo delante de los nodos existentes. Por último, el nodo recién creado se convierte en cabeza de la lista.

Ahora vamos a poblar esta lista enlazada con una serie de palabras para comprender mejor cómo funciona la operación de inserción. Para ello, vamos a crear primero un método diseñado para recorrer e imprimir el contenido de la lista:

    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

El método anterior imprimirá el contenido de nuestra lista enlazada. Procedamos ahora a utilizar los métodos que hemos definido para poblar nuestra lista con una serie de palabras: "el zorro marrón rápido".

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()

Las líneas de código anteriores deberían dar el siguiente resultado:

"the quick brown fox"

Insertar un nuevo nodo al final de una lista enlazada

Ahora crearemos un método llamado insertAtEnd dentro de la clase LinkedList, para crear un nuevo nodo al final de la lista. Si la lista está vacía, el nuevo nodo se convertirá en la cabeza de la lista. De lo contrario, se añadirá al último nodo de la lista. Veamos cómo funciona en la práctica:

def insertAtEnd(self, new_data):
        new_node = Node(new_data)  # Create a new node
        if self.head is None:
            self.head = new_node  # If the list is empty, make the new node the head
            return
        last = self.head 
        while last.next:  # Otherwise, traverse the list to find the last node
            last = last.next
        last.next = new_node  # Make the new node the next node of the last node

El método anterior comienza creando un nuevo nodo. A continuación, comprueba si la lista está vacía y, si es así, el nuevo nodo se asigna como cabeza de esa lista. En caso contrario, recorre la lista hasta encontrar el último nodo y establece el puntero de este nodo al nuevo nodo.

Ahora tenemos que incluir este método en nuestra clase LinkedList y utilizarlo para añadir una palabra al final de nuestra lista. Para conseguirlo, modifica tu función principal para que tenga este aspecto:

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 al método insertAtEnd para imprimir la palabra "salta" al final de la lista. El código anterior debería dar el siguiente resultado:

"the quick brown fox jumps"

Borrar un nodo del principio de una lista enlazada

Borrar el primer nodo de una lista enlazada es fácil, ya que consiste simplemente en apuntar la cabeza de esta lista al segundo nodo. De esta forma, el primer nodo dejará de formar parte de la lista. Para ello, incluye el siguiente 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

Borrar un nodo del final de una lista enlazada

Para eliminar el último nodo de una lista enlazada, debemos recorrer la lista hasta encontrar el penúltimo nodo y cambiar su siguiente puntero a Ninguno. De esta forma, el último nodo dejará de formar parte de la lista. Copia y pega el siguiente método en tu clase LinkedList para conseguirlo:

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

El método anterior comprueba primero si la lista enlazada está vacía, devolviendo un mensaje al usuario en caso afirmativo. En caso contrario, si la lista contiene un solo nodo, se elimina ese nodo. En las listas con varios nodos, el método localiza el penúltimo nodo y su referencia al nodo siguiente se actualiza a Ninguno.

Actualicemos ahora la función principal para eliminar elementos del inicio y del final de la lista enlazada:

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()

El código anterior imprimirá la lista antes y después de la eliminación, mostrando cómo funcionan las operaciones de inserción y eliminación en las listas enlazadas. Deberías ver la siguiente salida después de ejecutar este código:

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 aprenderemos en este capítulo es la recuperación de un valor concreto de la lista enlazada. Para ello, el método debe empezar en la cabeza de la lista e iterar por cada nodo, comprobando si los datos del nodo coinciden con el valor de búsqueda. Aquí tienes una aplicación práctica de esta operación:

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 encontrar valores concretos en la lista enlazada que hemos creado, actualiza tu función principal para incluir el método de búsqueda que acabamos de crear:

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

El código anterior dará el siguiente resultado:

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 "rápido" se ha localizado correctamente dentro de la lista enlazada, ya que existe en la primera posición de la lista. Sin embargo, la palabra "perezoso" no forma parte de la lista, por lo que no se ha encontrado.

Reflexiones finales

Si has llegado hasta aquí, ¡enhorabuena! Ahora tienes una sólida comprensión de los principios básicos de las listas enlazadas, incluida su estructura, tipos, cómo añadir y eliminar elementos y cómo recorrerlas.

Pero el viaje no termina aquí. Las listas enlazadas son sólo el principio del mundo de las estructuras de datos y los algoritmos. He aquí algunos posibles pasos siguientes para que profundices en el tema:

Crea tu propio proyecto

Sumérgete en las aplicaciones prácticas de las listas enlazadas integrándolas en un proyecto de codificación o de ciencia de datos. Las listas enlazadas se utilizan 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, consulta nuestros proyectos guiados gratuitos de ciencia de datos que te enseñan a resolver problemas del mundo real en Python, R y SQL.

Aprende sobre estructuras de datos y algoritmos

Aprender otras estructuras de datos, como árboles, pilas y colas, es una progresión natural a partir de la comprensión de las listas enlazadas. Estas estructuras se basan en los principios de las listas enlazadas, ayudándote a resolver con eficacia una gama más amplia de problemas de cálculo. Los árboles y los árboles de búsqueda binaria, por ejemplo, amplían el concepto de listas enlazadas a una forma jerárquica, permitiendo que cada nodo se conecte a varios elementos de la estructura de datos.

Si estos conceptos te suenan desconocidos, ¡no te preocupes! Datacamp tiene un curso entero sobre estructuras de datos y algoritmos en Python que te llevará a través de estos conceptos con mayor detalle. Primero aprenderás sobre estructuras de datos como pilas, árboles, tablas hash, colas y grafos. A medida que avances en el curso, comprenderás los algoritmos de búsqueda y ordenación, lo que te ayudará a convertirte en un programador y solucionador de problemas más eficaz.

Explorar conceptos avanzados de listas enlazadas

En este tutorial hemos implementado las listas simples, cubriendo operaciones como la inserción, la eliminación y el desplazamiento.

Puedes llevar estos conocimientos un paso más allá aprendiendo la implementación de listas doblemente enlazadas y circularmente enlazadas. Las listas de salto son otra extensión de las listas enlazadas que permiten operaciones de búsqueda más rápidas al facilitar un acceso más rápido a los elementos.

Aprender sobre estas estructuras de datos avanzadas llevará tus habilidades técnicas al siguiente nivel y mejorará drásticamente tus capacidades de programación, preparándote para retos más complejos en campos como la ciencia de datos, el desarrollo de software y la ingeniería de aprendizaje automático.

Si deseas una introducción más sencilla a la programación antes de abordar estos temas avanzados, explora nuestro itinerario profesional de Programador de Python. Ofrece una serie de cursos que te enseñarán los fundamentos de la lengua.