Cuándo debo usar una Lista vs una Lista enlazada

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 que List<T> solo puede agregar/eliminar a bajo costo 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 caro, ya que debe caminar por la cadena cada vez (por lo tanto, no tiene un indexador). Sin embargo, porque un List<T> es esencialmente sólo una matriz (con un envoltorio) el acceso aleatorio está bien.

List<T> también ofrece una gran cantidad de 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 menos de un factor.

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 existe un concepto real de índice en una lista enlazada, aunque pueda parecer que hay. Ciertamente ninguno de los métodos proporcionados en la clase acepta índices.

Las listas enlazadas pueden estar enlazadas por separado, o doblemente enlazadas. Esto se refiere a si cada elemento de la cadena tiene un enlace solo al siguiente (enlazado individualmente) o a ambos, el anterior / siguiente elementos (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 un LinkedList<T> generalmente será mayor que la de List<T> (con la advertencia de que List<T> puede tener elementos internos de matriz sin usar para mejorar el rendimiento durante las operaciones de anexar.)

Tienen diferentes características de rendimiento también:

Añadir

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

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) constante time
• List<T>.Insert(index, item) tiempo lineal

Remoció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) lineal time
• 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 engorrosa de usar, y los detalles de sus necesidades internas se derraman en su código.

Sin embargo, si necesita hacer muchas inserciones/eliminaciones dentro de una lista, ofrece tiempo constante. List<T> ofrece tiempo lineal, como elementos adicionales en la lista deben ser barajados después de la inserción / eliminación.

Las listas enlazadas proporcionan una inserción o eliminación muy rápida de un miembro de la lista. Cada miembro de una lista enlazada contiene un puntero al siguiente miembro de la lista, por lo que para insertar un miembro en la posición i:

• actualice 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 recorrer la lista hasta que el miembro encontrado.

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

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

Espero que esta ayuda,

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

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 comprobarlo en su entorno por su cuenta: https://github.com/ukushu/DataStructuresTestsAndOther.git

Resultados cortos:

• La matriz necesita usar:

  • Tan a menudo como sea posible. Es rápido y toma el más pequeño Rango de RAM para la misma cantidad de información.
  • Si usted sabe el recuento exacto de células necesarias
  • Si los datos se guardan en una matriz
  • Si es necesario alta velocidad de acceso aleatorio

• List 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 guardan en una matriz
  • Si es necesario Acceso aleatorio alto velocidad

• 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 objetos GRANDES, pero el número de objetos es bajo.
  • Mejor no usar para gran cantidad de elementos, ya que es usar memoria adicional para enlaces.

Más detalles:

Interesante para saber:

1. La Lista enlazada internamente no es una Lista en .NET. LinkedList<T>. Incluso no implementa IList<T>. Y es por eso que no hay índices y métodos 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 prior/next tienen un enlace al elemento actual. Y los datos están fragmentados different diferentes objetos de la lista se pueden ubicar en diferentes lugares de RAM. También habrá más memoria utilizada para LinkedList<T> que para List<T> o Matriz.

3. List<T> en. Net es la alternativa de Java de ArraList<T>. Esto significa que esto es envoltura de matriz. Por lo que se asigna en Menory como un bloque contiguo de datos. Si el tamaño de los datos asignados supera los 85000 bytes, se asignará iside del 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

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 debe copiarse a una nueva ubicación, mientras que una lista vinculada solo necesita administrar la memoria para los nodos recién insertados/eliminados.

Una circunstancia común para usar LinkedList es como esta:

Supongamos que desea eliminar muchas cadenas ciertas de una lista de cadenas con un tamaño grande, digamos 100,000. Las cadenas a eliminar se pueden buscar en el HashSet dic, y se cree que la lista de cadenas contiene entre 30.000 y 60.000 cadenas a 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, entonces iterando sobre ella y la eliminación de las cadenas coincidentes debería tomar a miles de millones de operaciones, mientras que toma solo 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, ordenación (y después de esta búsqueda binaria), y el método "toArray ()", debe usar List.

Esto es una adaptación de la respuesta aceptada de Tono Nam corrigiendo algunas mediciones erróneas 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 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í. Bastante claro - LinkedList<T> gana mucho tiempo en caso de inserciones. No he probado para la eliminación de la mitad de la lista, pero el resultado debe ser el mismo. Por supuesto List<T> tiene otras áreas donde funciona mucho mejor como O (1) acceso aleatorio.

Esencialmente, un List<>en.NET es una envoltura sobre una matriz . A LinkedList<> es una lista enlazada . Así que la pregunta se reduce a, ¿cuál es la diferencia entre una matriz y una lista vinculada, y cuando se debe utilizar una matriz en lugar de una lista vinculada. Probablemente los dos factores más importantes en su decisión de cual usar vendría a:

• Las listas enlazadas tienen mucho mejor rendimiento de inserción / eliminación, siempre y cuando las inserciones / eliminaciones no estén en el último elemento de 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 está al final de la lista, este cambio no es necesario (aunque el array puede necesitar ser redimensionado, si se excede su capacidad).
• Los arrays tienen capacidades de acceso mucho mejores. Los arrays se pueden indexar directamente (en tiempo constante). Las listas enlazadas deben ser recorridas (tiempo lineal).

Use LinkedList<> cuando

1. No sabes cuántos objetos están entrando por la puerta de inundación. Por ejemplo, Token Stream.
2. Cuando solo quería eliminar\insert al final.

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

Tantas respuestas promedio aquí...

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

Usar listas enlazadas cuando

1) Desea seguridad de hilo. Puede construir mejores algos seguros de hilo. 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 menos el final todo el tiempo . Las listas >100K existen 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 Steven Cleary de Deque era una solución. A diferencia de la colección de cola, Deque permite mover elementos de encendido/apagado por delante y por detrás. Es similar a la lista vinculada, pero con un rendimiento mejorado.

Estoy de acuerdo con la mayor parte del punto anterior. 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 donde LinkedList son mucho mejor opción que la Lista para una mejor eficiencia.

1. Supongamos 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 si 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 y más grandes objetos.

Espero que alguien encuentre útiles estos comentarios.