Inserimento di un nodo nella lista a collegamento singolo C++
- Implementare una funzione per inserire un nodo alla fine di un elenco collegato
- Implementare una funzione per inserire un nodo dopo un dato nodo in un elenco collegato
- Implementare una funzione per inserire un nodo all’inizio di un elenco collegato
Questo articolo spiega il metodo di come inserire un nuovo nodo in un elenco con collegamento singolo in C++.
Implementare una funzione per inserire un nodo alla fine di un elenco collegato
Gli elenchi collegati sono strutture di dati lineari che consistono in nodi che puntano l’uno all’altro, in sequenza. In questo articolo, ci concentriamo maggiormente su una struttura di elenco con collegamento singolo e implementiamo di conseguenza più operazioni di inserimento.
In un elenco con collegamento singolo, abbiamo uno o più oggetti dati e un puntatore al nodo successivo nella lista. Abbiamo definito una struttura a nodi denominata ListNode e due funzioni di supporto (freeNodes e printNodes) per dimostrare meglio le operazioni di inserimento delle liste. Si noti che la complessità del tempo dell’operazione di inserimento varia in base alla posizione in cui si sta inserendo un nodo. Ad esempio, l’inserimento alla fine della lista richiede un tempo lineare se la fine della lista è sconosciuta.
D’altra parte, l’inserimento di un nuovo nodo all’inizio richiede sempre un tempo costante. Il codice seguente mostra la funzione insertNodeEnd, che può essere trattata come la funzione principale per costruire un elenco. Prende la testa della lista come primo parametro e i dati string che devono essere memorizzati in un nuovo nodo. La funzione può creare il primo elemento nella lista e aggiungere nuovi elementi alla fine di esso. La funzione alloca nuovi nodi sulla memoria del negozio libero. Pertanto, la funzione freeNodes è necessaria per liberare tutta la memoria prima dell’uscita dal programma.
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNodeEnd(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;
}
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;
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
head = insertNodeEnd(head, data_set.at(0));
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
insertNodeEnd(head, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
insertNodeEnd(head, "Utopic");
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
Produzione:
node 0 - data : Precise node 1 - data : Quantal node 2 - data : Saucy node 3 -
data
: Raring-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
data : Precise node 1 - data : Quantal node 2 -
data : Saucy node 3 -
data : Raring node 4 - data : Utopic
Implementare una funzione per inserire un nodo dopo un dato nodo in un elenco collegato
L’inserimento di un nodo al centro della lista richiede generalmente un tempo costante più la complessità temporale dell’algoritmo di ricerca utilizzato per trovare la posizione data. Tuttavia, assumiamo che la funzione di ricerca sia implementata separatamente e costruiamo la funzione insertNodeAfter in modo che la posizione del nodo di destinazione debba essere fornita come primo argomento.
Poiché la funzione insertNodeEnd restituisce il puntatore a un nuovo nodo aggiunto, utilizziamo il suo valore restituito per dimostrare l’operazione di insertNodeAfter. Tieni presente che avresti bisogno di una funzione di ricerca separata per inserimenti di posizione arbitrari e potrebbe anche essere necessaria una struttura di dati esterna per implementare un’operazione di ricerca più rapida su un elenco collegato.
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNodeEnd(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;
}
struct ListNode *insertNodeAfter(struct ListNode *prev, string data) {
if (!prev) return nullptr;
auto new_node = new ListNode;
new_node->next = nullptr;
new_node->data = std::move(data);
prev->next = new_node;
return new_node;
}
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;
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
head = insertNodeEnd(head, data_set.at(0));
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
insertNodeEnd(head, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
auto iter = insertNodeEnd(head, "Utopic");
printNodes(head);
cout << " ----------------------------------- " << endl;
insertNodeAfter(iter, "Xenial");
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
Produzione:
node 0 - data : Precise node 1 - data : Quantal node 2 - data : Saucy node 3 -
data
: Raring-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
data : Precise node 1 - data : Quantal node 2 - data : Saucy node 3 -
data
: Raring node 4 -
data : Utopic-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
data : Precise node 1 - data : Quantal node 2 -
data
: Saucy node 3 -
data : Raring node 4 - data : Utopic node 5 - data : Xenial
Implementare una funzione per inserire un nodo all’inizio di un elenco collegato
Un’altra operazione di inserimento utile per la lista concatenata singola è aggiungere un nuovo nodo all’inizio. Questa funzione ha il miglior tempo di esecuzione O(1) in quanto la testata della lista viene sempre memorizzata per accedere alla lista stessa. La funzione insertNodeFront prende il riferimento a un puntatore root e all’oggetto string che deve essere memorizzato nel nodo. Il processo è implementato in modo da poterlo utilizzare per inizializzare una nuova lista collegata così come l’inserimento frontale.
In alternativa, puoi riscrivere la funzione per allocare un nuovo nodo quando l’argomento root non è nullptr. In caso contrario, restituire nullptr per indicare che la funzione non è riuscita. L’interfaccia di queste funzioni dipende dalle esigenze dei programmatori e dalla struttura del ListNode.
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNodeEnd(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;
}
struct ListNode *insertNodeFront(struct ListNode *&root, string data) {
auto new_node = new ListNode;
if (root) {
new_node->next = root;
new_node->data = std::move(data);
root = new_node;
return root;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
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;
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
head = insertNodeEnd(head, data_set.at(0));
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
insertNodeEnd(head, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
insertNodeFront(head, "Bionic");
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
Produzione:
node 0 - data : Precise node 1 - data : Quantal node 2 - data : Saucy node 3 -
data
: Raring-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
data : Bionic node 1 - data : Precise node 2 -
data : Quantal node 3 -
data : Saucy node 4 - data : Raring
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