Matriz versus lista vinculada

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

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

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

Esta pergunta não é uma duplicata desta pergunta, porque a outra pergunta está perguntando especificamente sobre uma classe Java específica, enquanto esta pergunta se refere às estruturas gerais de dados.

• É mais fácil armazenar dados de tamanhos diferentes em uma lista vinculada. Uma matriz assume que cada elemento tem exatamente o mesmo tamanho.
• Como você mencionou, é mais fácil para uma lista vinculada crescer organicamente. O tamanho de uma matriz precisa ser conhecido antecipadamente ou recriado quando precisar crescer.
• Baralhar uma lista vinculada é apenas uma questão de mudar o que aponta para o quê. Baralhar uma matriz é mais complicado e / ou requer mais memória.
• Desde que todas as suas iterações ocorram em um contexto de "foreach", você não perde nenhum desempenho na iteração.

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

Com uma lista vinculada, os iteradores também podem percorrer a lista enquanto ocorrem modificações. 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 uma trava global em toda a matriz, para que as modificações parem os assuntos mundiais.

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

Listas vinculadas têm várias vantagens sobre matrizes. Os elementos podem ser inseridos em listas vinculadas indefinidamente, enquanto uma matriz pode eventualmente ser preenchida ou precisar ser redimensionada, uma operação cara que talvez nem seja possível se a memória estiver fragmentada. Da mesma forma, uma matriz da qual muitos elementos são removidos pode tornar-se desnecessariamente vazia ou precisar ser reduzida.

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

Outra desvantagem das listas vinculadas é o armazenamento extra necessário para as referências, o que geralmente as torna impraticáveis ​​para listas de pequenos itens de dados, 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 conjuntos de memória.

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

Vou acrescentar outra - as listas podem funcionar 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 ...)

ou seja:

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

sem ter que copiar os dados apontados por apara be c.

É por isso que eles são tão populares em linguagens funcionais, que usam variáveis ​​imutáveis ​​- prepende as tailoperações podem ocorrer livremente sem a necessidade de copiar os dados originais - recursos muito importantes quando você trata os dados como imutáveis.

Além de inserir no meio da lista, é 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 e exclusão rápidas, também precisava de pesquisa rápida, então fui a um HashSet ou a um dicionário.

Mesclar duas listas vinculadas (especialmente duas listas duplamente vinculadas) é muito mais rápido que mesclar duas matrizes (assumindo que a mesclagem é destrutiva). O primeiro recebe O (1), o segundo recebe O (n).

Edição: Para esclarecer, eu quis dizer "mesclar" aqui no sentido não ordenado, não como no tipo de mesclagem. Talvez "concatenar" fosse uma palavra melhor.

Um argumento amplamente não apreciado para ArrayList e contra o LinkedList é que o LinkedLists é desconfortável durante a depuração . O tempo gasto pelos desenvolvedores de manutenção para entender o programa, por exemplo, para encontrar bugs, aumentos e o IMHO às vezes não justifica os nanossegundos nas melhorias de desempenho ou bytes no consumo de memória nos aplicativos corporativos. Às vezes (bem, é claro, depende do tipo de aplicativos), é melhor desperdiçar alguns bytes, mas ter um aplicativo que seja mais sustentável ou mais fácil de entender.

Por exemplo, em um ambiente Java e usando o depurador Eclipse, a depuração de um ArrayList revelará uma estrutura muito fácil de entender:

arrayList   ArrayList<String>
  elementData   Object[]
    [0] Object  "Foo"
    [1] Object  "Foo"
    [2] Object  "Foo"
    [3] Object  "Foo"
    [4] Object  "Foo"
    ...

Por outro lado, assistir o conteúdo de um LinkedList e localizar objetos específicos se torna um pesadelo ao clicar em Expand-The-Tree, sem mencionar a sobrecarga cognitiva necessária para filtrar os internos do LinkedList:

