Lista enlazada circular: ventajas con el ejemplo del programa C

Tabla de contenido:

Anonim

¿Qué es una lista enlazada circular?

Una lista enlazada circular es una secuencia de nodos organizados de tal manera que cada nodo se puede volver sobre sí mismo. Aquí, un "nodo" es un elemento autorreferencial con punteros a uno o dos nodos en la vecindad inmediata de iI.

A continuación se muestra una descripción de una lista enlazada circular con 3 nodos.

Aquí, puede ver que cada nodo es rastreable a sí mismo. El ejemplo que se muestra arriba es una lista circular enlazada individualmente.

Nota: La lista enlazada circular más simple es un nodo que se rastrea solo a sí mismo como se muestra

En este tutorial de lista enlazada circular, aprenderá:

  • ¿Qué es una lista enlazada circular?
  • Operaciones básicas
  • Operación de inserción
  • Operación de eliminación
  • Recorrido de una lista enlazada circular
  • Ventajas de la lista enlazada circular
  • Lista enlazada individualmente como una lista enlazada circular
  • Aplicaciones de la lista enlazada circular

Operaciones básicas

Las operaciones básicas en una lista enlazada circular son:

  1. Inserción
  2. Eliminación y
  3. El recorrido
  • La inserción es el proceso de colocar un nodo en una posición específica en la lista enlazada circular.
  • La eliminación es el proceso de eliminar un nodo existente de la lista vinculada. El nodo puede identificarse por la ocurrencia de su valor o por su posición.
  • El recorrido de una lista enlazada circular es el proceso de mostrar el contenido de la lista enlazada completa y volver al nodo de origen.

En la siguiente sección, comprenderá la inserción de un nodo y los tipos de inserción posibles en una lista circular simple enlazada.

Operación de inserción

Inicialmente, debe crear un nodo que apunte a sí mismo como se muestra en esta imagen. Sin este nodo, la inserción crea el primer nodo.

A continuación, hay dos posibilidades:

  • Inserción en la posición actual de la lista enlazada circular. Esto corresponde a la inserción al principio del final de una lista enlazada singular regular. En una lista enlazada circular, el principio y el final son iguales.
  • Inserción después de un nodo indexado. El nodo debe identificarse mediante un número de índice correspondiente a su valor de elemento.

Para insertar al principio / final de la lista circular vinculada, es decir, en la posición donde se agregó el primer nodo,

  • Tendrá que romper el autoenlace existente al nodo existente
  • El siguiente puntero del nuevo nodo se vinculará al nodo existente.
  • El siguiente puntero del último nodo apuntará al nodo insertado.

NOTA: El puntero que es el maestro de tokens o el principio / final del círculo se puede cambiar. Seguirá regresando al mismo nodo en un recorrido, que se analiza más adelante.

Los pasos en (a) i-iii se muestran a continuación:

(Nodo existente)

PASO 1) Romper el enlace existente

PASO 2) Cree un enlace de reenvío (de un nodo nuevo a un nodo existente)

PASO 3) Cree un enlace de bucle al primer nodo

A continuación, probará la inserción después de un nodo.

Por ejemplo, insertemos "VALOR2" después del nodo con "VALOR0". Supongamos que el punto de partida es el nodo con "VALOR0".

  • Tendrá que romper la línea entre el primer y el segundo nodo y colocar el nodo con "VALUE2" en el medio.
  • El siguiente puntero del primer nodo debe vincularse a este nodo, y el siguiente puntero de este nodo debe vincularse al segundo nodo anterior.
  • El resto del arreglo permanece sin cambios. Todos los nodos son rastreables a sí mismos.

NOTA: Dado que existe una disposición cíclica, la inserción de un nodo implica el mismo procedimiento para cualquier nodo. El puntero que completa un ciclo completa el ciclo como cualquier otro nodo.

Esto se muestra a continuación:

(Digamos que solo hay dos nodos. Este es un caso trivial)

PASO 1) Retire el enlace interno entre los nodos conectados

PASO 2) Conecte el nodo del lado izquierdo al nuevo nodo

PASO 3) Conecte el nuevo nodo al nodo del lado derecho.

Operación de eliminación

Supongamos una lista enlazada circular de 3 nodos. Los casos de eliminación se dan a continuación:

  • Eliminar el elemento actual
  • Eliminación después de un elemento.

Eliminación al principio / final:

  1. Atraviesa el primer nodo desde el último nodo.
  2. Para eliminar desde el final, debe haber solo un paso transversal, desde el último nodo al primer nodo.
  3. Elimina el enlace entre el último nodo y el siguiente.
  4. Vincula el último nodo al siguiente elemento del primer nodo.
  5. Libera el primer nodo.

