circular linked list data structure c with illustration
Una descripción completa de la lista enlazada circular.
Una lista enlazada circular es una variación de la lista enlazada. Es una lista enlazada cuyos nodos están conectados de tal manera que forma un círculo.
En la lista enlazada circular, el siguiente puntero del último nodo no se establece en nulo pero contiene la dirección del primer nodo formando así un círculo.
=> Visite aquí para aprender C ++ desde cero.
Lo que vas a aprender:
Lista enlazada circular en C ++
La disposición que se muestra a continuación es para una lista enlazada individualmente.
Una lista enlazada circular puede ser una lista enlazada individualmente o una lista enlazada doble. En una lista enlazada doblemente circular, el puntero anterior del primer nodo está conectado al último nodo mientras que el siguiente puntero del último nodo está conectado al primer nodo.
Su representación se muestra a continuación.
Declaración
Podemos declarar un nodo en una lista enlazada circular como cualquier otro nodo como se muestra a continuación:
|_+_|Para implementar la lista enlazada circular, mantenemos un puntero externo 'último' que apunta al último nodo en la lista enlazada circular. Por lo tanto, last-> next apuntará al primer nodo en la lista vinculada.
Al hacer esto, nos aseguramos de que cuando insertemos un nuevo nodo al principio o al final de la lista, no necesitemos recorrer toda la lista. Esto se debe a que el último apunta al último nodo, mientras que el último-> siguiente apunta al primer nodo.
Esto no habría sido posible si hubiéramos apuntado el puntero externo al primer nodo.
Operaciones básicas
La lista enlazada circular admite la inserción, eliminación y recorrido de la lista. Discutiremos cada una de las operaciones en detalle ahora.
Inserción
Podemos insertar un nodo en una lista enlazada circular, ya sea como primer nodo (lista vacía), al principio, al final o entre los otros nodos. Veamos cada una de estas operaciones de inserción usando una representación pictórica a continuación.
# 1) Insertar en una lista vacía
Cuando no hay nodos en la lista circular y la lista está vacía, el último puntero es nulo, luego insertamos un nuevo nodo N apuntando el último puntero al nodo N como se muestra arriba. El siguiente puntero de N apuntará al nodo N mismo, ya que solo hay un nodo. Por tanto, N se convierte en el primer y último nodo de la lista.
# 2) Insertar al principio de la lista
Como se muestra en la representación anterior, cuando agregamos un nodo al principio de la lista, el siguiente puntero del último nodo apunta al nuevo nodo N, lo que lo convierte en un primer nodo.
N-> siguiente = último-> siguiente
Último-> siguiente = N
# 3) Insertar al final de la lista
Para insertar un nuevo nodo al final de la lista, seguimos estos pasos:
las 10 mejores agencias de contratación del mundo
N-> siguiente = último -> siguiente;
último -> siguiente = N
último = N
# 4) Insertar entre la lista
Supongamos que necesitamos insertar un nuevo nodo N entre N3 y N4, primero necesitamos recorrer la lista y ubicar el nodo después del cual se insertará el nuevo nodo, en este caso, su N3.
Una vez ubicado el nodo, realizamos los siguientes pasos.
N -> siguiente = N3 -> siguiente;
N3 -> siguiente = N
Esto inserta un nuevo nodo N después de N3.
Supresión
La operación de eliminación de la lista enlazada circular implica ubicar el nodo que se debe eliminar y luego liberar su memoria.
Para esto mantenemos dos punteros adicionales curr y prev y luego recorremos la lista para ubicar el nodo. El nodo dado que se eliminará puede ser el primer nodo, el último nodo o el nodo intermedio. Dependiendo de la ubicación, establecemos los punteros curr y prev y luego eliminamos el nodo curr.
A continuación, se muestra una representación gráfica de la operación de eliminación.
El recorrido
El recorrido es una técnica de visitar todos y cada uno de los nodos. En listas enlazadas lineales como listas enlazadas individualmente y listas enlazadas doblemente, el recorrido es fácil ya que visitamos cada nodo y nos detenemos cuando se encuentra NULL.
Sin embargo, esto no es posible en una lista enlazada circular. En una lista enlazada circular, comenzamos desde el siguiente del último nodo que es el primer nodo y atravesamos cada nodo. Nos detenemos cuando llegamos una vez más al primer nodo.
Ahora presentamos una implementación de las operaciones de lista enlazada circular usando C ++ y Java. Hemos implementado operaciones de inserción, eliminación y recorrido aquí. Para una comprensión clara, hemos representado la lista enlazada circular como
Por lo tanto, al último nodo 50, adjuntamos nuevamente el nodo 10, que es el primer nodo, indicándolo así como una lista enlazada circular.
|_+_|Producción:
La lista circular vinculada creada es la siguiente:
10==>20==>30==>40==>50==>60==>10
El nodo con datos 10 se elimina de la lista.
La lista circular vinculada después de eliminar 10 es la siguiente:
20==>30==>40==>50==>60==>20
A continuación, presentamos una implementación de Java para las operaciones de lista enlazada circular.
|_+_|Producción:
La lista circular vinculada creada es:
10==>20==>30==>40==>50==>60==>10
Después de eliminar 40, la lista circular es:
10==>20==>30==>50==>60==>10
Ventajas desventajas
Analicemos algunas ventajas y desventajas de la lista enlazada circular.
Ventajas:
- Podemos ir a cualquier nodo y atravesar desde cualquier nodo. Solo debemos detenernos cuando volvamos a visitar el mismo nodo.
- Como el último nodo apunta al primer nodo, ir al primer nodo desde el último nodo solo requiere un paso.
Desventajas:
- Revertir una lista enlazada circular es engorroso.
- Como los nodos están conectados para formar un círculo, no hay una marca adecuada para el comienzo o el final de la lista. Por tanto, es difícil encontrar el final de la lista o el control de bucle. Si no se tiene cuidado, una implementación podría terminar en un bucle infinito.
- No podemos volver al nodo anterior en un solo paso. Tenemos que recorrer toda la lista desde el principio.
Aplicaciones de la lista enlazada circular
- La aplicación en tiempo real de la lista enlazada circular puede ser un sistema operativo de programación múltiple en el que programa múltiples programas. A cada programa se le asigna una marca de tiempo dedicada para su ejecución, después de lo cual los recursos se pasan a otro programa. Esto ocurre continuamente en un ciclo. Esta representación se puede lograr de manera eficiente utilizando una lista enlazada circular.
- Los juegos que se juegan con varios jugadores también se pueden representar mediante una lista enlazada circular en la que cada jugador es un nodo al que se le da la oportunidad de jugar.
- Podemos usar una lista enlazada circular para representar una cola circular. Al hacer esto, podemos eliminar los dos punteros delanteros y traseros que se utilizan para la cola. En cambio, podemos usar solo un puntero.
Conclusión
Una lista enlazada circular es una colección de nodos en los que los nodos están conectados entre sí para formar un círculo. Esto significa que en lugar de establecer el siguiente puntero del último nodo en nulo, se vincula al primer nodo.
Una lista enlazada circular es útil para representar estructuras o actividades que deben repetirse una y otra vez después de un intervalo de tiempo específico, como programas en un entorno de multiprogramación. También es beneficioso para diseñar una cola circular.
Las listas enlazadas circulares admiten varias operaciones como inserción, eliminación y recorridos. Por tanto, hemos visto las operaciones en detalle en este tutorial.
En nuestro próximo tema sobre estructuras de datos, aprenderemos sobre la estructura de datos de la pila.
=> Consulte aquí para ver los tutoriales de capacitación de la A a la Z de C ++ aquí.
Lectura recomendada
- Estructura de datos de lista vinculada en C ++ con ilustración
- Estructura de datos de lista doblemente enlazada en C ++ con ilustración
- Estructura de datos de cola en C ++ con ilustración
- Estructura de datos de pila en C ++ con ilustración
- Estructura de datos de cola de prioridad en C ++ con ilustración
- Las 15 mejores herramientas gratuitas de minería de datos: la lista más completa
- Introducción a las estructuras de datos en C ++
- 15 mejores herramientas ETL en 2021 (una lista completa actualizada)