Dopo aver creato una classe nodo e una classe lista collegata, vediamo ora le operazioni di inserimento e cancellazione eseguite su una lista collegata singolarmente.
Operazione di inserimento su una lista collegata singolarmente
Un’operazione di inserimento inserirà un nodo nella lista. Ci possono essere tre casi per l’operazione di inserimento.
- Inserire un nuovo nodo prima della testa (all’inizio della lista).
- Inserire un nuovo nodo dopo la coda (cioè alla fine della lista).
- Inserimento di un nuovo nodo nel mezzo della lista (in una data posizione casuale).
Inserimento di un nodo all’inizio della lista collegata singolarmente.
In questo caso, un nuovo nodo viene aggiunto prima del nodo di testa corrente. Per compiere questa operazione creeremo prima un nodo. Il nodo appena creato avrà due proprietà come definito nella funzione costruttore della classe Node, data e 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;}
Inserimento di un nodo alla fine della lista single linked.
In questo caso, viene aggiunto un nuovo nodo alla fine della lista. Per implementare questa operazione dovremo attraversare la lista per trovare il nodo di coda e modificare il prossimo puntatore della coda per puntare al nodo appena creato invece di null.
Inzialmente, la lista è vuota e il head punta a 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;}
Inserimento di un nodo in una data posizione casuale in una lista linkata singolarmente
Per implementare questa operazione dovremo attraversare la lista fino a raggiungere il nodo di posizione desiderato. Poi assegneremo il prossimo puntatore di newNode al nodo successivo al nodo di posizione. Il prossimo puntatore del nodo di posizione può quindi essere aggiornato per puntare al 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
}