Uma lista duplamente vinculada tem uma sobrecarga mínima (apenas outro ponteiro por célula) e permite anexar aos dois extremos e ir e voltar e geralmente se diverte muito.

Bem, se você olhar um pouco mais fundo, ambos também incluem matrizes no idioma base:

• O 5º Relatório de Esquema revisado (R5RS) inclui o tipo de vetor , que são coleções indexadas por número inteiro de tamanho fixo com tempo melhor que linear para acesso aleatório.
• O relatório Haskell 98 também possui um tipo de matriz .

As instruções de programação funcional, no entanto, enfatizaram há muito tempo as listas de vínculo único sobre matrizes ou listas de vínculo duplo. Muito provavelmente exagerou, de fato. Existem várias razões para isso, no entanto.

O primeiro é que as listas com link único são um dos tipos de dados recursivos mais simples e mais úteis. Um equivalente definido pelo usuário do tipo de lista de Haskell pode ser definido assim:

data List a           -- A list with element type `a`...
  = Empty             -- is either the empty list...
  | Cell a (List a)   -- or a pair with an `a` and the rest of the list. 

O fato de as listas serem um tipo de dados recursivo significa que as funções que trabalham nas listas geralmente usam recursão estrutural . Em termos de Haskell: você combina os padrões nos construtores da lista e recursa em uma subparte da lista. Nessas duas definições básicas de funções, eu uso a variável aspara referir-se ao final da lista. Portanto, observe que as chamadas recursivas "descem" na lista:

map :: (a -> b) -> List a -> List b
map f Empty = Empty
map f (Cell a as) = Cell (f a) (map f as)

filter :: (a -> Bool) -> List a -> List a
filter p Empty = Empty
filter p (Cell a as)
    | p a = Cell a (filter p as)
    | otherwise = filter p as

Essa técnica garante que sua função seja encerrada para todas as listas finitas e também é uma boa técnica de solução de problemas - ela tende a dividir naturalmente os problemas em subpartes mais simples e sustentáveis.

Portanto, listas com link único são provavelmente o melhor tipo de dados para apresentar aos alunos essas técnicas, que são muito importantes na programação funcional.

O segundo motivo é menos o motivo "por que listas com link único", mas mais o motivo "por que não listas ou matrizes com link duplo": esses últimos tipos de dados geralmente exigem mutação (variáveis ​​modificáveis), cuja programação funcional é muito frequente se afasta. Assim acontece:

• Em um idioma ansioso como o Scheme, você não pode criar uma lista com vínculo duplo sem usar o mutation.
• Em uma linguagem preguiçosa como Haskell, você pode fazer uma lista com vínculo duplo sem usar mutação. Mas sempre que você cria uma nova lista com base nessa lista, você é forçado a copiar a maioria, senão toda a estrutura do original. Enquanto nas listas com link único, você pode escrever funções que usam "compartilhamento de estrutura" - novas listas podem reutilizar as células de listas antigas, quando apropriado.
• Tradicionalmente, se você usava matrizes de maneira imutável, significava que toda vez que desejava modificar a matriz era necessário copiar a coisa toda. (Bibliotecas recentes de Haskell vector, como , no entanto, encontraram técnicas que melhoram bastante esse problema).

O terceiro e último motivo se aplica a idiomas preguiçosos, como Haskell, principalmente: as listas de links simples preguiçosos, na prática, geralmente são mais semelhantes aos iteradores do que as listas na memória apropriadas. Se o seu código estiver consumindo os elementos de uma lista seqüencialmente e jogando-os para fora à medida que você avança, o código do objeto só materializará as células da lista e seu conteúdo à medida que você avança na lista.

Isso significa que a lista inteira não precisa existir na memória de uma só vez, apenas na célula atual. As células anteriores à atual podem ser coletadas como lixo (o que não seria possível com uma lista com link duplo); células posteriores à atual não precisam ser computadas até você chegar lá.

Vai ainda mais longe do que isso. Existe uma técnica usada em várias bibliotecas Haskell populares, chamadas de fusão , onde o compilador analisa seu código de processamento de listas e identifica listas intermediárias que estão sendo geradas e consumidas sequencialmente e depois "jogadas fora". Com esse conhecimento, o compilador pode eliminar completamente a alocação de memória das células dessas listas. Isso significa que uma lista de link único em um programa de origem Haskell, após a compilação, pode realmente ser transformada em um loop em vez de em uma estrutura de dados.

