Quando usar uma lista vinculada em uma lista de matriz / matriz?

Eu uso muitas listas e matrizes, mas ainda não encontrei um cenário em que a lista de matrizes não pudesse ser usada tão facilmente quanto, se não mais fácil do que a lista vinculada. Eu esperava que alguém pudesse me dar alguns exemplos de quando a lista vinculada é notavelmente melhor.

As listas vinculadas são preferíveis às matrizes quando:

1. você precisa de inserções / exclusões em tempo constante da lista (como na computação em tempo real, onde a previsibilidade do tempo é absolutamente crítica)

2. você não sabe quantos itens estarão na lista. Com matrizes, pode ser necessário declarar novamente e copiar a memória se a matriz aumentar muito

3. você não precisa de acesso aleatório a nenhum elemento

4. você deseja inserir itens no meio da lista (como uma fila de prioridade)

Matrizes são preferíveis quando:

1. você precisa de acesso indexado / aleatório aos elementos

2. você sabe o número de elementos na matriz com antecedência, para poder alocar a quantidade correta de memória para a matriz

3. você precisa de velocidade ao percorrer todos os elementos em sequência. Você pode usar a matemática dos ponteiros na matriz para acessar cada elemento, enquanto você precisa procurar o nó com base no ponteiro para cada elemento na lista vinculada, o que pode resultar em falhas de página que podem resultar em resultados de desempenho.

4. memória é uma preocupação. As matrizes preenchidas ocupam menos memória que as listas vinculadas. Cada elemento na matriz é apenas os dados. Cada nó da lista vinculada requer os dados, bem como um (ou mais) ponteiros para os outros elementos na lista vinculada.

As listas de matrizes (como as do .Net) oferecem os benefícios das matrizes, mas alocam recursos dinamicamente para você, para que você não precise se preocupar muito com o tamanho da lista e pode excluir itens em qualquer índice sem nenhum esforço ou baralhar elementos ao redor. Em termos de desempenho, as listas de matrizes são mais lentas que as matrizes brutas.

As matrizes têm acesso aleatório O (1), mas são realmente caras para adicionar ou remover coisas.

Listas vinculadas são realmente baratas para adicionar ou remover itens em qualquer lugar e iterar, mas o acesso aleatório é O (n).

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

As ArrayLists são boas para escrever ou ler muitos ou anexos, mas são ruins para adicionar / remover da frente ou do meio.

Para adicionar às outras respostas, a maioria das implementações de lista de matrizes reserva capacidade extra no final da lista para que novos elementos possam ser adicionados ao final da lista em O (1). Quando a capacidade de uma lista de matrizes é excedida, uma nova matriz maior é alocada internamente e todos os elementos antigos são copiados. Geralmente, a nova matriz é o dobro do tamanho da antiga. Isso significa que, em média , adicionar novos elementos ao final de uma lista de matrizes é uma operação O (1) nessas implementações. Portanto, mesmo se você não souber o número de elementos antecipadamente, uma lista de matrizes ainda poderá ser mais rápida que uma lista vinculada para adicionar elementos, desde que você os adicione no final. Obviamente, inserir novos elementos em locais arbitrários em uma lista de matrizes ainda é uma operação O (n).

O acesso a elementos em uma lista de matrizes também é mais rápido que em uma lista vinculada, mesmo que os acessos sejam seqüenciais. Isso ocorre porque os elementos da matriz são armazenados na memória contígua e podem ser armazenados em cache facilmente. Os nós da lista vinculada podem potencialmente estar espalhados por muitas páginas diferentes.

Eu recomendaria usar apenas uma lista vinculada, se você souber que irá inserir ou excluir itens em locais arbitrários. As listas de matrizes serão mais rápidas para praticamente todo o resto.

A vantagem das listas aparece se você precisar inserir itens no meio e não quiser começar a redimensionar a matriz e mudar as coisas.

