Quais são as regras concretas para usar uma lista vinculada em vez de uma matriz?

18

Uma lista vinculada pode ser usada quando você deseja inserção e exclusão baratas de elementos e quando não importa que os elementos não estejam próximos um do outro na memória.

Isso é muito abstrato e eu gostaria de uma explicação concreta sobre por que uma lista vinculada deve ser usada em vez de uma matriz. Eu não sou muito experiente em programação, então não tenho muita experiência (se houver) no mundo real.

data-structures linked-list destro
fonte
3
Honestamente, não acho que exemplos signifiquem isso até você ter alguma experiência em escrever algo e depois ver o efeito que a alteração das estruturas de dados tem no seu código. Tente escrever algo do seu interesse e descubra quais estruturas e contêineres de dados são os mais adequados ou consulte um código existente e pense sobre por que cada contêiner foi selecionado e qual efeito a alteração teria.
Inutil)
Apenas não acho que seja possível comunicar utilmente os trade-offs e os efeitos colaterais da seleção da estrutura de dados ao OP (inexperiente) sem um exemplo muito mais elaborado do que o razoável aqui. Os exemplos dados como respostas são bons e respondem à pergunta conforme solicitado, mas não (o que eu leio como) uma solicitação implícita de entendimento real.
Inútil

Respostas:

37

Aqui está algo meio caminho entre um exemplo e uma analogia. Você tem algumas tarefas a fazer, então pega um pedaço de papel e escreve:

  • banco
  • mercearias
  • deixar a limpeza a seco

Então você se lembra de que também precisa comprar selos. Por causa da geografia da sua cidade, você precisa fazer isso depois do banco. Você pode copiar sua lista inteira em um novo pedaço de papel:

  • banco
  • selos
  • mercearias
  • deixar a limpeza a seco

ou você pode rabiscar o que você tinha:

  • banco ....... SELOS
  • mercearias
  • deixar a limpeza a seco

Ao pensar em outras tarefas, você pode escrevê-las no final da lista, mas com setas lembrando a você em que ordem fazê-las. Esta é uma lista vinculada. É mais rápido e fácil do que copiar toda a lista toda vez que você adicionar algo.

Então seu celular toca enquanto você está no banco "ei, eu tenho os selos, não atendo mais". Você apenas cruza STAMPS da lista, não reescreve um novo sem STAMPS.

Agora você pode realmente implementar uma lista de tarefas no código (talvez um aplicativo que coloque suas tarefas em ordem com base na sua região geográfica) e há uma chance razoável de você realmente usar uma lista vinculada para isso no código. Você deseja adicionar e remover muitos itens, o pedido é importante, mas não deseja copiar novamente a lista inteira após cada inserção ou exclusão.

Kate Gregory
fonte
3
De acordo com Bjarne Stroustrup, as LLs podem não ser tão rápidas e fáceis para copiar a lista inteira quanto você pensa .
Dennis
@ Dennis sim, eu sei, graças a mover semântica. No entanto, isso não é verdade para todos os idiomas, portanto, o exemplo permanece.
Kate Gregory
1
O @KateGregory é justo, mas ainda é bom ressaltar que estruturas de dados "básicas" geralmente são melhores do que as estruturas de dados interessantes que aprendemos na escola (ou em outro lugar). Eu não quero que novos graduados usem LLs em todos os lugares, porque é teoricamente apropriado, enquanto possivelmente é uma má escolha de maneira realista. Usar a estrutura de dados correta é importante e, às vezes, as pessoas a complicam demais. Ligeiramente relacionado é a palestra de Jonathan Blow (criador do "Braid") sobre estruturas de dados .
Dennis
1
@Ray: Uma lista vinculada pode superar a estrutura de uma árvore se você espera que haja da ordem de 4 elementos e as comparações são relativamente baratas. Não sei exatamente onde é o ponto de corte onde não é esse o caso. Além disso, uma estrutura em árvore exige que seus dados possam ser classificados, enquanto uma estrutura em lista permite manter a ordem de inserção (ou qualquer ordem arbitrária).
David Stone
2
Não acho que essa analogia seja muito precisa. Como seres humanos, podemos (pelo menos para uma lista tão curta) encontrar um elemento em O (1). Mas se você quiser fazer uma inserção aleatória em uma lista vinculada, precisará percorrer metade dos elementos, em média, o que custa O (n) apenas para encontrar a posição em que deseja inserir. O inserto real custa apenas O (1), mas com uma matriz, seu custo também é "apenas" O (n). Portanto, a razão não se deve apenas à movimentação da semântica, mas também algorítmica. O fator constante oculto pelo big-O é muito maior para a lista de curtidas, no entanto, devido ao acesso não-contíguo à memória.
5gon12eder
18
  • Tabelas de hash que usam encadeamento para resolver colisões de hash geralmente têm uma lista vinculada por bloco para os elementos nesse bloco.
  • Alocadores de memória simples usam uma lista livre de regiões de memória não utilizadas, basicamente uma lista vinculada com o ponteiro de lista dentro da própria memória livre
  • Em um sistema de arquivos FAT , os metadados de um arquivo grande são organizados como uma lista vinculada de entradas FAT.