linkedList  LinkedList<String>
    header  LinkedList$Entry<E>
        element E
        next    LinkedList$Entry<E>
            element E   "Foo"
            next    LinkedList$Entry<E>
                element E   "Foo"
                next    LinkedList$Entry<E>
                    element E   "Foo"
                    next    LinkedList$Entry<E>
                    previous    LinkedList$Entry<E>
                    ...
                previous    LinkedList$Entry<E>
            previous    LinkedList$Entry<E>
        previous    LinkedList$Entry<E>

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

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

Para mim é assim,

1. Acesso

   • As listas vinculadas permitem apenas acesso seqüencial aos elementos. Assim, as complexidades algorítmicas são da ordem de O (n)
   • As matrizes permitem acesso aleatório a seus elementos e, portanto, a complexidade é da ordem de O (1)

2. Armazenamento

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

3. Tamanho

   • O tamanho das listas vinculadas é dinâmico por natureza.
   • O tamanho da matriz é restrito à declaração.

4. Inserção / exclusão

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

Duas coisas:

Codificar uma lista vinculada é, sem dúvida, um pouco mais trabalhoso do que usar uma matriz e ele se perguntou o que justificaria o esforço adicional.

Nunca codifique uma lista vinculada ao usar C ++. Basta usar o STL. O quão difícil é implementar nunca deve ser uma razão para escolher uma estrutura de dados em detrimento de outra, porque a maioria já está implementada.

Quanto às diferenças reais entre uma matriz e uma lista vinculada, o mais importante para mim é como você planeja usar a estrutura. Usarei o termo vetor, já que esse é o termo para uma matriz redimensionável em C ++.

A indexação em uma lista vinculada é lenta porque você precisa percorrer a lista para chegar ao índice fornecido, enquanto um vetor é contíguo na memória e você pode chegar lá usando a matemática dos ponteiros.

Anexar no final ou no início de uma lista vinculada é fácil, pois você só precisa atualizar um link, onde em um vetor pode ser necessário redimensionar e copiar o conteúdo.

É fácil remover um item de uma lista, pois você só precisa quebrar um par de links e depois anexá-los novamente. A remoção de um item de um vetor pode ser mais rápida ou mais lenta, dependendo se você se importa com o pedido. Trocar o último item por cima do item que você deseja remover é mais rápido, enquanto mudar tudo depois para baixo é mais lento, mas mantém a ordem.

Eric Lippert recentemente teve um pós em uma das razões pelas matrizes devem ser usados de forma conservadora.

A inserção e remoção rápidas são realmente os melhores argumentos para listas vinculadas. Se sua estrutura cresce dinamicamente e o acesso em tempo constante a qualquer elemento não é necessário (como pilhas e filas dinâmicas), as listas vinculadas são uma boa opção.

Aqui está uma rápida: a remoção de itens é mais rápida.

A lista vinculada é especialmente útil quando a coleção está constantemente aumentando e diminuindo. Por exemplo, é difícil imaginar tentar implementar uma Fila (adicionar até o final, remover pela frente) usando uma matriz - você gastaria 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, eu gosto mais de listas vinculadas porque elas podem crescer e encolher dinamicamente.

Ninguém nunca mais codifica sua própria lista vinculada. Isso seria bobagem. A premissa de que o uso de uma lista vinculada exige mais código está errada.

