logo

TechCodeview

Introducción a la lista enlazada circular

¿Qué es la lista circular enlazada?

El lista circular enlazada es una lista enlazada donde todos los nodos están conectados para formar un círculo. En una lista enlazada circular, el primer nodo y el último nodo están conectados entre sí, lo que forma un círculo. No hay NULL al final.

Lista circular enlazada



Generalmente existen dos tipos de listas circulares enlazadas:

  • Lista circular individualmente enlazada: En una lista circular individualmente enlazada, el último nodo de la lista contiene un puntero al primer nodo de la lista. Recorremos la lista circular individualmente enlazada hasta llegar al mismo nodo donde comenzamos. La lista circular individualmente enlazada no tiene principio ni fin. No hay ningún valor nulo presente en la siguiente parte de ninguno de los nodos.

Representación de lista circular individualmente enlazada

  • Lista circular doblemente enlazada: La lista circular doblemente enlazada tiene propiedades tanto de la lista doblemente enlazada como de la lista circular enlazada en la que dos elementos consecutivos están enlazados o conectados por el puntero anterior y siguiente y el último nodo apunta al primer nodo mediante el siguiente puntero y también el primer nodo apunta a el último nodo por el puntero anterior.

Representación de lista circular doblemente enlazada.



Nota: Usaremos la lista enlazada circular simple para representar el funcionamiento de la lista enlazada circular.

Representación de lista enlazada circular:

Las listas enlazadas circulares son similares a las listas enlazadas individuales con la excepción de que conectan el último nodo con el primer nodo.

administrador de tareas linux

Representación de nodos de una lista enlazada circular:



C++ 
// Class Node, similar to the linked list class Node{  int value; // Points to the next node.  Node next; }>
C 
struct Node {  int data;  struct Node *next; };>
Java 
public class Node {  int data;  Node next;    public Node(int data) {  this.data = data;  this.next = null;  } }>
C# 
public class Node {  public int data;  public Node next;    public Node(int data)  {  this.data = data;  this.next = null;  } }>
JavaScript 
class Node {  constructor(data) {  this.data = data;  this.next = null;  } }>
PHP 
class Node {  public $data;  public $next;  function __construct($data) {  $this->datos = $datos;  $this->siguiente = nulo;  } }>
Python3 
# Class Node, similar to the linked list class Node: def __init__(self,data): self.data = data self.next = None>

Ejemplo de lista circular individualmente enlazada:

Ejemplo de lista enlazada circular

La lista circular individualmente enlazada anterior se puede representar como:

C++ 
// Initialize the Nodes. Node one = new Node(3); Node two = new Node(5); Node three = new Node(9); // Connect nodes one.next = two; two.next = three; three.next = one;>
C 
Node* one = createNode(3); Node* two = createNode(5); Node* three = createNode(9); // Connect nodes one->siguiente = dos; dos->siguiente = tres; tres->siguiente = uno;>
Java 
// Define the Node class class Node {  int value;  Node next;  public Node(int value) {  this.value = value;  } } // Initialize the Nodes. Node one = new Node(3); Node two = new Node(5); Node three = new Node(9); // Connect nodes one.next = two; two.next = three; three.next = one;>
C# 
Node one = new Node(3); Node two = new Node(5); Node three = new Node(9); // Connect nodes one.next = two; two.next = three; three.next = one;>
JavaScript 
let one = new Node(3); let two = new Node(5); let three = new Node(9); // Connect nodes one.next = two; two.next = three; three.next = one;>
PHP 
$one = new Node(3); $two = new Node(5); $three = new Node(9); // Connect nodes $one->siguiente = $dos; $dos->siguiente = $tres; $tres->siguiente = $uno;>
Python3 
# Initialize the Nodes. one = Node(3) two = Node(5) three = Node(9) # Connect nodes one.next = two two.next = three three.next = one>

Explicación: En el programa anterior uno, dos y tres son los nodos con valores 3, 5 y 9 respectivamente que están conectados de forma circular como:

  • Para el nodo uno: El puntero Siguiente almacena la dirección del Nodo dos.
  • Para el nodo dos: El siguiente almacena la dirección del nodo tres.
  • Para el nodo tres: El El siguiente apunta al nodo uno.

Operaciones en la lista circular enlazada:

