Inicio

Temas

Listas Simplemente (LSE) y Doblemente enlazadas (LDE)

Estructuras de Datos en Grafos

Listas circulares y operaciones

Una lista circular es un tipo de estructura de datos en la que cada elemento tiene un enlace a otro elemento en la lista, formando una estructura circular. Esto significa que la lista no tiene un comienzo o un final definidos, sino que cada elemento de la lista se encuentra en una posición relativa a los demás elementos.

Una de las principales ventajas de las listas circulares es que permiten un acceso rápido a cualquier elemento de la lista, ya que no es necesario recorrer la lista desde el principio para llegar a un elemento específico. Además, las listas circulares también pueden ser útiles en situaciones en las que se desea implementar una estructura de datos que permita el recorrido continuo de los elementos, como en el caso de una lista de reproducción de música o una lista de imágenes en una presentación.

Otra ventaja de las listas circulares es que pueden ser implementadas de manera eficiente utilizando punteros, lo que permite un acceso rápido a cualquier elemento de la lista y una inserción y eliminación rápidas de elementos. Sin embargo, también es importante tener en cuenta que las listas circulares requieren más espacio de memoria que otras estructuras de datos, ya que cada elemento debe almacenar un enlace adicional a otro elemento de la lista.

Insertar:

Para insertar un elemento en una lista circular, necesitarás seguir los siguientes pasos:

Crea un nuevo nodo para almacenar el elemento que deseas insertar. Este nodo debe tener un campo para el valor del elemento y otro para el enlace al siguiente elemento de la lista.

Si la lista está vacía, debes establecer el enlace del nodo recién creado al mismo nodo, de manera que forme una lista circular con un solo elemento.

Si la lista ya tiene elementos, debes encontrar el lugar donde deseas insertar el nuevo elemento. Puedes hacer esto recorriendo la lista hasta encontrar el elemento anterior al que deseas insertar o utilizando un puntero para saltar directamente al lugar correcto.

Una vez que hayas encontrado el lugar correcto, debes establecer el enlace del nodo anterior al nuevo nodo y el enlace del nuevo nodo al siguiente nodo en la lista. De esta manera, el nuevo nodo queda insertado en la lista circular en la posición correcta.

Es importante tener en cuenta que, al tratarse de una lista circular, el último elemento de la lista debe tener un enlace al primer elemento de la lista. De esta manera, la lista circular queda cerrada y permite el recorrido continuo de sus elementos.

                    
                        class ListaCircular {
                             private:
                              struct Nodo {
                                int valor;
                                Nodo* siguiente;
                              };
                              Nodo* cabeza;
                            
                             public:
                              ListaCircular() : cabeza(nullptr) {}
                            
                              void Insertar(int valor) {
                                // Crea un nuevo nodo para almacenar el valor
                                Nodo* nuevo = new Nodo;
                                nuevo->valor = valor;
                            
                                if (cabeza == nullptr) {
                                  // Si la lista está vacía, el nuevo nodo es la cabeza y tiene enlace a sí mismo
                                  cabeza = nuevo;
                                  cabeza->siguiente = cabeza;
                                } else {
                                  // Si la lista ya tiene elementos, encuentra el último nodo y enlázalo con el nuevo nodo
                                  Nodo* ultimo = cabeza;
                                  while (ultimo->siguiente != cabeza) {
                                    ultimo = ultimo->siguiente;
                                  }
                                  ultimo->siguiente = nuevo;
                                  nuevo->siguiente = cabeza;
                                }
                              }
                            };

Eliminar

Para eliminar un elemento de una lista circular, debes seguir los siguientes pasos:

Encuentra el nodo que almacena el elemento que deseas eliminar. Puedes hacer esto recorriendo la lista hasta encontrar el elemento o utilizando un puntero para saltar directamente al lugar correcto.

Una vez que has encontrado el nodo que almacena el elemento a eliminar, debes eliminar el enlace al siguiente nodo de la lista. Para ello, debes establecer el enlace del nodo anterior al siguiente nodo en la lista, saltándose el nodo que deseas eliminar.

