Lista circular duplamente vinculada em C++

Jinku Hu 12 outubro 2023

C++ C++ Data Structure

Lista circular duplamente vinculada em C++

Este artigo demonstrará como implementar uma lista duplamente vinculada circular em C++.

Estrutura de dados de lista circular duplamente vinculada desde o início em C++

Uma lista duplamente vinculada é uma estrutura de dados em que cada nó armazena ponteiros para o próximo nó e para o nó anterior. Isso o torna uma escolha ideal para implementar contêineres do tipo std::deque. Seria melhor fazer uma lista duplamente ligada circular de modo que o membro next do último nó aponte para o início da lista e o primeiro nó também aponte para o último nó como seu anterior.

Primeiramente, precisamos declarar uma struct chamada ListNode usada para construir uma lista. Em seguida, definimos uma classe CircularList com dois membros de dados do tipo ListNode e funções de três membros.

Observe que decidimos incluir apenas um construtor que aceita um valor string e inicializa o primeiro nó, mas esta parte pode ser modificada como o programador achar necessário. Dois membros de dados - head e end - armazenam o primeiro e o último nós. Também temos funções separadas para adicionar elementos em cada lado da lista.

#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;
  struct ListNode *prev = nullptr;
  string data;
} typedef ListNode;

class CircularList {
 public:
  explicit CircularList(string data) {
    head = new ListNode;
    head->next = head;
    head->prev = 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 = head;
  new_node->prev = end;
  new_node->data = std::move(data);

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

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

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

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() {
  CircularList clist("Xenial");

  clist.insertNodeHead("Saucy");
  clist.insertNodeEnd("Quantal");

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

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

  return EXIT_SUCCESS;
}

Produção:

node 0 - data: Saucy
node 1 - data: Xenial
node 2 - data: Quantal
 -----------------------------------
node 0 - data: Bionic
node 1 - data: Saucy
node 2 - data: Xenial
node 3 - data: Quantal

O algoritmo geral para inserção de elemento envolve a alocação de um novo objeto ListNode, atribuindo ponteiros de nó correspondentes a seus membros e, em seguida, modificando os membros head / end conforme necessário. Também incluímos uma função printNodes para exibir o conteúdo da lista, pois podemos precisar inspecionar a exatidão do código. Observe que não se deve esquecer de desalocar toda a memória depois que o objeto de lista sai do escopo. A última função é implementada como um destruidor.

Autor: Jinku Hu

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn Facebook

Estrutura de dados de lista circular duplamente vinculada desde o início em C++

Artigo relacionado - C++ Data Structure