Podemos realizar algunas operaciones en la lista enlazada circular similares a la lista enlazada individualmente que son:

  1. Inserción
  2. Supresión

1. Inserción en la lista circular enlazada:

Se puede agregar un nodo de tres maneras:

  1. Inserción al principio de la lista.
  2. Inserción al final de la lista.
  3. Inserción entre los nodos.

1) Inserción al principio de la lista: Para insertar un nodo al principio de la lista, siga estos pasos:

  • Crea un nodo, digamos T.
  • Haga T -> siguiente = último -> siguiente.
  • último -> siguiente = T.

Lista circular enlazada antes de la inserción

Y luego,

Lista circular enlazada después de la inserción

2) Inserción al final de la lista: Para insertar un nodo al final de la lista, siga estos pasos:

  • Crea un nodo, digamos T.
  • Hacer T -> siguiente = último -> siguiente;
  • último -> siguiente = T.
  • último = T.

Antes de la inserción,

Lista circular enlazada antes de la inserción del nodo al final

Después de la inserción,

Lista circular enlazada después de la inserción del nodo al final

3) Inserción entre los nodos: Para insertar un nodo entre los dos nodos, siga estos pasos:

  • Crea un nodo, digamos T.
  • Busque el nodo después del cual se debe insertar T, digamos que el nodo es P.
  • Hacer T -> siguiente = P -> siguiente;
  • P -> siguiente = T.

Supongamos que es necesario insertar 12 después de que el nodo tenga el valor 10,

Lista circular enlazada antes de la inserción

Después de la búsqueda e inserción,

Lista circular enlazada después de la inserción

2. Eliminación en una lista circular enlazada:

1) Elimine el nodo solo si es el único nodo en la lista circular enlazada:

  • Libera la memoria del nodo
  • El último valor debe ser NULL. Un nodo siempre apunta a otro nodo, por lo que la asignación NULL no es necesaria.
    Cualquier nodo se puede establecer como punto de partida.
    Los nodos se atraviesan rápidamente desde el primero hasta el último.

2) Eliminación del último nodo:

  • Ubique el nodo antes del último nodo (que sea temporal)
  • Mantenga la dirección del nodo al lado del último nodo en temp
  • Eliminar el último recuerdo
  • Pon temperatura al final

3) Eliminar cualquier nodo de la lista circular enlazada: Se nos dará un nodo y nuestra tarea es eliminar ese nodo de la lista circular enlazada.

Algoritmo:
Caso 1 : La lista esta vacía.

  • Si la lista está vacía simplemente regresaremos.

Caso 2 :La lista no está vacía

  • Si la lista no está vacía, definimos dos punteros. curr y anterior e inicializar el puntero curr con el cabeza nodo.
  • Recorre la lista usando curr para encontrar el nodo que se va a eliminar y antes de pasar a curr al siguiente nodo, cada vez configure prev = curr.
  • Si se encuentra el nodo, verifique si es el único nodo en la lista. En caso afirmativo, establezca head = NULL y free(curr).
  • Si la lista tiene más de un nodo, verifique si es el primer nodo de la lista. Condición para comprobar esto (curr == head). En caso afirmativo, mueva anterior hasta llegar al último nodo. Después de que prev llegue al último nodo, establezca head = head -> next y prev -> next = head. Eliminar actual.
  • Si curr no es el primer nodo, comprobamos si es el último nodo de la lista. La condición para verificar esto es (curr -> next == head).
  • Si curr es el último nodo. Establezca prev -> next = head y elimine el nodo curr mediante free(curr).
  • Si el nodo que se va a eliminar no es ni el primer nodo ni el último, configure prev -> next = curr -> next y elimine curr.
  • Si el nodo no está presente en la lista, regrese al encabezado y no haga nada.

A continuación se muestra la implementación del enfoque anterior:

