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 sob as quais uma lista encadeada é 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 funcionarão melhor sob circunstâncias específicas.

Edit: Devo dizer, estou muito impressionado com não só o número, mas a qualidade das respostas. Eu só posso aceitar um, mas há dois ou três mais que eu teria a dizer que valeria a pena aceitar se algo um pouco melhor não estivesse lá. Apenas um casal (especialmente o que acabei aceitando) apontou para situações em que uma linked list oferecia uma vantagem real. Eu acho que Steve Jessop merece algum tipo de menção honrosa por não ter apenas uma, mas três respostas diferentes, todas as quais eu achei bastante impressionantes. É claro que, apesar de ter sido postado apenas como comentário, e não uma resposta, acho que vale a pena ler também a input do blog de Neil – não apenas informativa, mas bastante divertida também.

Eles podem ser úteis para estruturas de dados concorrentes. (Existe agora uma amostra de uso do mundo real não concorrente abaixo – isso não estaria disponível se @Neil não tivesse mencionado o FORTRAN. 😉

Por exemplo, ConcurrentDictionary no .NET 4.0 RC usa listas vinculadas para encadear itens que possuem o mesmo bloco.

A estrutura de dados subjacente para ConcurrentStack também é uma linked list.

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

O novo Pool de segmentos, por sua vez, fornece a base para o agendamento de trabalho da nova Biblioteca paralela de tarefas .

Então, eles certamente podem ser úteis – uma lista encadeada está servindo atualmente como uma das principais estruturas de suporte de pelo menos uma grande nova tecnologia.

(Uma lista unida faz uma escolha sem bloqueio – mas não isenta de espera – nestes casos, porque as operações principais podem ser realizadas com um único CAS (+ tentativas). Em um ambiente GC-d moderno – como Java e .NET – o problema ABA pode ser facilmente evitado, basta include os itens adicionados nos nós recém-criados e não reutilizar esses nós – deixe o GC fazer o seu trabalho.A página do problema ABA também fornece a implementação de um bloqueio. pilha livre – que realmente funciona em .Net (& Java) com um nó (GC-ed) segurando os itens.

Edit : @ Neil: na verdade, o que você mencionou sobre FORTRAN me lembrou que o mesmo tipo de listas ligadas pode ser encontrado em provavelmente a estrutura de dados mais usada e abusada no .NET: o Dictionary .NET genérico simples Dictionary .

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

  • Evita fazer muitas pequenas (de) alocações em inserções / exclusões.
  • O carregamento inicial da tabela de hash é muito rápido, porque a matriz é preenchida sequencialmente (reproduz muito bem com o cache da CPU).
  • Sem mencionar que uma tabela hash de encadeamento é cara em termos de memory – e esse “truque” corta “tamanhos de ponteiro” pela metade em x64.

Essencialmente, muitas listas vinculadas são armazenadas em uma matriz. (uma para cada checkbox usada.) Uma lista livre de nós reutilizáveis ​​é “entrelaçada” entre eles (se houver exclusões). Uma matriz é alocada no início / no rehash e os nós das cadeias são mantidos nela. Há também um ponteiro livre – um índice na matriz – que segue exclusões. 😉 Então – acredite ou não – a técnica FORTRAN ainda continua viva. (… e em nenhum outro lugar, do que 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 tamanho arbitrário (desconhecido em tempo de compilation).

Dividir e ingressar em listas (bidirecionais) é muito eficiente.

Você também pode combinar listas vinculadas – por exemplo, estruturas de tree podem ser implementadas como listas vinculadas “verticais” (relações pai / filho) conectando listas horizontais vinculadas (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 no final, envolve (possivelmente realocar e) copiar muitos dos dados em uma posição

As listas vinculadas são muito flexíveis: com a modificação de um ponteiro, você pode fazer uma grande alteração, em que a mesma operação seria muito ineficiente em uma lista de matriz.

Matrizes 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 lista, enquanto as matrizes têm melhor desempenho do que as listas de access direto a elementos.

Aqui está uma lista de operações que podem ser realizadas em listas e arrays, comparadas com o custo de operação relativo (n = list / array length):

  • Adicionando um elemento:
    • nas listas você só precisa alocar memory para o novo elemento e redirect pointers. O (1)
    • nos arrays você tem que realocar o array. Em)
  • Removendo um elemento
    • nas listas você apenas redireciona os pointers. 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 da matriz ou diminuir o comprimento da matriz
  • Obtendo um elemento em uma posição conhecida:
    • nas listas, você precisa percorrer a lista do primeiro elemento até o elemento na posição específica. Pior caso: O (n)
    • em arrays você pode acessar o elemento imediatamente. O (1)

Essa é 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 melhor desempenho em situações em que você precisa fazer muitas modificações na própria lista (removendo ou adicionando elementos). Por outro lado, as matrizes funcionam melhor que as listas quando você precisa acessar diretamente os elementos da matriz.

Do ponto de vista da alocação de memory, 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 (pouca) sobrecarga de armazenar os pointers para o próximo elemento (ou até mesmo para o anterior).

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

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

Lista unicamente vinculada é uma boa escolha para a lista livre em um alocador de células ou em um pool de objects:

  1. Você só precisa de uma pilha, então uma lista unida é suficiente.
  2. Tudo é dividido em nós já. 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, já que quando você cria o heap pela primeira vez, todas as células são gratuitas, então é um custo inicial. No pior dos casos, duplica o requisito de memory por célula.

A lista de links duplos é uma boa escolha para definir a ordem de um hashmap que também define uma ordem nos elementos (LinkedHashMap em Java), especialmente quando ordenada pelo último access:

  1. Mais sobrecarga de memory do que um vetor associado ou deque (2 pointers em vez de 1), mas melhor inserir / remover o desempenho.
  2. Nenhuma sobrecarga de alocação, desde que você precisa de um nó para uma input de hash de qualquer maneira.
  3. Localidade de referência não é nenhum problema adicional comparado com um vetor ou deque de pointers, desde que você teria que puxar cada object na memory de qualquer maneira.

Claro, você pode argumentar sobre se um cache LRU é uma boa ideia, em primeiro lugar, comparado com algo mais sofisticado e sintonizá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 fim em um vetor ou deque em cada access de leitura, mas mover um nó para a cauda normalmente é bom.

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

Listas com link único são a implementação óbvia do tipo de dados “lista” comum em linguagens de programação funcionais:

  1. Adicionando à cabeça é rápido, e (append (list x) (L)) e (append (list y) (L)) pode compartilhar quase todos os seus dados. Não há necessidade de copy-on-write em um idioma sem gravações. Programadores funcionais sabem como aproveitar isso.
  2. Adicionando à cauda é, infelizmente, lento, mas assim seria qualquer outra implementação.

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

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

Por exemplo, ao implementar o rastreamento de memory em C ++ (substituição de novo / excluído), você precisa de alguma estrutura de dados de controle que rastreie quais pointers foram liberados, o que você precisa implementar completamente. A alternativa é colocar em excesso e adicionar uma linked list ao início de cada parte dos dados.

Porque você sempre sabe imediatamente, onde você está na lista quando delete é chamado, você pode facilmente desistir da memory em O (1). Também adicionando um novo pedaço que acaba de ser malloced está em O (1). Andar pela lista raramente é necessário neste caso, portanto o custo O (n) não é um problema aqui (andar de uma estrutura é O (n) de qualquer maneira).

Da minha experiência, implementando matrizes esparsas e pilhas de fibonacci. Listas vinculadas lhe dão mais controle sobre a estrutura geral dessas estruturas de dados. Embora eu não tenha certeza se as matrizes esparsas são melhor implementadas usando listas vinculadas – provavelmente existe uma maneira melhor, mas realmente ajudou a aprender os prós e contras de matrizes esparsas usando listas vinculadas na graduação CS 🙂

Um exemplo de bom uso para uma lista encadeada é onde os elementos da lista são muito grandes, por exemplo. grande o suficiente para que apenas um ou dois possam caber no cache da CPU ao mesmo tempo. Nesse ponto, a vantagem de contêineres de bloco contíguos, como vetores ou matrizes para iteração, é 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.

Considere que uma lista encadeada pode ser muito útil em uma implementação de estilo de Design Dirigido por Domínio de um sistema que inclui partes que se interligam com a repetição.

Um exemplo que vem à mente pode ser se você estivesse modelando uma corrente de suspensão. Se você quisesse saber qual era a tensão em qualquer link em particular, sua interface poderia include um getter para um peso “aparente”. A implementação do que includeia um link pedindo seu próximo link para seu peso aparente, adicionando seu próprio peso ao resultado. Dessa forma, todo o comprimento até o final seria avaliado com uma única chamada do cliente da cadeia.

Sendo um defensor do código que lê como linguagem natural, eu gosto de como isso deixaria o programador perguntar a um elo da cadeia quanto peso ele está carregando. Ele também mantém a preocupação de calcular essas crianças de propriedades dentro do limite da implementação do link, eliminando a necessidade de um serviço de cálculo de peso em cadeia “.

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

Agora, isso pode parecer um oxímoro completo que as listas vinculadas poderiam fazer tudo isso, já que são notórias por fazerem o oposto, mas têm uma propriedade única, pois cada nó da lista tem um tamanho fixo e requisitos de alinhamento que podemos explorar para permitir eles sejam armazenados de forma contígua e removidos em tempo constante de maneiras que coisas de tamanho variável não podem.

Como resultado, vamos considerar um caso em que queremos fazer o equivalente analógico de armazenar uma sequência de comprimento variável que contenha um milhão de subseqüências aninhadas de tamanho variável. Um exemplo concreto é uma malha indexada que armazena um milhão de polígonos (alguns triângulos, alguns quadríceps, alguns pentágonos, alguns hexágonos, etc.) e às vezes polígonos são removidos de qualquer lugar na malha e algumas vezes polígonos são reconstruídos para inserir um vértice em um polígono existente remova um. Nesse caso, se armazenarmos um milhão de std::vectors minúsculos, acabaremos enfrentando uma alocação de heap para cada vetor, bem como o uso de memory potencialmente explosivo. Um milhão de pequenos SmallVectors pode não sofrer tanto este problema em casos comuns, mas o buffer pré-alocado, que não é alocado separadamente por heap, ainda pode causar uso explosivo de memory.

O problema aqui é que um milhão de instâncias std::vector estariam tentando armazenar um milhão de itens de tamanho variável. As coisas de tamanho variável tendem a querer uma alocação de heap, pois não podem ser armazenadas de forma muito contígua e removidas em tempo constante (pelo menos de maneira direta, sem um alocador muito complexo) se não armazenassem seus conteúdos em outro local da pilha.

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 fvs; // Stores all the polygons. std::vector polys; }; 

… então reduzimos drasticamente o número de alocações de heap e falhas de cache. Em vez de exigir uma alocação de heap e possíveis falhas de cache obrigatórias para cada polígono que acessamos, agora só exigimos essa alocação de heap quando um dos dois vetores armazenados na malha inteira excede sua capacidade (um custo amortizado). E enquanto o passo para ir de um vértice para o próximo ainda pode causar sua plot de falhas de cache, ainda é menor do que se cada polígono armazenasse um array dynamic separado já que os nós são armazenados contiguamente e há uma probabilidade de que um vértice vizinho ser acessado antes do despejo (especialmente considerando que muitos polígonos irão adicionar seus vértices de uma só vez, o que torna a parte do leão dos vértices do polígono perfeitamente contígua).

Aqui está outro exemplo:

insira a descrição da imagem aqui

… 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 em cada quadro. Nesse exemplo de grade de partículas, usando listas vinculadas, podemos mover uma partícula de uma célula de grade para outra, apenas alterando 3 índices. Apagando de um vetor e empurrando de volta para outro pode ser consideravelmente mais caro e introduzir mais alocações de heap. As listas vinculadas também reduzem a memory de uma célula até 32 bits. Um vetor, dependendo da implementação, pode pré-alocar seu array dynamic até o ponto em que ele pode levar 32 bytes para um vetor vazio. Se temos cerca de um milhão de células, isso é uma grande diferença.

… e é aqui que encontro as listas vinculadas mais úteis nos dias de hoje, e especificamente acho útil a variedade “linked list indexada”, pois os índices de 32 bits cortam pela metade os requisitos de memory dos links em máquinas de 64 bits e implicam que o nós são armazenados contiguamente em uma matriz.

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

insira a descrição da imagem aqui

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

E esse é o caso de uso número um que encontro nas listas vinculadas nos dias de hoje. Quando queremos armazenar, digamos, um milhão de sub-seqüências de comprimento variável calculando, digamos, 4 elementos cada (mas às vezes com elementos sendo removidos e adicionados a uma dessas sub-sequências), a lista encadeada nos permite armazenar 4 milhões Os nós da lista encadeada contíguo, em vez de 1 milhão de contêineres, que são individualmente alocados 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 anterior ao .NET e até mesmo stl.

Eu provavelmente não usaria uma linked list agora em uma linguagem .NET porque todo o código de percurso que você precisa é fornecido por você através dos methods de extensão Linq.

Existem duas operações complementares que são trivialmente O (1) nas listas e muito difíceis de implementar em O (1) em outras estruturas de dados – removendo e inserindo um elemento da posição arbitrária, assumindo que você precisa manter a ordem dos elementos.

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

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

As inputs no mapa hash precisam ter pointers para os nós da linked list. Ao acessar o mapa de hash, o nó da linked list é desvinculado de sua posição atual e movido para o header da lista (O (1), yay para listas vinculadas!). Quando há necessidade de remover o elemento menos usado recentemente, o da cauda da lista precisa ser removido (novamente O (1) assumindo que você mantenha o ponteiro para o nó final) junto com a input de mapa de hash associada (portanto, backlinks de a lista para o mapa hash é necessária.)