(Configuración existente)

PASO 1 ) Retire el enlace circular

PASOS 2) Eliminar el vínculo entre el primero y el siguiente, vincular el último nodo con el nodo que sigue al primero.

PASO 3) Liberar / desasignar el primer nodo

Eliminación después de un nodo:

  1. Recorra hasta que el siguiente nodo sea el nodo que se eliminará.
  2. Desplácese hasta el siguiente nodo, colocando un puntero en el nodo anterior.
  3. Conecte el nodo anterior al nodo posterior al nodo actual, utilizando su siguiente puntero.
  4. Libera el nodo actual (desvinculado).

PASO 1) Digamos que necesitamos eliminar un nodo con "VALUE1".

PASO 2) Elimine el enlace entre el nodo anterior y el nodo actual. Vincula su nodo anterior con el siguiente nodo señalado por el nodo actual (con VALUE1).

PASO 3) Libere o desasigne el nodo actual.

Recorrido de una lista enlazada circular

Para recorrer una lista enlazada circular, comenzando desde un último puntero, verifique si el último puntero en sí es NULL. Si esta condición es falsa, verifique si solo hay un elemento. De lo contrario, recorra con un puntero temporal hasta que se alcance nuevamente el último puntero, o tantas veces como sea necesario, como se muestra en el GIF a continuación.

Ventajas de la lista enlazada circular

Algunas de las ventajas de las listas enlazadas circulares son:

  1. No hay ningún requisito para una asignación NULL en el código. La lista circular nunca apunta a un puntero NULL a menos que esté completamente desasignado.
  2. Las listas enlazadas circulares son ventajosas para las operaciones finales ya que el principio y el final coinciden. Algoritmos como la programación Round Robin pueden eliminar perfectamente los procesos que están en cola de forma circular sin encontrar punteros referenciales colgantes o NULL.
  3. La lista enlazada circular también realiza todas las funciones regulares de una lista enlazada individualmente. De hecho, las listas circulares doblemente enlazadas que se analizan a continuación pueden incluso eliminar la necesidad de un recorrido completo para localizar un elemento. Ese elemento, como mucho, sería exactamente opuesto al inicio, completando solo la mitad de la lista vinculada.

Lista enlazada individualmente como una lista enlazada circular

Le recomendamos que intente leer e implementar el código a continuación. Presenta la aritmética de punteros asociada con listas enlazadas circulares.

#include#includestruct node{int item;struct node *next;};struct node* addToEmpty(struct node*,int);struct node *insertCurrent(struct node *, int);struct node *insertAfter(struct node *, int, int);struct node *removeAfter(struct node *, int);struct node *removeCurrent(struct node *);void peek(struct node *);int main(){…

Explicación del código:

  1. Las dos primeras líneas de código son los archivos de encabezado incluidos necesarios.
  2. La siguiente sección describe la estructura de cada nodo autorreferencial. Contiene un valor y un puntero del mismo tipo que la estructura.
  3. Cada estructura se enlaza repetidamente con objetos de estructura del mismo tipo.
  4. Existen diferentes prototipos de funciones para:
    1. Agregar un elemento a una lista vinculada vacía
    2. Insertar en la posición señalada actualmente de una lista enlazada circular.
    3. Insertar después de un valor indexado particular en la lista vinculada.
    4. Eliminar / Eliminar después de un valor indexado particular en la lista vinculada.
    5. Eliminar en la posición actualmente señalada de una lista enlazada circular
  5. La última función imprime cada elemento a través de un recorrido circular en cualquier estado de la lista vinculada.
int main(){struct node *last = NULL;last = insertCurrent(last,4);last = removeAfter(last, 4);peek(last);return 0;}struct node* addToEmpty(struct node*last, int data){struct node *temp = (struct node *)malloc(sizeof( struct node));temp->item = data;last = temp;last->next = last;return last;}struct node *insertCurrent(struct node *last, int data)

Explicación del código:

  1. Para el código addEmpty, asigne un nodo vacío usando la función malloc.
  2. Para este nodo, coloque los datos en la variable temporal.
  3. Asignar y vincular la única variable a la variable temporal
  4. Devuelve el último elemento al contexto principal () / aplicación.
struct node *insertCurrent(struct node *last, int data){if(last == NULL){return addToEmpty(last, data);}struct node *temp = (struct node *)malloc(sizeof( struct node));temp -> item = data;temp->next = last->next;last->next = temp;return last;}struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;…

