Aggiungi un nodo in un elenco collegato in C ++

Un elenco collegato è una struttura di dati che memorizza una raccolta di nodi, in cui ciascun nodo memorizza un valore di dati e un puntatore al nodo successivo nell'elenco. A differenza degli array, gli elenchi collegati possono crescere e ridursi in modo dinamico, rendendo più facile lavorare con i dati che cambiano costantemente. L'inserimento dell'elenco collegato è il processo di aggiunta di un nuovo nodo a un elenco collegato.

In C ++, possiamo inserire un nuovo nodo in un elenco collegato in tre modi:

1. All'inizio dell'elenco collegato
2. Alla fine dell'elenco collegato
3. Dopo un determinato nodo nell'elenco collegato

Parliamo di come eseguire ciascuno dei metodi di inserimento dell'elenco collegato uno per uno.

All'inizio dell'elenco collegato

Per aggiungere qualsiasi nodo all'inizio dell'elenco collegato, dobbiamo seguire questi passaggi:

1. Crea un nuovo nodo.
2. L'indirizzo di intestazione dell'elenco collegato viene dato al nuovo puntatore del nodo in modo che possa iniziare a puntare sul nodo di intestazione che esiste già.
3. Assegna il nuovo indirizzo nodo all'intestazione.

Il prossimo sarebbe null se questo newnode è il primo nodo nell'elenco collegato.

Alla fine dell'elenco collegato

Per aggiungere qualsiasi nodo alla fine dell'elenco collegato, dobbiamo seguire questi passaggi:

1. Crea un nuovo nodo.
2. Attraversare l'elenco collegato fino a raggiungere la fine dell'elenco collegato.
3. Assegna il nodo appena creato dell'indirizzo puntatore dell'elenco collegato all'ultimo nodo dell'indirizzo puntatore dell'elenco collegato in modo che possa iniziare a puntare sul nodo appena creato.
4. Alla fine, aggiungi un puntatore nullo al nodo appena creato dell'elenco collegato poiché ora è l'ultimo nodo.

Dopo un determinato nodo nell'elenco collegato

Per aggiungere qualsiasi nodo nella posizione nth dell'elenco collegato, dobbiamo seguire questi passaggi:

1. Crea un nuovo nodo.
2. Controllare se la posizione desiderata dell'utente per il nuovo nodo è valida; Cioè, se la posizione del nuovo nodo è maggiore o inferiore alla dimensione dell'elenco collegato.
3. Attraversare l'elenco collegato all'ennesima posizione dell'elenco collegato.
4. Assegna l'ennesimo puntatore successivo al puntatore successivo appena creato.
5. Assegna il nuovo indirizzo nodo all'ennesimo puntatore successivo in modo che possa iniziare a puntare sul nuovo nodo.

Implementazione del programma C ++ per l'inserimento del nodo nell'elenco collegato:

// Completa il programma per l'inserimento in un elenco collegato in C++
#includere
Utilizzo dello spazio dei nomi std;
nodo di classe

pubblico:
Int Data;
Nodo *Next;
;
void insertatbeginningLinkedList (nodo ** headnode, int data)
// Crea dinamicamente la memoria per questo newnode
Nodo* newNode = new node ();
newnode-> data = data;
newnode-> next = *headnode;
*headnode = newnode;
cout << newNode->dati << " inserted data successfully"
"Nell'elenco collegato" << endl;

void insertatLastLinkedList (nodo ** headnode, int data)
Nodo* newNode = new node ();
newnode-> data = data;
// L'ultimo nodo punta sempre a null
newnode-> next = null;
// Se l'elenco collegato era vuoto
if (*headnode == null)
*headnode = newnode;
cout << newNode->dati << " inserted data successfully"
"Nell'elenco collegato" << endl;
ritorno;

Nodo * tempNode = * headnode;
// Raggiungi l'ultimo nodo dell'elenco collegato
while (tempnode-> next!= Null)
tempNode = tempNode-> Next;
// Assegna Newnode al prossimo nodo dell'ultimo nodo
tempnode-> next = newnode;
cout << newNode->dati dimensione ++;

dimensione di ritorno;

void insertafternthnodelinkedlist
(Int N, Int Data, Node ** HeadNode)

int loc = n;
int size = longOfLinkedList (*headnode);
// non consentiti inserti di posizione negativi
// L'inserimento non è possibile se la posizione è maggiore
// della dimensione dell'elenco collegato.
Se (n < 0 || n > misurare)
cout << "Insert position not valid";
if (n == 0)
insertatBeginningLinkedList (headnode, dati);

altro
Nodo* newNode = new node ();
newnode-> data = data;
newnode-> next = null;
// ha usato tempnode per iterare attraverso l'elenco collegato
Nodo * tempNode = * headnode;
// attraversa fino a raggiungere l'ennesimo nodo
while (-n)
tempNode = tempNode-> Next;
// Al prossimo nodo dell'ennesimo nodo, assegna il newnode.
newnode-> next = tempNode-> Next;
// Assegna il nth nodo accanto a questo nuovo nodo
tempnode-> next = newnode;
// newnode inserita
cout << newNode->dati << " inserted data after index " <

