Listas enlazadas en detalle con ejemplos de Python: Listas enlazadas individuales

Las listas enlazadas son una de las estructuras de datos más utilizadas en cualquier lenguaje de programación. En este artículo, estudiaremos las listas enlazadas en detalle. Veremos q...

Las listas enlazadas son una de las estructuras de datos más utilizadas en cualquier lenguaje de programación. En este artículo, estudiaremos las listas enlazadas en detalle. Veremos cuáles son los diferentes tipos de listas enlazadas, cómo atravesar una lista enlazada, cómo insertar y eliminar elementos de una lista enlazada, cuáles son las diferentes técnicas para ordenar una lista enlazada, cómo invertir una lista enlazada, etc. .

After reading this article, you should be able to crack all the preguntas de entrevista de lista enlazada.

¿Qué es una lista enlazada?

Antes de estudiar qué son las listas enlazadas, primero revisemos brevemente cómo las matrices almacenan datos. En las matrices, los datos se almacenan en ubicaciones de memoria contiguas. Por ejemplo, si el primer elemento de la matriz se almacena en el índice 10 de la memoria y tiene un tamaño de 15 bytes, el segundo elemento se almacenará en el índice 10+15+1 = índice 26. Por lo tanto, es sencillo recorrer una matriz.

Para encontrar el tercer elemento en una matriz, simplemente puede usar el índice inicial del primer elemento, más el tamaño del primer elemento, más el tamaño del segundo elemento, más 1.

Cómo almacenan datos las listas vinculadas

Las listas enlazadas, por otro lado, son diferentes. Listas enlazadas, no almacene datos en ubicaciones de memoria contiguas. Para cada elemento en la ubicación de la memoria, la lista enlazada almacena el valor del elemento y la referencia o puntero al siguiente elemento. Un par del elemento de la lista enlazada y la referencia al siguiente elemento constituye un nodo.

Por ejemplo, si un nodo consta de 34|10, significa que el valor del nodo es 30, mientras que el siguiente elemento se almacena en la ubicación de memoria "10". Para recorrer una lista enlazada, solo necesita conocer la ubicación de memoria o la referencia del primer nodo, el resto de los nodos se pueden recorrer secuencialmente utilizando la referencia al siguiente elemento en cada nodo.

La referencia al primer nodo también se conoce como nodo de inicio.

Listas vinculadas frente a matrices:

  • Una lista enlazada es una estructura de datos dinámica, lo que significa que la memoria reservada para la lista de enlaces se puede aumentar o reducir en tiempo de ejecución. No se asigna memoria por adelantado para una estructura de datos de lista enlazada. Cada vez que se requiere agregar un nuevo elemento al vinculado, la memoria para el nuevo nodo se crea en tiempo de ejecución. Por otro lado, en el caso de la matriz, la memoria debe asignarse por adelantado para un número específico de elementos. En los casos en que no hay suficientes elementos disponibles para llenar todo el índice de matriz, se desperdicia espacio de memoria.
  • Dado que las matrices requieren ubicaciones de memoria contiguas, es muy difícil eliminar o insertar un elemento en una matriz, ya que se deben actualizar las ubicaciones de memoria de una gran cantidad de elementos. Por otro lado, los elementos de la lista vinculada no se almacenan en una ubicación de memoria contigua, por lo tanto, puede actualizar fácilmente las listas vinculadas.
  • Debido a su flexibilidad, una lista enlazada es más adecuada para implementar estructuras de datos como pilas, colas y listas.

Sin embargo, también hay algunas desventajas en la lista enlazada.

  • Dado que cada elemento de la lista vinculada tiene que almacenar la referencia al elemento siguiente, se requiere algo de memoria adicional.
  • A diferencia de las matrices, donde puede acceder directamente a un elemento, no puede acceder directamente a un elemento de una lista vinculada, ya que la única información que tiene es la referencia al primer elemento. En Grandes términos O, el peor tiempo de acceso es O(n).

En esta serie de artículos estudiaremos los siguientes tipos de listas enlazadas junto con sus diferentes funcionalidades.

  • Lista enlazada única
  • Lista doblemente enlazada
  • Lista enlazada circular
  • Lista vinculada con encabezado
  • Lista ordenada ordenada

En esta primera parte del artículo, nos centraremos en la lista enlazada única y sus diferentes operaciones.

Lista enlazada única
Crear la clase de nodo
Creando la Clase de Lista Vinculada Única
Atravesar elementos de lista enlazada
Insertar elementos
Elementos de conteo
Elementos de búsqueda
Creación de una lista vinculada
Eliminación de elementos
Invertir una lista vinculada

