Implementar uma lista duplamente vinculada em C++

Jinku Hu 12 outubro 2023

C++ C++ Data Structure

Use struct para implementar lista duplamente vinculada em C++
Use o recipiente std::list como uma lista duplamente vinculada em C++

Este artigo demonstrará vários métodos sobre como implementar uma lista duplamente vinculada em C++.

Use `struct` para implementar lista duplamente vinculada em C++

Listas vinculadas são consideradas uma das estruturas de dados mais comuns que você pode encontrar na programação. Essas estruturas estão vinculadas no sentido de que cada nó contém o endereço de outro. As listas vinculadas têm dois tipos: listas unidas individualmente e listas duplamente vinculadas. Uma lista com links simples contém nós que apontam apenas para o próximo nó da lista; assim, torna a travessia da estrutura unidirecional. Por outro lado, as listas duplamente vinculadas fornecem acesso bidirecional de cada nó na lista.

Nesse caso, implementamos uma lista duplamente vinculada usando o comando struct, tornando públicos todos os seus membros de dados e definindo as funções de manipulação do elemento separadamente. Observe que pode-se preferir uma versão orientada a objetos com funções de membro fornecendo as rotinas de manipulação de elemento e alguns membros de dados de manutenção de registros.

O código de exemplo a seguir inclui o código do driver na função main que testa o cenário de uso básico, onde os elementos do vetor string são inseridos em uma lista e, em seguida, a lista é desalocada. Utilizamos o operador new para alocar dinamicamente cada nó e, consequentemente, a função freeNodes itera através da lista para chamar delete em cada Node.

O método de alocar separadamente cada Node pode ser ineficiente se o usuário quiser projetar uma estrutura de lista vinculada de desempenho relativamente alto. Pode-se considerar uma alocação em massa de recursos de memória para adicionar novos nós rapidamente e, quando não for necessário, desalocar múltiplos ao mesmo tempo. Neste projeto, começamos a construir a lista com o elemento válido que representa o primeiro nó na estrutura. Algumas implementações podem criar um elemento fictício, que denota o topo da lista, mas não contém os dados do elemento.

#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{};
  struct Node *prev{};
  string data;
};

template <typename T>
struct Node *addNewNode(struct Node *node, T &data) {
  auto new_node = new Node;
  if (node) node->next = new_node;
  new_node->prev = 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 printNodeData(struct Node *node) {
  cout << "data: " << node->data << endl;
}

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

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

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

  printNodeData(root);
  printNodeData(end);

  freeNodes(root);
  return EXIT_SUCCESS;
}

Resultado:

data : Rocket Lake data : Meteor Lake

Você pode utilizar listas vinculadas como blocos de construção de estruturas de dados mais especializadas, como pilhas, deques, filas ou listas circulares. O último é interessante porque é essencialmente uma lista duplamente vinculada, onde o último nó aponta para o primeiro elemento como o próximo nó e, correspondentemente, o primeiro aponta para o último elemento como o nó anterior. Observe que o fragmento de código a seguir adiciona a função printNodes para exibir o conteúdo de cada nó na lista construída.

#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{};
  struct Node *prev{};
  string data;
};

struct Node *addNewNode(struct Node *node, string &data) {
  auto new_node = new Node;
  if (node) node->next = new_node;
  new_node->prev = 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, *root = nullptr;
  struct Node *end = nullptr;

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

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

  printNodes(root);

  freeNodes(root);
  return EXIT_SUCCESS;
}

Resultado:

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

Use o recipiente `std::list` como uma lista duplamente vinculada em C++

Alternativamente, pode-se utilizar o contêiner std::list do C++ STL, que geralmente é implementado como a lista duplamente vinculada e fornece várias funções de manipulação de elementos. Além disso, o contêiner std::list é implementado para suportar algoritmos bastante poderosos incluídos na biblioteca padrão para que o usuário possa economizar tempo no desenvolvimento se algumas características de desempenho muito especiais não forem necessárias.

#include <iostream>
#include <list>
#include <string>

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

template <typename T>
void printList(std::list<T> l) {
  for (const auto &item : l) {
    cout << item << "; ";
  }
  cout << endl;
}

int main() {
  std::list<int> l = {1, 2, 3, 4};
  l.push_back(5);
  l.push_front(0);
  printList(l);

  auto it = std::find(l.begin(), l.end(), 3);
  if (it != l.end()) {
    l.insert(it, 99);
  }
  printList(l);

  return EXIT_SUCCESS;
}

Resultado:

0;
1;
2;
3;
4;
5;
0;
1;
2;
99;
3;
4;
5;

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 struct para implementar lista duplamente vinculada em C++

Use o recipiente std::list como uma lista duplamente vinculada em C++

Artigo relacionado - C++ Data Structure

Use `struct` para implementar lista duplamente vinculada em C++

Use o recipiente `std::list` como uma lista duplamente vinculada em C++