¿Cuándo debería usar una Lista frente a una Lista Vinculada?

¿Cuándo es mejor usar una Lista frente a una Lista Vinculada ?

Editar

Por favor, lea los comentarios a esta respuesta. La gente dice que no hice las pruebas adecuadas. Estoy de acuerdo en que esta no debería ser una respuesta aceptada. Mientras estaba aprendiendo hice algunas pruebas y sentí el deseo de compartirlas.

Respuesta original …

Encontré resultados interesantes:

// 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 enlazada (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; 

Incluso si solo tienes acceso a los datos, ¡es mucho más lento! Yo digo que nunca use una lista enlazada.




Aquí hay otra comparación que realiza muchas inserciones (planeamos insertar un elemento en el medio de la lista)

Lista enlazada (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 enlazada con referencia de ubicación donde insertar (.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; 

Entonces, solo si planeas insertar varios ítems y también tienes la referencia de dónde planeas insertar el ítem, entonces utiliza una lista vinculada. El hecho de que tenga que insertar muchos elementos no lo hace más rápido porque la búsqueda de la ubicación donde desea insertarla lleva tiempo.

En la mayoría de los casos, List es más útil. LinkedList tendrá un menor costo al agregar / eliminar elementos en el medio de la lista, mientras que List solo puede agregarse / eliminarse al final de la lista.

LinkedList solo es más eficiente si está accediendo a datos secuenciales (ya sea hacia adelante o hacia atrás): el acceso aleatorio es relativamente caro, ya que debe recorrer la cadena cada vez (de ahí que no tenga un indexador). Sin embargo, como una List es esencialmente solo una matriz (con un contenedor), el acceso aleatorio está bien.

List también ofrece muchos métodos de soporte: Find , ToArray , etc; sin embargo, estos también están disponibles para LinkedList con .NET 3.5 / C # 3.0 a través de métodos de extensión, por lo que es un factor menor.

Pensar en una lista vinculada como una lista puede ser un poco engañoso. Es más como una cadena. De hecho, en .NET, LinkedList ni siquiera implementa IList . No existe un concepto real de índice en una lista vinculada, aunque pueda parecer que sí existe. Ciertamente, ninguno de los métodos proporcionados en la clase acepta índices.

Las listas enlazadas pueden estar individualmente vinculadas o doblemente vinculadas. Esto se refiere a si cada elemento de la cadena tiene un enlace solo al siguiente (vinculado individualmente) o a ambos elementos anterior / siguiente (doblemente vinculados). LinkedList está doblemente vinculado.

Internamente, List está respaldado por una matriz. Esto proporciona una representación muy compacta en la memoria. Por el contrario, LinkedList implica memoria adicional para almacenar los enlaces bidireccionales entre elementos sucesivos. Por lo tanto, la huella de memoria de una LinkedList generalmente será mayor que para List (con la advertencia de que List puede tener elementos de matriz interna no utilizados para mejorar el rendimiento durante las operaciones de adición).

También tienen diferentes características de rendimiento:

Adjuntar

  • LinkedList.AddLast(item) tiempo constante
  • List.Add(item) tiempo constante amortizado, peor caso lineal

Prefijo

  • LinkedList.AddFirst(item) tiempo constante
  • List.Insert(0, item) tiempo lineal

Inserción

  • LinkedList.AddBefore(node, item) tiempo constante
  • LinkedList.AddAfter(node, item) tiempo constante
  • List.Insert(index, item) tiempo lineal

Eliminación

  • LinkedList.Remove(item) tiempo lineal
  • LinkedList.Remove(node) tiempo constante
  • List.Remove(item) tiempo lineal
  • List.RemoveAt(index) tiempo lineal

Contar

  • LinkedList.Count tiempo constante
  • List.Count tiempo constante

Contiene

  • LinkedList.Contains(item) linear time
  • List.Contains(item) tiempo lineal

Claro

  • LinkedList.Clear() tiempo lineal
  • List.Clear() tiempo lineal

Como puede ver, son en su mayoría equivalentes. En la práctica, la API de LinkedList es más engorrosa de usar, y los detalles de sus necesidades internas se dertwign en su código.

Sin embargo, si necesita hacer muchas inserciones / eliminaciones dentro de una lista, ofrece un tiempo constante. List ofrece tiempo lineal, ya que los elementos adicionales de la lista se deben barajar después de la inserción / eliminación.

Las listas vinculadas proporcionan una inserción o eliminación muy rápida de un miembro de la lista. Cada miembro en una lista vinculada contiene un puntero al siguiente miembro en la lista para insertar un miembro en la posición i:

  • actualice el puntero en el miembro i-1 para señalar al nuevo miembro
  • establecer el puntero en el nuevo miembro para apuntar al miembro i

La desventaja de una lista vinculada es que el acceso aleatorio no es posible. Acceder a un miembro requiere recorrer la lista hasta encontrar el miembro deseado.

La diferencia entre List y LinkedList radica en su implementación subyacente. List es una colección basada en arreglos (ArrayList). LinkedList es una colección basada en puntero de nodo (LinkedListNode). En el uso del nivel API, ambos son prácticamente iguales ya que ambos implementan el mismo conjunto de interfaces, como ICollection, IEnumerable, etc.

La diferencia clave se presenta cuando el rendimiento importa. Por ejemplo, si está implementando la lista que tiene una operación pesada de “INSERT”, LinkedList supera a List. Dado que LinkedList puede hacerlo en O (1) vez, pero List puede necesitar expandir el tamaño de la matriz subyacente. Para obtener más información / detalles, es posible que desee leer sobre la diferencia algorítmica entre LinkedList y las estructuras de datos de la matriz. http://en.wikipedia.org/wiki/Linked_list y matriz

Espero que esto ayude,

La principal ventaja de las listas vinculadas en las matrices es que los enlaces nos brindan la capacidad de reorganizar los elementos de manera eficiente. Sedgewick, p. 91

Mi respuesta anterior no fue lo suficientemente precisa. Realmente fue horrible: D Pero ahora puedo publicar respuestas mucho más útiles y correctas.


Hice algunas pruebas adicionales. Puede encontrar su origen en el siguiente enlace y volver a verificarlo en su entorno por su cuenta: https://github.com/ukushu/DataStructuresTestsAndOther.git

Resultados cortos:

  • Matriz necesita usar:

    • Tan a menudo como sea posible Es rápido y requiere el rango de RAM más pequeño para la misma cantidad de información.
    • Si conoce el recuento exacto de las celdas necesarias
    • Si los datos se guardaron en matriz <85000 b
    • Si es necesario, alta velocidad de acceso aleatorio
  • Lista necesita usar:

    • Si es necesario agregar celdas al final de la lista (a menudo)
    • Si es necesario agregar celdas al principio / medio de la lista (NO A MENUDO)
    • Si los datos se guardaron en matriz <85000 b
    • Si es necesario, alta velocidad de acceso aleatorio
  • LinkedList necesita usar:

    • Si es necesario para agregar celdas al principio / medio / final de la lista (a menudo)
    • Si es necesario solo acceso secuencial (hacia adelante / hacia atrás)
    • Si necesita guardar artículos GRANDES, pero el número de artículos es bajo.
    • Mejor no utilizar para una gran cantidad de elementos, ya que es utilizar memoria adicional para enlaces.

Más detalles:

введите сюда описание изображения Interesante saber:

  1. La Lista Vinculada internamente no es una Lista en .NET. LinkedList . Incluso no implementa IList . Y es por eso que hay índices y métodos ausentes relacionados con los índices.

  2. LinkedList es una colección basada en un puntero de nodo. En .NET está en implementación doblemente vinculada. Esto significa que los elementos anteriores / siguientes tienen un enlace al elemento actual. Y los datos están fragmentados: diferentes objetos de lista pueden ubicarse en diferentes lugares de RAM. También se usará más memoria para LinkedList que para List o Array.

  3. List en .Net es la alternativa de Java de ArraList . Esto significa que esta es una envoltura de matriz. Por lo tanto, se asigna en menory como un bloque contiguo de datos. Si el tamaño de los datos asignados excede los 85000 bytes, se asignará a iside del Gran montón de objetos. Dependiendo del tamaño, esto puede conducir a la fragmentación del montón, una forma leve de pérdida de memoria. Pero al mismo tiempo, si el tamaño es <85000 bytes, esto proporciona una representación muy compacta y de acceso rápido en la memoria.

  4. Se prefiere un solo bloque contiguo para el rendimiento de acceso aleatorio y el consumo de memoria, pero para las colecciones que necesitan cambiar de tamaño regularmente una estructura como una matriz generalmente necesita copiarse a una nueva ubicación, mientras que una lista vinculada solo necesita administrar la memoria para el recién insertado / nodos eliminados.

Una circunstancia común para utilizar LinkedList es así:

Supongamos que desea eliminar muchas cadenas determinadas de una lista de cadenas con un tamaño grande, digamos 100,000. Las cadenas para eliminar se pueden buscar en HashSet dic, y se cree que la lista de cadenas contiene entre 30,000 y 60,000 cadenas para eliminar.

Entonces, ¿cuál es el mejor tipo de Lista para almacenar las 100,000 Cadenas? La respuesta es LinkedList. Si están almacenados en una ArrayList, al iterar sobre ella y eliminar Strings coincidentes se necesitarán miles de millones de operaciones, mientras que solo se requieren unas 100.000 operaciones mediante el uso de un iterador y el 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(); } 

Cuando necesite acceso indexado incorporado, clasificación (y después de esta búsqueda binaria) y método “ToArray ()”, debería usar List.

Esto está adaptado de la respuesta aceptada de Tono Nam corrigiendo algunas mediciones incorrectas en él.

La prueba:

 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); } 

