Quando devo usar uma lista versus uma lista de links

Editar

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

Resposta original …

Eu 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 list = new LinkedList(); 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 list = new List(); // 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 dados, essencialmente, é muito mais lento! Eu digo nunca use um linkedList.

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

Lista vinculada (51 segundos)

  LinkedList list = new LinkedList(); 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 list = new List(); 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 tendo referência de localização 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 em algum lugar você tem a referência de onde planeja inserir o item, use uma linked list. Só porque você tem que inserir muitos itens, isso não faz com que seja mais rápido, porque pesquisar o local onde você deseja inseri-lo leva tempo.

Na maioria dos casos, List é mais útil. LinkedList terá menos custo ao adicionar / remover itens no meio da lista, enquanto List só pode adicionar / remover de maneira barata no final da lista.

LinkedList é apenas o mais eficiente se você estiver acessando dados sequenciais (para frente ou para trás) – o access random é relativamente caro, já que ele deve percorrer a cadeia a cada vez (daí porque não tem um indexador). No entanto, porque um List é essencialmente apenas uma matriz (com um wrapper) o access random é bom.

List também oferece muitos methods de suporte – Find , ToArray , etc; no entanto, estes também estão disponíveis para LinkedList com o .NET 3.5 / C # 3.0 por meio de methods de extensão – de modo que é menos um fator.

Pensar em uma linked list como uma lista pode ser um pouco enganoso. É mais como uma corrente. Na verdade, no .NET, LinkedList nem sequer implementa IList . Não existe um conceito real de índice em uma linked list, mesmo que pareça existir. Certamente nenhum dos methods fornecidos na class aceita índices.

Listas vinculadas podem ser ligadas individualmente ou duplamente ligadas. Isso se refere a se cada elemento na cadeia tem um link apenas para o próximo (ligado separadamente) ou para os elementos anterior / seguinte (duplamente vinculados). LinkedList está duplamente ligado.

Internamente, List é apoiado por um array. Isso fornece uma representação muito compacta na memory. Por outro lado, LinkedList envolve memory adicional para armazenar os links bidirecionais entre elementos sucessivos. Portanto, o footprint de memory de um LinkedList geralmente será maior do que para List (com a ressalva de que o List pode ter elementos de array internos não utilizados para melhorar o desempenho durante operações de append).

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

Acrescentar

• Tempo de constante LinkedList.AddLast(item)
• List.Add(item) tempo constante amortizado, pior caso linear

Prefender

• Tempo constante de LinkedList.AddFirst(item)
• List.Insert(0, item) tempo linear

Inserção

• Tempo de constante LinkedList.AddBefore(node, item)
• Tempo constante de LinkedList.AddAfter(node, item)
• List.Insert(index, item) tempo linear List.Insert(index, item)

Remoção

• Tempo linear LinkedList.Remove(item)
• Tempo de constante LinkedList.Remove(node)
• List.Remove(item) tempo linear
• List.RemoveAt(index) tempo linear

Contagem

• LinkedList.Count constante de LinkedList.Count
• List.Count tempo constante da constante List.Count

Contém

• LinkedList.Contains(item) tempo linear
• List.Contains(item) tempo linear

Claro

• Tempo linear LinkedList.Clear()
• List.Clear() tempo linear List.Clear()

Como você pode ver, eles são na maior parte equivalentes. Na prática, a API de LinkedList é mais complicada de usar, e os detalhes de suas necessidades internas se espalham em seu código.

No entanto, se você precisar fazer muitas inserções / remoções de dentro de uma lista, ela oferece tempo constante. List oferece tempo linear, uma vez que os itens extras na lista devem ser aleatoriamente distribuídos após a inserção / remoção.

Listas vinculadas fornecem inserção ou exclusão muito rápida de um membro da lista. Cada membro em uma linked list contém um ponteiro para o próximo membro da lista, de modo a inserir um membro na posição i:

• atualizar o ponteiro no membro i-1 para apontar para o novo membro
• definir o ponteiro no novo membro para apontar para o membro i

A desvantagem de uma linked list é que o access random não é possível. Acessar um membro requer atravessar a lista até que o membro desejado seja encontrado.

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

A principal diferença vem quando o desempenho é importante. Por exemplo, se você estiver implementando a lista que possui operação “INSERT” pesada, o LinkedList supera a Lista. Desde LinkedList pode fazê-lo na hora O (1), mas a lista pode precisar expandir o tamanho da matriz subjacente. Para mais informações / detalhes, você pode querer ler a diferença algorítmica entre as estruturas de dados LinkedList e array. http://en.wikipedia.org/wiki/Linked_list and Array

Espero que essa ajuda,

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

Minha resposta anterior não foi suficiente. Como verdadeiramente foi horrível: D Mas agora posso postar uma resposta muito mais útil e correta.

Eu fiz alguns testes adicionais. Você pode encontrá-lo pelo seguinte link e verificá-lo novamente em seu ambiente: https://github.com/ukushu/DataStructuresTestsAndOther.git

Resultados curtos:

• Array precisa usar:

  • Tão frequentemente quanto possível. É rápido e leva o menor intervalo de RAM para informações de mesma quantidade.
  • Se você sabe a contagem exata de células necessárias
  • Se os dados salvos na matriz <85000 b
  • Se necessário alta velocidade de access random

