Lista enlazada en Python

  2. HowTo
  3. How-To's de Python
  4. Lista enlazada en Python
Aditya Raj 30 enero 2023
Python Python Data Structure
  1. ¿Qué es una lista enlazada en Python?
  2. Cómo crear una lista enlazada en Python
  3. Imprimir todos los elementos de una lista enlazada en Python
  4. Insertar un elemento en una lista vinculada en Python
  5. Eliminar un elemento de la lista vinculada en Python
  6. Cuente la cantidad de elementos en una lista vinculada en Python
  7. Actualizar un nodo en la lista vinculada en Python
  8. Por qué usar una lista enlazada en Python
  9. Lista enlazada de implementación completa en Python
  10. Conclusión
Lista enlazada en Python

Python nos proporciona varias estructuras de datos integradas.

Sin embargo, cada estructura de datos tiene sus restricciones. Debido a esto, necesitamos estructuras de datos personalizadas.

Este artículo discutirá una estructura de datos personalizada llamada Lista enlazada. También implementaremos una lista vinculada en Python y realizaremos varias operaciones en la lista vinculada.

¿Qué es una lista enlazada en Python?

Como sugiere el nombre, una lista enlazada es una estructura de datos que contiene elementos conectados mediante un enlace.

Una lista enlazada se crea usando objetos llamados nodos. Cada nodo contiene dos atributos: uno para almacenar los datos y el otro para conectarse al siguiente nodo en la lista vinculada.

Puede comprender la estructura de un nodo utilizando la siguiente figura.

Nodo en Python

Aquí,

  • Un Node es un objeto que contiene los atributos data y next.
  • El atributo data almacena los datos.
  • El atributo next se refiere al siguiente nodo en la lista enlazada.

Como se muestra en la siguiente imagen, podemos conectar varios nodos para crear una lista enlazada.

Lista enlazada en Python

Aquí,

  • Hemos creado una lista enlazada que consta de cuatro nodos.
  • El primer nodo contiene el número 10, el segundo nodo contiene 20, el tercer nodo contiene 30 y el último nodo contiene 40.
  • También hemos creado una variable Head que hace referencia al primer nodo. Solo mantenemos la variable Head en un objeto de lista enlazada. Los datos de todos los demás nodos se obtienen recorriendo la lista enlazada a partir del primer nodo al que hace referencia Head.
  • El atributo next del último nodo hace referencia a un objeto None. El atributo next del último nodo de una lista enlazada siempre se referirá al objeto None.
  • Si una lista enlazada está vacía, la variable Head se referirá al objeto None.

Ahora entendemos la estructura básica de una lista enlazada. Implementemos una lista enlazada en Python.

Cómo crear una lista enlazada en Python

Como los nodos son los componentes básicos de una lista enlazada, primero crearemos un nodo. Para ello, definiremos una clase Node con los atributos data y next como se muestra a continuación.

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


myNode = Node(10)
print("The data in the node is:", myNode.data)
print("The next attribute in the node is:", myNode.next)

Producción :

The data in the node is: 10
The next attribute in the node is: None

En el ejemplo anterior, puede observar que el atributo next del Node se refiere a None por defecto. Cuando lo insertamos en una lista enlazada, asignamos el atributo next a los nodos de la lista enlazada, como veremos más adelante.

Debemos crear un objeto con el atributo Head para crear una lista enlazada. Podemos definir la clase LinkedList como se muestra a continuación.

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


class LinkedList:
    def __init__(self):
        self.Head = None


myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4

print("The elements in the linked list are:")
print(myLinkedList.Head.data, end=" ")
print(myLinkedList.Head.next.data, end=" ")
print(myLinkedList.Head.next.next.data, end=" ")
print(myLinkedList.Head.next.next.next.data)

Producción :

The linked list is:
10 20 30 40

En el ejemplo anterior, creamos una lista enlazada.

Después de eso, creamos manualmente los nodos utilizando los datos proporcionados, los agregamos a la lista vinculada uno por uno y los imprimimos. Más tarde, aprenderemos a insertar elementos en una lista enlazada utilizando el bucle while de Python.

Analicemos ahora cómo podemos imprimir todos los elementos de una lista enlazada sin acceder manualmente a todos los nodos.

Imprimir todos los elementos de una lista enlazada en Python

Usaremos un bucle while para imprimir todos los elementos de la lista enlazada.

Comenzando desde el puntero Head, primero imprimiremos los datos en el nodo actual usando el atributo data del nodo. Después de eso, nos moveremos al siguiente nodo usando el puntero next.

