Em que circunstâncias as listas vinculadas são úteis?

Na maioria das vezes vejo pessoas tentando usar listas vinculadas, parece-me uma escolha ruim (ou muito ruim). Talvez seja útil explorar as circunstâncias em que uma lista vinculada é ou não uma boa escolha de estrutura de dados.

Idealmente, as respostas explicariam os critérios a serem usados ​​na seleção de uma estrutura de dados e quais estruturas de dados provavelmente funcionariam melhor em circunstâncias específicas.

Edit: Devo dizer que estou bastante impressionado não apenas com o número, mas também com a qualidade das respostas. Só posso aceitar um, mas há mais dois ou três que eu diria que valeria a pena aceitar se algo um pouco melhor não estivesse lá. Apenas um casal (especialmente aquele que acabei aceitando) apontou para situações em que uma lista vinculada proporcionava uma vantagem real. Eu realmente acho que Steve Jessop merece algum tipo de menção honrosa por apresentar não apenas uma, mas três respostas diferentes, todas as quais eu achei bastante impressionantes. Claro, embora tenha sido postado apenas como um comentário, não como uma resposta, acho que vale a pena ler o post de Neil no blog - não apenas informativo, mas também bastante divertido.

Eles podem ser úteis para estruturas de dados concorrentes. (Agora há um exemplo de uso não simultâneo no mundo real abaixo - que não estaria lá se @Neil não tivesse mencionado FORTRAN. ;-)

Por exemplo, ConcurrentDictionary<TKey, TValue>no .NET 4.0 RC, use listas vinculadas para encadear itens com hash no mesmo balde.

A estrutura de dados subjacente para ConcurrentStack<T>também é uma lista vinculada.

ConcurrentStack<T>é uma das estruturas de dados que servem de base para o novo Thread Pool (com as "filas" locais implementadas como pilhas, essencialmente). (A outra estrutura de suporte principal é ConcurrentQueue<T>.)

O novo Thread Pool, por sua vez, fornece a base para o agendamento de trabalho da nova Task Parallel Library .

Portanto, eles certamente podem ser úteis - uma lista vinculada atualmente está servindo como uma das principais estruturas de suporte de pelo menos uma grande nova tecnologia.

(Uma lista unida de forma única torna uma escolha atraente sem bloqueio - mas não sem espera - nesses casos, porque as operações principais podem ser realizadas com um único CAS (+ novas tentativas). Em um ambiente GC-d moderno - como Java e .NET - o problema ABA pode ser facilmente evitado. Apenas empacote os itens que você adiciona em nós recém-criados e não reutilize esses nós - deixe o GC fazer seu trabalho. A página sobre o problema ABA também fornece a implementação de um bloqueio pilha livre - que realmente funciona em .Net (e Java) com um nó (GC-ed) contendo os itens.)

Edit : @ Neil: na verdade, o que você mencionou sobre FORTRAN me lembrou que o mesmo tipo de listas vinculadas pode ser encontrado provavelmente na estrutura de dados mais usada e abusada do .NET: o .NET genérico simples Dictionary<TKey, TValue>.

Não uma, mas muitas listas vinculadas são armazenadas em uma matriz.

• Ele evita fazer muitas pequenas (des) alocações em inserções / exclusões.
• O carregamento inicial da tabela hash é muito rápido, porque o array é preenchido sequencialmente (funciona muito bem com o cache da CPU).
• Sem mencionar que uma tabela hash de encadeamento é cara em termos de memória - e esse "truque" corta "tamanhos de ponteiro" pela metade no x64.

Basicamente, muitas listas vinculadas são armazenadas em uma matriz. (um para cada depósito usado.) Uma lista livre de nós reutilizáveis ​​é "entrelaçada" entre eles (se houver exclusões). Um array é alocado no início / no rehash e nós de cadeias são mantidos nele. Há também um ponteiro livre - um índice na matriz - que segue as exclusões. ;-) Então - acredite ou não - a técnica FORTRAN ainda vive. (... e em nenhum outro lugar, a não ser em uma das estruturas de dados .NET mais comumente usadas ;-).

Listas vinculadas são muito úteis quando você precisa fazer muitas inserções e remoções, mas não muita pesquisa, em uma lista de comprimento arbitrário (desconhecido em tempo de compilação).

Dividir e unir listas (vinculadas bidirecionalmente) é muito eficiente.

Você também pode combinar listas vinculadas - por exemplo, estruturas em árvore podem ser implementadas como listas vinculadas "verticais" (relações pai / filho) conectando listas vinculadas horizontais (irmãos).

O uso de uma lista baseada em matriz para esses fins tem limitações severas:

