Ajouter un nœud dans une liste liée en C ++

Une liste liée est une structure de données qui stocke une collection de nœuds, où chaque nœud stocke une valeur de données et un pointeur vers le nœud suivant de la liste. Contrairement aux tableaux, les listes liées peuvent croître et rétrécir dynamiquement, ce qui facilite le travail avec des données qui changent constamment. L'insertion de la liste liée est le processus d'ajout d'un nouveau nœud à une liste liée.

En C ++, nous pouvons insérer un nouveau nœud dans une liste liée de trois manières:

1. Au début de la liste liée
2. À la fin de la liste liée
3. Après un nœud donné dans la liste liée

Parlons de la façon de faire chacune des méthodes d'insertion de liste liée une par une.

Au début de la liste liée

Pour ajouter n'importe quel nœud au début de la liste liée, nous devons suivre ces étapes:

1. Créer un nouveau nœud.
2. L'adresse d'en-tête de la liste liée est donnée au nouveau pointeur de nœud afin qu'il puisse commencer à pointer du nœud d'en-tête qui existe déjà.
3. Attribuez la nouvelle adresse de nœud à l'en-tête.

Né prochain serait nul si ce newnode est le premier nœud de la liste liée.

À la fin de la liste liée

Pour ajouter n'importe quel nœud à la fin de la liste liée, nous devons suivre ces étapes:

1. Créer un nouveau nœud.
2. Traverser la liste liée jusqu'à ce que nous atteignions la fin de la liste liée.
3. Attribuez le nœud nouvellement créé de l'adresse du pointeur lié à la liste liée au dernier nœud de l'adresse du pointeur de liste liée afin qu'il puisse commencer à pointer vers le nœud nouvellement créé.
4. À la fin, ajoutez un pointeur nul au nœud nouvellement créé de la liste liée car il est maintenant le dernier nœud.

Après un nœud donné dans la liste liée

Pour ajouter n'importe quel nœud en première position de la liste liée, nous devons suivre ces étapes:

1. Créer un nouveau nœud.
2. Vérifiez si la position souhaitée de l'utilisateur pour le nouveau nœud est valide; c'est-à-dire si la position du nouveau nœud est supérieure ou inférieure à la taille de la liste liée.
3. Traverser la liste liée à la nième position de la liste liée.
4. Attribuez le pointeur NEXT NTH au pointeur suivant nouvellement créé.
5. Attribuez la nouvelle adresse de nœud au pointeur du Nième Nième afin qu'il puisse commencer à pointer vers le nouveau nœud.

C ++ Programme Imprélation pour l'insertion de nœud dans la liste liée:

// Programme complet pour l'insertion dans une liste liée en C++
#inclure
Utilisation de Namespace Std;
nœud de classe

public:
données int;
Nœud * suivant;
;
void insertAtBeginningLinkedList (Node ** headnode, int data)
// Créer dynamiquement de la mémoire pour ce newnode
Node * newNode = new node ();
newNode-> data = data;
newNode-> next = * headnode;
* headnode = newNode;
couter << newNode->données << " inserted data successfully"
"dans la liste liée" << endl;

void insertatlastLinkedList (Node ** headnode, int data)
Node * newNode = new node ();
newNode-> data = data;
// Dernier nœud pointe toujours vers null
newNode-> next = null;
// Si la liste liée était vide
if (* headnode == null)
* headnode = newNode;
couter << newNode->données << " inserted data successfully"
"dans la liste liée" << endl;
retour;

Node * tempnode = * headnode;
// atteignez le dernier nœud de la liste liée
tandis que (tempnode-> suivant!= Null)
tempnode = tempnode-> suivant;
// Attribuez le NewNode au prochain nœud du dernier nœud
tempnode-> next = newNode;
couter << newNode->données taille ++;

taille de retour;

vide insertafternthnodelinkedlist
(int n, int, nœud ** headnode)

int loc = n;
int size = longueurofLinkedList (* headnode);
// Aucun insert de position négatif autorisé
// L'insertion n'est pas possible si l'emplacement est plus grand
// que la taille de la liste liée.
si (n < 0 || n > taille)
couter << "Insert position not valid";
if (n == 0)
insertatBinginningLinkedList (headnode, data);

autre
Node * newNode = new node ();
newNode-> data = data;
newNode-> next = null;
// a utilisé Tempnode pour itérer via la liste liée
Node * tempnode = * headnode;
// Traversé jusqu'à ce que vous atteigniez le nœud nième
tandis que (- n)
tempnode = tempnode-> suivant;
// au Nième nœud Suivant, attribuez le prochain à NewNode.
newNode-> next = tempnode-> suivant;
// Attribuez le nœud n / nème à côté de ce nouveau nœud
tempnode-> next = newNode;
// newNode inséré
couter << newNode->données << " inserted data after index " <