void printLinkedList (nodo* nodo)
cout << "\n";
// mentre la condizione si fermerà quando nodo == null
mentre (nodo!= Null)
cout << node->dati << " "; node = node->Prossimo;

cout << "\n" << endl;

int main ()

Nodo* headnode = null;
insertatBeginningLinkedList (& HeadNode, 10);
insertatBeginningLinkedList (& HeadNode, 9);
insertatBeginningLinkedList (& HeadNode, 8);
PrintLinkEdList (HeadNode);
insertatLastLinkedList (& HeadNode, 11);
insertatLastLinkedList (& HeadNode, 12);
insertatLastLinkedList (& HeadNode, 14);
PrintLinkEdList (HeadNode);
// inserisce i dati nella posizione particolare
insertaFternThnodelinkEdList (5, 17 e HeadNode);
insertafternthnodelinkEdList (1, 11 e headnode);
PrintLinkEdList (HeadNode);
restituzione 0;

Produzione:

10 Dati inseriti Elenco collegato correttamente
9 Dati inseriti Elenco collegato correttamente
8 Dati inseriti Elenco collegato correttamente
8 9 10
11 dati inseriti alla fine
12 dati inseriti alla fine
14 dati inseriti alla fine
8 9 10 11 12 14
17 dati inseriti dopo l'indice 5
11 dati inseriti dopo l'indice 1
8 11 9 10 11 12 17 14

Spiegazione:

Il codice definisce una classe denominata nodo che ha due proprietà: (1) dati (di tipo int) per archiviare il valore del nodo e (2) successivo (del nodo di tipo*) per archiviare il puntatore al nodo successivo nell'elenco.

Il programma implementa tre funzioni per inserire i nodi nell'elenco collegato:

• insertotbeginninglinklist: Inserisce un nodo all'inizio dell'elenco collegato.
• InsertLastLinkedlist: Inserisce un nodo alla fine dell'elenco collegato.
• insertafternthnodelinklist: Inserisce un nodo dopo l'ennesimo nodo dell'elenco collegato.

Un dati interi e un doppio puntatore al nodo della testa dell'elenco collegato vengono passati alla funzione insertBeginningLinkedList (). Utilizzando il nuovo nodo (), la memoria di un nuovo nodo viene creata dinamicamente e i dati vengono quindi assegnati al nuovo nodo. Successivamente, aggiorna il nodo principale in modo che sia il nuovo nodo impostando il puntatore successivo del nuovo nodo sul nodo principale precedente.

Un dati intero e un doppio puntatore al nodo della testa dell'elenco collegato vengono passati al metodo InserTLastLinkedList (). Utilizzando il nuovo nodo (), la memoria di un nuovo nodo viene creata dinamicamente e i dati vengono quindi assegnati al nuovo nodo. Il prossimo puntatore del nuovo nodo è quindi impostato su NULL. Se l'elenco collegato è vuoto, il nodo principale viene aggiornato per fungere da nuovo nodo. In ogni altro caso, attraversa l'elenco collegato fino a quando non raggiunge l'ultimo nodo, quando imposta il nuovo nodo sul puntatore successivo dell'ultimo nodo.

La funzione INSERTAFterTHNODELINKEDLIST () aggiunge un nuovo nodo con i dati dati dopo il nodo NTH in un elenco collegato. L'elenco collegato e le sue dimensioni, nonché la posizione N e i dati da inserire, vengono passati come argomenti. Innanzitutto, la funzione verifica se la posizione n è corretta (i.e., non negativo e non più grande della dimensione dell'elenco collegato). I messaggi di errore vengono stampati se la posizione non è valida. Se la posizione è valida, la funzione costruisce un nuovo nodo, imposta i suoi dati e i campi successivi, quindi cerca iterativamente attraverso l'elenco collegato per trovare il nodo nth. Quindi, collega il nodo n. E il nuovo nodo modificando i suggerimenti successivi del nodo n.

La lunghezza dell'elenco collegato viene restituita dalla funzione LongOfLinkedList () che accetta un puntatore al nodo della testa dell'elenco collegato. Ciò si ottiene looping attorno all'elenco collegato, contando i nodi e restituendo il conteggio.

Nel metodo principale, il programma crea un elenco collegato vuoto, quindi chiama tutti e tre i metodi di inserimento con vari dati di dati e posizione. Infine, stampa l'elenco collegato per vedere i risultati.

Conclusione

A seconda di dove viene trasformato un inserimento in un elenco collegato, ci sono vari problemi di complessità temporale e spaziale. Come un'operazione estremamente efficace, l'inserimento all'inizio dell'elenco ha una costante complessità temporale di O (1) e una costante complessità spaziale di O (1). Nel peggiore scenario, l'inserimento alla fine dell'elenco richiede tempo lineare O (n), dove n è il numero totale di voci dell'elenco. Questo è così che possiamo scoprire il nodo di coda attraversando l'elenco. Nel peggiore dei casi, l'inserimento in una posizione specifica nell'elenco richiede anche tempo lineare, che è O (n), perché dobbiamo passare attraverso l'elenco per trovare il nodo nella posizione specifica. Non importa come vengono aggiunti, gli elenchi collegati sono un modo flessibile e dinamico per archiviare i dati che possono essere utilizzati in molti modi diversi.