arrays - singly - Matriz versus lista vinculada




singly linked list (20)

Por que alguém desejaria usar uma lista vinculada em uma matriz?

Esta é apenas uma das razões - se você precisa de uma estrutura de dados de lista vinculada e uma linguagem de programação que você está usando não é compatível com ponteiros.

Por que alguém desejaria usar uma lista vinculada em uma matriz?

Codificar uma lista encadeada é, sem dúvida, um pouco mais trabalhoso do que usar uma matriz e pode-se imaginar o que justificaria o esforço adicional.

Eu acho que a inserção de novos elementos é trivial em uma lista vinculada, mas é uma grande tarefa em uma matriz. Existem outras vantagens em usar uma lista vinculada para armazenar um conjunto de dados versus armazená-lo em uma matriz?

Esta questão não é uma duplicata desta questão porque a outra questão é perguntar especificamente sobre uma determinada classe Java enquanto esta questão está relacionada com as estruturas de dados gerais.


É realmente uma questão de eficiência, a sobrecarga para inserir, remover ou mover (onde você não está simplesmente trocando) elementos dentro de uma lista vinculada é mínima, ou seja, a operação em si é O (1), versos O (n) para uma matriz. Isso pode fazer uma diferença significativa se você estiver operando intensamente em uma lista de dados. Você escolheu seus tipos de dados com base em como você estará operando neles e escolherá o mais eficiente para o algoritmo que você está usando.


A Wikipedia tem uma seção muito boa sobre as diferenças.

Listas vinculadas têm várias vantagens sobre matrizes. Os elementos podem ser inseridos indefinidamente em listas encadeadas, enquanto um array acabará sendo preenchido ou precisará ser redimensionado, uma operação dispendiosa que talvez nem seja possível se a memória estiver fragmentada. Da mesma forma, um array do qual muitos elementos são removidos pode se tornar um desperdício vazio ou precisar ser reduzido.

Por outro lado, as matrizes permitem acesso aleatório, enquanto as listas vinculadas permitem somente acesso sequencial aos elementos. Listas com ligações singulares, na verdade, só podem ser percorridas em uma direção. Isso torna as listas vinculadas inadequadas para aplicativos em que é útil procurar um elemento pelo índice rapidamente, como o heapsort. O acesso seqüencial em matrizes também é mais rápido do que em listas vinculadas em muitas máquinas devido à localidade de referência e caches de dados. Listas vinculadas quase não recebem benefícios do cache.

Outra desvantagem das listas vinculadas é o armazenamento extra necessário para referências, o que muitas vezes as torna impraticáveis ​​para listas de itens de dados pequenos, como caracteres ou valores booleanos. Também pode ser lento, e com um alocador ingênuo, um desperdício, alocar memória separadamente para cada novo elemento, um problema geralmente resolvido usando pools de memória.

http://en.wikipedia.org/wiki/Linked_list


A lista vinculada é especialmente útil quando a coleção está em constante crescimento e encolhimento. Por exemplo, é difícil imaginar a tentativa de implementar uma fila (adicionar ao final, remover da frente) usando uma matriz - você estaria gastando todo o seu tempo mudando as coisas. Por outro lado, é trivial com uma lista vinculada.


Além de adicionar e remover do meio da lista, gosto mais de listas vinculadas porque elas podem crescer e diminuir dinamicamente.


Além de inserir no meio da lista ser mais fácil - também é muito mais fácil excluir do meio de uma lista vinculada do que uma matriz.

Mas, francamente, nunca usei uma lista vinculada. Sempre que eu precisava de inserção rápida e exclusão, eu também precisava de pesquisa rápida, então eu fui para um HashSet ou um dicionário.


Arrays Vs Linked List:

  1. Alocação de memória de matriz falhará às vezes por causa de memória fragmentada.
  2. O armazenamento em cache é melhor em matrizes, pois todos os elementos recebem espaço de memória contíguo.
  3. A codificação é mais complexa que as matrizes.
  4. Nenhuma restrição de tamanho na Lista vinculada, ao contrário de matrizes
  5. A inserção / exclusão é mais rápida na Lista vinculada e o acesso é mais rápido nas matrizes.
  6. Lista vinculada melhor do ponto de vista multi-threading.

Dependendo do seu idioma, algumas dessas desvantagens e vantagens podem ser consideradas:

Linguagem de Programação C : Ao usar uma lista vinculada (através de ponteiros de estrutura tipicamente), consideração especial deve ser feita para garantir que você não está vazando memória. Como foi mencionado anteriormente, as listas interligadas são fáceis de misturar, porque todas estavam mudando os ponteiros, mas vamos nos lembrar de liberar tudo?

