Implementar una lista doblemente vinculada en C++

1. Utilice struct para implementar una lista doblemente enlazada en C++
2. Utilice el contenedor std::list como lista doblemente enlazada en C++

Este artículo demostrará varios métodos sobre cómo implementar una lista doblemente enlazada en C++.

Utilice struct para implementar una lista doblemente enlazada en C++

Las listas vinculadas se consideran una de las estructuras de datos más comunes que puede encontrar en la programación. Estas estructuras están vinculadas en el sentido de que cada nodo contiene la dirección de otro. Las listas enlazadas tienen dos tipos: listas enlazadas individualmente y listas enlazadas doblemente. Una lista de un solo enlace contiene nodos que solo apuntan al siguiente nodo de la lista; por tanto, hace que el recorrido de la estructura sea unidireccional. Por otro lado, las listas doblemente enlazadas proporcionan acceso bidireccional desde cada nodo de la lista.

En este caso, implementamos una lista doblemente enlazada usando el comando struct, haciendo públicos todos sus miembros de datos y definiendo las funciones de manipulación de elementos por separado. Tenga en cuenta que se puede preferir una versión orientada a objetos con funciones miembro que proporcionen las rutinas de manipulación de elementos y algunos miembros de datos de mantenimiento de registros.

El siguiente código de ejemplo incluye el código del controlador en la función main que prueba el escenario de uso básico, donde los elementos del vector cadena se insertan en una lista, y luego la lista se desasigna. Utilizamos el operador new para asignar dinámicamente cada nodo y, en consecuencia, la función freeNodes recorre la lista para llamar a delete en cada Node.

El método de asignar por separado cada Node podría resultar ineficaz si el usuario desea diseñar una estructura de lista enlazada de rendimiento relativamente alto. Se podría considerar una asignación masiva de recursos de memoria para agregar nuevos nodos rápidamente y, cuando no sea necesario, desasignar múltiples al mismo tiempo. En este diseño, comenzamos a construir la lista con el elemento válido que representa el primer nodo en la estructura. Algunas implementaciones pueden crear un elemento ficticio, que denota el encabezado de la lista pero no contiene los datos del 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;
}

Producción :

data: Rocket Lake
data: Meteor Lake

Puede utilizar listas vinculadas como bloques de construcción de estructuras de datos más especializadas como pilas, deques, colas o listas circulares. Este último es interesante porque es esencialmente una lista doblemente enlazada donde el último nodo apunta al primer elemento como el siguiente nodo y, en consecuencia, el primero apunta al último elemento como el nodo anterior. Observe que el siguiente fragmento de código agrega la función printNodes para mostrar el contenido de cada nodo en la lista construida.

#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;
}

Producción :

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

Utilice el contenedor std::list como lista doblemente enlazada en C++

Alternativamente, se puede utilizar el contenedor std::list de C++ STL, que generalmente se implementa como la lista doblemente enlazada y proporciona varias funciones de manipulación de elementos. Además, el contenedor std::list está implementado para soportar algoritmos bastante poderosos incluidos en la biblioteca estándar para que el usuario pueda ahorrar tiempo en el desarrollo si no se requieren algunas características de rendimiento muy especiales.

#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;
}

Producción :

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