¿Cuándo debo usar una lista frente a una lista enlazada?

¿Cuándo es mejor usar una lista frente a una lista enlazada ?

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 aprendía, hice algunas pruebas y sentí ganas 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 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;

¡Incluso si solo accedes a los datos esencialmente, es mucho más lento! Yo digo que nunca uses una lista enlazada.

Aquí hay otra comparación que realiza muchas inserciones (planeamos insertar un elemento en el medio de la 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 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 planea insertar varios elementos y también en algún lugar tiene la referencia de dónde planea insertar el elemento, use una lista vinculada. El hecho de que tenga que insertar muchos elementos no lo hace más rápido, ya que la búsqueda de la ubicación en la que desea insertarlo lleva tiempo.

En la mayoría de los casos, List<T>es más útil. LinkedList<T>tendrá menos costo al agregar / eliminar elementos en el medio de la lista, mientras List<T>que solo puede agregar / eliminar de forma económica al final de la lista.

LinkedList<T>solo es más eficiente si está accediendo a datos secuenciales (ya sea hacia adelante o hacia atrás): el acceso aleatorio es relativamente costoso, ya que debe recorrer la cadena cada vez (por lo tanto, no tiene un indexador). Sin embargo, dado que a List<T>es esencialmente solo una matriz (con un contenedor), el acceso aleatorio está bien.

List<T>También ofrece una gran cantidad de métodos de apoyo - Find, ToArray, etc; sin embargo, estos también están disponibles para LinkedList<T>.NET 3.5 / C # 3.0 a través de métodos de extensión, por lo que eso es menos importante.

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<T>ni siquiera se implementa IList<T>. No existe un concepto real de índice en una lista vinculada, aunque parezca que sí. Ciertamente, ninguno de los métodos proporcionados en la clase acepta índices.

Las listas vinculadas pueden estar individualmente vinculadas o doblemente vinculadas. Esto se refiere a si cada elemento de la cadena tiene un enlace solo con el siguiente (vinculado individualmente) o con los elementos anteriores / siguientes (doblemente vinculados). LinkedList<T>está doblemente vinculado

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

También tienen diferentes características de rendimiento:

Adjuntar

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

Anteponer

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

Inserción

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

Eliminación

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

Contar

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

Contiene

• LinkedList<T>.Contains(item) tiempo lineal
• List<T>.Contains(item) tiempo lineal

Claro

• LinkedList<T>.Clear() tiempo lineal
• List<T>.Clear() tiempo lineal

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

Sin embargo, si necesita hacer muchas inserciones / eliminaciones desde una lista, ofrece tiempo constante. List<T>ofrece tiempo lineal, ya que los elementos adicionales en 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 de una lista vinculada contiene un puntero al siguiente miembro de la lista para insertar un miembro en la posición i:

• actualice el puntero en el miembro i-1 para que apunte al nuevo miembro
• establecer el puntero en el nuevo miembro para que apunte 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 que se encuentre el miembro deseado.

Mi respuesta anterior no fue lo suficientemente precisa. Como realmente fue horrible: D Pero ahora puedo publicar una respuesta mucho más útil y correcta.

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

Resultados cortos:

• Matriz necesita usar:

  • Tan a menudo como sea posible. Es rápido y toma el rango de RAM más pequeño para la misma cantidad de información.
  • Si sabe el recuento exacto de células necesarias
  • Si los datos se guardaron en una matriz <85000 b (85000/32 = 2656 elementos para datos enteros)
  • 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 una matriz <85000 b (85000/32 = 2656 elementos para datos enteros)
  • Si es necesario, alta velocidad de acceso aleatorio

• LinkedList necesita usar:

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

Más detalles:

Interesante saber:

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

2. LinkedList<T>es una colección basada en 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: se pueden ubicar diferentes objetos de lista en diferentes lugares de RAM. También habrá más memoria utilizada para LinkedList<T>que para List<T>o Array.

3. List<T>en .Net es la alternativa de Java de ArrayList<T>. Esto significa que este es un contenedor de matriz. Por lo tanto, se asigna en la memoria como un bloque contiguo de datos. Si el tamaño de datos asignado supera los 85000 bytes, se moverá a Montón de objetos grandes. 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 bloque contiguo único para el rendimiento de acceso aleatorio y el consumo de memoria, pero para las colecciones que necesitan cambiar regularmente el tamaño, una estructura como una matriz generalmente debe copiarse en una nueva ubicación, mientras que una lista vinculada solo necesita administrar la memoria para el recién insertado / nodos eliminados.

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

La diferencia clave viene cuando el rendimiento es importante. Por ejemplo, si está implementando la lista que tiene una operación pesada "INSERTAR", LinkedList supera a List. Dado que LinkedList puede hacerlo en tiempo O (1), 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 matriz. http://en.wikipedia.org/wiki/Linked_list and Array

Espero que esto ayude,

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

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

Suponga 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 se almacenan en una ArrayList, la iteración sobre ella y la eliminación de cadenas coincidentes requeriría miles de millones de operaciones, mientras que solo se necesitan alrededor de 100,000 operaciones mediante el uso de un iterador y el 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();
}