A fusão também é a técnica que a vectorbiblioteca mencionada acima usa para gerar código eficiente para matrizes imutáveis. O mesmo vale para as bibliotecas extremamente populares bytestring(matrizes de bytes) e text(seqüências de caracteres Unicode), que foram criadas como um substituto para o Stringtipo nativo não muito bom de Haskell (que é o mesmo que a [Char]lista de caracteres com link único). Portanto, na moderna Haskell, há uma tendência em que tipos de matrizes imutáveis ​​com suporte a fusão estão se tornando muito comuns.

A fusão de lista é facilitada pelo fato de que em uma lista vinculada única você pode avançar, mas nunca para trás . Isso traz um tema muito importante na programação funcional: usar a "forma" de um tipo de dados para derivar a "forma" de uma computação. Se você deseja processar elementos sequencialmente, uma lista vinculada única é um tipo de dados que, quando você a consome com recursão estrutural, fornece esse padrão de acesso com muita naturalidade. Se você deseja usar uma estratégia de "dividir e conquistar" para atacar um problema, as estruturas de dados em árvore tendem a suportar isso muito bem.

Muitas pessoas abandonam o vagão de programação funcional logo no início, para que sejam expostas às listas de links únicos, mas não às idéias subjacentes mais avançadas.

Porque eles funcionam bem com imutabilidade. Suponha que você tenha duas listas imutáveis, [1, 2, 3]e [10, 2, 3]. Representadas como listas vinculadas individualmente, em que cada item da lista é um nó que contém o item e um ponteiro para o restante da lista, elas se pareceriam com isso:

node -> node -> node -> empty
 1       2       3

node -> node -> node -> empty
 10       2       3

Veja como as [2, 3]porções são idênticas? Com estruturas de dados mutáveis, elas são duas listas diferentes porque o código que grava novos dados em uma delas não afeta o código usando a outra. No entanto, com dados imutáveis , sabemos que o conteúdo das listas nunca muda e o código não pode gravar novos dados. Assim, podemos reutilizar as caudas e fazer com que as duas listas compartilhem parte de sua estrutura:

node -> node -> node -> empty
 1      ^ 2       3
        |
node ---+
 10

Como o código que usa as duas listas nunca as modifica, nunca precisamos nos preocupar com alterações em uma lista que afetem a outra. Isso também significa que, ao adicionar um item à frente da lista, você não precisa copiar e fazer uma lista totalmente nova.

No entanto, se você tentar representar [1, 2, 3]e [10, 2, 3]como listas duplamente vinculadas:

node <-> node <-> node <-> empty
 1       2       3

node <-> node <-> node <-> empty
 10       2       3

Agora as caudas não são mais idênticas. O primeiro [2, 3]tem um ponteiro para 1na cabeça, mas o segundo tem um ponteiro para 10. Além disso, se você deseja adicionar um novo item ao cabeçalho da lista, é necessário alterar o cabeçalho anterior da lista para que ele aponte para o novo cabeçalho.

O problema de várias cabeças pode ser solucionado com a possibilidade de cada nó armazenar uma lista de cabeças conhecidas e a criação de novas listas modificá-las, mas você deve manter essa lista em ciclos de coleta de lixo quando versões da lista com cabeças diferentes têm vida útil diferente devido ao uso em diferentes partes do código. Acrescenta complexidade e sobrecarga, e na maioria das vezes não vale a pena.

A resposta da @ sacundim é quase sempre verdadeira, mas também existem outras informações importantes sobre o trade-off sobre designs de idiomas e requisitos práticos.

Objetos e referências

Essas linguagens geralmente exigem (ou assumem) objetos com extensões dinâmicas não acopladas (ou na linguagem de C, durante a vida útil , embora não sejam exatamente as mesmas devido às diferenças de significado dos objetos entre essas linguagens, veja abaixo) por padrão, evitando referências de primeira classe ( por exemplo, ponteiros de objeto em C) e comportamento imprevisível nas regras semânticas (por exemplo, comportamento indefinido da ISO C relacionado à semântica).

Além disso, a noção de objetos (de primeira classe) nessas linguagens é conservadora e restritiva: nada de propriedades "locativas" são especificadas e garantidas por padrão. Isso é completamente diferente em algumas linguagens semelhantes ao ALGOL, cujos objetos não têm extensões dinâmicas não acopladas (por exemplo, em C e C ++), onde objetos basicamente significam alguns tipos de "armazenamento digitado", geralmente acoplados a locais de memória.

Codificar o armazenamento nos objetos traz alguns benefícios adicionais, como poder anexar efeitos computacionais determinísticos ao longo da vida útil, mas esse é outro tópico.

Problemas de simulação de estruturas de dados