Y el 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(); } } } 

Puede ver que los resultados están de acuerdo con el rendimiento teórico que otros han documentado aquí. Muy claro: LinkedList gana mucho en caso de inserciones. No he probado la eliminación del medio de la lista, pero el resultado debería ser el mismo. Por supuesto, List tiene otras áreas en las que se comporta mucho mejor, como O (1) acceso aleatorio.

Esencialmente, una List<> en .NET es un contenedor sobre una matriz . Una LinkedList<> es una lista vinculada . De modo que la pregunta se reduce a cuál es la diferencia entre una matriz y una lista vinculada, y cuándo se debe usar una matriz en lugar de una lista vinculada. Probablemente los dos factores más importantes en su decisión de utilizar se reducirían a:

  • Las listas vinculadas tienen un rendimiento de inserción / eliminación mucho mejor, siempre que las inserciones / eliminaciones no estén en el último elemento de la colección. Esto se debe a que una matriz debe desplazar todos los elementos restantes que vienen después del punto de inserción / eliminación. Sin embargo, si la inserción / eliminación se encuentra en el extremo final de la lista, este cambio no es necesario (aunque es posible que sea necesario redimensionar la matriz, si se excede su capacidad).
  • Las matrices tienen capacidades de acceso mucho mejores. Las matrices se pueden indexar directamente (en tiempo constante). Las listas enlazadas deben atravesarse (tiempo lineal).