void printLinkedList (nœud * nœud)
couter << "\n";
// tandis que la condition s'arrêtera quand nœud == null
while (nœud!= Null)
couter << node->données << " "; node = node->suivant;

couter << "\n" << endl;

int main()

Nœud * headnode = null;
insertatbeginningLinkedList (& headnode, 10);
insertatbeginningLinkedList (& headnode, 9);
insertatbeginningLinkedList (& headnode, 8);
PrintLinkedList (HeadNode);
insertatlastLinkedList (& headnode, 11);
insertatlastLinkedList (& headnode, 12);
insertatlastLinkedList (& headnode, 14);
PrintLinkedList (HeadNode);
// insère des données à la position particulière
INSERTAFTERNTHNODELINKEDLIST (5, 17, & HeadNode);
insertafternHnodeLinkedList (1, 11, & headnode);
PrintLinkedList (HeadNode);
retour 0;

Sortir:

10 Données insérées Liste liée avec succès
9 Données insérées Liste liée avec succès
8 Données insérées Liste liée avec succès
8 9 10
11 données insérées à la fin
12 données insérées à la fin
14 données insérées à la fin
8 9 10 11 12 14
17 données insérées après l'indice 5
11 données insérées après l'indice 1
8 11 9 10 11 12 17 14

Explication:

Le code définit une classe nommée Node qui a deux propriétés: (1) Données (de type int) pour stocker la valeur du nœud, et (2) Suivant (du nœud de type *) pour stocker le pointeur vers le nœud suivant de la liste.

Le programme implémente trois fonctions pour insérer les nœuds dans la liste liée:

• insertatbeginningLinkedlist: Insère un nœud au début de la liste liée.
• insertatlastLinkedlist: Insère un nœud à la fin de la liste liée.
• insertafternthNodeLinkedlist: Insère un nœud après le nœud du nième de la liste liée.

Une donnée entière et un double pointeur vers le nœud de tête de la liste liée sont transmis à la fonction insertatbeginningLinkedList (). En utilisant le nouveau nœud (), la mémoire d'un nouveau nœud est créée dynamiquement, et les données sont ensuite affectées au nouveau nœud. Plus tard, il met à jour le nœud de tête afin qu'il s'agisse du nouveau nœud en définissant le prochain pointeur du nouveau nœud vers le nœud de tête précédent.

Une donnée entière et un double pointeur vers le nœud de tête de la liste liée sont transmis à la méthode insertatlastLinkedList (). En utilisant le nouveau nœud (), la mémoire d'un nouveau nœud est créée dynamiquement, et les données sont ensuite affectées au nouveau nœud. Le prochain pointeur du nouveau nœud est ensuite défini sur null. Si la liste liée est vide, le nœud de tête est mis à jour pour servir de nouveau nœud. Dans tout autre cas, il traverse la liste liée jusqu'à ce qu'elle atteigne le dernier nœud, moment où il définit le nouveau nœud au prochain pointeur du dernier nœud.

La fonction insertafternHnodeLinkEdList () ajoute un nouveau nœud avec les données données après le nœud nième dans une liste liée. La liste liée et sa taille, ainsi que la position n et les données à insérer, sont passées comme arguments. Tout d'abord, la fonction vérifie si l'emplacement n est correct (i.e., pas négatif et pas plus grand que la taille de la liste liée). Les messages d'erreur sont imprimés si la position n'est pas valide. Si la position est valide, la fonction construit un nouveau nœud, définit ses données et ses prochains champs, puis recherche de manière itérative via la liste liée pour trouver le nœud nième. Ensuite, il relie le nième nœud et le nouveau nœud en modifiant les pointeurs suivants du nœud du Nd et du nouveau nœud.

La longueur de la liste liée est renvoyée par la fonction LongueurofLinkedList () qui accepte un pointeur vers le nœud de tête de la liste liée. Ceci est accompli en bouclant autour de la liste liée, en comptant les nœuds et en renvoyant le décompte.

Dans la méthode principale, le programme crée une liste liée vide, puis appelle les trois méthodes d'insertion avec diverses données et entrées de position. Enfin, il imprime la liste liée pour voir les résultats.

Conclusion

Selon l'endroit où une insertion est transformée en une liste liée, il y a divers problèmes de complexité temporelle et spatiale. En tant qu'opération extrêmement efficace, l'insertion au début de la liste a une complexité de temps constante d'O (1) et une complexité d'espace constante d'O (1). Dans le pire scénario, l'insertion à la fin de la liste prend un temps linéaire (n), où n est le nombre total d'entrées de liste. C'est pour que nous puissions découvrir le nœud de queue en traversant la liste. Dans le pire des cas, l'insertion d'une position spécifique dans la liste prend également du temps linéaire, qui est O (n), car nous devons parcourir la liste pour trouver le nœud à la position spécifique. Peu importe comment ils sont ajoutés, les listes liées sont un moyen flexible et dynamique de stocker les données qui peuvent être utilisées de différentes manières.