Você está certo, pois normalmente não é esse o caso. Eu tive alguns casos muito específicos como esse, mas não muitos.

Tudo depende do tipo de operação que você está executando durante a iteração, todas as estruturas de dados têm trocas entre tempo e memória e, dependendo de nossas necessidades, devemos escolher o DS certo. Portanto, há alguns casos em que o LinkedList é mais rápido que o array e vice-versa. Considere as três operações básicas em estruturas de dados.

• Procurando

Como a matriz é uma estrutura de dados baseada em índice, a pesquisa em array.get (index) levará O (1) tempo enquanto a lista vinculada não for o índice DS, portanto, você precisará ir até o índice, onde índice <= n, n é o tamanho da lista vinculada, para que a matriz seja mais rápida na lista vinculada quando tiver acesso aleatório aos elementos.

P. Então, qual é a beleza por trás disso?

Como matrizes são blocos de memória contíguos, grandes pedaços deles serão carregados no cache no primeiro acesso, o que torna comparativamente rápido o acesso aos elementos restantes da matriz, por mais que acessemos os elementos na localidade de referência da matriz também aumenta, portanto, menos capturas falta, a localidade do cache refere-se às operações que estão no cache e, portanto, são executadas muito mais rapidamente do que na memória, basicamente no array, maximizamos as chances de o acesso sequencial ao elemento estar no cache. Embora as listas vinculadas não estejam necessariamente em blocos contíguos de memória, não há garantia de que os itens que aparecem seqüencialmente na lista sejam realmente organizados um perto do outro na memória, isso significa menos ocorrências de cache, por exemplo

• Inserção

Isso é fácil e rápido no LinkedList, pois a inserção é a operação O (1) no LinkedList (em Java) em comparação com o array; considere o caso quando o array estiver cheio; precisamos copiar o conteúdo para o novo array, se o array ficar cheio, o que torna a inserção de um no ArrayList de O (n), na pior das hipóteses, enquanto ArrayList também precisa atualizar seu índice, se você inserir algo em qualquer lugar, exceto no final da matriz, no caso de lista vinculada, não precisamos redimensioná-lo, você só precisa atualizar ponteiros.

• Eliminação

Funciona como inserções e é melhor no LinkedList do que no array.

Essas são as implementações usadas mais comuns do Collection.

ArrayList:

• inserir / excluir no final geralmente O (1) pior caso O (n)

• inserir / excluir no meio O (n)

• recuperar qualquer posição O (1)

LinkedList:

• insira / exclua em qualquer posição O (1) (observe se você tem uma referência ao elemento)

• recuperar no meio O (n)

• recuperar o primeiro ou o último elemento O (1)

Vector: não use. É uma implementação antiga semelhante ao ArrayList, mas com todos os métodos sincronizados. Não é a abordagem correta para uma lista compartilhada em um ambiente multithreading.

HashMap

inserir / excluir / recuperar por chave em O (1)

TreeSet inserir / excluir / contém em O (log N)

HashSet inserir / remover / conter / tamanho em O (1)

Na realidade, a localidade da memória tem uma enorme influência no desempenho no processamento real.

O aumento do uso do streaming de disco no processamento de "big data" versus acesso aleatório mostra como a estruturação do aplicativo em torno disso pode melhorar drasticamente o desempenho em uma escala maior.

Se houver alguma maneira de acessar uma matriz sequencialmente, esse é de longe o melhor desempenho. Projetar com isso como uma meta deve ser pelo menos considerado se o desempenho for importante.

Hmm, o Arraylist pode ser usado em casos como os seguintes, eu acho:

1. você não tem certeza de quantos elementos estarão presentes
2. mas você precisa acessar todos os elementos aleatoriamente através da indexação

Por exemplo, você precisa importar e acessar todos os elementos em uma lista de contatos (cujo tamanho é desconhecido para você)

Use a lista vinculada para a classificação Radix sobre matrizes e para operações polinomiais.