C++ 
// C++ program to delete a given key from // linked list. #include  using namespace std; // Structure for a node class Node { public:  int data;  Node* next; }; // Function to insert a node at the // beginning of a Circular linked list void push(Node** head_ref, int data) {  // Create a new node and make head  // as next of it.  Node* ptr1 = new Node();  ptr1->datos = datos;  ptr1->siguiente = *head_ref;  // Si la lista enlazada no es NULL entonces // establece el siguiente del último nodo if (*head_ref != NULL) { // Encuentra el nodo antes del encabezado y // actualiza el siguiente.  Nodo* temp = *head_ref;  mientras (temperatura->siguiente!= *head_ref) temperatura = temperatura->siguiente;  temperatura->siguiente = ptr1;  } else // Para el primer nodo ptr1->next = ptr1;  *head_ref = ptr1; } // Función para imprimir nodos en una // lista circular enlazada determinada void printList(Node* head) { Node* temp = head;  si (cabeza! = NULL) {hacer {cout<< temp->datos<< ' ';  temp = temp->próximo;  } mientras (temperatura! = cabeza);  } escucha<< endl; } // Function to delete a given node // from the list void deleteNode(Node** head, int key) {  // If linked list is empty  if (*head == NULL)  return;  // If the list contains only a  // single node  if ((*head)->datos == clave && (*cabeza)->siguiente == *cabeza) { gratis(*cabeza);  *cabeza = NULO;  devolver;  } Nodo *último = *cabeza, *d;  // Si se va a eliminar el encabezado if ((*head)->data == key) { // Encuentra el último nodo de la lista while (last->next != *head) last = last->next;  // Apunta el último nodo al siguiente // encabezado, es decir, el segundo nodo // de la lista last->next = (*head)->next;  libre(*cabeza);  *cabeza = último->siguiente;  devolver;  } // El nodo que se va a eliminar // no se encuentra o // no se alcanza el final de la lista while (último->siguiente!= *head && último->siguiente->datos!= clave) { último = último ->siguiente;  } // Si se encontró el nodo a eliminar if (último->siguiente->datos == clave) { d = último->siguiente;  último->siguiente = d->siguiente;  liberado);  } más cout<< 'Given node is not found in the list!!!
'; } // Driver code int main() {  // Initialize lists as empty  Node* head = NULL;  // Created linked list will be  // 2->5->7->8->10 empujar(&cabeza, 2);  empujar(&cabeza, 5);  empujar(&cabeza, 7);  empujar(&cabeza, 8);  empujar(&cabeza, 10);  corte<< 'List Before Deletion: ';  printList(head);  deleteNode(&head, 7);  cout << 'List After Deletion: ';  printList(head);  return 0; }>
C 
#include  #include  // Structure for a node struct Node {  int data;  struct Node* next; }; // Function to insert a node at the // beginning of a Circular linked list void push(struct Node** head_ref, int data) {  // Create a new node and make head  // as next of it.  struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node));  ptr1->datos = datos;  ptr1->siguiente = *head_ref;  // Si la lista enlazada no es NULL entonces // establece el siguiente del último nodo if (*head_ref != NULL) { // Encuentra el nodo antes del encabezado y // actualiza el siguiente.  estructura Nodo* temp = *head_ref;  mientras (temperatura->siguiente!= *head_ref) temperatura = temperatura->siguiente;  temperatura->siguiente = ptr1;  } else // Para el primer nodo ptr1->next = ptr1;  *head_ref = ptr1; } // Función para imprimir nodos en una // lista circular enlazada dada void printList(struct Node* head) { struct Node* temp = head;  if (head! = NULL) { hacer { printf('%d ', temp->data);  temperatura = temperatura->siguiente;  } mientras (temperatura! = cabeza);  } printf('
'); } // Función para eliminar un nodo determinado // de la lista void deleteNode(struct Node** head, int key) { // Si la lista enlazada está vacía if (*head == NULL) return;  // Si la lista contiene solo un // único nodo if ((*head)->data == key && (*head)->next == *head) { free(*head);  *cabeza = NULO;  devolver;  } estructura Nodo *último = *cabeza, *d;  // Si se va a eliminar el encabezado if ((*head)->data == key) { // Encuentra el último nodo de la lista while (last->next != *head) last = last->next;  // Apunta el último nodo al siguiente // encabezado, es decir, el segundo nodo // de la lista last->next = (*head)->next;  libre(*cabeza);  *cabeza = último->siguiente;  devolver;  } // El nodo que se va a eliminar // no se encuentra o // no se alcanza el final de la lista mientras (último->siguiente!= *head && último->siguiente->datos!= clave) { último = último ->siguiente;  } // Si se encontró el nodo a eliminar if (último->siguiente->datos == clave) { d = último->siguiente;  último->siguiente = d->siguiente;  liberado);  } else printf('¡¡¡El nodo dado no se encuentra en la lista!!!
'); } // Código del controlador int main() { // Inicializa listas como estructura vacía Node* head = NULL;  // La lista enlazada creada será // 2->5->7->8->10 push(&head, 2);  empujar(&cabeza, 5);  empujar(&cabeza, 7);  empujar(&cabeza, 8);  empujar(&cabeza, 10);  printf('Lista antes de eliminar: ');  imprimirLista(cabeza);  eliminarNodo(&cabeza, 7);  printf('Lista después de la eliminación: ');  imprimirLista(cabeza);  devolver 0; }>
Java 
// Java program to delete a given key from // linked list. import java.io.*; import java.util.*; public class GFG {  /* structure for a node */  static class Node {  int data;  Node next;  };  /* Function to insert a node at the beginning of a Circular linked list */  static Node push(Node head_ref, int data)  {  // Create a new node and make head as next  // of it.  Node ptr1 = new Node();  ptr1.data = data;  ptr1.next = head_ref;  /* If linked list is not null then set the next of last node */  if (head_ref != null) {  // Find the node before head and update  // next of it.  Node temp = head_ref;  while (temp.next != head_ref)  temp = temp.next;  temp.next = ptr1;  }  else  ptr1.next = ptr1; /*For the first node */  head_ref = ptr1;  return head_ref;  }  /* Function to print nodes in a given circular linked list */  static void printList(Node head)  {  Node temp = head;  if (head != null) {  do {  System.out.printf('%d ', temp.data);  temp = temp.next;  } while (temp != head);  }  System.out.printf('
');  }  /* Function to delete a given node from the list */  static Node deleteNode(Node head, int key)  {  if (head == null)  return null;  int flag = 0;  // Find the required node  Node curr = head, prev = new Node();  while (curr.data != key) {  if (curr.next == head) {  System.out.printf(  'Given node is not found in the list!!!
');  flag = 1;  break;  }  prev = curr;  curr = curr.next;  }  // Check if the element is not present in the list  if (flag == 1)  return head;  // Check if node is only node  if (curr == head && curr.next == head) {  head = null;  return head;  }  // If more than one node, check if  // it is first node  if (curr == head) {  prev = head;  while (prev.next != head)  prev = prev.next;  head = curr.next;  prev.next = head;  }  // check if node is last node  else if (curr.next == head) {  prev.next = head;  }  else {  prev.next = curr.next;  }  return head;  }  /* Driver code */  public static void main(String args[])  {  /* Initialize lists as empty */  Node head = null;  /* Created linked list will be 2.5.7.8.10 */  head = push(head, 2);  head = push(head, 5);  head = push(head, 7);  head = push(head, 8);  head = push(head, 10);  System.out.printf('List Before Deletion: ');  printList(head);  head = deleteNode(head, 7);  System.out.printf('List After Deletion: ');  printList(head);  } } // This code is contributed by Susobhan Akhuli>
C# 
using System; // Structure for a node public class Node {  public int data;  public Node next; } // Class for Circular Linked List public class CircularLinkedList {  // Function to insert a node at the  // beginning of a Circular linked list  public static void Push(ref Node head_ref, int data)  {  // Create a new node and make head  // as next of it.  Node ptr1 = new Node();  ptr1.data = data;  ptr1.next = head_ref;  // If linked list is not NULL then  // set the next of last node  if (head_ref != null) {  // Find the node before head and  // update next of it.  Node temp = head_ref;  while (temp.next != head_ref)  temp = temp.next;  temp.next = ptr1;  }  else  // For the first node  ptr1.next = ptr1;  head_ref = ptr1;  }  // Function to print nodes in a given  // circular linked list  public static void PrintList(Node head)  {  Node temp = head;  if (head != null) {  do {  Console.Write(temp.data + ' ');  temp = temp.next;  } while (temp != head);  }  Console.WriteLine();  }  // Function to delete a given node  // from the list  public static void DeleteNode(ref Node head, int key)  {  // If linked list is empty  if (head == null)  return;  // If the list contains only a  // single node  if (head.data == key && head.next == head) {  head = null;  return;  }  Node last = head, d;  // If head is to be deleted  if (head.data == key) {  // Find the last node of the list  while (last.next != head)  last = last.next;  // Point last node to the next of  // head i.e. the second node  // of the list  last.next = head.next;  head = last.next;  return;  }  // Either the node to be deleted is  // not found or the end of list  // is not reached  while (last.next != head && last.next.data != key) {  last = last.next;  }  // If node to be deleted was found  if (last.next.data == key) {  d = last.next;  last.next = d.next;  }  else  Console.WriteLine(  'Given node is not found in the list!!!');  }  // Driver code  public static void Main()  {  // Initialize lists as empty  Node head = null;  // Created linked list will be  // 2->5->7->8->10 Empujar (cabezal de referencia, 2);  Empujar (cabeza de referencia, 5);  Empujar (cabeza de referencia, 7);  Empujar (cabeza de referencia, 8);  Empujar (cabeza de referencia, 10);  Console.Write('Lista antes de eliminar: ');  ListaImprimir(cabeza);  EliminarNodo(cabeza de referencia, 7);  Console.Write('Lista después de la eliminación: ');  ListaImprimir(cabeza);  } }>
JavaScript 
 // Javascript program to delete a given key from linked list.  // Structure for a node  class Node {  constructor() {  this.data;  this.next;  }  }  // Function to insert a node at the  // beginning of a Circular linked list  function push(head, data) {  // Create a new node and make head  // as next of it.  var ptr1 = new Node();  ptr1.data = data;  ptr1.next = head;  // If linked list is not NULL then  // set the next of last node  if (head != null) {  // Find the node before head and  // update next of it.  let temp = head;  while (temp.next != head) temp = temp.next;  temp.next = ptr1;  }  // For the first node  else ptr1.next = ptr1;  head = ptr1;  return head;  }  // Function to print nodes in a given  // circular linked list  function printList(head) {  let tempp = head;  if (head != null) {  do {  console.log(tempp.data);  tempp = tempp.next;  } while (tempp != head);  }  }  // Function to delete a given node  // from the list  function deleteNode(head, key) {  // If linked list is empty  if (head == null) return;  // If the list contains only a  // single node  if (head.data == key && head.next == head) {  head = null;  return;  }  let last = head;  // If head is to be deleted  if (head.data == key) {  // Find the last node of the list  while (last.next != head) last = last.next;  // Point last node to the next of  // head i.e. the second node  // of the list  last.next = head.next;  head = last.next;  return;  }  // Either the node to be deleted is  // not found or the end of list  // is not reached  while (last.next != head && last.next.data != key) {  last = last.next;  }  // If node to be deleted was found  if (last.next.data == key) {  d = last.next;  last.next = d.next;  d = null;  } else console.log('Given node is not found in the list!!!');  }  // Driver code  // Initialize lists as empty  head = null;  // Created linked list will be  // 2->5->7->8->10 cabeza = empujar(cabeza, 2);  cabeza = empujar(cabeza, 5);  cabeza = empujar(cabeza, 7);  cabeza = empujar(cabeza, 8);  cabeza = empujar(cabeza, 10);  console.log('Lista antes de eliminar: ');  imprimirLista(cabeza);  eliminarNodo(cabeza, 7);  console.log('Lista después de la eliminación: ');  imprimirLista(cabeza);>
