Elimina un nodo in una lista collegata in C++

Jinku Hu 12 ottobre 2023

C++ C++ Data Structure

Elimina un nodo in una lista collegata in C++

Questo articolo discuterà il metodo di implementazione di una funzione che elimina un determinato nodo in un elenco collegato C++.

Implementare una funzione per eliminare un determinato nodo in un elenco collegato

In questo articolo, implementiamo da zero un elenco collegato singolarmente senza utilizzare i contenitori di STL. Pertanto, dobbiamo definire alcune funzioni necessarie per gestire i nodi in una lista concatenata.

L’elemento insertNode è la funzione principale che deve essere invocata per creare una nuova lista collegata. Poiché è necessario memorizzare l’inizio della lista, l’insertNode restituisce il puntatore al nodo di tipo ListNode. Quest’ultima è la rappresentazione minima del nodo della lista concatenata. Contiene solo un puntatore al nodo successivo e l’oggetto dati string.

Durante il test e la dimostrazione del programma, è importante disporre di alcune funzioni di utilità per visualizzare alcuni messaggi sulla console dell’utente. In questo caso, l’elemento printNodes viene utilizzato per stampare tutti i nodi nella struttura della lista data. Inoltre, è necessario deallocare ogni nodo esistente nella lista all’uscita dal programma utilizzando la funzione freeNodes durante l’allocazione di nuovi nodi sulla memoria dinamica.

Una volta costruita una lista con i dati arbitrari come mostrato nella funzione main del seguente frammento di codice, siamo pronti per invocare deleteNode, che implementa l’operazione di rimozione del nodo. La rimozione di un nodo richiede la gestione di diversi casi angolari al suo interno. Vale a dire, lo scenario in cui il dato nodo è lo stesso della testa della lista e l’altro quando il dato nodo è l’unico nodo nella lista.

In quest’ultimo scenario, possiamo semplicemente chiamare l’operatore delete sul puntatore del nodo e tornare dalla funzione. Anche se è importante assegnare nullptr all’indirizzo perché questo ci aiuterà ad aggiungere nuovi elementi alla stessa variabile head nella funzione principale.

D’altra parte, rimuovere il nodo head quando ci sono altri nodi nella lista è relativamente complicato. Dobbiamo copiare il contenuto del secondo nodo nel nodo head ed eliminare il primo. Notare che ogni caso restituisce il valore EXIT_SUCCESS per indicare una chiamata di funzione riuscita.

#include <iostream>
#include <string>

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

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

struct ListNode *insertNode(struct ListNode *root, string data) {
  auto new_node = new ListNode;
  if (root) {
    while (root->next) root = root->next;

    new_node->next = nullptr;
    new_node->data = std::move(data);
    root->next = new_node;

    return root->next;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

int deleteNode(struct ListNode *root, struct ListNode *node) {
  if (node == nullptr || root == nullptr) return EXIT_FAILURE;

  if (root == node) {
    if (root->next == nullptr) {
      delete node;
      root = nullptr;
      return EXIT_SUCCESS;
    }

    node = root->next;
    root->data = root->next->data;
    root->next = root->next->next;
    delete node;
    return EXIT_SUCCESS;
  }

  auto prev = root;
  while (prev->next != node && prev->next != nullptr) {
    prev = prev->next;
  }

  prev->next = node->next;
  delete node;
  return EXIT_SUCCESS;
}

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

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

int main() {
  struct ListNode *head = nullptr;

  head = insertNode(head, "Xenial");

  insertNode(head, "Artful");
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  deleteNode(head, head);
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

Produzione:

node 0 - data : Xenial node 1 -
                data
    : Artful-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
      data : Artful

Il codice della funzione rimanente implementa il caso normale, in cui il nodo dato viene scollegato dalla catena di elenchi e quindi deallocato utilizzando l’operatore delete. Si noti, tuttavia, che questa operazione richiede che venga trovato il nodo precedente, che è l’operazione di tempo lineare per ogni nodo tranne che dall’inizio della lista. Solitamente, si dovrebbe memorizzare la fine della lista nella struttura della lista collegata per garantire la rimozione del tempo costante per la fine della lista.

Il seguente frammento di codice mostra un diverso scenario di funzione main, in cui un nodo viene rimosso dal centro della lista.

#include <iostream>
#include <string>

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

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

struct ListNode *insertNode(struct ListNode *root, string data) {
  auto new_node = new ListNode;
  if (root) {
    while (root->next) root = root->next;

    new_node->next = nullptr;
    new_node->data = std::move(data);
    root->next = new_node;

    return root->next;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

int deleteNode(struct ListNode *root, struct ListNode *node) {
  if (node == nullptr || root == nullptr) return EXIT_FAILURE;

  if (root == node) {
    if (root->next == nullptr) {
      delete node;
      root = nullptr;
      return EXIT_SUCCESS;
    }

    node = root->next;
    root->data = root->next->data;
    root->next = root->next->next;
    delete node;
    return EXIT_SUCCESS;
  }

  auto prev = root;
  while (prev->next != node && prev->next != nullptr) {
    prev = prev->next;
  }

  prev->next = node->next;
  delete node;
  return EXIT_SUCCESS;
}

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

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

int main() {
  struct ListNode *head = nullptr;

  head = insertNode(head, "Xenial");

  auto iter = insertNode(head, "Bionic");
  insertNode(head, "Artful");
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  deleteNode(head, iter);
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

Produzione:

node 0 - data : Xenial node 1 - data : Bionic node 2 -
                                       data
    : Artful-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
      data : Xenial node 1 - data : Artful

Autore: 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

Implementare una funzione per eliminare un determinato nodo in un elenco collegato

Articolo correlato - C++ Data Structure