Seguiremos este proceso hasta llegar al final de la lista enlazada (es decir, el atributo next de un nodo resulta ser None). Como se muestra a continuación, puede implementar toda la lógica en el método printList().

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next


myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4

print("The elements in the linked list are:")
myLinkedList.printList()

Producción :

The elements in the linked list are:
10 20 30 40

Insertar un elemento en una lista vinculada en Python

Hay cuatro situaciones al insertar un elemento en una lista enlazada.

  1. La lista enlazada puede estar vacía antes de la inserción.
  2. Tenemos que insertar un elemento al principio de una lista enlazada no vacía.
  3. Tenemos que insertar un elemento al final de una lista enlazada.
  4. Tenemos que insertar un elemento en una posición dada en la lista enlazada.

Discutamos cómo insertar un elemento en la lista enlazada en todas las situaciones.

Insertar un elemento en una lista vinculada vacía

Para insertar un elemento en una lista enlazada vacía, definiremos un método insertIntoEmptyList() que acepta el elemento como argumento de entrada y agrega un nodo que contiene el elemento de entrada en la lista enlazada.

Para ello crearemos un nodo en el insertIntoEmptyList() con el elemento input como data. Después de crear el nodo, asignaremos el nodo al atributo Head.

De esta forma, el nuevo nodo se convertirá en el primer nodo de la lista enlazada. El método se puede implementar de la siguiente manera.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertIntoEmptyList(self, element):
        newNode = Node(element)
        self.Head = newNode


myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
print("The elements in the linked list are:")
myLinkedList.printList()

Producción :

The elements in the linked list are:
10

Insertar un elemento al principio de una lista vinculada

Para insertar un elemento al comienzo de una lista no vacía, definiremos un método insertAtBeginning() que toma un elemento como entrada y lo agrega al comienzo de la lista enlazada. En el método insertAtBeginning(), primero crearemos un nodo con el elemento de entrada como datos.

Después de eso, apuntaremos el atributo next del nodo recién creado al nodo donde apunta el atributo Head de la lista enlazada. A continuación, asignaremos el nodo recién creado al atributo Head.

De esta forma, el nuevo nodo se insertará al principio de la lista enlazada.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertIntoEmptyList(self, element):
        newNode = Node(element)
        self.Head = newNode

    def insertAtBeginning(self, element):
        newNode = Node(element)
        newNode.next = self.Head
        self.Head = newNode


myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()

Producción :

The elements in the linked list are:
30 20 10

