c# - listas - ¿Cuándo debo usar una lista frente a una lista enlazada?

ejemplos de listas simples en c#

Question

¿Cuándo es mejor usar una List frente a una LinkedList ?

Answer 1

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 debe 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 enlazada (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, 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 centro de la lista)

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

Por lo tanto, solo si planea insertar varios elementos y también tiene una 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 porque buscar el lugar donde desea insertarlo lleva tiempo.

Answer 2

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

Answer 3

En la mayoría de los casos, la List<T> es más útil. LinkedList<T> tendrá un costo menor al agregar / eliminar elementos en la mitad de la lista, mientras que List<T> 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 (hacia adelante o hacia atrás). El acceso aleatorio es relativamente caro ya que debe recorrer la cadena cada vez (por lo tanto, no tiene un indexador). Sin embargo, debido a que una List<T> es esencialmente una matriz (con un envoltorio), el acceso aleatorio está bien.

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

Answer 4

Esencialmente, una List<> en .NET es una envoltura sobre una matriz . Un LinkedList<> es una lista enlazada . Entonces, la pregunta se reduce a cuál es la diferencia entre una matriz y una lista vinculada, y cuándo se debe utilizar una matriz en lugar de una lista vinculada. Probablemente los dos factores más importantes en su decisión de 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 / extracció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 enlazadas deben ser atravesadas (tiempo lineal).

Answer 5

Esto se adaptó de la respuesta aceptada de Tono Nam corrigiendo algunas mediciones incorrectas en ella.

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 
{
    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í. Bastante claro: LinkedList<T> gana mucho tiempo en caso de inserciones. No he probado la eliminación de la mitad de la lista, pero el resultado debería ser el mismo. Por supuesto, la List<T> tiene otras áreas en las que se desempeña mejor como el acceso aleatorio O (1).

Answer 6

Estoy de acuerdo con la mayoría de los puntos mencionados anteriormente. Y también estoy de acuerdo en que la Lista parece una opción más obvia en la mayoría de los casos.

Pero, solo quiero añadir que hay muchos casos en los que LinkedList es una opción mucho mejor que List para una mejor eficiencia.

1. Supongamos que está atravesando los elementos y desea realizar muchas inserciones / borrados; 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 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 objetos más grandes.

Espero que alguien encuentre estos comentarios útiles.

Answer 7

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 de colas, Deque permite mover elementos en el frente y la parte posterior. Es similar a la lista enlazada, pero con un rendimiento mejorado.

Answer 8

La diferencia entre List y LinkedList radica en su implementación subyacente. La lista es una colección basada en arreglos (ArrayList). LinkedList es una colección basada en puntero de nodo (LinkedListNode). En el nivel de uso de la 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 importa. Por ejemplo, si está implementando la lista que tiene una pesada operación de "INSERTAR", LinkedList supera a la lista. Ya que LinkedList puede hacerlo en O (1), pero List puede necesitar expandir el tamaño de la matriz subyacente. Para obtener más información / detalles, puede leer 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,

Answer 9

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

Answer 10

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:

• actualizar el puntero en el miembro i-1 para que apunte al nuevo miembro
• establece el puntero en el nuevo miembro para que apunte al miembro i

La desventaja de una lista enlazada es que el acceso aleatorio no es posible. El acceso a un miembro requiere atravesar la lista hasta que se encuentre el miembro deseado.

Answer 11

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 origen en el siguiente enlace y volver a verificarlo en su entorno por su cuenta: https://github.com/ukushu/DataStructuresTestsAndOther.git

Resultados cortos:

• Array 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 conoces el recuento exacto de células necesarias
  • Si los datos se guardan en matriz <85000 b
  • Si es necesario alta velocidad de acceso aleatorio

• Lista necesita utilizar:

  • Si es necesario agregar celdas al final de la lista (a menudo)
  • Si es necesario agregar celdas al principio / en la mitad de la lista (NO A menudo)
  • Si los datos se guardan en matriz <85000 b
  • 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 número de elementos es bajo.
  • Mejor no usar para gran cantidad de elementos, ya que se usa memoria adicional para enlaces.

Más detalles:

Interesante saber:

1. LinkedList<T> internamente no es una lista en .NET. Incluso no 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 enlazada. Esto significa que los elementos anteriores / siguientes tienen un enlace al elemento actual. Y los datos están fragmentados: los diferentes objetos de la lista pueden ubicarse en diferentes lugares de la 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 ArrayList<T> Java. Esto significa que esto es envoltura de matriz. Así que se asigna en la memoria como un bloque de datos contiguos. Si el tamaño de los datos asignados supera los 85000 bytes, se moverá a Large Object Heap. Dependiendo del tamaño, esto puede llevar 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 el tamaño regularmente, una estructura como una matriz generalmente se debe copiar a una nueva ubicación, mientras que una lista vinculada solo necesita administrar la memoria para la nueva inserción / Nodos eliminados.

Answer 12

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

Las listas enlazadas pueden estar enlazadas individualmente, o doblemente vinculadas. Esto se refiere a si cada elemento de la cadena tiene un enlace solo al siguiente (enlace simple) o al elemento anterior / siguiente (enlace doble). LinkedList<T> está doblemente vinculado.

Internamente, la List<T> está respaldada 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 una lista LinkedList<T> generalmente será mayor que para la List<T> (con la advertencia de que la List<T> puede tener elementos de matriz interna no utilizados para mejorar el rendimiento durante las operaciones de adición).

Tienen diferentes características de rendimiento también:

Adjuntar

• LinkedList<T>.AddLast(item) tiempo constante
• List<T>.Add(item) tiempo constante amortizado, en el peor de los casos lineales

Prepend

• 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 puedes ver, son en su mayoría equivalentes. En la práctica, la API de LinkedList<T> es más incómoda de usar, y los detalles de sus necesidades internas se extienden a su código.

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

Answer 13

Tantas respuestas promedio aquí ...

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

Usa listas enlazadas cuando

1) Quieres hilo de seguridad. Puedes construir mejores algos de hilo seguro. 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. > 100K listas existen pero no son tan comunes.

Answer 14

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

Supongamos que desea eliminar muchas cadenas determinadas de una lista de cadenas con un tamaño grande, por ejemplo, 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 cuerdas? La respuesta es LinkedList. Si se almacenan en un ArrayList, iterando sobre él y eliminando Strings coincidentes debería llevar a miles de millones de operaciones, mientras que toma alrededor de 100,000 operaciones utilizando 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();
}

Answer 15

Usa LinkedList<> cuando

1. No sabes cuántos objetos vienen por la puerta de la inundación. Por ejemplo, Token Stream .
2. Cuando SOLO quisiste borrar / insert en los extremos.

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