Insira um nó em uma lista vinculada simples C++
- Implementar uma função para inserir um nó no final de uma lista vinculada
- Implementar uma função para inserir um nó após um determinado nó em uma lista vinculada
- Implementar uma função para inserir um nó no início de uma lista vinculada
Este artigo explica o método de como inserir um novo nó em uma lista vinculada individualmente em C++.
Implementar uma função para inserir um nó no final de uma lista vinculada
Listas vinculadas são estruturas de dados lineares que consistem em nós apontando uns para os outros, sequencialmente. Neste artigo, estamos nos concentrando mais em uma estrutura de lista vinculada individualmente e implementamos várias operações de inserção de forma correspondente.
Em uma lista unida individualmente, temos um (s) objeto (s) de dados e um ponteiro para o próximo nó na lista. Definimos uma estrutura de nó chamada ListNode e duas funções auxiliares (freeNodes e printNodes) para demonstrar melhor as operações de inserção de lista. Observe que a complexidade do tempo de operação de inserção varia com base na posição em que estamos inserindo um nó. Por exemplo, a inserção no final da lista leva tempo linear se o final da lista for desconhecido.
Por outro lado, inserir um novo nó no início sempre leva um tempo constante. O código a seguir demonstra a função insertNodeEnd, que pode ser tratada como a função principal para construir uma lista. Ele pega o topo da lista como o primeiro parâmetro e os dados string que precisam ser armazenados em um novo nó. A função pode criar o primeiro elemento da lista e acrescentar novos elementos no final dela. A função aloca novos nós na memória de armazenamento livre. Assim, a função freeNodes é necessária para liberar toda a memória antes da saída do programa.
#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;
}
Resultado:
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
Implementar uma função para inserir um nó após um determinado nó em uma lista vinculada
Inserir um nó no meio da lista geralmente leva um tempo constante mais a complexidade do tempo do algoritmo de pesquisa usado para encontrar a posição dada. Embora, assumamos que a função de pesquisa é implementada separadamente e construímos a função insertNodeAfter para que a posição do nó de destino precise ser fornecida como o primeiro argumento.
Como a função insertNodeEnd retorna o ponteiro para um nó recém-anexado, utilizamos seu valor de retorno para demonstrar a operação de insertNodeAfter. Lembre-se de que você precisaria de uma função de pesquisa separada para inserções de posições arbitrárias e até mesmo de uma estrutura de dados externa para implementar uma operação de pesquisa mais rápida em uma lista vinculada.
#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;
}
Resultado:
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
Implementar uma função para inserir um nó no início de uma lista vinculada
Outra operação de inserção útil para a lista vinculada individualmente é anexar um novo nó no início. Esta função tem o melhor tempo de execução O(1) uma vez que o cabeçalho da lista é sempre armazenado para acessar a própria lista. A função insertNodeFront leva a referência a um ponteiro raiz e ao objeto string que precisa ser armazenado no nó. O processo é implementado para que você possa usá-lo para inicializar uma nova lista vinculada, bem como a inserção frontal.
Alternativamente, você pode reescrever a função para alocar um novo nó quando o argumento root não for nullptr. Caso contrário, retorne nullptr para indicar que a função falhou. A interface dessas funções depende das necessidades dos programadores e da estrutura do 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;
}
Resultado:
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 FacebookArtigo relacionado - C++ Data Structure
- Estrutura de pilha de dados usando lista vinculada em C++
- Excluir um nó da árvore binária de busca em C++
- Implementar Inorder Traversal para árvore binária de busca em C++
- Implementar Matriz Circular em C++
- Implementar uma estrutura de dados de fila usando lista vinculada em C++
- Inserção de árvore binária de busca em C++