1) Conforme explicado acima, as operações de inserção e remoção fornecem um bom desempenho (O (1)) no LinkedList em comparação com ArrayList (O (n)). Portanto, se houver um requisito de adição e exclusão freqüentes no aplicativo, o LinkedList é a melhor opção.

2) As operações de pesquisa (método get) são rápidas no Arraylist (O (1)), mas não no LinkedList (O (n)), portanto, se houver menos operações de adição e remoção e mais requisitos de operações de pesquisa, o ArrayList seria sua melhor aposta.

Eu acho que a principal diferença é se você frequentemente precisa inserir ou remover coisas do topo da lista.

Com uma matriz, se você remover algo do topo da lista, a complexidade será n (n) porque todos os índices dos elementos da matriz terão que mudar.

Com uma lista vinculada, é o (1) porque você precisa apenas criar o nó, reatribuir o cabeçalho e atribuir a referência a next como cabeçalho anterior.

Ao inserir ou remover com frequência no final da lista, as matrizes são preferíveis porque a complexidade será o (1), não é necessário reindexar, mas para uma lista vinculada será o (n) porque você precisa sair da cabeça até o último nó.

Eu acho que a pesquisa na lista vinculada e nas matrizes será o (log n) porque você provavelmente estará usando uma pesquisa binária.

Fiz alguns testes de comparação e descobri que a classe list é realmente mais rápida que o LinkedList para inserção aleatória:

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 20000;
            Random rand = new Random(12345);

            Stopwatch watch = Stopwatch.StartNew();
            LinkedList<int> ll = new LinkedList<int>();
            ll.AddLast(0);
            for (int i = 1; i < count; i++)
            {
                ll.AddBefore(ll.Find(rand.Next(i)),i);

            }
            Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds);

            watch = Stopwatch.StartNew();
            List<int> list = new List<int>();
            list.Add(0);
            for (int i = 1; i < count; i++)
            {
                list.Insert(list.IndexOf(rand.Next(i)), i);

            }
            Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds);

            Console.ReadLine();
        }
    }
}

São necessários 900 ms para a lista vinculada e 100 ms para a classe da lista.

Ele cria listas de números inteiros subseqüentes. Cada novo número inteiro é inserido após um número aleatório que já está na lista. Talvez a classe List use algo melhor do que apenas uma matriz.

Matrizes, de longe, são as estruturas de dados mais usadas. No entanto, as listas vinculadas são úteis de uma maneira única, onde as matrizes são desajeitadas - ou caras, para dizer o mínimo.

Listas vinculadas são úteis para implementar pilhas e filas em situações em que seu tamanho está sujeito a variar. Cada nó na lista vinculada pode ser pressionado ou exibido sem perturbar a maioria dos nós. O mesmo vale para inserção / exclusão de nós em algum lugar no meio. Nas matrizes, no entanto, todos os elementos precisam ser deslocados, o que é um trabalho caro em termos de tempo de execução.

Árvores binárias e árvores de pesquisa binária, tabelas de hash e tentativas são algumas das estruturas de dados em que - pelo menos em C - você precisa de listas vinculadas como ingrediente fundamental para construí-las.

No entanto, as listas vinculadas devem ser evitadas em situações nas quais se espera que seja possível chamar qualquer elemento arbitrário pelo seu índice.

Uma resposta simples para a pergunta pode ser dada usando estes pontos:

1. As matrizes devem ser usadas quando uma coleção de elementos de dados do tipo semelhante é necessária. Considerando que, lista vinculada é uma coleção de elementos vinculados de dados de tipo misto conhecidos como nós.

2. Na matriz, pode-se visitar qualquer elemento no tempo O (1). Enquanto na lista vinculada precisaríamos percorrer toda a lista vinculada da cabeça para o nó necessário, levando tempo O (n).

3. Para matrizes, um tamanho específico precisa ser declarado inicialmente. Mas as listas vinculadas são dinâmicas em tamanho.