Lista de enlaces únicos

Una sola lista enlazada es la más simple de todas las variantes de listas enlazadas. Cada nodo en una sola lista enlazada contiene un elemento y una referencia al siguiente elemento y eso es todo.

En esta sección, veremos cómo crear un nodo para la lista enlazada única junto con las funciones para diferentes tipos de inserción, recorrido y eliminación.

Creación de la clase de nodo

Lo primero que debe hacer es crear una clase para los nodos. Los objetos de esta clase serán los nodos reales que insertaremos en nuestra lista enlazada. Sabemos que un nodo de una sola lista enlazada contiene el elemento y la referencia al siguiente nodo. Por lo tanto, nuestra clase de nodo contendrá dos variables miembro item y ref. El valor del elemento se establecerá mediante el valor pasado a través del constructor, mientras que la referencia se establecerá inicialmente en nulo.

Ejecute el siguiente script:

1
2
3
4
class Node:
    def __init__(self, data):
        self.item = data
        self.ref = None

Creación de la clase de lista enlazada única

A continuación, necesitamos crear una clase para la Lista enlazada. Esta clase contendrá los métodos para insertar, eliminar, atravesar y ordenar la lista. Inicialmente, la clase solo contendrá un miembro start_node que apuntará al nodo inicial o primero de la lista. El valor de start_node se establecerá en nulo usando el constructor ya que la lista vinculada estará vacía en el momento de la creación. El siguiente script crea una clase para la lista enlazada.

1
2
3
class LinkedList:
    def __init__(self):
        self.start_node = None

Ahora hemos creado una clase para nuestra lista única. El siguiente paso es agregar la función de inserción para insertar elementos en la lista vinculada. Pero antes de eso, agregaremos una función para recorrer una lista enlazada. Esta función nos ayudará a leer los datos de nuestra lista.

Atravesar elementos de listas enlazadas

El código de Python para la función poligonal es el siguiente. Agregue la siguiente función a la clase LinkedList que creamos en la última sección.

1
2
3
4
5
6
7
8
9
def traverse_list(self):
    if self.start_node is None:
        print("List has no element")
        return
    else:
        n = self.start_node
        while n is not None:
            print(n.item , " ")
            n = n.ref

Veamos qué está pasando en la función anterior. La función tiene dos partes principales. Primero, verifica si la lista enlazada está vacía o no. El siguiente código comprueba que:

1
2
3
  if self.start_node is None:
        print("List has no element")
        return

Si la lista vinculada está vacía, eso significa que no hay ningún elemento para iterar. En tales casos, la función traverse_list() simplemente imprime la declaración de que la lista no tiene elementos.

De lo contrario, si la lista tiene un elemento, se ejecutará el siguiente código:

1
2
3
4
    n = self.start_node
        while n is not None:
            print(n.item , " ")
            n = n.ref

Como dijimos antes, la variable start contendrá una referencia a los primeros nodos. Por lo tanto, inicializamos una variable n con la variable start. A continuación, ejecutamos un ciclo que se ejecuta hasta que n se convierte en ninguno. Dentro del bucle, imprimimos el elemento almacenado en el nodo actual y luego establecemos el valor de la variable n en n.ref, que contiene la referencia al siguiente nodo. La referencia del último nodo es Ninguno ya que no hay ningún nodo después de eso. Por lo tanto, cuando n se convierte en Ninguno, el ciclo termina.

Ahora, tenemos una función para recorrer una lista enlazada, veamos cómo podemos agregar elementos a una sola lista enlazada.

Inserción de elementos

Según la ubicación en la que desee insertar un elemento, existen diferentes formas de insertar elementos en una sola lista vinculada.

Inserción de elementos al principio

La forma más sencilla de insertar un elemento en una sola lista vinculada es agregar un elemento al comienzo de la lista. La siguiente función inserta un elemento al principio de la lista. Agregue esta función a la clase LinkedList que creamos anteriormente.

1
2
3
4
    def insert_at_start(self, data):
        new_node = Node(data)
        new_node.ref = self.start_node
        self.start_node= new_node

En el script anterior, creamos un método insert_at_start(), el método acepta un parámetro, que es básicamente el valor del elemento que queremos insertar. Dentro del método, simplemente creamos un objeto de la clase Node y establecemos su referencia a start_node ya que start_node estaba almacenando previamente el primer nodo, que después de la inserción de un nuevo nodo al inicio se convertirá en el segundo nodo .