Sem referências de primeira classe, as listas vinculadas individualmente não podem simular muitas estruturas de dados tradicionais (ansiosas / mutáveis) de maneira eficaz e portável, devido à natureza da representação dessas estruturas de dados e às operações primitivas limitadas nesses idiomas. (Pelo contrário, em C, você pode derivar listas vinculadas com bastante facilidade, mesmo em um programa estritamente conforme .) E essas estruturas de dados alternativas, como matrizes / vetores, têm algumas propriedades superiores em comparação às listas vinculadas individualmente na prática. É por isso que o R ⁵ RS introduz novas operações primitivas.

Mas existem tipos de vetor / matriz de diferenças versus listas duplamente vinculadas. Uma matriz geralmente é assumida com complexidade de tempo de acesso O (1) e menos sobrecarga de espaço, que são excelentes propriedades não compartilhadas por listas. (Embora estritamente falando, nenhum dos dois é garantido pela ISO C, mas os usuários quase sempre esperam isso e nenhuma implementação prática violaria essas garantias implícitas com muita clareza.) OTOH, uma lista duplamente vinculada geralmente torna ambas as propriedades ainda piores do que uma lista isolada , enquanto a iteração para trás / para frente também é suportada por uma matriz ou um vetor (junto com índices inteiros) com ainda menos sobrecarga. Portanto, uma lista duplamente vinculada não apresenta um desempenho melhor em geral. Pior ainda, o desempenho sobre a eficiência do cache e a latência na alocação dinâmica de memória das listas são catastroficamente piores que o desempenho para matrizes / vetores ao usar o alocador padrão fornecido pelo ambiente de implementação subjacente (por exemplo, libc). Portanto, sem um tempo de execução muito específico e "inteligente" otimizando bastante essas criações de objetos, os tipos de matriz / vetor geralmente são preferidos às listas vinculadas. (Por exemplo, usando ISO C ++, há uma ressalva de questd::vectordeve ser preferido std::listpor defeito.) Assim, para introduzir novas primitivas de suporte especificamente listas encadeadas (doubly-) não é definitivamente tão benéfico como a matriz de suporte / estruturas de dados do vetor em prática.

Para ser justo, as listas ainda têm algumas propriedades específicas melhores que matrizes / vetores:

• As listas são baseadas em nós. A remoção de elementos das listas não invalida a referência a outros elementos em outros nós. (Isso também se aplica a algumas estruturas de dados em árvore ou gráfico.) OTOH, matrizes / vetores podem fazer com que a posição de rastreamento seja invalidada (com realocação maciça em alguns casos).
• As listas podem emendar no tempo O (1). A reconstrução de novas matrizes / vetores com as atuais é muito mais cara.

No entanto, essas propriedades não são muito importantes para um idioma com suporte para listas vinculadas individualmente integradas, que já é capaz de tal uso. Embora ainda existam diferenças, em idiomas com extensões dinâmicas obrigatórias de objetos (o que geralmente significa que existe um coletor de lixo mantendo as referências pendentes), a invalidação também pode ser menos importante, dependendo das intenções. Portanto, os únicos casos em que as listas duplamente vinculadas vencem podem ser:

• São necessários requisitos de garantia de não realocação e de iteração bidirecional. (Se o desempenho do acesso ao elemento for importante e o conjunto de dados for grande o suficiente, eu escolheria árvores de pesquisa binária ou tabelas de hash.
• São necessárias operações de emenda bidirecional eficientes. Isso é consideravelmente raro. (Apenas atendo aos requisitos apenas na implementação de algo como registros lineares de histórico em um navegador.)

Imutabilidade e alias

Em uma linguagem pura como Haskell, os objetos são imutáveis. O objeto do esquema é frequentemente usado sem mutação. Tal fato torna possível melhorar efetivamente a eficiência da memória com a internação de objetos - compartilhamento implícito de vários objetos com o mesmo valor em tempo real.

Essa é uma estratégia agressiva de otimização de alto nível no design da linguagem. No entanto, isso envolve problemas de implementação. Na verdade, ele introduz aliases implícitos nas células de armazenamento subjacentes. Isso torna a análise de aliasing mais difícil. Como resultado, é possível que haja menos possibilidades de eliminar a sobrecarga de referências de primeira classe, mesmo os usuários nunca as tocam. Em idiomas como Scheme, uma vez que a mutação não está totalmente descartada, isso também interfere no paralelismo. No entanto, pode ser bom em um idioma lento (que já apresenta problemas de desempenho causados ​​por thunks).

Para programação de propósito geral, essa escolha do design da linguagem pode ser problemática. Mas com alguns padrões de codificação funcional comuns, as linguagens ainda parecem funcionar bem.