Quando devo usar uma lista versus uma lista vinculada

Quando é melhor usar uma lista versus uma lista vinculada ?

Editar

Por favor, leia os comentários para esta resposta. As pessoas afirmam que eu não fiz testes adequados. Concordo que isso não deve ser uma resposta aceita. Enquanto aprendia, fiz alguns testes e tive vontade de compartilhá-los.

Resposta original ...

Encontrei resultados interessantes:

// Temporary class to show the example
class Temp
{
    public decimal A, B, C, D;

    public Temp(decimal a, decimal b, decimal c, decimal d)
    {
        A = a;            B = b;            C = c;            D = d;
    }
}

Lista vinculada (3,9 segundos)

        LinkedList<Temp> list = new LinkedList<Temp>();

        for (var i = 0; i < 12345678; i++)
        {
            var a = new Temp(i, i, i, i);
            list.AddLast(a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Lista (2,4 segundos)

        List<Temp> list = new List<Temp>(); // 2.4 seconds

        for (var i = 0; i < 12345678; i++)
        {
            var a = new Temp(i, i, i, i);
            list.Add(a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Mesmo se você acessar apenas os dados essencialmente, é muito mais lento !! Eu digo nunca use um LinkedList.

Aqui está outra comparação executando várias inserções (planejamos inserir um item no meio da lista)

Lista vinculada (51 segundos)

        LinkedList<Temp> list = new LinkedList<Temp>();

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.AddLast(a);
            var curNode = list.First;

            for (var k = 0; k < i/2; k++) // In order to insert a node at the middle of the list we need to find it
                curNode = curNode.Next;

            list.AddAfter(curNode, a); // Insert it after
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Lista (7,26 segundos)

        List<Temp> list = new List<Temp>();

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.Insert(i / 2, a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Lista vinculada com referência do local onde inserir (0,04 segundos)

        list.AddLast(new Temp(1,1,1,1));
        var referenceNode = list.First;

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.AddLast(a);
            list.AddBefore(referenceNode, a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Portanto, somente se você planeja inserir vários itens e também tiver em algum lugar a referência de onde planeja inserir o item, use uma lista vinculada. Só porque você precisa inserir muitos itens, não o torna mais rápido, porque pesquisar no local em que você deseja inserir leva tempo.

Na maioria dos casos, List<T>é mais útil. LinkedList<T>terá menos custo ao adicionar / remover itens no meio da lista, ao passo que List<T>apenas poderá adicionar / remover mais barato no final da lista.

LinkedList<T>é o mais eficiente se você estiver acessando dados seqüenciais (para frente ou para trás) - o acesso aleatório é relativamente caro, pois deve percorrer a cadeia a cada vez (daí o motivo de não ter um indexador). No entanto, como a List<T>é essencialmente apenas um acesso aleatório de matriz (com um invólucro), tudo bem.

List<T>também oferece uma série de métodos de apoio - Find, ToArray, etc; no entanto, eles também estão disponíveis LinkedList<T>no .NET 3.5 / C # 3.0 por meio de métodos de extensão - portanto, isso é menos importante.

Pensar em uma lista vinculada como uma lista pode ser um pouco enganador. É mais como uma corrente. De fato, no .NET, LinkedList<T>nem sequer implementa IList<T>. Não existe um conceito real de índice em uma lista vinculada, mesmo que pareça existir. Certamente, nenhum dos métodos fornecidos na classe aceita índices.

As listas vinculadas podem ser vinculadas individualmente ou duplamente vinculadas. Isso se refere ao fato de cada elemento da cadeia ter um link apenas para o próximo (vinculado individualmente) ou para os elementos anteriores / próximos (vinculados duplamente). LinkedList<T>está duplamente ligado.

Internamente, List<T>é apoiado por uma matriz. Isso fornece uma representação muito compacta na memória. Por outro lado, LinkedList<T>envolve memória adicional para armazenar os links bidirecionais entre elementos sucessivos. Portanto, o espaço de memória de a LinkedList<T>geralmente será maior do que para List<T>(com a ressalva de que List<T>pode haver elementos de matriz internos não utilizados para melhorar o desempenho durante operações de acréscimo).

Eles também têm características de desempenho diferentes:

Acrescentar

• LinkedList<T>.AddLast(item) tempo constante
• List<T>.Add(item) tempo constante amortizado, pior caso linear

Anexar

• LinkedList<T>.AddFirst(item) tempo constante
• List<T>.Insert(0, item) tempo linear

Inserção

• LinkedList<T>.AddBefore(node, item) tempo constante
• LinkedList<T>.AddAfter(node, item) tempo constante
• List<T>.Insert(index, item) tempo linear

Remoção

• LinkedList<T>.Remove(item) tempo linear
• LinkedList<T>.Remove(node) tempo constante
• List<T>.Remove(item) tempo linear
• List<T>.RemoveAt(index) tempo linear

Contagem

• LinkedList<T>.Count tempo constante
• List<T>.Count tempo constante

Contém

• LinkedList<T>.Contains(item) tempo linear
• List<T>.Contains(item) tempo linear

Claro

• LinkedList<T>.Clear() tempo linear
• List<T>.Clear() tempo linear

Como você pode ver, eles são basicamente equivalentes. Na prática, a API de LinkedList<T>é mais complicada de usar e detalhes de suas necessidades internas se espalham pelo seu código.

No entanto, se você precisar fazer muitas inserções / remoções de uma lista, ele oferece tempo constante. List<T>oferece tempo linear, pois itens extras na lista devem ser embaralhados após a inserção / remoção.

As listas vinculadas fornecem inserção ou exclusão muito rápidas de um membro da lista. Cada membro de uma lista vinculada contém um ponteiro para o próximo membro da lista, para inserir um membro na posição i:

• atualize o ponteiro no membro i-1 para apontar para o novo membro
• defina o ponteiro no novo membro para apontar para o membro i

A desvantagem de uma lista vinculada é que o acesso aleatório não é possível. Para acessar um membro, é necessário percorrer a lista até que o membro desejado seja encontrado.

Minha resposta anterior não foi suficientemente precisa. Como realmente foi horrível: D Mas agora posso postar respostas muito mais úteis e corretas.

Eu fiz alguns testes adicionais. Você pode encontrar a fonte no seguinte link e verificar novamente em seu ambiente: https://github.com/ukushu/DataStructuresTestsAndOther.git

Resultados curtos:

• A matriz precisa usar:

  • Tão frequentemente quanto possível. É rápido e utiliza o menor intervalo de RAM para obter informações sobre a mesma quantidade.
  • Se você souber a contagem exata de células necessárias
  • Se os dados salvos na matriz <85000 b (85000/32 = 2656 elementos para dados inteiros)
  • Se necessário, alta velocidade de acesso aleatório

• A lista precisa usar:

  • Se necessário, adicione células ao final da lista (geralmente)
  • Se necessário, adicione células no começo / meio da lista (NÃO É MUITO)
  • Se os dados salvos na matriz <85000 b (85000/32 = 2656 elementos para dados inteiros)
  • Se necessário, alta velocidade de acesso aleatório

• O LinkedList precisa usar:

  • Se necessário, adicione células no começo / meio / fim da lista (frequentemente)
  • Se necessário, apenas acesso sequencial (avançar / retroceder)
  • Se você precisar salvar itens GRANDES, mas a contagem de itens é baixa.
  • Melhor não usar para uma grande quantidade de itens, pois é usar memória adicional para links.

Mais detalhes:

Interessante saber:

1. LinkedList<T>internamente não é uma lista no .NET. É mesmo não implementa IList<T>. E é por isso que existem índices e métodos ausentes relacionados a índices.

2. LinkedList<T>é uma coleção baseada em ponteiro de nó. No .NET está em implementação duplamente vinculada. Isso significa que os elementos anteriores / próximos têm um link para o elemento atual. E os dados são fragmentados - diferentes objetos de lista podem ser localizados em diferentes locais da RAM. Também haverá mais memória usada para LinkedList<T>que para List<T>ou Array.

3. List<T>em .Net é a alternativa de Java para ArrayList<T>. Isso significa que este é um wrapper de matriz. Portanto, é alocado na memória como um bloco de dados contíguo. Se o tamanho dos dados alocados exceder 85000 bytes, ele será movido para Heap de Objetos Grandes. Dependendo do tamanho, isso pode levar à fragmentação da pilha (uma forma moderada de vazamento de memória). Mas, ao mesmo tempo, se o tamanho for <85000 bytes - isso fornece uma representação muito compacta e de acesso rápido na memória.

4. Um único bloco contíguo é preferido para desempenho de acesso aleatório e consumo de memória, mas para coleções que precisam mudar de tamanho regularmente, uma estrutura como uma matriz geralmente precisa ser copiada para um novo local, enquanto uma lista vinculada precisa gerenciar a memória para os recém-inseridos / nós excluídos.

A diferença entre List e LinkedList está na implementação subjacente. Lista é uma coleção baseada em matriz (ArrayList). LinkedList é uma coleção baseada em ponteiro de nó (LinkedListNode). No uso no nível da API, os dois são praticamente os mesmos, pois implementam o mesmo conjunto de interfaces, como ICollection, IEnumerable, etc.

A principal diferença ocorre quando o desempenho é importante. Por exemplo, se você estiver implementando a lista que possui uma operação pesada "INSERT", o LinkedList supera a lista. Como o LinkedList pode fazê-lo em O (1), mas a Lista pode precisar expandir o tamanho da matriz subjacente. Para obter mais informações / detalhes, convém ler a diferença algorítmica entre o LinkedList e as estruturas de dados da matriz. http://en.wikipedia.org/wiki/Linked_list e matriz

Espero que esta ajuda,

A principal vantagem das listas vinculadas sobre as matrizes é que os links nos fornecem a capacidade de reorganizar os itens com eficiência. Sedgewick, p. 91

Uma circunstância comum para usar o LinkedList é assim:

Suponha que você queira remover muitas cadeias de caracteres de uma lista de grandes dimensões, digamos 100.000. As cadeias a serem removidas podem ser consultadas no HashSet dic e acredita-se que a lista de cadeias contenha entre 30.000 a 60.000 dessas cadeias para remover.

Então, qual é o melhor tipo de lista para armazenar as 100.000 cordas? A resposta é LinkedList. Se eles estiverem armazenados em um ArrayList, a iteração e a remoção de Strings correspondentes levarão bilhões de operações, enquanto são necessárias cerca de 100.000 operações usando um iterador e o método remove ().

LinkedList<String> strings = readStrings();
HashSet<String> dic = readDic();
Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()){
    String string = iterator.next();
    if (dic.contains(string))
    iterator.remove();
}

Quando você precisar de acesso indexado interno, classificação (e após esta pesquisa binária) e o método "ToArray ()", use a Lista.

Essencialmente, um List<>no .NET é um invólucro sobre uma matriz . A LinkedList<> é uma lista vinculada . Portanto, a questão se resume a: qual é a diferença entre uma matriz e uma lista vinculada e quando deve ser usada uma matriz em vez de uma lista vinculada. Provavelmente, os dois fatores mais importantes na sua decisão de qual usar se resumiriam a:

• As listas vinculadas têm um desempenho de inserção / remoção muito melhor, desde que as inserções / remoções não estejam no último elemento da coleção. Isso ocorre porque uma matriz deve mudar todos os elementos restantes que vêm após o ponto de inserção / remoção. No entanto, se a inserção / remoção estiver no final da lista, essa mudança não será necessária (embora a matriz possa precisar ser redimensionada, se sua capacidade for excedida).
• Matrizes têm recursos de acesso muito melhores. As matrizes podem ser indexadas diretamente (em tempo constante). As listas vinculadas devem ser percorridas (tempo linear).

Isso é adaptado da resposta aceita de Tono Nam , corrigindo algumas medidas erradas.

O teste:

static void Main()
{
    LinkedListPerformance.AddFirst_List(); // 12028 ms
    LinkedListPerformance.AddFirst_LinkedList(); // 33 ms

    LinkedListPerformance.AddLast_List(); // 33 ms
    LinkedListPerformance.AddLast_LinkedList(); // 32 ms

    LinkedListPerformance.Enumerate_List(); // 1.08 ms
    LinkedListPerformance.Enumerate_LinkedList(); // 3.4 ms

    //I tried below as fun exercise - not very meaningful, see code
    //sort of equivalent to insertion when having the reference to middle node

    LinkedListPerformance.AddMiddle_List(); // 5724 ms
    LinkedListPerformance.AddMiddle_LinkedList1(); // 36 ms
    LinkedListPerformance.AddMiddle_LinkedList2(); // 32 ms
    LinkedListPerformance.AddMiddle_LinkedList3(); // 454 ms

    Environment.Exit(-1);
}

E o código:

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

namespace stackoverflow
{
    static class LinkedListPerformance
    {
        class Temp
        {
            public decimal A, B, C, D;

            public Temp(decimal a, decimal b, decimal c, decimal d)
            {
                A = a; B = b; C = c; D = d;
            }
        }



        static readonly int start = 0;
        static readonly int end = 123456;
        static readonly IEnumerable<Temp> query = Enumerable.Range(start, end - start).Select(temp);

        static Temp temp(int i)
        {
            return new Temp(i, i, i, i);
        }

        static void StopAndPrint(this Stopwatch watch)
        {
            watch.Stop();
            Console.WriteLine(watch.Elapsed.TotalMilliseconds);
        }

        public static void AddFirst_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Insert(0, temp(i));

            watch.StopAndPrint();
        }

        public static void AddFirst_LinkedList()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (int i = start; i < end; i++)
                list.AddFirst(temp(i));

            watch.StopAndPrint();
        }

        public static void AddLast_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Add(temp(i));

            watch.StopAndPrint();
        }

        public static void AddLast_LinkedList()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (int i = start; i < end; i++)
                list.AddLast(temp(i));

            watch.StopAndPrint();
        }

        public static void Enumerate_List()
        {
            var list = new List<Temp>(query);
            var watch = Stopwatch.StartNew();

            foreach (var item in list)
            {

            }

            watch.StopAndPrint();
        }

        public static void Enumerate_LinkedList()
        {
            var list = new LinkedList<Temp>(query);
            var watch = Stopwatch.StartNew();

            foreach (var item in list)
            {

            }

            watch.StopAndPrint();
        }

        //for the fun of it, I tried to time inserting to the middle of 
        //linked list - this is by no means a realistic scenario! or may be 
        //these make sense if you assume you have the reference to middle node

        //insertion to the middle of list
        public static void AddMiddle_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Insert(list.Count / 2, temp(i));

            watch.StopAndPrint();
        }

        //insertion in linked list in such a fashion that 
        //it has the same effect as inserting into the middle of list
        public static void AddMiddle_LinkedList1()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            LinkedListNode<Temp> evenNode = null, oddNode = null;
            for (int i = start; i < end; i++)
            {
                if (list.Count == 0)
                    oddNode = evenNode = list.AddLast(temp(i));
                else
                    if (list.Count % 2 == 1)
                        oddNode = list.AddBefore(evenNode, temp(i));
                    else
                        evenNode = list.AddAfter(oddNode, temp(i));
            }

            watch.StopAndPrint();
        }

        //another hacky way
        public static void AddMiddle_LinkedList2()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start + 1; i < end; i += 2)
                list.AddLast(temp(i));
            for (int i = end - 2; i >= 0; i -= 2)
                list.AddLast(temp(i));

            watch.StopAndPrint();
        }

        //OP's original more sensible approach, but I tried to filter out
        //the intermediate iteration cost in finding the middle node.
        public static void AddMiddle_LinkedList3()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
            {
                if (list.Count == 0)
                    list.AddLast(temp(i));
                else
                {
                    watch.Stop();
                    var curNode = list.First;
                    for (var j = 0; j < list.Count / 2; j++)
                        curNode = curNode.Next;
                    watch.Start();

                    list.AddBefore(curNode, temp(i));
                }
            }

            watch.StopAndPrint();
        }
    }
}

