Reverter a lista vinculada em C++

Jinku Hu 12 outubro 2023

C++ C++ Data Structure

Este artigo demonstrará como reverter uma estrutura de dados de lista vinculada em C++.

Use a função iterativa para reverter a lista vinculada em C++

Assumimos que o objeto de destino é uma lista vinculada individualmente e implementamos trechos de código de acordo. Primeiramente, precisamos examinar os utilitários de função básicos no código do driver implementado para demonstrar o exemplo.

O nó da lista vinculada é uma struct simples com um único objeto de dados string e um ponteiro para o próximo nó. Também temos a função addNewNode que recebe dois argumentos, Node* e uma referência à string. A função addNewNode é chamada várias vezes na rotina main para construir um novo objeto de lista e armazenar strings do vetor data_set. A função aloca cada nó na memória dinâmica e retorna o ponteiro para o nó recém-criado.

Outra função útil para nossa estrutura de dados de lista vinculada é printNodes, que é usada para enviar dados de cada nó para o fluxo cout. O último nos ajudará a verificar vagamente a correção da função de reversão. Observe que printNodes mantém a contagem de nós durante a travessia da lista e imprime o índice para cada elemento. Finalmente, precisamos desalocar todos os nós antes de encerrar o programa. Esta etapa não é necessária para demonstração da função de reversão, mas é importante para qualquer projeto do mundo real limpar toda a memória alocada durante o tempo de execução.

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

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

struct Node {
  struct Node *next{};
  string data;
};

struct Node *addNewNode(struct Node *node, string &data) {
  auto new_node = new Node;
  if (node) node->next = new_node;
  new_node->next = nullptr;
  new_node->data = data;
  return new_node;
}

void freeNodes(struct Node *node) {
  struct Node *tmp = nullptr;
  while (node) {
    tmp = node;
    node = node->next;
    delete tmp;
  }
}

void printNodes(struct Node *node) {
  auto count = 0;
  while (node) {
    cout << "node " << count << " - data: " << node->data << endl;
    node = node->next;
    count++;
  }
}

int main() {
  struct Node *tmp, *head = nullptr;

  vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
                             "Meteor Lake"};

  head = addNewNode(head, data_set.at(0));
  tmp = head;
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    tmp = addNewNode(tmp, *it);
  }

  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

Resultado:

node 0 - data : Rocket Lake node 1 - data : Alder Lake node 2 -
                                            data : Tiger Lake node 3 -
                                                   data : Meteor Lake

Depois de inicializarmos uma nova lista vinculada e armazenar o cabeçalho da lista em um ponteiro separado, podemos usá-lo para reverter o conteúdo. Neste caso, implementamos a função reverseList, que aceita um único argumento Node* e retorna um novo nó raiz. Primeiramente, duplicamos o ponteiro passado e o armazenamos como uma variável head. Também precisamos de dois ponteiros do tipo Node adicionais para fazer a contabilidade interna durante o loop while.

O algoritmo de reversão pode ser descrito como segue: Armazenamos o próximo ponteiro do nó em uma variável temporária (next) e atribuímos o valor nullptr ao original. Como resultado, o nó main original estará apontando para nullptr como seu próximo nó na lista. Em seguida, atualizamos a variável head para armazenar o próximo (o segundo) nó na lista original e também salvamos o endereço do nó principal original em uma variável temporária separada.

Repetimos os passos anteriores até que o ponteiro head avalie como nullptr, o que significaria que o fim da lista foi alcançado. No final, retornamos o endereço do novo nó principal armazenado na variável temporária n. Consequentemente, o programa main chama a função printNodes para o usuário comparar o conteúdo da lista vinculada modificada.

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

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

struct Node {
  struct Node *next{};
  string data;
};

struct Node *addNewNode(struct Node *node, string &data) {
  auto new_node = new Node;
  if (node) node->next = new_node;
  new_node->next = nullptr;
  new_node->data = data;
  return new_node;
}

void freeNodes(struct Node *node) {
  struct Node *tmp = nullptr;
  while (node) {
    tmp = node;
    node = node->next;
    delete tmp;
  }
}

void printNodes(struct Node *node) {
  auto count = 0;
  while (node) {
    cout << "node " << count << " - data: " << node->data << endl;
    node = node->next;
    count++;
  }
}

Node *reverseList(struct Node *node) {
  auto head = node;
  Node *n = nullptr;
  Node *next = nullptr;

  while (head) {
    next = head->next;
    head->next = n;

    n = head;
    head = next;
  }
  return n;
}

int main() {
  struct Node *tmp, *head = nullptr;

  vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
                             "Meteor Lake"};

  head = addNewNode(head, data_set.at(0));
  tmp = head;
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    tmp = addNewNode(tmp, *it);
  }

  printNodes(head);

  cout << " ----------------------------------- " << endl;
  printNodes(reverseList(head));

  freeNodes(head);
  return EXIT_SUCCESS;
}

Resultado:

node 0 - data : Rocket Lake node 1 - data : Alder Lake node 2 -
                                            data : Tiger Lake node 3 -
                                                   data
    : Meteor Lake-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
      data
    : Meteor Lake node 1 -
      data : Tiger Lake node 2 - data : Alder Lake node 3 - data : Rocket Lake

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

Use a função iterativa para reverter a lista vinculada em C++

Artigo relacionado - C++ Data Structure