arrays - diferencia - linkedlist vs list

¿Cuándo usar una lista vinculada en una matriz/matriz?

Question

Uso una gran cantidad de listas y matrices, pero todavía tengo que encontrar un escenario en el que la lista de matrices no se pueda usar tan fácilmente como, si no más fácil, que la lista vinculada. Esperaba que alguien pudiera darme algunos ejemplos de cuándo la lista vinculada es notablemente mejor.

Answer 1

1) Como se explicó anteriormente, las operaciones de inserción y eliminación ofrecen un buen rendimiento (O (1)) en LinkedList en comparación con ArrayList (O (n)). Por lo tanto, si hay un requisito de adición y eliminación frecuente en la aplicación, LinkedList es la mejor opción.

2) Las operaciones de búsqueda (obtener método) son rápidas en Arraylist (O (1)) pero no en LinkedList (O (n)), por lo que si hay menos operaciones de agregar y eliminar y más requisitos de búsqueda, ArrayList sería su mejor opción.

Answer 2

Creo que la principal diferencia es si con frecuencia necesita insertar o eliminar cosas de la parte superior de la lista.

Con una matriz, si elimina algo de la parte superior de la lista, la complejidad es o (n) porque todos los índices de los elementos de la matriz tendrán que cambiar.

Con una lista enlazada, es o (1) porque solo necesita crear el nodo, reasignar el encabezado y asignar la referencia a la siguiente como encabezado anterior.

Cuando inserte o elimine con frecuencia al final de la lista, las matrices son preferibles porque la complejidad será o (1), no es necesario reindexar, pero para una lista vinculada será o (n) porque debe pasar del encabezado al último nodo.

Creo que la búsqueda tanto en la lista vinculada como en las matrices será o (log n) porque probablemente utilizará una búsqueda binaria.

Answer 3

Esas son las implementaciones usadas más comunes de Collection.

Lista de arreglo:

• insertar / eliminar al final generalmente O (1) peor caso O (n)

• insertar / eliminar en el medio O (n)

• recuperar cualquier posición O (1)

Lista enlazada:

• insertar / eliminar en cualquier posición O (1) (tenga en cuenta si tiene una referencia al elemento)

• recuperar en el medio O (n)

• recuperar el primer o último elemento O (1)

Vector: no lo use. Es una implementación anterior similar a ArrayList pero con todos los métodos sincronizados. No es el enfoque correcto para una lista compartida en un entorno de subprocesos múltiples.

HashMap

insertar / borrar / recuperar por clave en O (1)

TreeSet insert / delete / contains en O (log N)

HashSet insert / remove / contains / size en O (1)

Answer 4

Hice algunos benchmarking y descubrí que la clase de lista es en realidad más rápida que LinkedList para la inserción aleatoria:

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 20000;
            Random rand = new Random(12345);

            Stopwatch watch = Stopwatch.StartNew();
            LinkedList<int> ll = new LinkedList<int>();
            ll.AddLast(0);
            for (int i = 1; i < count; i++)
            {
                ll.AddBefore(ll.Find(rand.Next(i)),i);

            }
            Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds);

            watch = Stopwatch.StartNew();
            List<int> list = new List<int>();
            list.Add(0);
            for (int i = 1; i < count; i++)
            {
                list.Insert(list.IndexOf(rand.Next(i)), i);

            }
            Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds);

            Console.ReadLine();
        }
    }
}

Se necesitan 900 ms para la lista vinculada y 100ms para la clase de lista.

Crea listas de números enteros posteriores. Cada nuevo entero se inserta después de un número aleatorio que ya está en la lista. Tal vez la clase List use algo mejor que solo una matriz.

Answer 5

Hmm, Arraylist se puede usar en casos como los siguientes, supongo:

1. no estás seguro de cuántos elementos estarán presentes
2. pero necesita acceder a todos los elementos al azar a través de la indexación

Por ejemplo, necesita importar y acceder a todos los elementos en una lista de contactos (cuyo tamaño le es desconocido)

Answer 6

La ventaja de las listas aparece si necesita insertar elementos en el medio y no desea comenzar a cambiar el tamaño de la matriz y cambiar las cosas.

Estás en lo correcto en que esto no suele ser el caso. He tenido algunos casos muy específicos como ese, pero no demasiados.

Answer 7

Las matrices tienen O (1) acceso aleatorio, pero es realmente costoso agregar cosas o eliminarlas.

Las listas enlazadas son realmente baratas para agregar o eliminar elementos en cualquier lugar y para iterar, pero el acceso aleatorio es O (n).

Answer 8

Para agregar a las otras respuestas, la mayoría de las implementaciones de listas de arreglos reservan capacidad adicional al final de la lista para que los nuevos elementos puedan agregarse al final de la lista en O (1) tiempo. Cuando se excede la capacidad de una lista de matriz, se asigna internamente una matriz nueva y más grande y se copian todos los elementos antiguos. Por lo general, la nueva matriz es el doble del tamaño de la anterior. Esto significa que, en promedio , agregar nuevos elementos al final de una lista de arreglos es una operación O (1) en estas implementaciones. Por lo tanto, incluso si no conoce la cantidad de elementos por adelantado, una lista de matriz puede ser más rápida que una lista vinculada para agregar elementos, siempre que los agregue al final. Obviamente, la inserción de nuevos elementos en ubicaciones arbitrarias en una lista de arreglos sigue siendo una operación O (n).