• Adicionar um novo item significa que a matriz deve ser realocada (ou você deve alocar mais espaço do que o necessário para permitir o crescimento futuro e reduzir o número de realocações)
• Remover itens deixa espaço desperdiçado ou requer uma realocação
• inserir itens em qualquer lugar exceto o final envolve (possivelmente realocar e) copiar muitos dados uma posição acima

Listas vinculadas são muito flexíveis: com a modificação de um ponteiro, você pode fazer uma mudança massiva, onde a mesma operação seria muito ineficiente em uma lista de array.

Arrays são as estruturas de dados às quais as listas vinculadas são geralmente comparadas.

Normalmente, as listas vinculadas são úteis quando você precisa fazer muitas modificações na própria lista, enquanto os arrays têm um desempenho melhor do que as listas no acesso direto ao elemento.

Aqui está uma lista de operações que podem ser realizadas em listas e matrizes, em comparação com o custo de operação relativo (n = lista / comprimento da matriz):

• Adicionando um elemento:
  • nas listas você só precisa alocar memória para o novo elemento e redirecionar ponteiros. O (1)
  • em matrizes, você deve realocar a matriz. Em)
• Removendo um elemento
  • nas listas, você apenas redireciona os ponteiros. O (1).
  • em matrizes, você gasta O (n) tempo para realocar a matriz se o elemento a ser removido não for o primeiro ou o último elemento da matriz; caso contrário, você pode simplesmente realocar o ponteiro para o início do array ou diminuir o comprimento do array
• Obtendo um elemento em uma posição conhecida:
  • nas listas, você deve percorrer a lista desde o primeiro elemento até o elemento na posição específica. Pior caso: O (n)
  • em arrays, você pode acessar o elemento imediatamente. O (1)

Esta é uma comparação de nível muito baixo dessas duas estruturas de dados populares e básicas e você pode ver que as listas têm um desempenho melhor em situações em que você tem que fazer várias modificações na própria lista (removendo ou adicionando elementos). Por outro lado, os arrays têm um desempenho melhor do que as listas quando você precisa acessar diretamente os elementos do array.

Do ponto de vista da alocação de memória, as listas são melhores porque não há necessidade de ter todos os elementos próximos uns dos outros. Por outro lado, há a (pequena) sobrecarga de armazenar os ponteiros para o próximo (ou mesmo para o anterior) elemento.

Saber essas diferenças é importante para os desenvolvedores escolherem entre listas e matrizes em suas implementações.

Observe que esta é uma comparação de listas e matrizes. Existem boas soluções para os problemas aqui relatados (por exemplo: SkipLists, Dynamic Arrays, etc ...). Nesta resposta, levei em consideração a estrutura de dados básica que todo programador deve conhecer.

A lista vinculada individualmente é uma boa escolha para a lista livre em um alocador de células ou pool de objetos:

1. Você só precisa de uma pilha, portanto, uma lista com links simples é suficiente.
2. Tudo já está dividido em nós. Não há sobrecarga de alocação para um nó de lista intrusivo, desde que as células sejam grandes o suficiente para conter um ponteiro.
3. Um vetor ou deque imporia uma sobrecarga de um ponteiro por bloco. Isso é significativo, pois quando você cria o heap pela primeira vez, todas as células são gratuitas, portanto, é um custo inicial. Na pior das hipóteses, ele dobra o requisito de memória por célula.

A lista duplamente vinculada é uma boa escolha para definir a ordem de um hashmap que também define uma ordem nos elementos (LinkedHashMap em Java), especialmente quando ordenado pelo último acesso:

1. Mais sobrecarga de memória do que um vetor ou deque associado (2 ponteiros em vez de 1), mas melhor desempenho de inserção / remoção.
2. Sem sobrecarga de alocação, já que você precisa de um nó para uma entrada hash de qualquer maneira.
3. A localidade de referência não é um problema adicional em comparação com um vetor ou deque de ponteiros, já que você teria que puxar cada objeto para a memória de qualquer maneira.

Claro, você pode discutir se um cache LRU é uma boa ideia em primeiro lugar, em comparação com algo mais sofisticado e ajustável, mas se você vai ter um, esta é uma implementação bastante decente. Você não deseja executar uma exclusão do meio e adicionar ao final em um vetor ou deque a cada acesso de leitura, mas mover um nó para a cauda normalmente é bom.

Listas vinculadas são uma das escolhas naturais quando você não pode controlar onde seus dados são armazenados, mas você ainda precisa de alguma forma ir de um objeto para o próximo.

Por exemplo, ao implementar o rastreamento de memória em C ++ (nova / exclusão de substituição), você também precisa de alguma estrutura de dados de controle que monitore quais ponteiros foram liberados, que você mesmo precisa implementar por completo. A alternativa é superalocar e adicionar uma lista vinculada ao início de cada bloco de dados.