Atualmente, a criação de uma lista vinculada é apenas um exercício para os alunos, para que eles possam entender o conceito. Em vez disso, todos usam uma lista pré-criada. Em C ++, com base na descrição de nossa pergunta, isso provavelmente significaria um vetor stl ( #include <vector>).

Portanto, a escolha de uma lista ligada vs uma matriz é inteiramente sobre pesando as diferentes características de cada estrutura em relação às necessidades do seu aplicativo. Superar a carga adicional de programação não deve ter impacto nulo na decisão.

É realmente uma questão de eficiência, a sobrecarga de 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 fortemente em uma lista de dados. Você escolheu seus tipos de dados com base em como você irá operá-los e escolhe o mais eficiente para o algoritmo que está usando.

As matrizes fazem sentido onde o número exato de itens será conhecido e onde a pesquisa por índice faz sentido. Por exemplo, se eu quisesse armazenar o estado exato da minha saída de vídeo em um determinado momento sem compactação, provavelmente usaria uma matriz de tamanho [1024] [768]. Isso me fornecerá exatamente o que eu preciso, e uma lista seria muito, muito mais lenta para obter o valor de um determinado pixel. Em locais onde uma matriz não faz sentido, geralmente existem tipos de dados melhores do que uma lista para lidar com dados de maneira eficaz.

Matrizes versus lista vinculada:

1. Às vezes, a alocação de memória da matriz falha devido à 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 das 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 multithreading.

como matrizes são estáticas por 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.

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, posteriormente, você possa obter um elemento anterior ou próximo. Por exemplo, uma lista de tarefas ou um conjunto de parágrafos em um livro.

Primeiro, devemos observar que, se você deseja manter referências a objetos fora do 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 forem incorporados na matriz, eles serão movidos durante as inserções e quaisquer ponteiros para eles se tornarão inválidos. O mesmo vale para índices de matriz.

Seu primeiro problema, como você observou, é a lista vinculada à inserção permite a inserção em O (1), mas uma matriz geralmente requer O (n). Esse problema pode ser parcialmente superado - é possível criar uma estrutura de dados que ofereça uma interface de acesso por ordem ordinária, onde matriz e leitura e gravação são, na pior das hipóteses, logarítmicas.

Seu segundo e mais grave problema é que, dado um elemento que encontra o próximo elemento, é O (n). Se o conjunto não foi modificado, você pode manter o índice do elemento como referência, em vez do ponteiro, tornando assim find-next uma operação O (1), mas, como é tudo o que você tem, é um ponteiro para o próprio objeto e de nenhuma maneira para determinar seu índice atual na matriz que não seja a varredura de toda a "matriz". Esse é um problema insuperável para matrizes - mesmo que você possa otimizar inserções, não há nada que possa ser feito para otimizar a operação do tipo encontrar a próxima.

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

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

Lista vinculada

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

1 -> 3 -> 4

Inserção (2)

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

Finalmente

1 -> 2 -> 3 -> 4

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

Simples!

Mas da matriz

| 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 4 índices, estamos realizando 3 etapas

E se o comprimento da matriz for de um milhão? A matriz é eficiente? A resposta é não! :)

A mesma coisa vale para exclusão! Na lista vinculada, podemos simplesmente usar o ponteiro e anular o elemento e o próximo na classe de objeto! Mas para o array, precisamos executar shiftLeft ()

Espero que ajude! :)

A lista vinculada é mais uma sobrecarga para manter do que a matriz, também requer armazenamento de memória adicional, todos esses pontos são acordados. Mas existem algumas coisas que o array não pode fazer. Em muitos casos, suponha que você queira uma matriz de comprimento 10 ^ 9 que não possa obtê-la porque a localização de uma memória contínua deve estar presente. A lista vinculada pode ser um salvador aqui.

Suponha que você queira armazenar várias coisas com dados para que possam ser facilmente estendidos na lista vinculada.

Os contêineres STL geralmente têm implementação de lista vinculada nos bastidores.

1- lista vinculada é uma estrutura de dados dinâmica, para que possa crescer e diminuir em tempo de execução, alocando e desalocando memória. Portanto, não há necessidade de fornecer um tamanho inicial da lista vinculada. A inserção e exclusão de nós são realmente mais fáceis.

O tamanho 2 da lista vinculada pode aumentar ou diminuir no tempo de execução, para que não haja desperdício de memória. No caso da matriz, há muito desperdício de memória, como se declarássemos uma matriz de tamanho 10 e armazenássemos apenas 6 elementos nela, o espaço de 4 elementos seria desperdiçado. Não existe esse problema na lista vinculada, pois a memória é alocada somente quando necessário.

