Adicione um nó em uma lista vinculada em C ++

Uma lista vinculada é uma estrutura de dados que armazena uma coleção de nós, onde cada nó armazena um valor de dados e um ponteiro para o próximo nó na lista. Ao contrário das matrizes, as listas vinculadas podem crescer e encolher dinamicamente, facilitando o trabalho com dados que estão mudando constantemente. A inserção da lista vinculada é o processo de adicionar um novo nó a uma lista vinculada.

Em C ++, podemos inserir um novo nó em uma lista vinculada de três maneiras:

1. No início da lista vinculada
2. No final da lista vinculada
3. Depois de um determinado nó na lista vinculada

Vamos falar sobre como fazer cada um dos métodos de inserção de lista vinculados um por um.

No início da lista vinculada

Para adicionar qualquer nó no início da lista vinculada, precisamos seguir estas etapas:

1. Crie um novo nó.
2. O endereço do cabeçalho da lista vinculada é dada ao novo ponteiro do nó para que possa começar a apontar para o nó do cabeçalho que já existe.
3. Atribua o novo endereço do nó ao cabeçalho.

Em seguida, seria nulo se este newNode for o primeiro nó na lista vinculada.

No final da lista vinculada

Para adicionar qualquer nó no final da lista vinculada, temos que seguir estas etapas:

1. Crie um novo nó.
2. Atravesse a lista vinculada até chegarmos ao final da lista vinculada.
3. Atribua o nó recém -criado do endereço do ponteiro da lista vinculado ao último nó do endereço do ponteiro da lista vinculada, para que possa começar a apontar para o nó recém -criado.
4. No final, adicione um ponteiro nulo ao nó recém -criado da lista vinculada, pois agora é o último nó.

Depois de um determinado nó na lista vinculada

Para adicionar qualquer nó na enésima posição da lista vinculada, precisamos seguir estas etapas:

1. Crie um novo nó.
2. Verifique se a posição desejada pelo usuário para o novo nó é válida; Ou seja, se a posição do novo nó é maior que ou menor que o tamanho da lista vinculado.
3. Atravesse a lista vinculada para a enésima posição da lista vinculada.
4. Atribua o enésimo próximo ponteiro para o recém -criado Próximo Ponteiro.
5. Atribua o novo endereço do nó ao enésimo próximo ponteiro para que ele possa começar a apontar para o novo nó.

Programa C ++ Impleemenação para a inserção do nó na lista vinculada:

// Programa completo para inserção em uma lista vinculada em C++
#incluir
usando namespace std;
Nó da classe

público:
int dados;
Nó *a seguir;
;
void insertatbeginningLinkedList (nó ** headNode, int dados)
// Crie dinamicamente a memória para este newNode
Nó* newNode = new Node ();
newNode-> dados = dados;
newNode-> próximo = *headNode;
*headNode = newNode;
cout << newNode->dados << " inserted data successfully"
"Na lista vinculada" << endl;

void insertatLastLinkedList (nó ** headNode, int data)
Nó* newNode = new Node ();
newNode-> dados = dados;
// Último nó sempre aponta para nulo
newNode-> próximo = null;
// se a lista vinculada estivesse vazia
if (*headNode == null)
*headNode = newNode;
cout << newNode->dados << " inserted data successfully"
"Na lista vinculada" << endl;
retornar;

Nó * tempnode = * headNode;
// alcance para o último nó da lista vinculada
enquanto (tempnode-> próximo!= Nulo)
tempnode = tempnode-> próximo;
// atribui newNode ao próximo nó
tempnode-> next = newNode;
cout << newNode->dados tamanho ++;

tamanho de retorno;

Void InsertAfternThNodelinkedList
(int n, int dados, nó ** headNode)

int loc = n;
int size = comprimentoflinkedlist (*headNode);
// Nenhuma inserção de posição negativa permitida
// A inserção não é possível se o local for maior
// do que o tamanho da lista vinculada.
se (n < 0 || n > tamanho)
cout << "Insert position not valid";
if (n == 0)
insertatbeginningLinkedList (HeadNode, Data);

outro
Nó* newNode = new Node ();
newNode-> dados = dados;
newNode-> próximo = null;
// usou tempnode para iterar através da lista vinculada
Nó * tempnode = * headNode;
// atravessar até chegar ao enésimo nó
enquanto (-n)
tempnode = tempnode-> próximo;
// Para o NO NO NOD.
newNode-> próximo = tempnode-> próximo;
// atribui o nó do nó ao lado deste novo nó
tempnode-> next = newNode;
// newNode inserido
cout << newNode->dados << " inserted data after index " <