Como se muestra a continuación, podemos combinar los métodos anteriores para crear un solo método para insertar un elemento al comienzo de una lista vinculada.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertAtBeginning(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = self.Head
            self.Head = newNode


myLinkedList = LinkedList()
myLinkedList.insertAtBeginning(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()

Producción :

The elements in the linked list are:
30 20 10

Hemos fusionado el método insertIntoEmptyList() en el método insertAtBeginning() porque insertar en una lista enlazada vacía esencialmente significa que estamos insertando un elemento al principio de la lista enlazada.

Insertar un elemento al final de una lista vinculada

Insertar un elemento al final de una lista vacía es similar a insertar el elemento al principio de la lista enlazada.

Para insertar un elemento al final de una lista enlazada, primero comprobaremos si la lista enlazada está vacía. Si se encuentra que la lista enlazada está vacía, simplemente podemos asignar un nodo que contenga el nuevo elemento al atributo Head como hicimos en el método insertAtBeginning().

De lo contrario, recorreremos la lista enlazada hasta el final usando un bucle while. Comenzaremos con la Head y continuaremos moviéndonos al siguiente nodo usando el atributo next de los nodos hasta que encontremos que el atributo next del nodo apunta a None.

Una vez que llegamos a un nodo cuyo atributo next apunta a None, estamos en el último nodo. Ahora, crearemos un nuevo nodo usando los datos de entrada y asignaremos este nodo al siguiente atributo del último nodo de la lista enlazada.

De esta forma, el nuevo elemento se insertará al final de la lista enlazada. Puede implementar toda esta lógica en el método insertAtEnd() de la siguiente manera.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertAtEnd(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            current = self.Head
            while current.next is not None:
                current = current.next
            newNode = Node(element)
            current.next = newNode


myLinkedList = LinkedList()
myLinkedList.insertAtEnd(10)
myLinkedList.insertAtEnd(20)
myLinkedList.insertAtEnd(30)
print("The elements in the linked list are:")
myLinkedList.printList()

Producción :

The elements in the linked list are:
10 20 30

Insertar un Elemento en una Posición Dada en la Lista Vinculada

Usaremos una variable de contador y un bucle while para insertar un elemento en una posición dada en la lista enlazada.

Comenzaremos desde el puntero Head y continuaremos moviéndonos al siguiente nodo usando el bucle while. En cada iteración, también incrementaremos la variable contador.

Una vez que alcanzamos el nodo antes de la posición dada, salimos del bucle while. Además, saldremos del bucle si llegamos al final de la lista enlazada. De lo contrario, el programa se ejecutará en un error.

Después de eso, si todavía estamos en el Head, tenemos que agregar el elemento en la primera posición de la lista enlazada; asignaremos el nodo en la posición dada al puntero next que contiene el nuevo elemento de nodo. A continuación, asignaremos el nodo del nuevo elemento al Head de la lista enlazada.

Si no tenemos que insertar el elemento en la primera posición, asignaremos el nodo en la posición dada al puntero next del nodo que contiene el nuevo elemento. A continuación, asignaremos el nuevo nodo al atributo next del nodo en position-1.

De esta forma, el nuevo elemento se insertará en la posición dada. Como se muestra a continuación, puede implementar toda la lógica en el método insertAtPosition().

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(20, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(30, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()

Producción :

The elements in the linked list are:
10 
The elements in the linked list are:
10 20 
The elements in the linked list are:
10 20 30 
The elements in the linked list are:
10 40 20 30

Eliminar un elemento de la lista vinculada en Python

Puede haber tres situaciones cuando intentamos eliminar un elemento de una lista enlazada.

  1. Tenemos que eliminar el primer elemento de la lista enlazada.
  2. Tenemos que eliminar el último elemento de la lista enlazada.
  3. Tenemos que eliminar el elemento en cualquier posición de la lista Vinculada.

Discutamos todos estos casos uno por uno.

Eliminar el primer elemento de una lista vinculada

Para eliminar el primer elemento de una lista enlazada, primero comprobaremos si la lista enlazada está vacía o no.

Para ello comprobaremos si el Head de la lista enlazada apunta a None. En caso afirmativo, informaremos al usuario que la lista vinculada está vacía y no tenemos ningún elemento para eliminar.

De lo contrario, asignaremos el primer nodo a una variable temporal. Después de eso, asignaremos el segundo nodo de la lista enlazada al atributo Head.

Luego, eliminaremos el primer nodo almacenado en la variable temporal usando la instrucción del. Como se muestra a continuación, puede implementar toda la lógica en el método deleteFromBeginning().

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteFromBeginning(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            node = self.Head
            self.Head = self.Head.next
            del node


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()

Producción :

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
40 20 30 
The elements in the linked list are:
20 30

Eliminar el último elemento de una lista vinculada

Para eliminar el último elemento de una lista enlazada, primero comprobaremos si la lista enlazada está vacía o no.

Para ello comprobaremos si el Head de la lista enlazada apunta a None. En caso afirmativo, informaremos al usuario que la lista vinculada está vacía y no tenemos ningún elemento para eliminar.

Si hay elementos presentes en la lista, seguiremos el siguiente proceso.

  1. Asignar el primer nodo a una variable current.
  2. Inicializar una variable previous a None.
  3. Atraviese la lista enlazada utilizando un bucle while, asigne el nodo en la variable current a la variable previous y avance la variable current al siguiente nodo hasta que la variable current llegue al último nodo . En este caso, el atributo next del nodo asignado a current pasa a ser None.
  4. Una vez que la variable actual llegue al último nodo, asignaremos None al atributo next de la variable previous y eliminaremos el nodo asignado a la variable current.

Podemos eliminar el último elemento de una lista enlazada ejecutando los pasos anteriores. Como se muestra a continuación, puede implementar toda la lógica en el método deleteFromLast().

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteFromLast(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            while current.next is not None:
                previous = current
                current = current.next
            previous.next = None
            del current


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()

Producción :

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
10 40 20 
The elements in the linked list are:
10 40

Eliminar el elemento en cualquier posición dada en la lista vinculada

Para eliminar un elemento en cualquier posición dada en la lista vinculada, primero verificaremos si la lista vinculada está vacía o no.

Para ello comprobaremos si el Head de la lista enlazada apunta a None. En caso afirmativo, informaremos al usuario que la lista vinculada está vacía y no tenemos ningún elemento para eliminar.

Si hay elementos presentes en la lista enlazada, y tenemos que eliminar un elemento en cualquier otra posición, seguiremos los siguientes pasos.

  1. Asignar el primer nodo a una variable current.
  2. Inicializar una variable previous a None.
  3. Inicializar una variable contar a 1.
  4. Atraviese la lista enlazada usando un bucle while, incremente count en cada iteración, asigne el nodo en la variable current a previous, y avance la variable current al siguiente nodo hasta que el count la variable tiene la posición del elemento a borrar o llegamos al final de la lista enlazada. En este punto, la variable actual se referirá al nodo que debe eliminarse.
  5. Una vez que el conteo llega a ser igual a la posición del elemento a ser borrado, puede haber dos situaciones.
  6. Si todavía estamos en la Head, en la 1ª posición, asignaremos al atributo Head el nodo al que hace referencia el atributo next de la variable actual. Después de eso, eliminaremos la variable current.
  7. Si no estamos en la 1ª posición, asignaremos el siguiente nodo de la variable current al siguiente atributo del nodo asignado a la variable previous. Eliminaremos el nodo asignado a la variable current. De esta forma, se eliminará el elemento en la posición dada.

Podemos implementar la lógica anterior en el método deleteAtPosition() discutido a continuación.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteAtPosition(self, position):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            count = 1
            while current.next is not None and count < position:
                previous = current
                current = current.next
                count += 1
            if current == self.Head:
                self.Head = current.next
                del current
            else:
                previous.next = current.next
                del current


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(2)
print("The elements in the linked list are:")
myLinkedList.printList()

Producción :

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
40 20 30 
The elements in the linked list are:
40 30

Cuente la cantidad de elementos en una lista vinculada en Python

Para contar el número de elementos en una lista enlazada, simplemente inicializaremos una variable contar a 0.

Después de eso, comenzaremos desde el Head y pasaremos al siguiente nodo usando un bucle while hasta llegar al final de la lista enlazada. En cada iteración del bucle while, incrementaremos el conteo en 1.

Tras ejecutar el bucle while, tendremos el número de elementos de la lista enlazada en la variable count. Puede implementar esta lógica como se muestra en el método countElements() a continuación.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def countElements(self):
        count = 0
        current = self.Head
        while current is not None:
            count += 1
            current = current.next
        print("Number of elements in the linked list are:", count)


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.countElements()

Producción :

The elements in the linked list are:
10 40 20 30 
Number of elements in the linked list are: 4

Actualizar un nodo en la lista vinculada en Python

Puede haber dos situaciones para actualizar el valor en un nodo en la lista enlazada.

  1. Necesitamos reemplazar un valor.
  2. Necesitamos asignar un nuevo valor al elemento en cualquier posición dada en la lista enlazada.

Reemplazar un valor en la lista vinculada

Para reemplazar un valor en la lista enlazada, comenzaremos desde el primer nodo y recorreremos la lista enlazada usando un bucle while.

Verificaremos si el nodo current contiene el valor a reemplazar en cada nodo. En caso afirmativo, reemplazaremos el valor en el nodo actual con el nuevo valor.

De esta forma, podemos actualizar la primera aparición de cualquier elemento en la lista enlazada como se muestra en el método replaceElement().

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def replaceElement(self, old_element, new_element):
        current = self.Head
        while current is not None:
            if current.data == old_element:
                current.data = new_element
                break
            current = current.next


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(30, 100)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(20, 150)
print("The elements in the linked list are:")
myLinkedList.printList()

Producción :

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
10 40 20 100 
The elements in the linked list are:
10 40 150 100

Actualice el elemento en una posición dada en la lista vinculada

Para actualizar el elemento en una posición dada en la lista enlazada, primero verificaremos si la lista enlazada está vacía. Si es así, puede haber dos situaciones.

Si la lista enlazada está vacía y tenemos que actualizar algún elemento que no sea la primera posición, avisaremos al usuario de que no se puede hacer.

Si la lista enlazada está vacía y tenemos que actualizar el elemento en la primera posición, crearemos un nuevo nodo con el elemento dado y asignaremos el nodo al Head de la lista enlazada. De lo contrario, inicializaremos una variable contador a 1.

Después de eso, recorreremos la lista enlazada usando un bucle while. En cada iteración del bucle while, nos moveremos al siguiente nodo en la lista enlazada, incrementaremos la variable contador en 1 y comprobaremos si hemos llegado a la posición del elemento que necesita ser actualizado.

Si llegamos a la posición que necesita ser actualizada, actualizaremos el valor en el nodo actual de la lista enlazada y notificaremos al usuario.

Si no podemos llegar a la posición que necesita ser actualizada y el bucle while termina, le notificaremos al usuario que no hay suficientes elementos y no podemos actualizar el valor. Esta lógica se puede implementar como se muestra a continuación en el método updateAtPosition().

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def updateAtPosition(self, new_element, position):
        if self.Head is None and position != 1:
            print("No element to update in the linked list.")
            return
        elif self.Head is None and position == 1:
            newNode = Node(new_element)
            self.Head = newNode
            return
        count = 1
        current = self.Head
        while current.next is not None and count < position:
            count += 1
            current = current.next
        if count == position:
            current.data = new_element
        elif current.next is None:
            print("Not enough elements in the linked list.")


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(100, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(150, 12)
print("The elements in the linked list are:")
myLinkedList.printList()

Producción :

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
10 40 100 30 
Not enough elements in the linked list.
The elements in the linked list are:
10 40 100 30

Por qué usar una lista enlazada en Python

  • Si no necesita acceso aleatorio a los elementos, las listas enlazadas pueden ser una mejor alternativa. Debe usar listas vinculadas en lugar de listas normales en Python cuando tenemos millones de elementos para almacenar y no necesitamos acceso aleatorio.
  • El tamaño real de las listas es muy grande en comparación con el número de elementos presentes en ellas. El tamaño real de una lista es aproximadamente 1,5 veces el número de elementos presentes en ella. Asegura que tengamos suficiente memoria para insertar elementos en la lista. Sin embargo, una lista enlazada no requiere espacios adicionales.
  • Cuando insertamos un elemento en la lista enlazada, solo se requiere almacenamiento. Las listas también requieren una ubicación de memoria contigua. Por el contrario, los nodos de una lista enlazada pueden estar presentes en cualquier lugar de la memoria física. Se conectan mediante referencias.
  • Puede implementar estructuras de datos de pila y cola de manera eficiente utilizando listas vinculadas. Por otro lado, implementar una cola usando una lista es costoso en términos de complejidad de tiempo.

Lista enlazada de implementación completa en Python

El siguiente es el código de ejecución completo para implementar una lista vinculada en Python con todos los métodos discutidos en este artículo.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtBeginning(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = self.Head
            self.Head = newNode

    def insertAtEnd(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            current = self.Head
            while current.next is not None:
                current = current.next
            newNode = Node(element)
            current.next = newNode

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteFromBeginning(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            node = self.Head
            self.Head = self.Head.next
            del node

    def deleteFromLast(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            while current.next is not None:
                previous = current
                current = current.next
            previous.next = None
            del current

    def deleteAtPosition(self, position):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            count = 1
            while current.next is not None and count < position:
                previous = current
                current = current.next
                count += 1
            if current == self.Head:
                self.Head = current.next
                del current
            else:
                previous.next = current.next
                del current

    def countElements(self):
        count = 0
        current = self.Head
        while current is not None:
            count += 1
            current = current.next
        print("Number of elements in the linked list are:", count)

    def replaceElement(self, old_element, new_element):
        current = self.Head
        while current is not None:
            if current.data == old_element:
                current.data = new_element
                break
            current = current.next

    def updateAtPosition(self, new_element, position):
        if self.Head is None and position != 1:
            print("No element to update in the linked list.")
            return
        elif self.Head is None and position == 1:
            newNode = Node(new_element)
            self.Head = newNode
            return
        count = 1
        current = self.Head
        while current.next is not None and count < position:
            count += 1
            current = current.next
        if count == position:
            current.data = new_element
        elif current.next is None:
            print("Not enough elements in the linked list.")

Conclusión

En este artículo, hemos discutido la estructura de datos de la lista enlazada y su implementación en Python. También hemos implementado los métodos para varias operaciones en una lista enlazada.

En este artículo, hemos implementado todas las operaciones usando métodos. También puede implementar cada operación usando funciones que toman el Head de la lista enlazada como entrada y devuelven el encabezado después de ejecutar las operaciones requeridas.

Sin embargo, esto requerirá más recursos durante la ejecución. Por lo tanto, le sugiero que utilice el enfoque utilizado en este artículo.

Autor: Aditya Raj
Aditya Raj avatar Aditya Raj avatar

Aditya Raj is a highly skilled technical professional with a background in IT and business, holding an Integrated B.Tech (IT) and MBA (IT) from the Indian Institute of Information Technology Allahabad. With a solid foundation in data analytics, programming languages (C, Java, Python), and software environments, Aditya has excelled in various roles. He has significant experience as a Technical Content Writer for Python on multiple platforms and has interned in data analytics at Apollo Clinics. His projects demonstrate a keen interest in cutting-edge technology and problem-solving, showcasing his proficiency in areas like data mining and software development. Aditya's achievements include securing a top position in a project demonstration competition and gaining certifications in Python, SQL, and digital marketing fundamentals.

GitHub

Artículo relacionado - Python Data Structure