Por lo tanto, agregamos la referencia de start_node a la variable ref del nuevo nodo. Ahora que new_node es el primer nodo, establecemos el valor de la variable start_node en new_node.

Inserción de elementos al final

La siguiente función se utiliza para agregar un elemento al final de la lista vinculada.

1
2
3
4
5
6
7
8
9
  def insert_at_end(self, data):
        new_node = Node(data)
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

En el script anterior, creamos una función insert_at_end(), que inserta el elemento al final de la lista enlazada. El valor del elemento que queremos insertar se pasa como argumento a la función. La función consta de dos partes. Primero verificamos si la lista enlazada está vacía o no, si la lista enlazada está vacía, todo lo que tenemos que hacer es establecer el valor de la variable start_node en el objeto new_node.

Por otro lado, si la lista ya contiene algunos nodos. Inicializamos una variable n con el nodo de inicio. Luego iteramos a través de todos los nodos en la lista usando un ciclo while como lo hicimos en el caso de la función traverse_list. El ciclo termina cuando llegamos al último nodo. Luego establecemos la referencia del último nodo al nuevo_nodo recién creado.

Agrega la función insert_at_end() a la clase LinkedList.

Insertar elemento después de otro elemento

Es posible que necesitemos agregar un elemento después de otro elemento en una sola lista vinculada. Para hacerlo, podemos usar la función insert_after_item() como se define a continuación:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
    def insert_after_item(self, x, data):

        n = self.start_node
        print(n.ref)
        while n is not None:
            if n.item == x:
                break
            n = n.ref
        if n is None:
            print("item not in the list")
        else:
            new_node = Node(data)
            new_node.ref = n.ref
            n.ref = new_node

La función insert_after_item() acepta dos parámetros: x y data. El primer parámetro es el elemento después del cual desea insertar el nuevo nodo, mientras que el segundo parámetro contiene el valor del nuevo nodo.

Comenzamos creando una nueva variable n y asignándole la variable start_node. A continuación, recorremos la lista enlazada usando el bucle while. El bucle while se ejecuta hasta que n se convierte en Ninguno. Durante cada iteración, verificamos si el valor almacenado en el nodo actual es igual al valor pasado por el parámetro x. Si la comparación devuelve verdadero, rompemos el bucle.

A continuación, si se encuentra el elemento, la variable n no será Ninguno. La referencia de nuevo_nodo se establece en la referencia almacenada por n y la referencia de n se establece en nuevo_nodo. Agrega la función insert_after_item() a la clase LinkesList.

Insertar elemento antes de otro elemento
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    def insert_before_item(self, x, data):
        if self.start_node is None:
            print("List has no element")
            return

        if x == self.start_node.item:
            new_node = Node(data)
            new_node.ref = self.start_node
            self.start_node = new_node
            return

        n = self.start_node
        print(n.ref)
        while n.ref is not None:
            if n.ref.item == x:
                break
            n = n.ref
        if n.ref is None:
            print("item not in the list")
        else:
            new_node = Node(data)
            new_node.ref = n.ref
            n.ref = new_node

En el script de arriba definimos la función insert_before_item(). La función tiene tres partes. Veamos cada parte en detalle.

1
2
3
     if self.start_node is None:
        print("List has no element")
        return

En el script anterior, verificamos si la lista está vacía. Si en realidad está vacío, simplemente imprimimos que la lista no tiene ningún elemento y regresamos de la función.

A continuación, comprobamos si el elemento se encuentra en el primer índice. Mira el siguiente guión:

1
2
3
4
5
     if x == self.start_node.item:
        new_node = Node(data)
        new_node.ref = self.start_node
        self.start_node = new_node
        return

Si el elemento después del cual queremos insertar un nuevo nodo se encuentra en el primer índice. Simplemente establecemos la referencia del nodo recién insertado en start_node y luego establecemos el valor de start_node en new_node.

Finalmente, si la lista no es Ninguno y el elemento no se encuentra en el primer índice, creamos una nueva variable n y le asignamos la variable start_node. A continuación, recorremos la lista enlazada usando el bucle while. El bucle while se ejecuta hasta que n.ref se convierte en Ninguno. Durante cada iteración, comprobamos si el valor almacenado en la referencia del nodo actual es igual al valor pasado por el parámetro x. Si la comparación devuelve verdadero, rompemos el bucle.