Michael Borgwardt
fonte
12

A pilha de chamadas em linguagem C é implementada como uma lista vinculada nas APIs binárias x86 (e na maioria das outras).

Ou seja, a chamada de procedimento em linguagem C segue uma disciplina de primeiro a entrar, último a sair. O resultado da execução de chamadas de função (possivelmente recursivas) é chamado de "pilha de chamadas" ou, às vezes, apenas "a pilha".

A CALLinstrução x86 acaba implementando uma lista vinculada usando a "pilha de chamadas". Uma CALLinstrução envia o conteúdo do registro% EIP, o endereço da instrução após a CALLmemória da pilha. O prólogo de função chamada envia o conteúdo do registro% EBP, o endereço mais baixo das variáveis ​​locais na função de chamada, para a memória da pilha. Em seguida, o prólogo da função chamada define% EBP para a base da pilha da função atual.

Isso significa que% EBP é um ponteiro para um local de memória que contém o endereço do valor% EBP da função de chamada. Isso não passa de uma lista vinculada, implementada parcialmente em hardware via CALL.

Na medida em que isso é bom, é como as CPUs x86 implementam chamadas de função, particularmente chamadas de função em que a função possui sua própria cópia de argumentos e variáveis ​​locais para a função. Toda chamada de função fornece algumas informações na "pilha de chamadas" que permite que a CPU continue de onde parou na função de chamada, sem interferência da função chamada ou da função de chamada.

Bruce Ediger
fonte
3

Uma lista vinculada pode ser usada para implementar uma fila de mensagens.

Uma fila de mensagens é uma estrutura na qual armazenamos informações sobre eventos para processamento posterior. Por exemplo, quando o usuário pressiona uma tecla ou move o mouse, este é um evento. Um aplicativo pode estar ocupado no momento em que o evento ocorre, portanto, não se pode esperar que o evento seja processado no momento exato em que ocorre. Portanto, o evento é colocado em uma fila de mensagens (informações sobre qual tecla foi pressionada ou onde o mouse foi movido) e quando o aplicativo tem algum tempo de sobra, ele verifica sua fila de mensagens, busca eventos e processa eles. (Isso acontece dentro de um período de milissegundos, por isso não é perceptível.)

No cenário de uso que acabei de descrever, deve ser óbvio que nunca nos importamos em ter acesso aleatório a eventos armazenados na fila de mensagens; só nos preocupamos em poder armazenar mensagens nele e recuperá-las. Portanto, faz sentido usar uma lista vinculada, que fornece o tempo ideal para inserção / remoção.

(Não se esqueça de apontar que uma fila de mensagens é provável, ou mais provável, ou quase tão provável, a ser implementada usando uma lista de matriz circular; isso é um detalhe técnico e tem uma limitação: você só pode armazenar um número limitado de mensagens.)

Mike Nakis
fonte