Então, me fale sobre as listas vinculadas
Tendo me formado recentemente em um bootcamp de codificação, estudei profundamente em estruturas de dados e algoritmos para melhorar meu conhecimento fundamental. Listas vinculadas são uma estrutura de dados relativamente simples, mas são a base para estruturas de dados mais complexas no futuro. Este artigo discutirá listas vinculadas - seus pontos fortes e fracos e como implementá-los.
As estruturas de dados são, simplesmente, maneiras de organizar e manter os dados de forma eficiente
O que são estruturas de dados?
As estruturas de dados são, simplesmente, maneiras de organizar e manter os dados com eficiência. Isso nos permite reter informações para que possamos acessá-las para mais tarde - procurando por um item específico, ou classificando-os para ter uma determinada ordem ou mesmo gerenciando grandes conjuntos de dados. JavaScript tem estruturas de dados com as quais você provavelmente está familiarizado - arrays e objetos. Essas são estruturas de dados primitivas que são nativas da linguagem. Estruturas de dados não primitivas são estruturas de dados definidas pelo programador. Os exemplos incluem pilhas, filas, árvores, gráficos e tabelas hash.
O que são listas vinculadas?
Uma lista vinculada é uma estrutura de dados linear que contém elementos em ordem sequencial. Soa familiar? Eles são semelhantes aos arrays, mas não são exatamente iguais. As matrizes são indexadas por zero , o que significa que cada índice é mapeado para um valor, e o primeiro elemento da matriz começa em um índice de 0. Você pode extrair facilmente os elementos da matriz, desde que conheça o índice.
Por outro lado, uma lista vinculada consiste em nós que apontam para outros nós. Cada nó conhece apenas a si mesmo e o próximo nó. Como uma estrutura de dados linear, os itens são organizados em ordem. Você pode pensar nisso como um trem - cada vagão é conectado ao próximo vagão e assim por diante. Listas vinculadas não são indexadas , portanto, você não pode acessar o quinto elemento diretamente. Você teria que começar do início, ir para o próximo e ir para o próximo até encontrar o 5º elemento. O primeiro nó é denominado cabeça e o último nó é denominado cauda. Existem vários tipos de listas vinculadas - lista vinculada individualmente, lista vinculada duplamente e lista vinculada circular. Para o propósito deste artigo, vou me concentrar na lista vinculada individualmente.
Acessar elementos em todo o array é mais fácil, mas tem um custo.
Por que usar listas vinculadas em vez de matrizes?
Você pode estar se perguntando - mas por que usar isso se posso acessar elementos diretamente com arrays? Isso é verdade! Acessar elementos em todo o array é mais fácil, mas tem um custo.
Os arrays são indexados - portanto, sempre que você precisar remover um elemento do início ou do meio, todos os índices a seguir precisam ser alterados. Isso também é verdadeiro se você precisar inserir um elemento - todos os elementos a seguir precisam ser reindexados. Ao inserir ou remover elementos de uma lista vinculada, você não precisa reindexar - tudo o que importa é o nó para o qual aponta .
Implementando uma lista vinculada individualmente
Existem vários tipos de listas vinculadas - individual, dupla e circular. Listas unidas individualmente são um tipo de lista vinculada em que cada nó possui um valor e um ponteiro para o próximo nó (nulo se for o nó final). Listas duplamente vinculadas, por outro lado, têm um ponteiro adicional para o nó anterior. Listas circulares vinculadas são onde o nó final aponta para o nó principal.
Nota: Se você é um aprendiz visual, VisuAlgo é um ótimo lugar para brincar e ver a estrutura de dados passar por mudanças.
Se você quiser pular para o código completo: confira esta essência do GitHub .
Criando um Nó
Vamos começar construindo um nó para usar. Ele terá um valor e um próximo ponteiro, que indicará seu vizinho subsequente.
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
Começaremos construindo uma classe chamada SinglyLinkedList e forneceremos uma base para o início, o fim e o comprimento da lista.
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
Para adicionar um nó ao final, vamos verificar se já existe uma cabeça declarada na lista. Caso contrário, defina a cabeça e a cauda como o nó recém-criado. Se já houver uma propriedade principal, defina a próxima propriedade na cauda para o novo nó, e a propriedade final como o novo nó. Vamos aumentar o comprimento em 1.
push(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
this.tail = newNode
}
this.length++;
return this;
}
Para remover um nó no final, devemos primeiro verificar se há nós na lista. Se houver nós, temos que percorrer a lista até chegar ao final. Definiremos a próxima propriedade do penúltimo nó como nula, definiremos a propriedade tail para esse nó, diminuiremos o comprimento em 1 e retornaremos o valor do nó removido.
pop() {
if (!this.head) return undefined;
var current = this.head
var newTail = current
while (current.next) {
newTail = current
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}
Para remover o nó do início, verificamos se há nós na lista. Armazenaremos a propriedade do cabeçalho atual em uma variável e definiremos o cabeçalho como o próximo nó do cabeçalho atual. Diminua o comprimento em 1 e retorne o valor do nó removido.
shift() {
if (!this.head) return undefined
var oldHead = this.head;
this.head = oldHead.next;
this.length--
if (this.length===0) {
this.head = null;
this.tail = null;
}
return oldHead
}
Para adicionar um nó ao início, primeiro criamos o nó e verificamos se há uma propriedade head na lista. Nesse caso, defina a próxima propriedade do nó recém-criado para o cabeçote atual, defina o cabeçote para o novo nó e aumente o comprimento.
unshift(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++
return this
}
Para acessar um nó com base em sua posição na lista, primeiro verificaremos se o índice é válido. Depois, vamos percorrer a lista, mantendo uma variável de contador. Assim que a variável do contador corresponder ao índice, retornaremos o nó encontrado
get(idx) {
if (idx < 0 || idx >= this.length) return null
var counter = 0;
var current = this.head
while (counter !== idx) {
current = current.next;
counter++;
}
return current;
}
Para alterar um nó com base em sua posição, primeiro encontramos o nó, usando o método get e definimos o valor para o novo valor.
set(idx, val) {
var foundNode = this.get(idx)
if (foundNode) {
foundNode.val = val
return true;
}
return false;
}
Para inserir um nó, primeiro verificamos o índice. Se for igual a 0, usamos nosso método unshift. Se for igual ao comprimento, nós o colocamos na lista. Caso contrário, obteremos o nó before usando o método get a menos que o índice. Essencialmente, precisamos acompanhar o nó antes e depois do índice selecionado para garantir que nossos ponteiros sejam direcionados para o nó correto.
insert(idx, val) {
if (idx < 0 || idx > this.length) return false;
if (idx === 0) {
this.unshift(val)
return true;
};
if (idx === this.length) {
this.push(val);
return true;
};
var newNode = new Node(val);
var beforeNode = this.get(idx-1);
var afterNode = beforeNode.next;
beforeNode.next = newNode;
newNode.next = afterNode;
this.length++;
return true;
}
Para remover um nó com base na posição, usaremos nosso método get novamente e usaremos o mesmo princípio que usamos para inserir um nó. Mantendo o controle do nó anterior ao índice escolhido, podemos manobrar nossos ponteiros.
remove(idx) {
if (idx < 0 || idx > this.length) return undefined;
if (idx === this.length-1) {
this.pop()
}
if (idx === 0) {
this.shift()
}
var prevNode = this.get(idx-1)
var removeNode = prevNode.next
prevNode.next = removeNode.next
this.length--;
return removeNode;
}
Pontos fortes das listas vinculadas
A vantagem de usar uma lista vinculada é a capacidade de inserir e remover elementos rapidamente. Como as listas vinculadas não são indexadas, inserir elementos é relativamente rápido e fácil.
Adicionar ao final da lista vinculada simplesmente requer que a cauda antiga aponte para o novo nó e a propriedade da cauda seja configurada para o novo nó. Adicionar ao início da lista vinculada é a mesma premissa, mas o novo nó aponta para o cabeçalho antigo e a propriedade head é definida para o novo nó. Fundamentalmente mesmas ações, então a inserção é O (1).
Nota: Inserir no meio de uma lista vinculada requer pesquisar para encontrar seu nó (O (N)) e depois inserir o nó (O (1)).
Remover um nó da lista vinculada pode ser fácil ... mas também não. Isso depende de onde. Remover um nó do início da lista é simples - o segundo nó se torna o novo cabeçalho e definimos o próximo ponteiro do cabeçalho antigo como nulo. Remover do final é mais complicado porque requer examinar toda a lista e parar no penúltimo nó. Pior caso O (N) e melhor caso O (1).
Fraquezas das listas vinculadas
Os pontos fracos de uma lista vinculada são causados por sua falta de reindexação. Como você não pode acessar os elementos diretamente, torna a busca e o acesso aos elementos mais difícil.
Pesquisar e acessar um nó em uma lista vinculada requer começar no início da lista e seguir a trilha de migalhas de pão na lista. Se estivermos procurando pelo nó no final da lista, teremos que percorrer toda a lista encadeada, tornando efetivamente a complexidade do tempo O (N). Conforme a lista cresce, o número de operações também cresce. Comparado a uma matriz que possui acesso aleatório - leva um tempo constante para acessar um elemento.
É isso aí!
Listas vinculadas são ótimas alternativas para matrizes quando a inserção e exclusão no início são ações-chave. As matrizes são indexadas, enquanto as listas vinculadas não. Listas vinculadas também são a estrutura de dados fundamental a partir da qual as pilhas e filas são construídas, que discutirei em um artigo posterior. Se você chegou até aqui, parabéns para você e espero que tenha aprendido um pouco com sua jornada de programação!