Como você sempre sabe imediatamente onde está na lista quando o delete é chamado, você pode facilmente abrir mão da memória em O (1). Também adicionando um novo pedaço que acabou de ser malocado está em O (1). Percorrer a lista raramente é necessário neste caso, portanto, o custo de O (n) não é um problema aqui (percorrer uma estrutura é O (n) de qualquer maneira).

Eles são úteis quando você precisa de push, pop e rotação em alta velocidade e não se importa com a indexação O (n).

Listas unidas individualmente são a implementação óbvia do tipo de dados "lista" comum em linguagens de programação funcionais:

1. Adicionar ao cabeçote é rápido (append (list x) (L))e (append (list y) (L))pode compartilhar quase todos os seus dados. Não há necessidade de copiar na gravação em um idioma sem gravações. Os programadores funcionais sabem como tirar vantagem disso.
2. Adicionar à cauda infelizmente é lento, mas o mesmo aconteceria com qualquer outra implementação.

Por comparação, um vetor ou deque normalmente seria lento para adicionar em qualquer uma das extremidades, exigindo (pelo menos no meu exemplo de dois anexos distintos) que uma cópia seja feita de toda a lista (vetor) ou do bloco de índice e do bloco de dados sendo anexado a (deque). Na verdade, pode haver algo a ser dito lá para deque em grandes listas que precisam ser adicionadas no final por algum motivo, não estou suficientemente informado sobre a programação funcional para julgar.

Um exemplo de bom uso para uma lista vinculada é quando os elementos da lista são muito grandes, ou seja. grande o suficiente para que apenas um ou dois possam caber no cache da CPU ao mesmo tempo. Nesse ponto, a vantagem que os contêineres de bloco contíguos, como vetores ou matrizes para iteração, têm é mais ou menos anulada e uma vantagem de desempenho pode ser possível se muitas inserções e remoções estiverem ocorrendo em tempo real.

De minha experiência, implementando matrizes esparsas e pilhas de fibonacci. As listas vinculadas fornecem mais controle sobre a estrutura geral dessas estruturas de dados. Embora eu não tenha certeza se matrizes esparsas são melhor implementadas usando listas vinculadas - provavelmente há uma maneira melhor, mas realmente ajudou a aprender os meandros das matrizes esparsas usando listas vinculadas em cursos de CS :)

Existem duas operações complementares que são trivialmente O (1) em listas e muito difíceis de implementar em O (1) em outras estruturas de dados - remover e inserir um elemento de uma posição arbitrária, supondo que você precise manter a ordem dos elementos.

Os mapas hash podem obviamente fazer inserção e exclusão em O (1), mas você não pode iterar sobre os elementos em ordem.

Dado o fato acima, o hash map pode ser combinado com uma lista vinculada para criar um cache LRU bacana: Um mapa que armazena um número fixo de pares de chave-valor e descarta a chave acessada menos recentemente para abrir espaço para novas.

As entradas no mapa hash precisam ter ponteiros para os nós da lista vinculada. Ao acessar o mapa hash, o nó da lista vinculada é desvinculado de sua posição atual e movido para o topo da lista (O (1), yay para listas vinculadas!). Quando houver necessidade de remover o elemento menos usado recentemente, aquele do final da lista precisa ser eliminado (novamente O (1) assumindo que você mantenha o ponteiro para o nó final) junto com a entrada do mapa hash associado (assim, backlinks de a lista para o mapa de hash são necessários.)

Considere que uma lista vinculada pode ser muito útil em uma implementação do estilo Domain Driven Design de um sistema que inclui partes que se interligam com a repetição.

Um exemplo que vem à mente seria se você fosse modelar uma corrente suspensa. Se você quisesse saber qual era a tensão em qualquer link específico, sua interface poderia incluir um getter para peso "aparente". A implementação do que incluiria um link solicitando seu próximo link por seu peso aparente, então adicionando seu próprio peso ao resultado. Dessa forma, toda a extensão até o fundo seria avaliada com uma única ligação do cliente da rede.

Sendo um proponente de código que lê como linguagem natural, gosto de como isso permitiria ao programador perguntar a um elo de corrente quanto peso ele está carregando. Também mantém a preocupação de calcular esses filhos de propriedades dentro dos limites da implementação do elo, eliminando a necessidade de um serviço de cálculo do peso da corrente ”.

Um dos casos mais úteis que encontro para listas vinculadas que trabalham em campos de desempenho crítico, como processamento de malha e imagem, mecanismos de física e raytracing, é quando o uso de listas vinculadas realmente melhora a localidade de referência e reduz as alocações de heap e às vezes até reduz o uso de memória em comparação com as alternativas diretas.

Isso pode parecer um oxímoro completo que as listas vinculadas podem fazer tudo isso, já que são conhecidas por fazerem frequentemente o contrário, mas têm uma propriedade única em que cada nó da lista tem um tamanho fixo e requisitos de alinhamento que podemos explorar para permitir eles devem ser armazenados contiguamente e removidos em tempo constante de maneiras que coisas de tamanho variável não podem.