Explicación del código

  1. Si no hay ningún elemento para insertar, debe asegurarse de agregarlo a una lista vacía y devolver el control.
  2. Crea un elemento temporal para colocarlo después del elemento actual.
  3. Vincula los punteros como se muestra.
  4. Devuelve el último puntero como en la función anterior.
… struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;if (last == NULL){return addToEmpty(last, item);}do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found. Please try again");…

Explicación del código:

  1. Si no hay ningún elemento en la lista, ignore los datos, agregue el elemento actual como último elemento de la lista y devuelva el control
  2. Para cada iteración en el ciclo do-while, asegúrese de que haya un puntero anterior que contenga el último resultado atravesado.
  3. Solo entonces puede ocurrir el siguiente cruce.
  4. Si se encuentran los datos, o temp vuelve al último puntero, el do-while termina. La siguiente sección de código decide qué se debe hacer con el artículo.
… if(temp->item != data){printf("Element not found. Please try again");return last;}else{newnode = (struct node *)malloc(sizeof(struct node));newnode->item = item;prev->next = newnode;newnode->next = temp;}return last;}struct node *removeCurrent(struct node *last)…

Explicación del código:

  1. Si se ha recorrido toda la lista, pero el elemento no se encuentra, muestre un mensaje de "elemento no encontrado" y luego devuelva el control a la persona que llama.
  2. Si se encuentra un nodo y / o el nodo aún no es el último nodo, cree uno nuevo.
  3. Vincula el nodo anterior con el nuevo nodo. Vincula el nodo actual con temp (la variable transversal).
  4. Esto asegura que el elemento se coloque después de un nodo particular en la lista enlazada circular. Regrese a la persona que llama.
struct node *removeCurrent(struct node *last){if(last == NULL){printf("Element Not Found");return NULL;}struct node *temp = last->next;last->next = temp->next;free(temp);return last;}struct node *removeAfter(struct node *last, int data)

Explicación del código

  1. Para eliminar solo el último nodo (actual), compruebe si esta lista está vacía. Si es así, no se puede eliminar ningún elemento.
  2. La variable temporal solo atraviesa un enlace hacia adelante.
  3. Vincula el último puntero al puntero después del primero.
  4. Libera el puntero de temperatura. Desasigna el último puntero no vinculado.
struct node *removeAfter(struct node *last,int data){struct node *temp = NULL,*prev = NULL;if (last == NULL){printf("Linked list empty. Cannot remove any element\n");return NULL;}temp = last->next;prev = temp;do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found");…

Explicación del código

  1. Al igual que con la función de eliminación anterior, verifique si no hay ningún elemento. Si esto es cierto, no se puede eliminar ningún elemento.
  2. A los punteros se les asignan posiciones específicas para localizar el elemento que se va a eliminar.
  3. Los punteros avanzan, uno detrás del otro. (anterior detrás de la temperatura)
  4. El proceso continúa hasta que se encuentra un elemento o el siguiente elemento vuelve al último puntero.
if(temp->item != data){printf("Element not found");return last;}else{prev->next = temp->next;free(temp);}return last;}void peek(struct node * last){struct node *temp = last;if (last == NULL){return;

Explicación del programa

  1. Si el elemento se encuentra después de recorrer toda la lista vinculada, se muestra un mensaje de error que indica que no se encontró el elemento.
  2. De lo contrario, el elemento se desvincula y se libera en los pasos 3 y 4.
  3. El puntero anterior está vinculado a la dirección señalada como "siguiente" por el elemento a eliminar (temp).
  4. Por tanto, el puntero temporal se desasigna y se libera.
… void peek(struct node * last){struct node *temp = last;if (last == NULL){return;}if(last -> next == last){printf("%d-", temp->item);}while (temp != last){printf("%d-", temp->item);temp = temp->next;}}

Explicación del código

  1. La mirada o el recorrido no es posible si no se necesitan cero. El usuario necesita asignar o insertar un nodo.
  2. Si solo hay un nodo, no es necesario recorrerlo, el contenido del nodo se puede imprimir y el ciclo while no se ejecuta.
  3. Si hay más de un nodo, el temp imprime todo el elemento hasta el último elemento.
  4. En el momento en que se alcanza el último elemento, el ciclo termina y la función devuelve la llamada a la función principal.

Aplicaciones de la lista enlazada circular

  • Implementar la programación por turnos en los procesos del sistema y la programación circular en gráficos de alta velocidad.
  • Programación de Token Ring en redes informáticas.
  • Se utiliza en unidades de visualización como tableros de tiendas que requieren un recorrido continuo de datos.