¿Cuándo usar una lista vinculada sobre una matriz / lista de matrices?

Utilizo muchas listas y matrices, pero aún no he encontrado un escenario en el que la lista de matrices no se pueda usar tan fácilmente como, si no es más fácil, que la lista vinculada. Esperaba que alguien pudiera darme algunos ejemplos de cuándo la lista vinculada es notablemente mejor.

Las listas vinculadas son preferibles a las matrices cuando:

1. necesita inserciones / eliminaciones en tiempo constante de la lista (como en la computación en tiempo real donde la previsibilidad del tiempo es absolutamente crítica)

2. No sabe cuántos elementos habrá en la lista. Con las matrices, es posible que deba volver a declarar y copiar memoria si la matriz crece demasiado

3. no necesitas acceso aleatorio a ningún elemento

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

Las matrices son preferibles cuando:

1. necesita acceso indexado / aleatorio a los elementos

2. usted sabe la cantidad de elementos en la matriz con anticipación para que pueda asignar la cantidad correcta de memoria para la matriz

3. necesitas velocidad cuando recorres todos los elementos en secuencia. Puede usar las matemáticas del puntero en la matriz para acceder a cada elemento, mientras que necesita buscar el nodo en función del puntero para cada elemento en la lista vinculada, lo que puede provocar fallas en la página que pueden dar lugar a resultados de rendimiento.

4. La memoria es una preocupación. Las matrices llenas ocupan menos memoria que las listas vinculadas. Cada elemento de la matriz es solo los datos. 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 matrices (como las de .Net) le brindan los beneficios de las matrices, pero asignan recursos dinámicamente para que no tenga que preocuparse demasiado por el tamaño de la lista y pueda eliminar elementos en cualquier índice sin ningún esfuerzo o recuperación. barajando elementos alrededor. En cuanto al rendimiento, las listas de matrices son más lentas que las matrices sin procesar.

Las matrices tienen acceso aleatorio O (1), pero son realmente caras de agregar o quitar.

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

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)

Las ArrayLists son buenas para escribir, leer una vez muchos o anexos, pero son malas para agregar / quitar desde el frente o el medio.

Para agregar a las otras respuestas, la mayoría de las implementaciones de la lista de matrices reservan capacidad adicional al final de la lista para que se puedan agregar nuevos elementos al final de la lista en el tiempo O (1). Cuando se excede la capacidad de una lista de matriz, se asigna internamente una nueva matriz 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 matriz es una operación O (1) en estas implementaciones. Por lo tanto, incluso si no conoce el número de elementos de antemano, una lista de matriz aún puede ser más rápida que una lista vinculada para agregar elementos, siempre que los agregue al final. Obviamente, insertar nuevos elementos en ubicaciones arbitrarias en una lista de matriz sigue siendo una operación O (n).

Acceder 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 almacenar en caché fácilmente. Los nodos de la lista vinculada pueden estar potencialmente dispersos en muchas páginas diferentes.

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.

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.

Tienes razón en que este no suele ser el caso. He tenido algunos casos muy específicos como ese, pero no demasiados.

Todo depende del tipo de operación que esté haciendo mientras itera, todas las estructuras de datos tienen un equilibrio entre el tiempo y la 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 la matriz y viceversa. Considere las tres operaciones básicas en estructuras de datos.

• buscando

Dado que la matriz está basada en la estructura de datos basada en el índice, la búsqueda de array.get (index) tomará O (1) tiempo mientras que la lista vinculada no es el índice DS, por lo que deberá recorrer hasta el índice, donde index <= n, n es el tamaño de la lista vinculada, entonces la matriz es más rápida que la lista vinculada cuando tiene acceso aleatorio de elementos.

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

