Nas linguagens de alto nível como JavaScript, que geralmente não se preocupam com a forma como os objetos são armazenados na memória, deixamos a VM lidar com isso para gente e, já que a linguagem contém arrays, a maioria dos usuários nunca encontra uma necessidade de listas vinculadas, mesmo que seja uma estrutura de dados muito poderosa e útil.

Eu, como a maioria dos desenvolvedores front-end, não tenho diploma em Ciência da Computação e comecei a programar usando linguagens de alto nível. Demorei um tempo para me deparar com as listas vinculadas, por isso é que vou explicar os casos de uso básicos, prós/contras dessa estrutura de dados simples e por que ela é amplamente utilizada. – Você provavelmente usou antes, sem saber.

Este artigo foi motivado por este tweet:

Listas vinculadas não são indexadas

A principal diferença para um array é que as listas vinculadas não são indexadas.

A lista vinculada não tem uma referência para todos os itens que armazena. Geralmente, só cont[em referências para seu head (primeiro elemento) e/ou tail (último elemento). Cada item da lista vinculada é responsável por armazenar uma referência para o elemento seguinte e/ou anterior da lista.

Não ter índices é a principal vantagem e desvantagem das listas vinculadas.

Elas não suportam acesso arbitrário

A busca e iteração em uma lista vinculada são geralmente sequenciais.

Em um array, você pode pegar o quarto item pelo seu índice, como myArray[3]. Como as listas vinculadas não contêm índices (ou referências a todos os itens), você precisa obter uma referência para a head ou tail da lista e iterar sobre os itens da mesma como myLinkedList.head.next.next.next.

Como você pode ver, as listas vinculadas não são recomendadas quando você precisa ter acesso arbitrário aos elementos; nesse caso, arrays ou Dictionaries/Hashes (bons e velhos objetos JavaScript) são mais adequados.

Adicionar/remover itens é normalmente mais rápido

Adicionar e remover itens de uma lista não-indexada geralmente é mais rápido, pois não é necessário reconstruir o índice sempre que os itens mudarem. Só é preciso atualizar as referências para os elementos next e/ou previous.

Busca/iteração pode ser mais lenta/ineficiente

A falta de índice e a estrutura simples podem ser uma desvantagem, já que você não pode pular para uma determinada posição na lista. Algumas operações exigirão iteração na maioria dos nós da lista ou todos os elementos dela. Sempre existem prós e contras.

A listas vinculadas geralmente não contêm métodos auxiliares, como os métodos ES5 Array (maps, reduce, some, forEach) que podem dificultar um pouco as coisas na hora de gerenciar (você pode implementá-los por si mesmo).

Linguagens de baixo nível

As listas vinculadas são muito comuns em linguagens de baixo nível , já que você geralmente precisa definir previamente quantos bytes devem ser alocados para cada objeto (retornando um pointer para esse local na memória e verificando que ele não vai colidir com outros pointers). As listas vinculadas não armazenam uma referência para todos os itens que podem expandir indefinidamente sem causar overlap de memória, e os itens não precisam ser armazenados sequencialmente na memória ou têm o mesmo tamanho – é uma estrutura de dados muito flexível e muito comum por causa disso.

Implementação básica

Implementação bem simples de uma lista vinculada no JavaScript:

// items of the list
var bird = {name:'Mockingbird'};
var cat = {name:'Keyboard'};
var dog = {name:'Fort'};
var duck = {name:'Scrooge'};

// the linked-list itself
var animals = {
    head : bird
};
// each item of the list stores reference to the next one
bird.next = cat;
cat.next = dog;
dog.next = duck;

Para iterar todos os itens na lista, você pode simplesmente fazer:

var animal = animals.head;
while (animal) {
    console.log(animal.name);
    animal = animal.next;
}

DOM é uma lista vinculada

O DOM é uma lista vinculada. Você utiliza node.nextSibling, node.parentNode, Node.firstChild etc. para iterar os elementos. As listas vinculadas são muito boas para esse caso de uso, uma vez que a gente adiciona/remove itens e reorganiza os nós muitas vezes durante o ciclo de vida do aplicativo. Isso também simplifica muito o percurso. As listas de navegação por índice podem ser muito ineficientes; node.previousSibling é mais simples que nodesList [nodesList.indexOf (node) – 1].

Lista vinculada dupla/múltipla/circular

As listas vinculadas podem ter referências a outros elementos além do elemento next. Isso é útil, em especial, quando você precisa iterar uma lista reversível ou acelerar algumas iterações/manipulações complexas.

Uma lista vinculada dupla é uma lista na qual os nós também contêm referências para os elementos anteriores.

// doubly-linked
cat.prev = bird;
dog.prev = cat;
// storing the tail (last item) is also useful in some cases
animals.tail = dog;

Em uma lista vinculada múltipla, cada nó contém referência a dois ou mais nós. As listas Circular têm o ponto tail.next para a lista head e são menos comuns.

Em rocambole, eu uso uma lista vinculada dupla para os tokens (referências prev e next). Nos nós, eu uso uma lista vinculada múltipla (as referências a parent, startToken, endToken, next e prev), que simplifica muito a manipulação AST e permite a criação de métodos auxiliares semelhantes a jQuery com muita facilidade.

As referências cruzadas são extremamente úteis. Não deixe que a falta e índice seja uma limitação. Use e abuse dela quando for necessário!

Removendo/adicionando itens

Outra grande vantagem das listas vinculadas é que se você adiciona/remove itens durante a iteração, elas geralmente não causam efeitos colaterais indesejáveis. Imagine este cenário:

var animals = [bird, cat, dog, duck];
for(var i = 0, n = animals.length; i < n; i++) {
    // OOPS! TypeError!
    // length changed during iteration, animals[3] doesn't exist anymore.
    var animal = animals[i];
    console.log(animal.name);
    if (animal.name === 'Fort') {
        animals.splice(i, 1);
    }
}

Se você tivesse usado uma lista vinculada (ou não tivesse armazenado em cache o valor animals.length), esse problema não existiria. A remoção de itens de uma lista vinculada não quebra a iteração:

var animal = animals.head;
while (animal) {
    console.log(animal.name);
    if (animal.name === 'Fort') {
        removeItem(animals, animal);
    }
    animal = animal.next;
}

// to remove an item we just need to remove all references to it
function removeItem(list, item){
    // assuming that list is doubly-linked
    if (list.head === item) list.head = item.next;
    if (list.tail === item) list.tail = item.prev;
    if (item.prev) item.prev.next = item.next;
    item.next = item.prev = null;
    // on a singly-linked list the process is more expensive since you need to
    // loop over the items to find out where to remove
}

Resumindo

Espero que tenha sido claro o suficiente e que você tenha encontrado um bom uso para isso. Acho muito importante aprender sobre estruturas de dados e outros assuntos de ciência da computação. Nunca se sabe quando esse tipo de conhecimento pode ser útil, e muita gente inteligente já pensou nesses problemas antes. É bom ter opções!

A Wikipedia tem uma explicação detalhada sobre as vantagens/desvantagens, caso esteja interessado em obter todos os detalhes (não é para leigos).

Você também pode criar uma implementação genérica que funcione para vários casos, mas que está fora do escopo deste artigo. Tentei mantê-lo o mais simples possível, apenas para explicar o conceito, e não uma implementação específica – uma rápida pesquisa no Google fornece muitos resultados. Eu tenho uma implementação antiga em meus arquivos pessoais, mas, para ser honesto, não a utilizo em meus projetos, e hoje eu a construiria de uma maneira diferente – torne-a uma lista vinculada dupla, retire os helpers de iteração e simplifique a estrutura (não há necessidade de um objeto wrapper para cada nó, prev e next são muito pouco prováveis de causar colisões). Talvez um dia eu a atualize e a lance como um projeto separado…

É isso aí!

***

Artigo traduzido pela Redação iMasters com autorização do autor. Publicado originalmente em http://blog.millermedeiros.com/linked-lists/