Cuándo utilizar una lista enlazada a través de una serie de listas / matriz?

Question

Puedo utilizar una gran cantidad de listas y matrices, pero todavía tengo que venir a través de un escenario en el que la lista de arreglo no se podía utilizar la misma facilidad que, si no es más fácil que la lista enlazada. Tenía la esperanza de que alguien me podría dar algunos ejemplos de cuando la lista enlazada es notablemente mejor.

Answer 1

Las listas enlazadas son preferibles sobre arrays cuando:

1. necesita inserciones constantes en el tiempo / supresiones de la lista (por ejemplo, en tiempo real, donde el tiempo de computación previsibilidad es absolutamente crítico)

2. usted no sabe cuántos elementos estarán en la lista. Con los arreglos, es posible que tenga que volver a declarar y copiar la memoria si la matriz crece demasiado grande

3. que no es necesario el acceso aleatorio a cualquier elemento

4. que desea ser capaz de insertar elementos en la mitad de la lista (por ejemplo, una cola de prioridad)

Arrays son preferibles cuando:

1. necesita acceso indexado / al azar a los elementos

2. Usted sabe que el número de elementos de la matriz antes de tiempo para que pueda asignar la cantidad correcta de memoria para la matriz

3. necesita velocidad cuando se itera a través de todos los elementos en secuencia. Puede usar las matemáticas puntero en la matriz para acceder a cada elemento, mientras que usted necesita para buscar el nodo basado en el puntero para cada elemento en la lista enlazada, lo que puede provocar fallos de página que puede dar lugar a golpes de rendimiento.

4. memoria es una preocupación. matrices llenas ocupan menos memoria que las listas enlazadas. Cada elemento de la matriz es sólo los datos. Cada nodo lista enlazada requiere los datos, así como una (o más) punteros a los otros elementos en la lista enlazada.

Listas de matriz (como los de .Net) le dará los beneficios de las matrices, pero dinámicamente la asignación de recursos para usted para que usted no tiene que preocuparse demasiado acerca de tamaño de la lista y se puede eliminar artículos en cualquier índice sin ningún esfuerzo o elementos re-arrastrando los pies. En cuanto al rendimiento, ArrayLists son más lentas que las matrices primas.

Answer 2

Las matrices tienen O (1) de acceso aleatorio, pero son muy caros para agregar material sobre o quitar cosas de.

Las listas enlazadas son muy baratos para añadir o eliminar elementos en cualquier lugar y para recorrer, pero el acceso aleatorio es O (n).

Answer 3

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 son buenos para una sola escritura-lectura-muchos o appenders, pero malo en añadir / quitar de la parte delantera o medio.

Answer 4

Para añadir a las otras respuestas, la mayoría de las implementaciones lista de arreglo reserva de capacidad extra al final de la lista, de modo que los nuevos elementos se pueden agregar al final de la lista en O (1) tiempo. Cuando se excede la capacidad de una lista de arreglo, un nuevo y mayor gama se asigna internamente, y todos los viejos elementos se copian. Por lo general, la nueva matriz es el doble del tamaño de la antigua. Esto significa que en promedio , la adición de nuevos elementos al final de una lista de matriz es un (1) operación O en estas implementaciones. Así que incluso si usted no sabe el número de elementos de antelación, una lista de arreglo puede ser todavía más rápido que una lista enlazada para añadir elementos, siempre y cuando se les está agregando al final. Obviamente, la inserción de nuevos elementos en ubicaciones arbitrarias en una lista de arreglo es todavía un O (n) la operación.

Acceso a los elementos en una lista de arreglo es también más rápido que una lista enlazada, incluso si los accesos son secuenciales. Esto se debe a elementos de la matriz se almacenan en memoria contigua y pueden almacenar en caché fácilmente. los nodos de lista enlazada potencialmente pueden ser esparcidas por muchas páginas diferentes.

Yo recomendaría sólo con una lista enlazada si sabe que va a estar insertar o eliminar elementos en ubicaciones arbitrarias. listas de matriz será más rápido para casi todo lo demás.

Answer 5

La ventaja de las listas aparece si es necesario insertar elementos en el medio y no quiere empezar a cambiar el tamaño de la matriz y el cambio de las cosas.

Tiene razón en que esto normalmente no es el caso. He tenido un par de casos muy específicos como esa, pero no demasiados.

Answer 6

Estas son las implementaciones de uso más comunes de la colección.

ArrayList:

• insertar / eliminar en el extremo generalmente O (1) peor caso O (n)

• insertar / eliminar en la O medio (n)

• recuperar cualquier posición O (1)

LinkedList:

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

• recuperar en el medio O (n)

• recuperar primero o el último elemento de O (1)

Vectores: no lo use. Es una vieja aplicación similar a ArrayList, pero con todos los métodos sincronizados. No es el enfoque correcto para una lista compartida en un entorno multihilo.

HashMap

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

TreeSet insertar / eliminar / contiene en O (log n)

