As listas vinculadas devem sempre ter um ponteiro de cauda?

Meu entendimento...

Vantagens:

• A inserção no final é O (1) em vez de O (N).
• Se a lista for uma lista duplamente vinculada, a remoção do final também será O (1) em vez de O (N).

Desvantagem:

• Consome uma quantidade trivial de memória extra: 4-8 bytes .
• O implementador deve acompanhar a cauda.

Observando essas vantagens e desvantagens, não vejo por que uma lista vinculada evitaria o uso de um ponteiro de cauda. Tem algo que estou perdendo?

Você está correto, um ponteiro de cauda nunca é demais e só pode ajudar. No entanto, há uma situação em que não é necessário um ponteiro de cauda.

Se alguém estiver usando uma lista vinculada para implementar uma pilha, não há necessidade de um ponteiro de cauda, ​​pois é possível garantir que todos os acessos, inserções e remoções ocorram na cabeça. Dito isto, é possível usar uma lista duplamente vinculada com um ponteiro de cauda de qualquer maneira, porque essa é a implementação padrão em uma biblioteca ou plataforma e a memória é barata, mas não é necessário .

As listas vinculadas geralmente são persistentes e imutáveis. De fato, em linguagens de programação funcionais, esse uso é onipresente. Ponteiros de cauda quebram essas duas propriedades. No entanto, se você não se importa com imutabilidade ou persistência, há muito pouco inconveniente em incluir um ponteiro de cauda.

Eu raramente uso um ponteiro de cauda para listas vinculadas e tendem a usar listas vinculadas individualmente com mais frequência, onde é suficiente um padrão push / pop de inserção e remoção em forma de pilha (ou apenas remoção em tempo linear do meio). Isso ocorre porque, em meus casos de uso comuns, o ponteiro de cauda é realmente caro, assim como é caro tornar a lista vinculada individualmente em uma lista duplamente vinculada.

Muitas vezes, meu uso comum de caso para uma lista vinculada individualmente pode armazenar centenas de milhares de listas vinculadas, que contêm apenas alguns nós da lista cada. Eu também geralmente não uso ponteiros para listas vinculadas. Eu uso índices em uma matriz, pois os índices podem ter 32 bits, por exemplo, ocupando metade do espaço de um ponteiro de 64 bits. Eu também geralmente não aloco os nós da lista, um de cada vez; em vez disso, basta usar uma grande matriz para armazenar todos os nós e, em seguida, usar índices de 32 bits para vincular os nós.

Como exemplo, imagine um videogame usando uma grade de 400x400 para particionar um milhão de partículas que se movem e se refletem para acelerar a detecção de colisões. Nesse caso, uma maneira bastante eficiente de armazenar isso é armazenar 160.000 listas vinculadas individualmente, que se traduz em 160.000 números inteiros de 32 bits no meu caso (~ 640 kilobytes) e um número inteiro de 32 bits por partícula. Agora, à medida que as partículas se movem na tela, tudo o que precisamos fazer é atualizar alguns números inteiros de 32 bits para mover uma partícula de uma célula para outra, da seguinte forma:

... com o nextíndice ("ponteiro") de um nó de partícula servindo como um índice para a próxima partícula na célula ou a próxima partícula livre para recuperar se a partícula morreu (basicamente uma implementação de alocador de lista livre usando índices):

A remoção em tempo linear de uma célula não é realmente uma sobrecarga, pois estamos processando a lógica das partículas iterando através das partículas em uma célula; portanto, uma lista duplamente vinculada adicionaria sobrecarga de um tipo que não é benéfico em tudo no meu caso, assim como um rabo também não me beneficiaria.

Um ponteiro de cauda duplicaria o uso de memória da grade e aumentaria o número de falhas de cache. Também requer inserção para exigir que uma ramificação verifique se a lista está vazia em vez de sem ramificação. Torná-lo uma lista duplamente vinculada dobraria a sobrecarga da lista de cada partícula. 90% do tempo em que uso listas vinculadas, é para casos como esses e, portanto, um indicador de cauda seria relativamente caro de armazenar.

Portanto, 4-8 bytes na verdade não são triviais na maioria dos contextos em que eu uso listas vinculadas em primeiro lugar. Só queria entrar lá porque se você estiver usando uma estrutura de dados para armazenar uma carga de elementos, de 4 a 8 bytes nem sempre podem ser tão insignificantes. Na verdade, eu uso listas vinculadas para reduzir o número de alocações de memória e a quantidade de memória necessária, em vez de, por exemplo, armazenar 160.000 matrizes dinâmicas que crescem para a grade que teriam um uso explosivo de memória (normalmente um ponteiro mais dois números inteiros pelo menos por célula da grade) juntamente com alocações de heap por célula da grade, em oposição a apenas um número inteiro e zero alocações de heap por célula).

Costumo encontrar muitas pessoas que procuram listas vinculadas por sua complexidade de tempo constante associada à remoção frontal / média e inserção frontal / média, quando as LLs geralmente são uma má escolha nesses casos devido à sua falta geral de contiguidade. Onde as LLs são bonitas para mim do ponto de vista de desempenho, é a capacidade de mover apenas um elemento de uma lista para outra, manipulando alguns ponteiros e conseguir uma estrutura de dados de tamanho variável sem um alocador de memória de tamanho variável (desde cada nó tem um tamanho uniforme, podemos usar listas gratuitas, por exemplo). Se cada nó da lista está sendo alocado individualmente em relação a um alocador de uso geral, geralmente é quando as listas vinculadas ficam muito piores em comparação com as alternativas, e é '

Em vez disso, eu sugeriria que, na maioria dos casos em que as listas vinculadas servem como uma otimização muito eficaz em relação a alternativas simples, as formas mais úteis geralmente são vinculadas individualmente, precisam apenas de um ponteiro principal e não exigem uma alocação de memória de uso geral por nó e, em vez disso, pode apenas agrupar a memória já alocada por nó (de uma grande matriz já alocada previamente, por exemplo). Além disso, cada SLL geralmente armazenaria um número muito pequeno de elementos nesses casos, como arestas conectadas a um nó gráfico (muitas pequenas listas vinculadas em oposição a uma lista vinculada massiva).

Também vale lembrar que temos um monte de DRAM atualmente, mas esse é o segundo tipo de memória mais lento disponível. Ainda estamos com algo em torno de 64 KB por núcleo quando se trata do cache L1 com linhas de cache de 64 bytes. Como resultado, essas pequenas poupanças de bytes podem realmente ser importantes em uma área crítica de desempenho, como o simulador de partículas acima, quando multiplicado milhões de vezes, se isso significa a diferença entre armazenar o dobro de nós em uma linha de cache ou não, por exemplo