Java : Java tem uma coleta de lixo automática, portanto, vazar memória não será um problema, mas oculto do programador de alto nível estão os detalhes de implementação do que é uma lista vinculada. Métodos como remover um nó do meio da lista são mais complicados do que alguns usuários da linguagem esperariam que fosse.


Em uma matriz, você tem o privilégio de acessar qualquer elemento no tempo O (1). Por isso, é adequado para operações como pesquisa binária, classificação rápida, etc. Lista vinculada, por outro lado, é adequada para exclusão de inserção como seu tempo O (1). Ambos têm vantagens e desvantagens e preferir um sobre o outro se resume ao que você deseja implementar.

- Maior questão é que podemos ter um híbrido de ambos. Algo como o que python e perl implementam como listas.


Enquanto muitos de vocês têm tocado nos principais adv./dis da lista de links vs. array, a maioria das comparações é como um é melhor / pior do que o outro.Eg. você pode fazer acesso aleatório em matriz, mas não é possível na lista vinculada e em outros. No entanto, isso pressupõe que as listas de links e a matriz serão aplicadas em um aplicativo semelhante. No entanto, uma resposta correta deve ser como a lista de links seria preferida em relação à matriz e vice-versa em uma implantação de aplicativo específica. Suponha que você queira implementar um aplicativo de dicionário, o que você usaria? Matriz: mmm permitiria fácil recuperação através de busca binária e outro algoritmo de busca .. mas vamos pensar como a lista de links pode ser melhor .. Digamos que você queira pesquisar "Blob" no dicionário. Faz sentido ter uma lista de links de A-> B-> C-> D ----> Z e, em seguida, cada elemento da lista também apontando para uma matriz ou outra lista de todas as palavras que começam com essa letra.

A -> B -> C -> ...Z
|    |    |
|    |    [Cat, Cave]
|    [Banana, Blob]
[Adam, Apple]

Agora é melhor a abordagem acima ou uma matriz plana de [Adão, Maçã, Banana, Bolha, Gato, Caverna]? Seria mesmo possível com array? Portanto, uma grande vantagem da lista de links é que você pode ter um elemento não apenas apontando para o próximo elemento, mas também para alguma outra lista de links / array / heap / ou qualquer outro local de memória. Array é uma memória plana contígua dividida em blocos de tamanho do elemento que irá armazenar. Lista de links, por outro lado, é um bloco de unidades de memória não contíguas (pode ser de qualquer tamanho e pode armazenar qualquer coisa) e apontando para cada uma. outro do jeito que você quiser. Da mesma forma, digamos que você está fazendo um drive USB. Agora você gostaria que os arquivos fossem salvos como qualquer matriz ou como uma lista de links? Eu acho que você entendeu o que eu estou apontando :)


Eu também acho que a lista de links é melhor do que os arrays. porque nós percorremos na lista de links, mas não nos arrays


Lista vinculada

É mais preferível quando se trata de inserção! Basicamente, o que é que ele lida com o ponteiro

1 -> 3 -> 4

Inserir (2)

1 ........ 3 ...... 4
..... 2

Finalmente

1 -> 2 -> 3 -> 4

Uma flecha dos 2 pontos a 3 e a flecha de 1 pontos a 2

Simples!

Mas de Array

| 1 | 3 | 4 |

Inserir (2) | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |

Bem, qualquer um pode visualizar a diferença! Apenas para o índice 4 estamos realizando 3 etapas

E se o tamanho da matriz for um milhão então? O array é eficiente? A resposta é não! :)

A mesma coisa vale para apagar! Em Linked List, podemos simplesmente usar o ponteiro e anular o elemento e o próximo na classe de objeto! Mas para array, precisamos realizar shiftLeft ()

Espero que ajude! :)


Mesclar duas listas vinculadas (especialmente duas listas duplamente vinculadas) é muito mais rápido do que mesclar duas matrizes (supondo que a mesclagem seja destrutiva). O primeiro toma O (1), o último toma O (n).

EDIT: Para esclarecer, eu quis dizer "fundir" aqui no sentido não ordenado, não como no tipo de mesclagem. Talvez "concatenar" teria sido uma palavra melhor.


Ninguém nunca codifica sua própria lista vinculada. Isso seria bobo. A premissa de que usar uma lista vinculada leva mais código é errado.