HashSet la inserción / extracción / contiene / tamaño en O (1)

Answer 7

Todo depende de qué tipo de operación que está haciendo, mientras que la iteración, todas las estructuras de datos tiene compromiso entre el tiempo y la memoria y en función de nuestras necesidades debemos elegir el DS derecha. Así que hay algunos casos en los que son más rápidos ListaEnlazada luego matriz y viceversa. Considere las tres operaciones básicas en las estructuras de datos.

• Buscar

Desde matriz es la estructura de datos basada índice de búsqueda array.get (índice) se llevará a O (1) tiempo mientras LinkedList no es DS índice por lo que tendrá que atravesar hasta índice, donde el índice <= n, n es el tamaño de lista enlazada, por lo que la matriz es más rápida es la lista enlazada cuando tiene acceso aleatorio de elementos.

Q.So lo que es la belleza detrás de esto?

Las matrices son bloques de memoria contiguos, grandes porciones de ellas serán cargados en la memoria caché al primer acceso esto hace que sea relativamente rápida de acceder a los elementos restantes de la matriz, por mucho que se accede a los elementos de la matriz de la localidad de referencia también aumenta por tanto, menos fallos de captura, caché localidad se refiere a las operaciones que están en la memoria caché y por lo tanto se ejecutan mucho más rápido en comparación con la memoria, básicamente en conjunto podemos maximizar las posibilidades de acceso secuencial elemento de estar en la memoria caché. Aunque las listas Vinculados no están necesariamente en bloques contiguos de memoria, no hay garantía de que los artículos que aparecen en secuencia en la lista están realmente dispuestos cerca uno del otro, en la memoria, esto significa menos aciertos de caché, por ejemplo, más caché pierde porque tenemos que leer de la memoria para cada acceso de elemento de lista enlazada que aumenta el tiempo que se necesita para acceder a ellos y el rendimiento sea lo que si estamos haciendo la operación de acceso aleatorio también conocido como la búsqueda, gama será rápido como se explica a continuación.

• Inserción

Esto es fácil y rápido en ListaEnlazada como la inserción es O (1) operación en LinkedList (en Java) con respecto a la matriz, consideremos el caso cuando la matriz es completa, tenemos que copiar el contenido a la nueva matriz si matriz se llena el cual hace que la inserción de un elemento en ArrayList de O (n) en el peor de los casos, mientras que ArrayList también tiene que actualizar su índice si se inserta algo en cualquier parte excepto al final de la serie, en el caso de la lista enlazada que no necesitamos ser cambiar su tamaño, se sólo tiene que actualizar los punteros.

• Supresión

Funciona como inserciones y mejor en ListaEnlazada de matriz.

Answer 8

He hecho un poco de evaluación comparativa, y se encontró que la clase de lista es más rápido 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 necesita 900 ms para la lista enlazada y 100 ms para la clase de lista.

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

Answer 9

En la localidad de memoria realidad tiene una gran influencia en el rendimiento de procesamiento real.

El aumento del uso de streaming de disco en "grandes datos" procesamiento vs acceso aleatorio muestra cómo estructurar su aplicación en todo esto puede mejorar drásticamente el rendimiento en una escala más grande.

Si hay alguna manera de acceder a una secuencialmente matriz que es, con mucho, el mejor rendimiento. Diseñar con esto como una meta debe ser al menos considerado si el rendimiento es importante.

Answer 10

Hmm, Arraylist se puede utilizar en casos como el que sigue, supongo:

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

Por ejemplo, es necesario importar y acceder a todos los elementos de una lista de contactos (el tamaño de las cuales es desconocido para usted)

Answer 11

Utilice lista enlazada de Radix sort sobre matrices y para operaciones polinómicas.

Answer 12

1) Como se explicó anteriormente el inserto y las operaciones de quitar dan un buen rendimiento (O (1)) en comparación con LinkedList ArrayList (O (n)). Por tanto, si existe un requisito de adición frecuente y eliminación en la solicitud de continuación LinkedList es una mejor opción.

2) Buscar (método GET) operaciones son rápidos en Arraylist (O (1)), pero no en LinkedList (O (n)) así que si hay menos añadir y eliminar las operaciones y más operaciones de búsqueda de requisitos, ArrayList sería su mejor apuesta.

Answer 13

Creo que la diferencia principal es si con frecuencia necesario poner o quitar cosas de la parte superior de la lista.

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

Con una lista enlazada, que es O (1), ya que sólo necesita crear el nodo, reasignar la cabeza y asignar la referencia a la siguiente como la cabeza anterior.

Cuando se suelen insertar o retirar al final de la lista, las matrices son preferibles debido a la complejidad será O (1), no se requiere indexación, pero para una lista enlazada será O (n), ya que tiene que ir desde la cabeza hasta el último nodo.

Creo que la búsqueda tanto en lista y matrices ligado será O (log n), ya que es probable que se esté utilizando una búsqueda binaria.