Después de crear una clase nodo y una clase lista enlazada, vamos a ver las operaciones de inserción y borrado que se realizan en una lista enlazada individualmente.
Operación de inserción en una lista enlazada individualmente
Una operación de inserción insertará un nodo en la lista. Puede haber tres casos para la operación de inserción.
- Insertar un nuevo nodo antes de la cabeza (al principio de la lista).
- Insertar un nuevo nodo después de la cola (es decir, al final de la lista).
- Inserción de un nuevo nodo en la mitad de la lista (en una posición aleatoria determinada).
Inserción de un nodo al principio de la lista unicatenaria.
En este caso, se añade un nuevo nodo antes del nodo cabeza actual. Para cumplir esta operación primero crearemos un nodo. El nodo recién creado tendrá dos propiedades definidas en la función constructora de la clase Node, data y 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;}
Insertar un nodo al final de la lista uni-enlazada.
En este caso, se añade un nuevo nodo al final de la lista. Para implementar esta operación tendremos que recorrer la lista para encontrar el nodo de cola y modificar el puntero next de la cola para que apunte al nodo recién creado en lugar de null.
Inicialmente, la lista está vacía y el head apunta 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;}
Insertar un nodo en una posición aleatoria dada en una lista enlazada individualmente
Para implementar esta operación tendremos que recorrer la lista hasta llegar al nodo de posición deseada. Entonces asignaremos el puntero next del newNode al nodo siguiente al nodo de posición. El siguiente puntero del nodo de posición puede entonces actualizarse para que apunte 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
}