Implementar uma estrutura de dados de lista ligada circular em C++

1. Implemente uma lista ligada unicamente circular com funções de membro para adicionar novos elementos no final e para imprimir elementos em C++
2. Implemente o destruidor e a função de membro para inserir novos elementos no início da lista em C++

Este artigo explicará como implementar uma estrutura de dados de lista ligada circular em C++.

Implemente uma lista ligada unicamente circular com funções de membro para adicionar novos elementos no final e para imprimir elementos em C++

Uma lista ligada circular pode ser caracterizada como uma lista ligada em que o último nó aponta para o topo da lista. Essencialmente, os nós da lista formam um círculo e não há nullptr para demarcar o final da lista. Você pode utilizar listas circulares vinculadas para construir estruturas de dados em estilo de fila. O recurso de circularidade pode ser adicionado à lista duplamente vinculada e a uma lista vinculada individualmente.

Nesse caso, vamos implementar o último. Lembre-se de que precisamos definir uma estrutura de nó que inclui um ponteiro para o próximo nó e um elemento de dados para construir uma lista unida individualmente. O objeto struct ListNode representa um único nó para nossa implementação e armazena um único objeto string denominado data, que servirá como os dados do elemento para este exemplo. Observe que é possível armazenar qualquer objeto definido de forma personalizada em um nó e, se o objeto for relativamente maior, é melhor incluí-lo como um ponteiro.

Uma vez que temos uma estrutura de um único nó, podemos definir uma classe CircularList, que tem apenas duas funções-membro para começar. Geralmente, uma lista ligada circular deve manter o controle do cabeçalho da lista ou de seu final; entretanto, o implementador geralmente é livre para tomar a decisão de design da classe com base em suas necessidades. Além disso, a classe CircularList armazena dois ponteiros separados para representar o início e o final da lista.

O ponteiro que armazena o início / fim da lista pode ser um nó fictício ou um nó real com os dados. Neste exemplo, escolhemos projetar a classe CircularList para não ter ponteiros fictícios. Definimos um construtor para aceitar um parâmetro string para inicializar o primeiro nó na lista circular. Observe que as escolhas de design durante a definição da classe geralmente afetam variáveis ​​diferentes, que devem ser consideradas com base no problema subjacente. Assim, a implementação a seguir pretende ser simples para explicar o conceito de listas circulares vinculadas.

Uma vez que o objeto CircularList é inicializado usando o construtor, podemos adicionar novos elementos usando a função de membro insertNodeEnd. Este último aceita o parâmetro string e constrói um novo elemento no final da lista. A função insertNodeEnd aloca novos elementos com o operador new e modifica os ponteiros de acordo para inserir o nó logo após o final da lista. Ele também atualiza o membro de dados final para apontar para um nó recém-alocado.

Outra função membro definida no próximo exemplo é o printNodes, que itera através da lista para imprimir seu conteúdo e não leva nenhum argumento. Agora, para demonstrar melhor o uso desta estrutura, precisamos de algum código de driver na função main. Escolhemos inicializar um vetor de strings arbitrárias para depois ser inserido no objeto CircularList usando o loop for. Finalmente, invocamos uma função printNodes para exibir o conteúdo da lista no 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;
}

Resultado:

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

Implemente o destruidor e a função de membro para inserir novos elementos no início da lista em C++

Observe que o fragmento de código anterior tem um grande problema de não ter um destruidor definido; isso implica que o programa que utiliza a classe CircularList vazará memória, uma vez que os nós criados na memória dinâmica não são liberados até a saída do programa.

A solução para este problema é implementar um destruidor que irá percorrer toda a lista e desalocar todos os nós usando o operador delete. Assim, não precisamos nos preocupar em liberar a memória da lista manualmente. Ele será automaticamente liberado assim que o objeto CircularList atingir o final do escopo.

Outra função útil para implementar é aquela que insere um novo elemento no topo da lista; o comando insertNodeHead é projetado para fazer exatamente isso. Leva apenas um argumento string para ser armazenado e retorna o ponteiro para o nó recém-alocado. Observe que o valor de retorno para as funções insertNodeEnd e insertNodeHead é outra opção de design, que é implementada de forma diferente conforme o programador decide. O fragmento de código a seguir inclui o código de driver semelhante na função main para testar e mostrar o uso da classe 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;
}

Resultado:

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