Python3 
# Python program to delete a given key from linked list class Node: def __init__(self, data): self.data = data self.next = None # Function to insert a node at the # beginning of a Circular linked list def push(head, data): # Create a new node and make head as next of it. newP = Node(data) newP.next = head # If linked list is not NULL then # set the next of last node if head != None: # Find the node before head and # update next of it. temp = head while (temp.next != head): temp = temp.next temp.next = newP else: newP.next = newP head = newP return head # Function to print nodes in a given circular linked list def printList(head): if head == None: print('List is Empty') return temp = head.next print(head.data, end=' ') if (head != None): while (temp != head): print(temp.data, end=' ') temp = temp.next print() # Function to delete a given node # from the list def deleteNode(head, key): # If linked list is empty if (head == None): return # If the list contains only a # single node if (head.data == key and head.next == head): head = None return last = head # If head is to be deleted if (head.data == key): # Find the last node of the list while (last.next != head): last = last.next # Point last node to the next of # head i.e. the second node # of the list last.next = head.next head = last.next return # Either the node to be deleted is # not found or the end of list # is not reached while (last.next != head and last.next.data != key): last = last.next # If node to be deleted was found if (last.next.data == key): d = last.next last.next = d.next d = None else: print('Given node is not found in the list!!!') # Driver code # Initialize lists as empty head = None # Created linked list will be # 2->5->7->8->10 cabeza = empujar(cabeza, 2) cabeza = empujar(cabeza, 5) cabeza = empujar(cabeza, 7) cabeza = empujar(cabeza, 8) cabeza = empujar(cabeza, 10) print('Lista antes de la eliminación: ') printList(head) eliminarNodo(head, 7) print('Lista después de la eliminación: ') printList(head)>
Producción 
List Before Deletion: 10 8 7 5 2 List After Deletion: 10 8 5 2>

