Après avoir créé une classe de nœud et une classe de liste liée, voyons maintenant les opérations d’insertion et de suppression effectuées sur une liste singulièrement liée.
Opération d’insertion sur une liste singulièrement liée
Une opération d’insertion va insérer un nœud dans la liste. Il peut y avoir trois cas pour l’opération d’insertion.
- Insérer un nouveau nœud avant la tête (au début de la liste).
- Insérer un nouveau nœud après la queue (c’est-à-dire à la fin de la liste).
- Insertion d’un nouveau nœud au milieu de la liste (à une position aléatoire donnée).
Insertion d’un nœud au début de la liste singulièrement liée.
Dans ce cas, un nouveau nœud est ajouté avant le nœud de tête actuel. Pour réaliser cette opération, nous allons d’abord créer un nœud. Le nœud nouvellement créé aura deux propriétés telles que définies dans la fonction constructeur de la classe Node, data et next.
LinkedList.prototype.insertAtBeginning = function(data){// A newNode object is created with property data and next = null let newNode = new Node(data);// The pointer next is assigned head pointer so that both pointers now point at the same node. newNode.next = this.head;// As we are inserting at the beginning the head pointer needs to now point at the newNode.
this.head = newNode; return this.head;}
Insérer un nœud à la fin de la liste singulièrement liée.
Dans ce cas, un nouveau nœud est ajouté à la fin de la liste. Pour mettre en œuvre cette opération, nous devrons parcourir la liste pour trouver le nœud de queue et modifier le pointeur suivant de la queue pour qu’il pointe vers le nœud nouvellement créé au lieu de null.
Initialement, la liste est vide et le head pointe vers null.
LinkedList.prototype.insertAtEnd = function(data){// A newNode object is created with property data and next=null
let newNode = new Node(data);// When head = null i.e. the list is empty, then head itself will point to the newNode. if(!this.head){
this.head = newNode;
return this.head;
}// Else, traverse the list to find the tail (the tail node will initially be pointing at null), and update the tail's next pointer. let tail = this.head;
while(tail.next !== null){
tail = tail.next;
}
tail.next = newNode; return this.head;}
.
Insérer un nœud à une position aléatoire donnée dans une liste singulièrement liée
Pour mettre en œuvre cette opération, nous devrons parcourir la liste jusqu’à atteindre le nœud de la position souhaitée. Nous affecterons ensuite le pointeur suivant du newNode au nœud suivant du nœud de position. Le pointeur suivant du nœud de position peut alors être mis à jour pour pointer vers le newNode.
// A helper function getAt() is defined to get to the desired position. This function can also be later used for performing delete operation from a given position. LinkedList.prototype.getAt = function(index){
let counter = 0;
let node = this.head;
while (node) {
if (counter === index) {
return node;
}
counter++;
node = node.next;
}
return null;
}// The insertAt() function contains the steps to insert a node at a given index. LinkedList.prototype.insertAt = function(data, index){// if the list is empty i.e. head = null if (!this.head) {
this.head = new Node(data);
return;
}// if new node needs to be inserted at the front of the list i.e. before the head. if (index === 0) {
this.head = new Node(data, this.head);
return;
}// else, use getAt() to find the previous node. const previous = this.getAt(index - 1);
let newNode = new Node(data);
newNode.next = previous.next;
previous.next = newNode;
return this.head
}
.