A continuación, si se encuentra el elemento, la variable n.ref no será Ninguno. La referencia de nuevo_nodo se establece en la referencia de n y la referencia de n se establece en nuevo_nodo. Mira el siguiente guión:

1
2
3
4
5
6
    if n.ref is None:
        print("item not in the list")
    else:
        new_node = Node(data)
        new_node.ref = n.ref
        n.ref = new_node

Agregue la función insert_before_item() a la clase LinkedList.

Inserción de elemento en un índice específico

A veces, necesitamos insertar un elemento en un índice específico, podemos hacerlo con la ayuda del siguiente script:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    def insert_at_index (self, index, data):
        if index == 1:
            new_node = Node(data)
            new_node.ref = self.start_node
            self.start_node = new_node
        i = 1
        n = self.start_node
        while i < index-1 and n is not None:
            n = n.ref
            i = i+1
        if n is None:
            print("Index out of bound")
        else: 
            new_node = Node(data)
            new_node.ref = n.ref
            n.ref = new_node

En el script, primero verificamos si el índice en el que queremos almacenar el elemento es 1, luego simplemente asignamos start_node a la referencia de new_node y luego establecemos el valor de start_node en new_node.

A continuación, ejecute un bucle while que se ejecute hasta que el contador i sea mayor o igual que index-1. Por ejemplo, si desea agregar un nuevo nodo al tercer índice. Durante la primera iteración del ciclo while, i se convertirá en 2 y el nodo iterado actualmente será '2'. El bucle no se ejecutará de nuevo ya que i ahora es 2, que es igual a índice-1 (3-1=2). Por lo tanto, el bucle se romperá. A continuación, agregamos un nuevo nodo después del nodo iterado actualmente (que es el nodo 2), por lo tanto, el nuevo nodo se agrega en index.

Es importante mencionar que si el índice o la ubicación pasada como argumento es mayor que el tamaño de la lista enlazada, se mostrará un mensaje al usuario de que el índice está fuera de rango o fuera de límite.

Prueba de funciones de inserción

Ahora que hemos definido todas nuestras funciones de inserción, vamos a probarlas.

Primero, cree un objeto de la clase de lista enlazada de la siguiente manera:

1
new_linked_list = LinkedList()

A continuación, llamemos primero a la función insert_at_end() para agregar tres elementos a la lista enlazada. Ejecute el siguiente script:

1
2
3
new_linked_list.insert_at_end(5)
new_linked_list.insert_at_end(10)
new_linked_list.insert_at_end(15)

Para ver si los elementos realmente se han insertado, recorramos la lista enlazada usando la función de recorrido.

1
new_linked_list.traverse_list()

Debería ver el siguiente resultado:

1
2
3
5
10
15

A continuación, agreguemos un elemento al principio:

1
new_linked_list.insert_at_start(20)

Ahora, si recorre la lista, debería ver el siguiente resultado:

1
2
3
4
20
5
10
15

Agreguemos un nuevo elemento 17 después del elemento 10:

1
new_linked_list.insert_after_item(10, 17)

Recorrer la lista devuelve el siguiente resultado ahora:

1
2
3
4
5
20
5
10
17
15 

Puede ver 17 insertado después de 10.

Ahora insertemos otro elemento 25 antes del elemento 17 usando la función insert_before_item() como se muestra a continuación:

1
new_linked_list.insert_before_item(17, 25)

Ahora la lista contendrá los siguientes elementos:

1
2
3
4
5
6
20
5
10
25
17
15

Finalmente, agreguemos un elemento en la tercera ubicación, que actualmente está ocupada por 10. Verá que 10 avanzará una ubicación y el nuevo elemento se insertará en su lugar. La función insert_at_index() puede usarse para este propósito. El siguiente script inserta el elemento 8 en el tercer índice de la lista.

1
new_linked_list.insert_at_index(3,8)

Ahora, si recorre la lista, debería ver el siguiente resultado:

1
2
3
4
5
6
7
20
5
8
10
25
17
15

Y con eso, hemos probado todas nuestras funciones de inserción. Actualmente tenemos 7 elementos en nuestra lista. Escribamos una función que devuelva el número de elementos en una lista enlazada.