Finalmente, debes eliminar el nodo que almacena el elemento a eliminar. Esto puede hacerse utilizando la función delete de C++ o la función free de C.

Es importante tener en cuenta que, al tratarse de una lista circular, debes asegurarte de que el último elemento de la lista tenga un enlace al primer elemento de la lista después de eliminar el elemento. De esta manera, la lista circular queda cerrada y permite el recorrido continuo de sus elementos.

                    
                        class ListaCircular {
                             private:
                              struct Nodo {
                                int valor;
                                Nodo* siguiente;
                              };
                              Nodo* cabeza;
                            
                             public:
                              ListaCircular() : cabeza(nullptr) {}
                            
                              void Eliminar(int valor) {
                                // Si la lista está vacía, no hay nada que eliminar
                                if (cabeza == nullptr) {
                                  return;
                                }
                            
                                // Si el elemento a eliminar es el único de la lista, elimina la cabeza
                                if (cabeza->siguiente == cabeza && cabeza->valor == valor) {
                                  delete cabeza;
                                  cabeza = nullptr;
                                  return;
                                }
                            
                                // Si el elemento a eliminar es la cabeza, encuentra el último nodo y cambia la cabeza
                                if (cabeza->valor == valor) {
                                  Nodo* ultimo = cabeza;
                                  while (ultimo->siguiente != cabeza) {
                                    ultimo = ultimo->siguiente;
                                  }
                                  cabeza = cabeza->siguiente;
                                  ultimo->siguiente = cabeza;
                                  delete ultimo;
                                  return;
                                }
                            
                                // Si el elemento a eliminar está en otra parte de la lista, busca su nodo anterior y enlázalo con el siguiente
                                Nodo* anterior = cabeza;
                                while (anterior->siguiente != cabeza && anterior->siguiente->valor != valor) {
                                  anterior = anterior->siguiente;
                                }
                            
                                // Si se encontró el elemento a eliminar, elimina su nodo y enlaza el anterior con el siguiente
                                if (anterior->siguiente != cabeza) {
                                  Nodo* eliminar = anterior->siguiente;
                                  anterior->siguiente = eliminar->siguiente;
                                  delete eliminar;
                                }
                              }
                            };

Buscar:

Para buscar un elemento en una lista circular, puedes seguir los siguientes pasos:

Comienza en el primer elemento de la lista y recorre la lista hasta encontrar el elemento que deseas buscar o hasta llegar al final de la lista.

Mientras recorres la lista, comparas el valor de cada elemento con el valor que estás buscando. Si encuentras un elemento con el valor correcto, puedes devolver el elemento o la posición en la que se encuentra.

Si llegas al final de la lista y no has encontrado el elemento que estás buscando, debes volver al principio de la lista y continuar recorriendo hasta encontrar el elemento o hasta llegar de nuevo al final de la lista.

Es importante tener en cuenta que, al tratarse de una lista circular, debes asegurarte de que no entras en un bucle infinito mientras recorres la lista. Una forma de evitar esto es utilizar una variable para llevar la cuenta del número de elementos que has recorrido y detener la búsqueda cuando hayas recorrido todos los elementos de la lista.

                    
                        class ListaCircular {
                             private:
                              struct Nodo {
                                int valor;
                                Nodo* siguiente;
                              };
                              Nodo* cabeza;
                            
                             public:
                              ListaCircular() : cabeza(nullptr) {}
                            
                              int Buscar(int valor) {
                                // Si la lista está vacía, devuelve -1
                                if (cabeza == nullptr) {
                                  return -1;
                                }
                            
                                // Recorre la lista hasta encontrar el elemento o llegar al final de la lista
                                Nodo* actual = cabeza;
                                int posicion = 0;
                                while (actual->siguiente != cabeza && actual->valor != valor) {
                                  actual = actual->siguiente;
                                  posicion++;
                                }
                            
                                // Si se encontró el elemento, devuelve su posición
                                if (actual->valor == valor) {
                                  return posicion;
                                }
                            
                                // Si no se encontró el elemento, devuelve -1
                                return -1;
                              }
                            };