Como resultado, vamos pegar um caso em que queremos fazer o equivalente analógico de armazenar uma sequência de comprimento variável que contém um milhão de sub-sequências de comprimento variável aninhadas. Um exemplo concreto é uma malha indexada que armazena um milhão de polígonos (alguns triângulos, alguns quadrantes, alguns pentágonos, alguns hexágonos, etc.) e às vezes polígonos são removidos de qualquer lugar da malha e, às vezes, polígonos são reconstruídos para inserir um vértice em um polígono existente ou remova um. Nesse caso, se armazenarmos um milhão de minúsculos std::vectors, acabaremos enfrentando uma alocação de heap para cada vetor único, bem como um uso de memória potencialmente explosivo. Um milhão de tiny SmallVectorspode não sofrer esse problema tanto em casos comuns, mas seu buffer pré-alocado que não é alocado em heap separadamente pode ainda causar uso de memória explosiva.

O problema aqui é que um milhão de std::vectorinstâncias estariam tentando armazenar um milhão de coisas de comprimento variável. Coisas de comprimento variável tendem a querer uma alocação de heap, uma vez que não podem ser armazenados de forma muito eficaz de forma contígua e removidas em tempo constante (pelo menos de forma direta, sem um alocador muito complexo) se não armazenarem seu conteúdo em outro lugar no heap.

Se, em vez disso, fizermos isso:

struct FaceVertex
{
    // Points to next vertex in polygon or -1
    // if we're at the end of the polygon.
    int next;
    ...
};

struct Polygon
{
     // Points to first vertex in polygon.
    int first_vertex;
    ...
};

struct Mesh
{
    // Stores all the face vertices for all polygons.
    std::vector<FaceVertex> fvs;

    // Stores all the polygons.
    std::vector<Polygon> polys;
};

... reduzimos drasticamente o número de alocações de heap e perdas de cache. Em vez de exigir uma alocação de heap e perdas de cache potencialmente obrigatórias para cada polígono que acessamos, agora exigimos apenas essa alocação de heap quando um dos dois vetores armazenados em toda a malha excede sua capacidade (um custo amortizado). E embora o passo para ir de um vértice ao próximo ainda possa causar sua parcela de perdas de cache, ainda é muitas vezes menor do que se cada polígono armazenasse uma matriz dinâmica separada, uma vez que os nós são armazenados de forma contígua e há uma probabilidade de que um vértice vizinho possa ser acessado antes do despejo (especialmente considerando que muitos polígonos adicionarão seus vértices todos de uma vez, o que torna a maior parte dos vértices poligonais perfeitamente contíguos).

Aqui está outro exemplo:

... onde as células da grade são usadas para acelerar a colisão partícula-partícula para, digamos, 16 milhões de partículas movendo-se a cada quadro. Nesse exemplo de grade de partículas, usando listas vinculadas, podemos mover uma partícula de uma célula da grade para outra apenas alterando 3 índices. Apagar de um vetor e enviar para outro pode ser consideravelmente mais caro e introduzir mais alocações de heap. As listas vinculadas também reduzem a memória de uma célula para 32 bits. Um vetor, dependendo da implementação, pode pré-alocar sua matriz dinâmica ao ponto em que pode levar 32 bytes para um vetor vazio. Se temos cerca de um milhão de células de grade, isso é uma grande diferença.

... e é aqui que considero as listas vinculadas mais úteis atualmente, e especificamente acho a variedade "lista vinculada indexada" útil, pois os índices de 32 bits reduzem pela metade os requisitos de memória dos links em máquinas de 64 bits e implicam que o os nós são armazenados de forma contígua em uma matriz.

Freqüentemente, também os combino com listas livres indexadas para permitir remoções e inserções em tempo constante em qualquer lugar:

Nesse caso, o nextíndice aponta para o próximo índice livre se o nó foi removido ou o próximo índice usado se o nó não foi removido.

E este é o caso de uso número um que encontro para listas vinculadas atualmente. Quando queremos armazenar, digamos, um milhão de subseqüências de comprimento variável com uma média de, digamos, 4 elementos cada (mas às vezes com elementos sendo removidos e adicionados a uma dessas subseqüências), a lista vinculada nos permite armazenar 4 milhões nós da lista encadeada contiguamente em vez de 1 milhão de contêineres, cada um individualmente alocado em heap: um vetor gigante, ou seja, não um milhão de pequenos.

Eu usei listas vinculadas (mesmo listas duplamente vinculadas) no passado em um aplicativo C / C ++. Isso foi antes do .NET e até do stl.

Eu provavelmente não usaria uma lista vinculada agora em uma linguagem .NET porque todo o código de passagem de que você precisa é fornecido por meio dos métodos de extensão Linq.