Você pode ver que os resultados estão de acordo com o desempenho teórico que outros documentaram aqui. Muito claro - LinkedList<T>ganha muito tempo em caso de inserções. Não testei a remoção no meio da lista, mas o resultado deve ser o mesmo. Obviamente, existem List<T>outras áreas em que o desempenho é muito melhor, como o acesso aleatório O (1).

Use LinkedList<>quando

1. Você não sabe quantos objetos estão passando pelo portão de inundação. Por exemplo Token Stream,.
2. Quando você SOMENTE queria excluir \ insert nas extremidades.

Para todo o resto, é melhor usar List<>.

Eu concordo com a maior parte do argumento exposto acima. E também concordo que a Lista parece uma escolha mais óbvia na maioria dos casos.

Mas quero apenas acrescentar que há muitas instâncias em que o LinkedList é uma escolha muito melhor do que List, para uma melhor eficiência.

1. Suponha que você esteja percorrendo os elementos e deseje executar muitas inserções / exclusões; O LinkedList faz isso em tempo O (n) linear, enquanto List faz isso em tempo O (n ^ 2) quadrático.
2. Suponha que você queira acessar objetos maiores repetidamente, o LinkedList se torne muito mais útil.
3. Deque () e fila () são melhor implementadas usando o LinkedList.
4. Aumentar o tamanho do LinkedList é muito mais fácil e melhor quando você lida com muitos objetos maiores.

Espero que alguém ache esses comentários úteis.

Tantas respostas médias aqui ...

Algumas implementações de lista vinculada usam blocos subjacentes de nós pré-alocados. Se eles não fizerem isso, o tempo constante / tempo linear será menos relevante, pois o desempenho da memória será ruim e o desempenho do cache ainda pior.

Use listas vinculadas quando

1) Você quer segurança da linha. Você pode criar melhores algos seguros para threads. Os custos de bloqueio dominam uma lista de estilos simultâneos.

2) Se você tem uma fila grande como estruturas e deseja remover ou adicionar qualquer lugar, exceto o final, o tempo todo. > 100K listas existem, mas não são tão comuns.

Fiz uma pergunta semelhante relacionada ao desempenho da coleção LinkedList e descobri que o implemento C # de Steven Cleary do Deque era uma solução. Diferentemente da coleção Fila, o Deque permite ativar / desativar itens na frente e atrás. É semelhante à lista vinculada, mas com desempenho aprimorado.