El acceso a elementos en una lista de matriz también es más rápido que una lista vinculada, incluso si los accesos son secuenciales. Esto se debe a que los elementos de la matriz se almacenan en la memoria contigua y se pueden guardar en la memoria caché fácilmente. Los nodos de la lista enlazada se pueden dispersar potencialmente en muchas páginas diferentes.

Yo recomendaría solo usar una lista vinculada si sabe que va a insertar o eliminar elementos en ubicaciones arbitrarias. Las listas de matrices serán más rápidas para casi todo lo demás.

Answer 9

Todo depende del tipo de operación que se realice durante la iteración, todas las estructuras de datos tienen una relación de intercambio entre tiempo y memoria y, según nuestras necesidades, debemos elegir el DS correcto. Entonces, hay algunos casos en los que LinkedList es más rápido que array y viceversa. Considere las tres operaciones básicas en estructuras de datos.

• buscando

Dado que la matriz es una estructura de datos basada en índice, la búsqueda array.get (índice) tomará O (1) vez que la lista enlazada no es índice DS, por lo que tendrá que desplazarse hasta el índice, donde el índice <= n, n es el tamaño de la lista vinculada. por lo que la matriz es más rápida en la lista vinculada cuando tiene acceso aleatorio a los elementos.

Q. Entonces, ¿cuál es la belleza detrás de esto?

Como las matrices son bloques de memoria contiguos, grandes trozos de ellos se cargarán en la memoria caché al acceder por primera vez, lo que hace que sea relativamente rápido acceder a los elementos restantes de la matriz, tanto como accedamos a los elementos en la matriz falla, la localidad de caché se refiere a las operaciones que están en la memoria caché y, por lo tanto, se ejecutan mucho más rápido que en la memoria, básicamente, en la matriz, maximizamos las posibilidades de acceso secuencial a los elementos en la caché. Si bien las listas vinculadas no están necesariamente en bloques contiguos de memoria, no hay garantía de que los elementos que aparecen secuencialmente en la lista estén dispuestos cerca uno del otro en la memoria, esto significa menos caché, por ejemplo, más fallas en la memoria caché porque necesitamos leer de memoria por cada acceso al elemento de la lista enlazada, lo que aumenta el tiempo de acceso y el rendimiento degradado, por lo que si realizamos más operaciones de acceso aleatorio, como buscar, la matriz será rápida, como se explica a continuación.

• Inserción

Esto es fácil y rápido en LinkedList ya que la inserción es O (1) operación en LinkedList (en Java) en comparación con la matriz, considere el caso cuando la matriz está llena, necesitamos copiar el contenido a la nueva matriz si ésta se llena lo que hace que insertar una elemento en ArrayList de O (n) en el peor de los casos, mientras ArrayList también necesita actualizar su índice si inserta algo en cualquier lugar excepto al final de la matriz, en caso de lista enlazada no necesitamos cambiar el tamaño, solo necesita actualizar punteros.

• Supresión

Funciona como inserciones y mejor en LinkedList que en la matriz.

Answer 10

Utilice la lista vinculada para ordenar por encima de matrices y para operaciones polinomiales.

Answer 11

Las listas vinculadas son preferibles sobre las matrices cuando:

a) necesita inserciones / eliminaciones de tiempo constante de la lista (como en la informática en tiempo real donde la previsibilidad del tiempo es absolutamente crítica)

b) no sabe cuántos elementos habrá en la lista. Con las matrices, es posible que necesite volver a declarar y copiar la memoria si la matriz crece demasiado

c) no necesita acceso aleatorio a ningún elemento

d) desea poder insertar elementos en el medio de la lista (como una cola de prioridad)

Las matrices son preferibles cuando:

a) necesitas acceso indexado / aleatorio a los elementos

b) conoce la cantidad de elementos en la matriz antes de tiempo para que pueda asignar la cantidad correcta de memoria para la matriz

c) necesita velocidad al iterar a través de todos los elementos en secuencia. Puede usar la función de puntero matemático en la matriz para acceder a cada elemento, mientras que necesita buscar el nodo según el puntero de cada elemento en la lista vinculada, lo que puede ocasionar fallas en la página que pueden generar aciertos de rendimiento.

d) la memoria es una preocupación. Los arrays rellenos ocupan menos memoria que las listas vinculadas. Cada elemento en la matriz es solo la información. Cada nodo de la lista vinculada requiere los datos, así como uno (o más) punteros a los otros elementos en la lista vinculada.

Las listas de arreglos (como las de .Net) le brindan los beneficios de las matrices, pero asignan dinámicamente recursos para que no tenga que preocuparse demasiado por el tamaño de la lista y puede eliminar elementos en cualquier índice sin ningún esfuerzo o recurso. mezclando elementos alrededor. En cuanto al rendimiento, las listas de arreglos son más lentas que las matrices en bruto.

Answer 12

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

ArrayLists es bueno para write-once-read-many o appenders, pero es malo para agregar / eliminar de la parte frontal o central.