Cuando necesite acceso indexado incorporado, clasificación (y después de esta búsqueda binaria) y método "ToArray ()", debe usar List.

Esencialmente, un List<>en .NET es un contenedor sobre una matriz . A LinkedList<> es una lista vinculada . Entonces, la pregunta se reduce a cuál es la diferencia entre una matriz y una lista vinculada, y cuándo debe usarse una matriz en lugar de una lista vinculada. Probablemente los dos factores más importantes en su decisión de cuál usar 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 al final de la lista, este cambio no es necesario (aunque es posible que se deba cambiar el tamaño de 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 vinculadas deben atravesarse (tiempo lineal).

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

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 codigo:

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

Puede ver que los resultados están de acuerdo con el rendimiento teórico que otros han documentado aquí. Muy claro: LinkedList<T>gana mucho tiempo 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<T>tiene otras áreas donde funciona mucho mejor como el acceso aleatorio O (1).

Usar LinkedList<>cuando

1. No sabes cuántos objetos entran por la puerta de inundación. Por ejemplo, Token Stream.
2. Cuando SOLO quería eliminar \ insertar en los extremos.

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

Estoy de acuerdo con la mayoría de los puntos mencionados anteriormente. Y también estoy de acuerdo en que List parece una opció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. Suponga que está atravesando los elementos y desea realizar muchas inserciones / eliminaciones; LinkedList lo hace en tiempo lineal O (n), mientras que List lo hace en tiempo cuadrático O (n ^ 2).
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 usando LinkedList.
4. Aumentar el tamaño de LinkedList es mucho más fácil y mejor una vez que se trata de muchos y más grandes objetos.

Espero que alguien encuentre útiles estos comentarios.

Tantas respuestas promedio aquí ...

Algunas implementaciones de listas vinculadas utilizan bloques subyacentes de nodos preasignados. Si no lo hacen, el tiempo constante / tiempo lineal es menos relevante ya que el rendimiento de la memoria será deficiente y el rendimiento de la memoria caché será aún peor.

Use listas vinculadas cuando

1) Desea seguridad del hilo. Puedes construir mejores algos seguros para hilos. Los costos de bloqueo dominarán una lista de estilos concurrentes.

2) Si tiene una cola grande como estructuras y desea eliminar o agregar en cualquier lugar excepto el final todo el tiempo. > Existen 100K listas pero no son tan comunes.

Hice una pregunta similar relacionada con el rendimiento de la colección LinkedList , y descubrí que el implemento C # de Deque de Steven Cleary era una solución. A diferencia de la colección Queue, Deque permite mover elementos hacia adelante y hacia atrás. Es similar a la lista vinculada, pero con un rendimiento mejorado.