Então, me fale sobre as listas vinculadas

Sep 21 2020
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.

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.

Removendo o nó final, nó 77.

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.

Adicione o nó 61 ao início da lista.

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.

Inserindo o nó 60 na posição 3 da lista.

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!

Referências

Estruturas de dados em JavaScript O que é uma lista vinculada, afinal? [Parte 1]