Elementos de conteo {#elementos de conteo}

La siguiente función cuenta el número total de elementos.

1
2
3
4
5
6
7
8
9
    def get_count(self):
        if self.start_node is None:
            return 0;
        n = self.start_node
        count = 0;
        while n is not None:
            count = count + 1
            n = n.ref
        return count

En el script anterior creamos la función get_count() que simplemente cuenta el número de elementos en la lista enlazada. La función simplemente atraviesa todos los nodos de la matriz e incrementa un contador usando el ciclo while. Al final del bucle, el contador contiene el número total de elementos del bucle.

Agregue la función anterior a la clase LinkedList, compile la clase LinkedList y luego inserte algunos elementos en LinkedList como hicimos en la última sección. Teníamos 7 artículos en nuestra lista enlazada, al final de la última sección.

Usemos la función get_count() para obtener el número total de elementos en la lista:

1
new_linked_list.get_count()

Debería ver la cantidad de elementos en su lista vinculada en la salida.

Alternativamente, otra forma de obtener el 'recuento' de la lista sería realizar un seguimiento del número de elementos insertados y eliminados de la lista en una variable de contador simple que pertenezca a la clase LinkedList. Esto funciona bien y es más rápido que el método get_count anterior, si la estructura de datos de la lista subyacente no se puede manipular desde fuera de la clase.

Elementos de búsqueda {#elementos de búsqueda}

Buscar un elemento es bastante similar a contar o recorrer una lista enlazada, todo lo que tiene que hacer es comparar el valor a buscar con el valor del nodo durante cada iteración. Si se encuentra el valor, imprima que se encuentra el valor y rompa el ciclo. Si el elemento no se encuentra después de recorrer todos los nodos, simplemente imprima que el elemento no se encuentra.

El script para search_item() es el siguiente:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    def search_item(self, x):
        if self.start_node is None:
            print("List has no elements")
            return
        n = self.start_node
        while n is not None:
            if n.item == x:
                print("Item found")
                return True
            n = n.ref
        print("item not found")
        return False

Agregue la función anterior a la clase LinkedList. Busquemos un elemento en la lista creada anteriormente. Ejecute el siguiente script:

1
new_linked_list.search_item(5)

Dado que insertamos 5 en nuestra lista vinculada, la función anterior devolverá verdadero. La salida se verá así:

1
2
Item found
True

Crear una lista enlazada

Aunque podemos agregar elementos uno por uno usando cualquiera de las funciones de inserción. Vamos a crear una función que le pida al usuario que ingrese la cantidad de elementos en el nodo y luego el elemento individual e ingrese ese elemento en la lista vinculada.

1
2
3
4
5
6
7
    def make_new_list(self):
        nums = int(input("How many nodes do you want to create: "))
        if nums == 0:
            return
        for i in range(nums):
            value = int(input("Enter the value for the node:"))
            self.insert_at_end(value)

En el script anterior, la función make_new_list() primero le pregunta al usuario la cantidad de elementos en la lista. A continuación, mediante un bucle for, se solicita al usuario que introduzca el valor de cada nodo, que luego se inserta en la lista vinculada mediante la función insert_at_end().

La siguiente captura de pantalla muestra la función make_new_list() en acción.

{.img-responsive}

Eliminación de elementos

En esta sección, veremos las diferentes formas de eliminar un elemento de una sola lista enlazada.

Eliminación desde el inicio

La eliminación de un elemento o elemento desde el inicio de la lista vinculada es sencilla. Tenemos que establecer la referencia de start_node al segundo nodo, lo que podemos hacer simplemente asignando el valor de la referencia del nodo de inicio (que apunta al segundo nodo) al nodo de inicio como se muestra a continuación:

1
2
3
4
5
    def delete_at_start(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        self.start_node = self.start_node.ref

En el script anterior, primero verificamos si la lista está vacía o no. Si la lista está vacía, mostramos el mensaje de que la lista no tiene ningún elemento para eliminar. De lo contrario, asignamos el valor de start_node.ref a start_node. El start_node ahora apuntará hacia el segundo elemento. Agrega la función delete_at_start() a la clase LinkedList.

Eliminación al final

Para eliminar un elemento del final de la lista, simplemente tenemos que iterar a través de la lista enlazada hasta el penúltimo elemento, y luego debemos establecer la referencia del penúltimo elemento en ninguno, lo que convertirá el penúltimo elemento en último elemento

El script para la función delete_at_end es el siguiente:

1
2
3
4
5
6
7
8
9
    def delete_at_end(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return

        n = self.start_node
        while n.ref.ref is not None:
            n = n.ref
        n.ref = None

Agregue el script anterior a la clase LinkedList().

Eliminación por valor de elemento

Para eliminar el elemento por valor, primero debemos encontrar el nodo que contiene el elemento con el valor especificado y luego eliminar el nodo. Encontrar el elemento con el valor especificado es bastante similar a buscar el elemento. Una vez que se encuentra el elemento que se va a eliminar, la referencia del nodo anterior al elemento se establece en el nodo que existe después de eliminar el elemento. Mira el siguiente guión:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
  def delete_element_by_value(self, x):
    if self.start_node is None:
        print("The list has no element to delete")
        return

    # Deleting first node 
    if self.start_node.item == x:
        self.start_node = self.start_node.ref
        return

    n = self.start_node
    while n.ref is not None:
        if n.ref.item == x:
            break
        n = n.ref

    if n.ref is None:
        print("item not found in the list")
    else:
        n.ref = n.ref.ref

En el script anterior, primero verificamos si la lista está vacía. A continuación, comprobamos si el elemento a eliminar se encuentra al principio de la lista enlazada. Si el elemento se encuentra al principio, lo eliminamos asignando el primer nodo a la referencia del primer nodo (que básicamente se refiere al segundo nodo).

Finalmente, si el elemento no se encuentra en el primer índice, iteramos a través de la lista enlazada y verificamos si el valor del nodo que se itera es igual al valor que se eliminará. Si la comparación devuelve verdadero, establecemos la referencia del nodo anterior al nodo que existe después del nodo que se está eliminando.

Prueba de funciones de eliminación

Probemos las funciones de borrado que acabamos de crear. Pero antes de eso, agregue algunos datos ficticios a nuestra lista vinculada utilizando el siguiente script:

1
2
3
4
5
new_linked_list.insert_at_end(10)
new_linked_list.insert_at_end(20)
new_linked_list.insert_at_end(30)
new_linked_list.insert_at_end(40)
new_linked_list.insert_at_end(50)

El script anterior inserta 5 elementos en una lista enlazada. Si recorre la lista, debería ver los siguientes elementos:

1
2
3
4
5
10
20
30
40
50

Primero eliminemos un elemento desde el principio:

1
new_linked_list.delete_at_start()

Ahora, si recorre la lista, debería ver el siguiente resultado:

1
2
3
4
20
30
40
50 

Ahora eliminemos un elemento del final:

1
new_linked_list.delete_at_end()

La lista ahora contiene los siguientes elementos:

1
2
3
20
30
40

Finalmente, eliminemos un elemento por valor, digamos 30.

1
new_linked_list.delete_element_by_value(30)

Ahora, si recorre la lista, no debería ver el elemento 30.

Inversión de una lista vinculada

Para invertir una lista enlazada, debe tener tres variables, anterior, n y siguiente. El prev hará un seguimiento del nodo anterior, el next hará un seguimiento del siguiente nodo y el n corresponderá al nodo actual.

Comenzamos un ciclo while asignando el nodo de inicio a la variable n y la variable prev se inicializa a none. El bucle se ejecuta hasta que n se convierte en ninguno. Dentro del ciclo while, debe realizar las siguientes funciones.

  • Asignar el valor de la referencia del nodo actual a siguiente.
  • Establecer el valor de referencia del nodo actual n al prev
  • Establezca la variable prev en el nodo actual n.
  • Establecer el nodo actual n al valor del nodo siguiente.

Al final del bucle, la variable prev apuntará al último nodo, debemos convertirlo en el primer nodo, por lo que establecemos el valor de la variable self.start_node en prev. El bucle while hará que cada nodo apunte a su nodo anterior, lo que dará como resultado una lista enlazada invertida. El guión es el siguiente:

1
2
3
4
5
6
7
8
9
    def reverse_linkedlist(self):
        prev = None
        n = self.start_node
        while n is not None:
            next = n.ref
            n.ref = prev
            prev = n
            n = next
        self.start_node = prev

Agregue la función anterior a la clase LinkedList. Cree una lista enlazada de números aleatorios y luego vea si puede revertirla usando la función reverse_linkedlist().

Conclusión

En este artículo, comenzamos nuestra discusión sobre una sola lista enlazada. Vimos cuáles son las diferentes funciones que se pueden realizar en la lista vinculada, como atravesar una lista vinculada, insertar elementos en una lista vinculada, buscar y contar elementos de lista vinculada, eliminar elementos de una lista vinculada e invertir una sola lista vinculada.

Esta es la Parte 1 de la serie de artículos en la lista enlazada. En la siguiente parte (próximamente), veremos cómo ordenar una sola lista enlazada, cómo fusionar listas ordenadas enlazadas y cómo eliminar ciclos de una sola lista enlazada. da.