void printlinkedlist (nó* nó)
cout << "\n";
// enquanto a condição vai parar quando nó == null
while (nó!= Null)
cout << node->dados << " "; node = node->próximo;

cout << "\n" << endl;

int main ()

Nó* headNode = null;
insertatbeginningLinkedList (& headnode, 10);
insertatbeginningLinkedList (& headnode, 9);
insertatbeginningLinkedList (& headnode, 8);
PrintLinkedList (HeadNode);
insertatLastLinkedList (& headnode, 11);
insertatLastLinkedList (& headnode, 12);
insertatLastLinkedList (& headnode, 14);
PrintLinkedList (HeadNode);
// insere dados na posição específica
insertafternthnodelinkedlist (5, 17, & headnode);
insertafternthnodelinkedlist (1, 11 e headnode);
PrintLinkedList (HeadNode);
retornar 0;

Saída:

10 dados inseridos com sucesso na lista vinculada
9 Dados inseridos com sucesso na lista vinculada
8 Dados inseridos com sucesso na lista vinculada
8 9 10
11 dados inseridos no final
12 dados inseridos no final
14 dados inseridos no final
8 9 10 11 12 14
17 dados inseridos após o índice 5
11 dados inseridos após o índice 1
8 11 9 10 11 12 17 14

Explicação:

O código define uma classe chamada nó que possui duas propriedades: (1) dados (do tipo int) para armazenar o valor do nó e (2) o próximo (do nó do tipo*) para armazenar o ponteiro para o próximo nó na lista.

O programa implementa três funções para inserir os nós na lista vinculada:

• insertatbeginningLinkedList: Insira um nó no início da lista vinculada.
• InsertatLastLinkedList: Insira um nó no final da lista vinculada.
• InsertAfternThNodelinkedList: Insere um nó após o nó nono da lista vinculada.

Dados inteiros e um ponteiro duplo para o nó da lista da lista vinculado são passados ​​para a função insertatBeginningLinkedList (). Usando o novo node (), a memória de um novo nó é criada dinamicamente e os dados são atribuídos ao novo nó. Mais tarde, ele atualiza o nó da cabeça para que seja o novo nó, definindo o próximo ponteiro do novo nó para o nó da cabeça anterior.

Dados inteiros e um ponteiro duplo para o nó da lista da lista vinculado são passados ​​para o método InsertatLastLinkedList (). Usando o novo node (), a memória de um novo nó é criada dinamicamente e os dados são atribuídos ao novo nó. O próximo ponteiro do novo nó é então definido como nulo. Se a lista vinculada estiver vazia, o nó da cabeça será atualizado para servir como o novo nó. Em qualquer outro caso, ele atravessa a lista vinculada até atingir o último nó, momento em que define o novo nó para o próximo ponteiro do último nó.

A função insertAfternThNodelinkedList () adiciona um novo nó com os dados fornecidos após o nó nono em uma lista vinculada. A lista vinculada e seu tamanho, bem como a posição n e os dados a serem inseridos, são passados ​​como argumentos. Primeiro, a função verifica se o local n estiver correto (i.e., não é negativo e não é maior que o tamanho da lista vinculada). As mensagens de erro são impressas se a posição for inválida. Se a posição for válida, a função constrói um novo nó, define seus dados e os próximos campos e, em seguida, pesquisa iterativamente na lista vinculada para encontrar o enésimo nó. Em seguida, ele vincula o enésimo nó e o novo nó, alterando os próximos ponteiros do enésimo nó e o novo nó.

O comprimento da lista vinculado é retornado pela função LengthOfLinkedList () que aceita um ponteiro para o nó da lista da lista vinculada. Isso é realizado em loop em torno da lista vinculada, contando os nós e retornando a contagem.

No método principal, o programa cria uma lista vinculada vazia e chama todos os três métodos de inserção com vários dados e entradas de posição. Finalmente, ele imprime a lista vinculada para ver os resultados.

Conclusão

Dependendo de onde uma inserção é transformada em uma lista vinculada, existem vários problemas de complexidade temporal e espacial. Como uma operação extremamente eficaz, a inserção no início da lista tem uma complexidade de tempo constante de O (1) e uma complexidade espacial constante de O (1). No pior cenário, a inserção no final da lista leva o tempo linear o (n), onde n é o número total de entradas da lista. Isso é para que possamos descobrir o nó da cauda atravessando a lista. Na pior das hipóteses, a inserção em uma posição específica na lista também leva tempo linear, que é o (n), porque temos que passar pela lista para encontrar o nó na posição específica. Não importa como eles sejam adicionados, as listas vinculadas são uma maneira flexível e dinâmica de armazenar os dados que podem ser usados ​​de várias maneiras diferentes.