Use LinkedList<> cuando

  1. No sabe cuántos objetos están entrando por la compuerta de inundación. Por ejemplo, Token Stream .
  2. Cuando SOLAMENTE quería eliminar \ inserte en los extremos.

Para todo lo demás, es mejor usar List<> .

Tantas respuestas promedio aquí …

Algunas implementaciones de listas enlazadas usan bloques subyacentes de nodos asignados previamente. Si no hacen esto, el tiempo constante / tiempo lineal es menos relevante ya que el rendimiento de la memoria será pobre y el rendimiento del caché será aún peor.

Use listas enlazadas cuando

1) Quieres seguridad de hilo. Puedes construir mejores algos seguros para hilos. Los costos de locking dominarán una lista de estilos simultáneos.

2) Si tiene una cola grande como estructuras y quiere eliminar o agregar en cualquier lugar pero el final todo el tiempo. > Las listas de 100K existen, pero no son tan comunes.

Hice una pregunta similar relacionada con el rendimiento de la colección LinkedList , y descubrí que el instrumento C # de Steven Cleary para Deque era una solución. A diferencia de la colección Queue, Deque permite activar / desactivar elementos de frente y atrás. Es similar a la lista vinculada, pero con un mejor rendimiento.

Estoy de acuerdo con la mayoría del punto mencionado anteriormente. Y también estoy de acuerdo en que List parece una elección más obvia en la mayoría de los casos.

Pero, solo quiero agregar que hay muchas instancias en las que LinkedList es una opción mucho mejor que List para una mejor eficiencia.

  1. Supongamos que atraviesa los elementos y desea realizar muchas inserciones / eliminaciones; LinkedList lo hace en tiempo O (n) lineal, mientras que List lo hace en tiempo O (n ^ 2) cuadrático.
  2. Supongamos que desea acceder a objetos más grandes una y otra vez, LinkedList se vuelve mucho más útil.
  3. Deque () y queue () se implementan mejor utilizando LinkedList.
  4. Aumentar el tamaño de LinkedList es mucho más fácil y mejor una vez que se trata de muchos objetos más grandes.

Espero que alguien encuentre útiles estos comentarios.