Como las matrices son bloques de memoria contiguos, se cargarán grandes porciones de ellas en la caché al primer acceso, esto hace que sea relativamente rápido acceder a los elementos restantes de la matriz, tanto como accedemos a los elementos en la localidad de referencia de la matriz también aumenta, por lo tanto, menos captura falla, la localidad de caché se refiere a las operaciones que se encuentran en la caché y, por lo tanto, se ejecutan mucho más rápido en comparación con la memoria, básicamente en la matriz maximizamos las posibilidades de acceso secuencial a 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 realmente organizados uno cerca del otro en la memoria, esto significa menos aciertos de caché, por ejemplo

• Inserción

Esto es fácil y rápido en LinkedList, ya que la inserción es una operación O (1) 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 la matriz se llena, lo que hace que insertar un elemento en ArrayList de O (n) en el peor de los casos, mientras que ArrayList también necesita actualizar su índice si inserta algo en cualquier lugar excepto al final de la matriz, en el caso de una lista vinculada, no necesitamos cambiar su tamaño, solo necesita punteros de actualización.

• Supresión

Funciona como inserciones y mejor en LinkedList que en array.

Esas son las implementaciones 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 uses. Es una implementación antigua 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 / eliminar / recuperar por clave en O (1)

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

HashSet insertar / eliminar / contiene / tamaño en O (1)

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

El mayor uso de la transmisión de disco en el procesamiento de "big data" frente al acceso aleatorio muestra cómo la estructuración de su aplicación en torno a esto puede mejorar drásticamente el rendimiento a mayor escala.

Si hay alguna forma de acceder a una matriz secuencialmente, ese es, con mucho, el mejor desempeño. Diseñar con esto como un objetivo debe considerarse al menos si el rendimiento es importante.

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

1. no está 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, debe importar y acceder a todos los elementos en una lista de contactos (cuyo tamaño es desconocido para usted)

Utilice la lista vinculada para la ordenación por radix sobre matrices y para operaciones polinómicas.

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

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

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 vinculada, es o (1) porque solo necesita crear el nodo, reasignar el encabezado y asignar la referencia al siguiente como el encabezado anterior.

Al insertar o eliminar con frecuencia al final de la lista, las matrices son preferibles porque la complejidad será o (1), no se requiere reindexar, pero para una lista vinculada será o (n) porque necesita ir desde la cabeza hasta el último nodo.

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

Hice algunas evaluaciones comparativas y descubrí que la clase de lista es realmente 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 100 ms 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 usa algo mejor que solo una matriz.

Las matrices, con mucho, son las estructuras de datos más utilizadas. Sin embargo, las listas vinculadas resultan útiles en su propia forma única donde los arreglos son torpes, o caros, por decir lo menos.

Las listas vinculadas son útiles para implementar pilas y colas en situaciones donde su tamaño está sujeto a variaciones. Cada nodo en la lista vinculada se puede empujar o reventar sin molestar a la mayoría de los nodos. Lo mismo ocurre con la inserción / eliminación de nodos en algún lugar en el medio. En las matrices, sin embargo, todos los elementos tienen que ser desplazados, lo cual es un trabajo costoso en términos de tiempo de ejecución.

Los árboles binarios y los árboles de búsqueda binaria, las tablas hash y los intentos son algunas de las estructuras de datos en las que, al menos en C, necesita listas vinculadas como ingrediente fundamental para construirlas.

Sin embargo, las listas vinculadas deben evitarse en situaciones en las que se espera que pueda llamar a cualquier elemento arbitrario por su índice.

Se puede dar una respuesta simple a la pregunta usando estos puntos:

1. Las matrices deben usarse cuando se requiere una colección de elementos de datos de tipo similar. Mientras que, la lista vinculada es una colección de elementos vinculados de datos de tipo mixto conocidos como nodos.

2. En conjunto, uno puede visitar cualquier elemento en O (1) tiempo. Mientras que, en la lista vinculada, tendríamos que recorrer toda la lista vinculada desde la cabeza hasta el nodo requerido, tomando tiempo O (n).

3. Para las matrices, un tamaño específico debe declararse inicialmente. Pero las listas vinculadas son dinámicas en tamaño.