Complejidad del tiempo: O (N), el peor de los casos ocurre cuando el elemento que se va a eliminar es el último elemento y necesitamos movernos por toda la lista.
Espacio Auxiliar: O (1), ya que se utiliza espacio adicional constante.

Ventajas de las listas enlazadas circulares:

  • Cualquier nodo puede ser un punto de partida. Podemos recorrer toda la lista comenzando desde cualquier punto. Solo necesitamos detenernos cuando se vuelva a visitar el primer nodo visitado.
  • Útil para la implementación de una cola. A diferencia de este implementación, no necesitamos mantener dos punteros para el frente y la parte trasera si usamos una lista enlazada circular. Podemos mantener un puntero al último nodo insertado y el frente siempre se puede obtener como el siguiente al último.
  • Las listas circulares son útiles en aplicaciones para recorrer la lista repetidamente. Por ejemplo, cuando se ejecutan varias aplicaciones en una PC, es común que el sistema operativo coloque las aplicaciones en ejecución en una lista y luego las recorra, dándole a cada una de ellas un tiempo para ejecutarse y luego haciéndolas esperar mientras se ejecutan. la CPU se entrega a otra aplicación. Es conveniente que el sistema operativo utilice una lista circular para que cuando llegue al final de la lista pueda pasar al principio de la lista.
  • Las listas circulares doblemente enlazadas se utilizan para la implementación de estructuras de datos avanzadas como la Montón de Fibonacci .
  • Implementar una lista enlazada circular puede ser relativamente fácil en comparación con otras estructuras de datos más complejas como árboles o gráficos.

