Implementa una lista doppiamente collegata in C++

1. Usa struct per implementare una lista doppiamente collegata in C++
2. Usa il contenitore std::list come lista doppiamente collegata in C++

Questo articolo dimostrerà più metodi su come implementare un elenco doppiamente collegato in C++.

Usa struct per implementare una lista doppiamente collegata in C++

Le liste concatenate sono considerate una delle strutture dati più comuni che puoi incontrare nella programmazione. Queste strutture sono collegate nel senso che ogni nodo contiene l’indirizzo di un altro. Gli elenchi collegati sono di due tipi: elenchi con collegamento singolo e elenchi con collegamento doppio. Un elenco con collegamento singolo contiene nodi che puntano solo al nodo successivo nella lista; rende quindi unidirezionale l’attraversamento della struttura. D’altra parte, gli elenchi doppiamente collegati forniscono un accesso bidirezionale da ciascun nodo nella lista.

In questo caso, implementiamo una lista doppiamente concatenata usando il comando struct, rendendo pubblici tutti i suoi membri dati e definendo separatamente le funzioni di manipolazione degli elementi. Si noti che si può preferire una versione orientata agli oggetti con funzioni membro che forniscano le routine di manipolazione degli elementi e alcuni membri dei dati di conservazione dei record.

Il codice di esempio seguente include il codice del driver nella funzione main che verifica lo scenario di utilizzo di base, in cui gli elementi del vettore string vengono inseriti in un elenco e quindi la lista viene deallocato. Utilizziamo l’operatore new per allocare dinamicamente ogni nodo e, di conseguenza, la funzione freeNodes scorre la lista per chiamare delete su ogni Node.

Il metodo di allocazione separata di ciascun Node potrebbe essere inefficiente se l’utente desidera progettare una struttura di elenchi collegati relativamente ad alte prestazioni. Si potrebbe prendere in considerazione un’allocazione di massa delle risorse di memoria per aggiungere rapidamente nuovi nodi e, quando non è necessario, deallocare multipli allo stesso tempo. In questo progetto, iniziamo a costruire la lista con l’elemento valido che rappresenta il primo nodo nella struttura. Alcune implementazioni possono creare un elemento fittizio, che denota la testa della lista ma non contiene i dati dell’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;
}

Produzione:

data : Rocket Lake data : Meteor Lake

È possibile utilizzare elenchi collegati come elementi costitutivi di strutture dati più specializzate come stack, deque, code o elenchi circolari. Quest’ultimo è interessante perché è essenzialmente una lista doppiamente collegata in cui l’ultimo nodo punta al primo elemento come nodo successivo e, di conseguenza, il primo punta all’ultimo elemento come nodo precedente. Si noti che il seguente frammento di codice aggiunge la funzione printNodes per visualizzare il contenuto di ciascun nodo nella lista costruito.

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

Produzione:

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

Usa il contenitore std::list come lista doppiamente collegata in C++

In alternativa, si può utilizzare il contenitore std::list di C++ STL, che di solito è implementato come lista doppiamente collegata e fornisce varie funzioni di manipolazione degli elementi. Inoltre, il contenitore std::list è implementato per supportare algoritmi abbastanza potenti inclusi nella libreria standard in modo che l’utente possa risparmiare tempo nello sviluppo se non sono richieste alcune caratteristiche prestazionali molto speciali.

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

Produzione:

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