3- Estruturas de dados como pilha e filas podem ser facilmente implementadas usando lista vinculada.

O único motivo para usar a lista vinculada é que é fácil inserir o elemento (removendo também).

Disadvatige pode ser que os ponteiros ocupem muito espaço.

E a codificação é mais difícil: geralmente você não precisa de uma lista vinculada de código (ou apenas uma vez), elas estão incluídas no STL e não é tão complicado se você ainda precisa fazer isso.

Eu também acho que a lista de links é melhor do que matrizes. porque percorremos a lista de links, mas não as matrizes

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

Linguagem de programação C : Ao usar uma lista vinculada (normalmente através de ponteiros de estrutura), é necessário ter uma consideração especial para garantir que você não esteja vazando memória. Como mencionado anteriormente, as listas vinculadas são fáceis de embaralhar, porque tudo o que estamos fazendo é mudar os ponteiros, mas vamos lembrar de liberar tudo?

Java : Java possui uma coleta automática de lixo, portanto, vazar memória não será um problema, mas ocultos ao 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 é um procedimento mais complicado do que alguns usuários da linguagem esperariam que fosse.

Por que uma lista vinculada em uma matriz? Bem, como alguns já disseram, maior velocidade de inserções e exclusões.

Mas talvez não tenhamos que conviver com os limites de ambos e obter o melhor de ambos, ao mesmo tempo ... eh?

Para exclusões de matriz, você pode usar um byte 'Excluído', para representar o fato de que uma linha foi excluída, portanto, não é mais necessário reorientar a matriz. Para aliviar o fardo das inserções ou alterar rapidamente os dados, use uma lista vinculada para isso. Então, quando se referir a eles, faça com que sua lógica procure primeiro uma e depois a outra. Assim, usá-los em combinação oferece o melhor de ambos.

Se você tiver uma matriz realmente grande, poderá combiná-la com outra matriz ou lista vinculada muito menor, onde a menor contém os itens 20, 50, 100 usados ​​mais recentemente. Se o necessário não estiver na lista ou matriz vinculada mais curta, você será direcionado para a matriz grande. Se encontrado lá, você poderá adicioná-lo à lista / matriz menor, com a presunção de que 'as coisas usadas mais recentemente são mais propensas a serem reutilizadas' (e sim, possivelmente colidindo com o item menos usado recentemente na lista). O que é verdade em muitos casos e resolveu um problema que tive de resolver em um módulo de verificação de permissões de segurança .ASP, com facilidade, elegância e velocidade impressionante.

Embora muitos de vocês tenham abordado os principais adv./dis da lista vinculada versus matriz, a maioria das comparações é como uma é melhor / pior que a outra. você pode acessar aleatoriamente na matriz, mas não é possível na lista vinculada e em outras. 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 preferível à 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, isso permitiria a recuperação fácil através de pesquisa binária e outros algo de pesquisa .. mas vamos pensar como a lista de links pode ser melhor .. Diga que você deseja pesquisar "Blob" no dicionário. Faria sentido ter uma lista de links de A-> B-> C-> D ---->

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

Agora, a abordagem acima é melhor ou uma matriz plana de [Adam, Apple, Banana, Blob, Cat, Cave]? Seria possível com o 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. Matriz é uma memória contígua plana dividida em blocos do tamanho do elemento que será armazenado. A lista de links, por outro lado, é um pedaço de unidades de memória não contígua (pode ter qualquer tamanho e pode armazenar qualquer coisa) e apontar para cada outro do jeito que você quiser. Da mesma forma, digamos que você esteja criando uma unidade USB. Agora você deseja que os arquivos sejam salvos como qualquer matriz ou como uma lista de links? Eu acho que você entendeu o que eu estou apontando :)