Implementar una estructura de datos de lista enlazada circular en C++

1. Implementar una lista circular enlazada individualmente con funciones miembro para agregar nuevos elementos al final e imprimir elementos en C++
2. Implementar la función Destructor y Miembro para insertar nuevos elementos al comienzo de la lista en C++

Este artículo explicará cómo implementar una estructura de datos de lista enlazada circular en C++.

Implementar una lista circular enlazada individualmente con funciones miembro para agregar nuevos elementos al final e imprimir elementos en C++

Una lista enlazada circular se puede caracterizar como una lista enlazada donde el último nodo apunta al encabezado de la lista. Esencialmente, los nodos de la lista forman un círculo y no existe un nullptr para demarcar el final de la lista. Puede utilizar listas enlazadas circulares para crear estructuras de datos al estilo de una cola. La característica de circularidad se puede agregar tanto a la lista de enlaces dobles como a una lista de enlaces individuales.

En este caso, implementaremos el último. Recuerde que necesitamos definir una estructura de nodo que incluya un puntero al siguiente nodo y un elemento de datos para construir una lista enlazada individualmente. El objeto struct ListNode representa un solo nodo para nuestra implementación y almacena un único objeto string llamado data, que servirá como los datos del elemento para este ejemplo. Tenga en cuenta que se puede almacenar cualquier objeto definido de forma personalizada en un nodo, y si el objeto es relativamente más grande, es mejor incluirlo como puntero.

Una vez que tenemos una estructura de un solo nodo, podemos definir una clase CircularList, que tiene solo dos funciones miembro para empezar. Generalmente, una lista enlazada circular debe mantener un registro del encabezado de la lista o su final; sin embargo, el implementador suele tener la libertad de tomar la decisión de diseño de la clase en función de sus necesidades. Además, la clase CircularList almacena dos punteros separados para representar el encabezado y el final de la lista.

El puntero que almacena el encabezado / final de la lista puede ser un nodo ficticio o un nodo real con los datos. En este ejemplo, elegimos diseñar la clase CircularList para que no tuviera punteros ficticios. Definimos un constructor para aceptar un parámetro string para inicializar el primer nodo de la lista circular. Tenga en cuenta que las elecciones de diseño durante la definición de la clase generalmente afectan diferentes variables, que deben considerarse en función del problema subyacente. Por lo tanto, la siguiente implementación solo pretende ser simple para explicar el concepto de listas enlazadas circulares.

Una vez que el objeto CircularList se inicializa usando el constructor, podemos agregar nuevos elementos usando la función miembro insertNodeEnd. Este último acepta el parámetro cadena y construye un nuevo elemento al final de la lista. La función insertNodeEnd asigna nuevos elementos con el operador new y modifica los punteros en consecuencia para insertar el nodo justo después del final de la lista. También actualiza el miembro de datos final para que apunte a un nodo recién asignado.

Otra función miembro definida en la siguiente muestra es printNodes, que recorre la lista para imprimir su contenido y no toma ningún argumento. Ahora, para demostrar mejor el uso de esta estructura, necesitamos algún código de controlador en la función main. Elegimos inicializar un vector de cadenas arbitrarias para luego insertarlo en el objeto CircularList usando el bucle for. Finalmente, invocamos una función printNodes para mostrar el contenido de la lista en la terminal.

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

struct ListNode {
  struct ListNode *next = nullptr;
  string data;
} typedef ListNode;

class CircularList {
 public:
  explicit CircularList(string data) {
    head = new ListNode;
    head->next = head;
    head->data = std::move(data);
    end = head;
  };

  ListNode *insertNodeEnd(string data);
  void printNodes();

 private:
  ListNode *head = nullptr;
  ListNode *end = nullptr;
};

ListNode *CircularList::insertNodeEnd(string data) {
  auto new_node = new ListNode;
  new_node->next = end->next;
  new_node->data = std::move(data);

  end->next = new_node;
  end = end->next;
  return new_node;
}

void CircularList::printNodes() {
  auto count = 0;
  auto tmp = head;
  while (tmp != end) {
    cout << "node " << count << " - data: " << tmp->data << endl;
    tmp = tmp->next;
    count++;
  }
  cout << "node " << count << " - data: " << tmp->data << endl;
}

int main() {
  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  CircularList clist("Xenial");

  for (const auto &item : data_set) {
    clist.insertNodeEnd(item);
  }

  clist.printNodes();

  return EXIT_SUCCESS;
}

Producción :

node 0 - data: Xenial
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring

Implementar la función Destructor y Miembro para insertar nuevos elementos al comienzo de la lista en C++

Tenga en cuenta que el fragmento de código anterior tiene el gran problema de no tener un destructor definido; esto implica que el programa que utiliza la clase CircularList perderá memoria ya que los nodos creados en la memoria dinámica no se liberan hasta que el programa sale.

La solución a este problema es implementar un destructor que recorra toda la lista y desasigne todos los nodos usando el operador delete. Por lo tanto, no debemos preocuparnos por liberar la memoria de la lista manualmente. Se liberará automáticamente una vez que el objeto CircularList llegue al final del alcance.

Otra función útil a implementar es la que inserta un nuevo elemento al comienzo de la lista; el comando insertNodeHead está diseñado para hacer precisamente eso. Solo se necesita un argumento de cadena para ser almacenado y devuelve el puntero al nodo recién asignado. Tenga en cuenta que el valor de retorno para las funciones insertNodeEnd e insertNodeHead es otra opción de diseño, que se implementa de manera diferente según lo decida el programador. El siguiente fragmento de código incluye el código de controlador similar en la función main para probar y mostrar el uso de la clase CircularList.

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

struct ListNode {
  struct ListNode *next = nullptr;
  string data;
} typedef ListNode;

class CircularList {
 public:
  explicit CircularList(string data) {
    head = new ListNode;
    head->next = head;
    head->data = std::move(data);
    end = head;
  };

  ListNode *insertNodeEnd(string data);
  ListNode *insertNodeHead(string data);
  void printNodes();

  ~CircularList();

 private:
  ListNode *head = nullptr;
  ListNode *end = nullptr;
};

ListNode *CircularList::insertNodeEnd(string data) {
  auto new_node = new ListNode;
  new_node->next = end->next;
  new_node->data = std::move(data);

  end->next = new_node;
  end = end->next;
  return new_node;
}

ListNode *CircularList::insertNodeHead(string data) {
  auto new_node = new ListNode;
  new_node->next = end->next;
  new_node->data = std::move(data);

  end->next = new_node;
  head = end->next;
  return new_node;
}

CircularList::~CircularList() {
  while (head != end) {
    auto tmp = head;
    head = head->next;
    delete tmp;
  }
  delete head;
}

void CircularList::printNodes() {
  auto count = 0;
  auto tmp = head;
  while (tmp != end) {
    cout << "node " << count << " - data: " << tmp->data << endl;
    tmp = tmp->next;
    count++;
  }
  cout << "node " << count << " - data: " << tmp->data << endl;
}

int main() {
  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  CircularList clist("Xenial");

  for (const auto &item : data_set) {
    clist.insertNodeEnd(item);
  }

  clist.printNodes();
  cout << " ----------------------------------- " << endl;

  clist.insertNodeHead("Bionic");
  clist.insertNodeEnd("Zeisty");
  clist.printNodes();

  return EXIT_SUCCESS;
}

Producción :

node 0 - data: Xenial
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring
 -----------------------------------
node 0 - data: Bionic
node 1 - data: Xenial
node 2 - data: Precise
node 3 - data: Quantal
node 4 - data: Saucy
node 5 - data: Raring
node 6 - data: Zeisty