Hoje em dia, construir uma lista vinculada é apenas um exercício para os alunos para que eles possam entender o conceito. Em vez disso, todo mundo usa uma lista pré-criada. Em C ++, baseado na descrição em nossa pergunta, isso provavelmente significaria um vetor stl ( #include <vector> ).

Portanto, escolher uma lista vinculada em relação a uma matriz é avaliar as diferentes características de cada estrutura em relação às necessidades do seu aplicativo. A superação da carga adicional de programação deve ter impacto zero na decisão.


Outro bom motivo é que as listas vinculadas se prestam muito bem a implementações multiencadeadas eficientes. A razão para isso é que as alterações tendem a ser locais - afetando apenas um ponteiro ou dois para inserir e remover em uma parte localizada da estrutura de dados. Assim, você pode ter muitos segmentos trabalhando na mesma lista vinculada. Ainda mais, é possível criar versões sem bloqueio usando operações do tipo CAS e evitar bloqueios de peso total.

Com uma lista vinculada, os iteradores também podem percorrer a lista enquanto as modificações estão ocorrendo. No caso otimista em que as modificações não colidem, os iteradores podem continuar sem contenção.

Com uma matriz, qualquer alteração que modifique o tamanho da matriz provavelmente exigirá o bloqueio de uma grande parte da matriz e, de fato, é raro que isso seja feito sem um bloqueio global em toda a matriz, para que as modificações parem os assuntos mundiais.


Para mim é assim,

  1. Acesso

    • Listas vinculadas permitem somente acesso sequencial aos elementos. Assim, as complexidades algorítmicas são ordem de O (n)
    • Matrizes permitem acesso aleatório aos seus elementos e, portanto, a complexidade é a ordem de O (1)
  2. Armazenamento

    • Listas vinculadas exigem um armazenamento extra para referências. Isso os torna impraticáveis ​​para listas de itens de dados pequenos, como caracteres ou valores booleanos.
    • Arrays não precisam de um armazenamento extra para apontar para o próximo item de dados. Cada elemento pode ser acessado por meio de índices.
  3. Tamanho

    • O tamanho das listas vinculadas é dinâmico por natureza.
    • O tamanho da matriz é restrito a declaração.
  4. Inserção / Exclusão

    • Elementos podem ser inseridos e excluídos em listas vinculadas indefinidamente.
    • Inserção / exclusão de valores em matrizes são muito caras. Requer realocação de memória.

Primeiro de tudo, em listas vinculadas C ++ não deve haver muito mais problemas para trabalhar do que uma matriz. Você pode usar o std::list ou a lista de apontadores de boost para listas vinculadas. Os principais problemas com listas vinculadas vs arrays são o espaço extra necessário para ponteiros e acesso aleatório terrível. Você deve usar uma lista vinculada se

  • você não precisa de acesso aleatório aos dados
  • você estará adicionando / excluindo elementos, especialmente no meio da lista

Suponha que você tenha um conjunto ordenado, que também deseja modificar adicionando e removendo elementos. Além disso, você precisa ter a capacidade de manter uma referência a um elemento de forma que mais tarde você possa obter um elemento anterior ou seguinte. Por exemplo, uma lista de tarefas ou um conjunto de parágrafos em um livro.

Primeiro, devemos observar que, se você quiser reter referências a objetos fora do próprio conjunto, provavelmente acabará armazenando ponteiros na matriz, em vez de armazenar os próprios objetos. Caso contrário, você não poderá inserir na matriz - se os objetos estiverem incorporados na matriz, eles serão movidos durante as inserções e quaisquer ponteiros para eles se tornarão inválidos. O mesmo é verdadeiro para índices de array.

Seu primeiro problema, como você mesmo observou, é que a lista ligada por inserção permite inserir em O (1), mas uma matriz geralmente exigiria O (n). Esse problema pode ser parcialmente superado - é possível criar uma estrutura de dados que forneça uma interface de acesso ordinal semelhante à matriz, em que tanto a leitura quanto a gravação são, na pior das hipóteses, logarítmicas.

Seu segundo problema, e mais grave, é que, dado um elemento, encontrar o próximo elemento é O (n). Se o conjunto não foi modificado, você poderia reter o índice do elemento como referência ao invés do ponteiro, assim fazendo find-next uma operação O (1), mas como é tudo que você tem é um ponteiro para o objeto em si e de jeito nenhum para determinar seu índice atual na matriz, exceto digitalizando todo o "array". Este é um problema insuperável para os arrays - mesmo que você possa fazer inserções otimizadas, não há nada que você possa fazer para otimizar a próxima operação do tipo find.


Vou adicionar outro - listas podem atuar como estruturas de dados puramente funcionais .

Por exemplo, você pode ter listas completamente diferentes compartilhando a mesma seção final

a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)

ie:

b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next  

sem ter que copiar os dados sendo apontados por a em b e c .

É por isso que eles são tão populares em linguagens funcionais, que usam variáveis ​​imutáveis ​​- operações prepend - prepend e prepend podem ocorrer livremente sem ter que copiar os dados originais - características muito importantes quando você está tratando dados como imutáveis.


como matrizes são estáticas na natureza, portanto, todas as operações, como alocação de memória, ocorrem apenas no momento da compilação. Portanto, o processador precisa colocar menos esforço em seu tempo de execução.







language-agnostic