Linked List ou em português Lista Interligada é uma estrutura de dados linear. Cada elemento(Node ou em português Nó) da lista contém dois elementos - os dados e a referência para o próximo nó. Um dos maiores potenciais da Lista Interligada é que o seu tamanho pode variar, ao contrário de um Array.
A referência é simplesmente o endereço físico de onde encontra-se armazenado o próximo nó na RAM.
Existem 4 tipos de Listas Interligadas, que são:
- Singly Linked List: Neste tipo de Lista Interligada, cada nó armazena os dados e a referência para o próximo nó.
- Circular Singly Linked List: Neste, a única diferença é que o último nó da lista aponta sempre para o primeiro como referência.
- Doubly Linked List: Neste, cada nó contém três elementos, a referência do nó anterior, os dados, e a referência do próximo nó da lista.
- Circular Doubly Linked List: Em relação ao tipo anterior, neste, a única diferença é que o último nó da lista aponta sempre para o primeiro como referência.
Propriedades da Lista Interligada:
Node(Nó): Contém dados e referência para o próximo nó.
Head: Contém referência do primeiro nó da lista.
Tail: Contém referência do último nó da lista.
Length: Número exacto de nós na lista.
Neste artigo, veremos a implementação de uma Singly Linked List.
Na ilustração acima, podemos ver que cada nó tem uma referência. Em uma Lista Interligada Simples, o último nó da fila tem a referência à null pois o mesmo não aponta para nenhum outro nó.
Criação de um Nó
class Node {
constructor(value) {
this.value = value;
this.next = next;
}
}
Um nó é nada mais do que um objecto com duas propriedades, value que armzenaráqualquer tipo de dados que queiramos, e next que armazenará a referência para o próximo nó. Para isto, criamos um nó usando uma class em Javascript.
Criando a Lista
class ListaInterligada {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
A recém lista criada, contém as três propriedas acima listadas.
Vamos agora criar a função responsável por adicionar novos Nós à lista.
class ListaInterligada {
// código anterior ocultado aqui
add(value) {
let node = new Node(value); // instanciamos um novo Nó
let currentNode = this.head;
// Caso a lista esteja vazia
// adicionaremos o novo Nó no topo dela
if (!currentNode) {
this.head = node;
this.tail = node;
this.length++;
return node;
} else {
// Caso a lista contenha elementos
// adicionaremos o novo Nó no final da mesma
while (currentNode.next) {
currentNode = currentNode.next
}
currentNode.next = node;
this.tail = node;
this.length++;
return node;
}
}
}
Instanciando a Lista Interligada e adicionando Nós à mesma
let lista = new ListaInterligada();
lista.add(5);
lista.add(9);
lista.add(15);
console.log(lista)
/*
{
"head": {
"value": 5,
"next": {
"value": 9,
"next": {
"value": 15,
"next": null
}
}
},
"tail": {
"value": 15,
"next": null
},
"length": 3
}
*/
Ao imprimirmos a lista no console, podemos ver que ela contém três Nós e todos eles estão ligados entre si.
Estamos quase la, e se agora quiséssemos remover um dos Nós da lista?
Pois então, isto é completamente possível.
Removendo Nós da Lista
class ListaInterligada {
// códigos anteriores ocultados aqui
remove(location) {
if (location === 0) {
// caso queiramos remover o primeiro elemento
this.head = this.head.next;
this.length--;
if (this.length === 0) {
// e caso não haja mais elementos na lista
this.tail = null;
}
}
// caso o indice seja maior que o número de elementos na lista
// removeremos o último elemento da mesma
else if (location >= this.length) {
let currentNode = this.head;
for (let i = 0; i < this.length - 1; i++) {
currentNode = currentNode.next; // currentNode sera o penúltimo elemento da lista
}
// caso este seja o último elemento da lista
if (currentNode === this.head) {
this.tail = this.head = null;
this.length--;
return;
} else {
currentNode.next = null;
this.tail = currentNode;
this.length--;
}
} else {
// caso queiramos remover um Nó que não seja o último nem o primeiro
let currentNode = this.head;
for (let i = 0; i < location - 1; i++) {
// atravessamos a lista até encontrarmos o elemento a ser removido
currentNode = currentNode.next;
}
currentNode.next = currentNode.next.next; // removemos o elemento desejado
this.tail = currentNode;
this.length--;
}
}
}
Note que ao removermos nós da lista, estamos simplesmente a cortar o ligação que eles têm entre si, em seguida, o Garbage Collector(em português Coletor de Lixo) fará uma limpeza e então apagará da RAM os nós que não tenham nenhuma ligação.
Iterando a Lista
class ListaInterligada {
// códigos anteriores ocultados aqui
traverse() {
let currentNode = this.head;
for (let i = 0; i < this.length; i++) {
console.log(currentNode.value);
currentNode = currentNode.next;
}
}
}
No código acima, iteramos na lista e para cada nó presente na mesma, imprimimos o seu valor. Note que a propriedade this.length corresponde ao número de nós que a lista contém!
A mesma lógica aplicada no código acima, pode ser utilizada para implementar uma função para procurar nós específicos na lista.
Top comments (0)