Desventajas de la lista enlazada circular:

  • En comparación con las listas enlazadas individualmente, las listas circulares son más complejas.
  • Invertir una lista circular es más complicado que invertir una lista circular simple o doblemente.
  • Es posible que el código entre en un bucle infinito si no se maneja con cuidado.
  • Es más difícil encontrar el final de la lista y controlar el bucle.
  • Aunque las listas enlazadas circulares pueden ser eficientes en ciertas aplicaciones, su rendimiento puede ser más lento que el de otras estructuras de datos en ciertos casos, como cuando es necesario ordenar o buscar la lista.
  • Las listas enlazadas circulares no proporcionan acceso directo a nodos individuales

Aplicaciones de listas enlazadas circulares:

  • Los juegos multijugador utilizan esto para darle a cada jugador la oportunidad de jugar.
  • Se puede utilizar una lista circular enlazada para organizar varias aplicaciones en ejecución en un sistema operativo. Estas aplicaciones son iteradas por el sistema operativo.
  • Las listas enlazadas circulares se pueden utilizar en problemas de asignación de recursos.
  • Las listas enlazadas circulares se utilizan comúnmente para implementar buffers circulares,
  • Las listas enlazadas circulares se pueden utilizar en simulación y juegos.

¿Por qué una lista circular enlazada?

  • Un nodo siempre apunta a otro nodo, por lo que la asignación NULL no es necesaria.
  • Cualquier nodo se puede establecer como punto de partida.
  • Los nodos se atraviesan rápidamente desde el primero hasta el último.

Siguientes publicaciones: Lista circular enlazada | Conjunto 2 (recorrido) Lista circular individualmente enlazada | Inserción Escriba comentarios si encuentra algún error en el código/algoritmo anterior, o encuentre otras formas de resolver el mismo problema.