• Lista precisa usar:

  • Se necessário, adicionar células ao final da lista (geralmente)
  • Se necessário para adicionar células no início / meio da lista (NÃO OFENDE)
  • Se os dados salvos na matriz <85000 b
  • Se necessário alta velocidade de access random

• LinkedList precisa usar:

  • Se necessário, adicionar células no início / meio / fim da lista (geralmente)
  • Se necessário, apenas access sequencial (frente / trás)
  • Se você precisar salvar itens GRANDES, mas a contagem de itens é baixa.
  • Melhor não usar para grande quantidade de itens, pois é usar memory adicional para links.

Mais detalhes:

Interessante saber:

1. Lista vinculada internamente não é uma lista no .NET. LinkedList . É mesmo não implementa IList . E é por isso que existem índices e methods ausentes relacionados a índices.

2. LinkedList é coleção baseada em ponteiro de nó. No .NET, está em implementação duplamente vinculada. Isso significa que os elementos anterior / próximo têm link para o elemento atual. E os dados são fragmentados – diferentes objects de lista podem ser localizados em diferentes locais da RAM. Também haverá mais memory usada para LinkedList que para List ou Array.

3. List no .net é a alternativa de ArraList do Java. Isso significa que esse é o wrapper de matriz. Então, é alocado em menory como um bloco contíguo de dados. Se o tamanho dos dados alocados exceder 85000 bytes, ele será alocado no iside da pilha de objects grandes. Dependendo do tamanho, isso pode levar à fragmentação de pilha, uma forma leve de memory leaks. Mas, ao mesmo tempo, se tamanho <85000 bytes - isso fornece uma representação muito compacta e de acesso rápido na memória.

4. Um único bloco contíguo é preferível para desempenho de access random e consumo de memory, mas para collections que precisam alterar o tamanho regularmente, uma estrutura como Array geralmente precisa ser copiada para um novo local, enquanto uma linked list precisa apenas gerenciar a memory para o recém-inserido. / nós excluídos.

Uma circunstância comum para usar LinkedList é assim:

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

Então, qual é o melhor tipo de lista para armazenar as 100.000 cordas? A resposta é LinkedList. Se eles forem armazenados em uma ArrayList, então iterá-la e remover as cadeias de caracteres correspondentes, o que deve levar bilhões de operações, enquanto são necessárias apenas cerca de 100.000 operações usando um iterador e o método remove ().

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

Quando você precisar de access indexado interno, sorting (e após essa pesquisa binária) e método “ToArray ()”, use Lista.

Isto é adaptado da resposta aceita de Tono Nam , corrigindo algumas medições 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 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(); 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(); 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(); 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(); 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(query); var watch = Stopwatch.StartNew(); foreach (var item in list) { } watch.StopAndPrint(); } public static void Enumerate_LinkedList() { var list = new LinkedList(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(); 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(); var watch = Stopwatch.StartNew(); LinkedListNode 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(); 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(); 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. Bastante claro - LinkedList ganha muito tempo no caso de inserções. Eu não testei para remoção do meio da lista, mas o resultado deve ser o mesmo. É claro que a List tem outras áreas onde ela se comporta melhor como O (1) access random.

Essencialmente, uma List<> no .NET é um wrapper sobre uma matriz . Uma LinkedList<> é uma linked list . Portanto, a questão se resume a qual é a diferença entre uma matriz e uma linked list e quando deve ser usada uma matriz em vez de uma linked list. Provavelmente, os dois fatores mais importantes na sua decisão de usar seriam:

• As listas vinculadas têm melhor desempenho de inserção / remoção, desde que as inserções / remoções não estejam no último elemento da coleção. Isso ocorre porque uma matriz deve deslocar 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 é necessária (embora a matriz precise ser redimensionada, se a capacidade for excedida).
• Arrays têm capacidades de access muito melhores. Os arrays podem ser indexados diretamente (em tempo constante). Listas vinculadas devem ser percorridas (tempo linear).

Use LinkedList<> quando

1. Você não sabe quantos objects estão chegando através do portão de inundação. Por exemplo, Token Stream .
2. Quando você só queria apagar \ inserir nas extremidades.

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

Tantas respostas médias aqui …

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

Use listas vinculadas quando

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

2) Se você tem uma grande fila como estruturas e quer remover ou adicionar em qualquer lugar, mas o fim o tempo todo. > 100 mil 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 era uma solução. Ao contrário da coleção Queue, Deque permite mover itens on / off frente e verso. É semelhante à linked list, mas com desempenho aprimorado.

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

Mas, só quero acrescentar que há muitas instâncias em que o LinkedList é uma opção muito melhor do que o List para uma melhor eficiência.

1. Suponha que você esteja percorrendo os elementos e queira executar muitas inserções / exclusões; LinkedList faz isso no tempo linear O (n), enquanto List faz no tempo quadrático O (n ^ 2).
2. Suponha que você queira acessar objects maiores de novo e de novo, o LinkedList se torna muito mais útil.
3. Deque () e queue () são melhor implementados usando LinkedList.
4. Aumentar o tamanho de LinkedList é muito mais fácil e melhor quando você está lidando com muitos objects maiores.

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