Depois de criar uma classe de nó e uma classe de lista ligada, vamos agora olhar para as operações de inserção e eliminação executadas numa lista ligada individualmente.
Inserir operação numa lista ligada individualmente
Uma operação de inserção irá inserir um nó na lista. Pode haver três casos para a operação de inserção.
- Inserir um novo nó antes da cabeça (no início da lista).
- Inserir um novo nó após a cauda (isto é, no fim da lista).
- Inserindo um novo nó no meio da lista (numa dada posição aleatória).
Inserindo um nó no início da lista ligada individualmente.
Neste caso, um novo nó é adicionado antes do nó da cabeça actual. Para realizar esta operação, vamos primeiro criar um nó. O nó recém-criado terá duas propriedades definidas na função construtora da classe Nó, dados e seguinte.
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;}
Inserindo um nó no fim da lista ligada individualmente.
Neste caso, é acrescentado um novo nó no fim da lista. Para implementar esta operação teremos de atravessar a lista para encontrar o nó de cauda e modificar o próximo ponteiro da cauda para apontar para o nó recentemente criado em vez de null.
Inicialmente, a lista está vazia e o head aponta para nulo.
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;}
Inserindo um nó em determinada posição aleatória numa lista ligada individualmente
Para implementar esta operação teremos de atravessar a lista até atingirmos o nó de posição desejado. Atribuiremos então o próximo ponteiro do novo nó ao próximo nó ao nó de posição. O próximo ponteiro do nó de posição pode então ser actualizado para apontar para o novoNó.
// 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
}