Matriz versus lista vinculada

¿Por qué alguien querría usar una lista vinculada en una matriz?

Codificar una lista vinculada es, sin duda, un poco más trabajo que usar una matriz y uno puede preguntarse qué justificaría el esfuerzo adicional.

Creo que la inserción de nuevos elementos es trivial en una lista vinculada, pero es una tarea importante en una matriz. ¿Existen otras ventajas de usar una lista vinculada para almacenar un conjunto de datos en lugar de almacenarlos en una matriz?

Esta pregunta no es un duplicado de esta pregunta porque la otra pregunta es específicamente sobre una clase de Java en particular, mientras que esta pregunta se refiere a las estructuras de datos generales.

• Es más fácil almacenar datos de diferentes tamaños en una lista vinculada. Una matriz supone que cada elemento tiene exactamente el mismo tamaño.
• Como mencionó, es más fácil que una lista vinculada crezca orgánicamente. El tamaño de una matriz debe conocerse con anticipación o volver a crearse cuando necesita crecer.
• Mezclar una lista vinculada es solo cuestión de cambiar qué puntos a qué. Mezclar una matriz es más complicado y / o requiere más memoria.
• Mientras sus iteraciones sucedan en un contexto "foreach", no perderá ningún rendimiento en la iteración.

Otra buena razón es que las listas enlazadas se prestan muy bien para implementaciones eficientes de subprocesos múltiples. La razón de esto es que los cambios tienden a ser locales, afectando solo un puntero o dos para insertar y eliminar en una parte localizada de la estructura de datos. Por lo tanto, puede tener muchos hilos trabajando en la misma lista vinculada. Aún más, es posible crear versiones sin bloqueo utilizando operaciones de tipo CAS y evitar por completo los bloqueos pesados.

Con una lista vinculada, los iteradores también pueden atravesar la lista mientras se producen modificaciones. En el caso optimista donde las modificaciones no chocan, los iteradores pueden continuar sin contención.

Con una matriz, es probable que cualquier cambio que modifique el tamaño de la matriz requiera bloquear una gran parte de la matriz y, de hecho, es raro que esto se haga sin un bloqueo global en toda la matriz para que las modificaciones se conviertan en un obstáculo para los asuntos mundiales.

Wikipedia tiene muy buena sección sobre las diferencias.

Las listas enlazadas tienen varias ventajas sobre las matrices. Los elementos se pueden insertar en listas vinculadas de forma indefinida, mientras que una matriz eventualmente se llenará o necesitará redimensionarse, una operación costosa que incluso podría no ser posible si la memoria está fragmentada. Del mismo modo, una matriz de la que se eliminan muchos elementos puede volverse un desperdicio vacío o debe hacerse más pequeña.

Por otro lado, las matrices permiten el acceso aleatorio, mientras que las listas vinculadas solo permiten el acceso secuencial a los elementos. Las listas enlazadas individualmente, de hecho, solo se pueden recorrer en una dirección. Esto hace que las listas vinculadas no sean adecuadas para aplicaciones en las que es útil buscar rápidamente un elemento por su índice, como el montón. El acceso secuencial en las matrices también es más rápido que en las listas vinculadas en muchas máquinas debido a la localidad de referencia y los cachés de datos. Las listas vinculadas casi no reciben ningún beneficio del caché.

Otra desventaja de las listas vinculadas es el almacenamiento adicional necesario para las referencias, lo que a menudo las hace poco prácticas para listas de elementos de datos pequeños, como caracteres o valores booleanos. También puede ser lento, y con un asignador ingenuo, derrochador, para asignar memoria por separado para cada elemento nuevo, un problema generalmente resuelto usando grupos de memoria.

http://en.wikipedia.org/wiki/Linked_list

Agregaré otro: las listas pueden actuar como estructuras de datos puramente funcionales .

Por ejemplo, puede tener listas completamente diferentes que comparten la misma sección final

a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)

es decir:

b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next  

sin tener que copiar los datos señalados por aen by c.

Es por eso que son tan populares en lenguajes funcionales, que usan variables inmutables, prependy las tailoperaciones pueden ocurrir libremente sin tener que copiar los datos originales, características muy importantes cuando se trata los datos como inmutables.

Además de insertar en el medio de la lista, es más fácil: también es mucho más fácil eliminar del medio de una lista vinculada que una matriz.

Pero, francamente, nunca he usado una lista vinculada. Cada vez que necesitaba una inserción y eliminación rápidas, también necesitaba una búsqueda rápida, así que fui a un HashSet o un Diccionario.

Fusionar dos listas vinculadas (especialmente dos listas doblemente vinculadas) es mucho más rápido que fusionar dos matrices (suponiendo que la fusión sea destructiva). El primero toma O (1), el segundo toma O (n).

EDITAR: Para aclarar, quise decir "fusionar" aquí en el sentido desordenado, no como en el tipo de fusión. Quizás "concatenar" hubiera sido una mejor palabra.

Un argumento muy poco apreciado para ArrayList y en contra de LinkedList es que los LinkedLists son incómodos durante la depuración . El tiempo dedicado por los desarrolladores de mantenimiento para comprender el programa, por ejemplo, para encontrar errores, aumenta y, en mi humilde opinión, a veces no justifica los nanosegundos en las mejoras de rendimiento o los bytes en el consumo de memoria en aplicaciones empresariales. A veces (bueno, por supuesto, depende del tipo de aplicaciones), es mejor desperdiciar algunos bytes pero tener una aplicación que sea más fácil de mantener o de entender.

Por ejemplo, en un entorno Java y usando el depurador Eclipse, depurar una ArrayList revelará una estructura muy fácil de entender:

arrayList   ArrayList<String>
  elementData   Object[]
    [0] Object  "Foo"
    [1] Object  "Foo"
    [2] Object  "Foo"
    [3] Object  "Foo"
    [4] Object  "Foo"
    ...

Por otro lado, ver el contenido de LinkedList y encontrar objetos específicos se convierte en una pesadilla de hacer clic en Expandir el árbol, sin mencionar la sobrecarga cognitiva necesaria para filtrar las partes internas de LinkedList:

linkedList  LinkedList<String>
    header  LinkedList$Entry<E>
        element E
        next    LinkedList$Entry<E>
            element E   "Foo"
            next    LinkedList$Entry<E>
                element E   "Foo"
                next    LinkedList$Entry<E>
                    element E   "Foo"
                    next    LinkedList$Entry<E>
                    previous    LinkedList$Entry<E>
                    ...
                previous    LinkedList$Entry<E>
            previous    LinkedList$Entry<E>
        previous    LinkedList$Entry<E>

En primer lugar, en las listas enlazadas de C ++ no debería haber muchos más problemas para trabajar que una matriz. Puede usar std :: list o la lista de punteros de impulso para las listas vinculadas. Los problemas clave con las listas vinculadas frente a las matrices son el espacio adicional requerido para los punteros y el terrible acceso aleatorio. Debe usar una lista vinculada si

• no necesita acceso aleatorio a los datos
• agregará / eliminará elementos, especialmente en el medio de la lista

Para mi es así,

1. Acceso

   • Las listas enlazadas solo permiten el acceso secuencial a los elementos. Por lo tanto, la complejidad algorítmica es el orden de O (n)
   • Las matrices permiten el acceso aleatorio a sus elementos y, por lo tanto, la complejidad es el orden de O (1)

2. Almacenamiento

   • Las listas vinculadas requieren un almacenamiento adicional para las referencias. Esto los hace poco prácticos para listas de elementos de datos pequeños como caracteres o valores booleanos.
   • Las matrices no necesitan un almacenamiento adicional para apuntar al siguiente elemento de datos. Se puede acceder a cada elemento a través de índices.

3. Talla

   • El tamaño de las listas vinculadas es dinámico por naturaleza.
   • El tamaño de la matriz está restringido a la declaración.

4. Inserción / Eliminación

   • Los elementos se pueden insertar y eliminar en listas vinculadas indefinidamente.
   • La inserción / eliminación de valores en matrices es muy costosa. Requiere reasignación de memoria.

Dos cosas:

Codificar una lista vinculada es, sin duda, un poco más trabajo que usar una matriz y se preguntó qué justificaría el esfuerzo adicional.

Nunca codifique una lista vinculada cuando use C ++. Solo usa el STL. Lo difícil que es implementar nunca debería ser una razón para elegir una estructura de datos sobre otra porque la mayoría ya están implementadas.

En cuanto a las diferencias reales entre una matriz y una lista vinculada, lo más importante para mí es cómo planea usar la estructura. Usaré el término vector ya que ese es el término para una matriz redimensionable en C ++.

La indexación en una lista vinculada es lenta porque tiene que recorrer la lista para llegar al índice dado, mientras que un vector es contiguo en la memoria y puede llegar allí usando las matemáticas de puntero.

Agregar al final o al principio de una lista vinculada es fácil, ya que solo tiene que actualizar un enlace, donde en un vector puede tener que cambiar el tamaño y copiar el contenido.

Eliminar un elemento de una lista es fácil, ya que solo tiene que romper un par de enlaces y luego volverlos a unir. Eliminar un elemento de un vector puede ser más rápido o más lento, dependiendo de si le importa el orden. Cambiar el último elemento por encima del elemento que desea eliminar es más rápido, mientras que cambiar todo después es más lento pero conserva el orden.

Eric Lippert recientemente tuvo una publicación sobre una de las razones por las cuales las matrices deben usarse de manera conservadora.

La inserción y eliminación rápidas son los mejores argumentos para las listas vinculadas. Si su estructura crece dinámicamente y no se requiere acceso de tiempo constante a cualquier elemento (como las pilas dinámicas y las colas), las listas vinculadas son una buena opción.

Aquí hay uno rápido: la eliminación de elementos es más rápida.

Las listas enlazadas son especialmente útiles cuando la colección crece y se reduce constantemente. Por ejemplo, es difícil imaginar tratar de implementar una Cola (agregar al final, eliminar desde el frente) usando una matriz: pasarías todo tu tiempo desplazando las cosas hacia abajo. Por otro lado, es trivial con una lista vinculada.

Además de agregar y eliminar del medio de la lista, me gustan más las listas vinculadas porque pueden crecer y reducirse dinámicamente.

Ya nadie codifica su propia lista vinculada. Eso sería una tontería. La premisa de que usar una lista vinculada requiere más código es simplemente errónea.

En estos días, crear una lista vinculada es solo un ejercicio para que los estudiantes puedan entender el concepto. En cambio, todos usan una lista preconstruida. En C ++, basado en la descripción de nuestra pregunta, eso probablemente significaría un vector stl ( #include <vector>).

Por lo tanto, elegir una lista vinculada frente a una matriz consiste en sopesar las diferentes características de cada estructura en relación con las necesidades de su aplicación. Superar la carga adicional de programación debería tener un impacto cero en la decisión.

Es realmente una cuestión de eficiencia, la sobrecarga para insertar, eliminar o mover (donde no se intercambia simplemente) elementos dentro de una lista vinculada es mínima, es decir, la operación en sí es O (1), versos O (n) para una matriz. Esto puede marcar una diferencia significativa si está operando fuertemente en una lista de datos. Usted elige sus tipos de datos en función de cómo los operará y elige el más eficiente para el algoritmo que está utilizando.

Las matrices tienen sentido donde se conocerá el número exacto de elementos, y donde la búsqueda por índice tiene sentido. Por ejemplo, si quisiera almacenar el estado exacto de mi salida de video en un momento dado sin compresión, probablemente usaría una matriz de tamaño [1024] [768]. Esto me proporcionará exactamente lo que necesito, y una lista sería mucho, mucho más lenta para obtener el valor de un píxel dado. En lugares donde una matriz no tiene sentido, generalmente hay mejores tipos de datos que una lista para tratar los datos de manera efectiva.

Lista enlazada de matrices vs.

1. La asignación de memoria de matriz fallará a veces debido a la memoria fragmentada.
2. El almacenamiento en caché es mejor en matrices ya que a todos los elementos se les asigna espacio de memoria contiguo.
3. La codificación es más compleja que las matrices.
4. Sin restricción de tamaño en la lista vinculada, a diferencia de las matrices
5. La inserción / eliminación es más rápida en la lista vinculada y el acceso es más rápido en las matrices.
6. Lista enlazada mejor desde el punto de vista de subprocesos múltiples.

Como las matrices son de naturaleza estática, por lo tanto, todas las operaciones, como la asignación de memoria, ocurren solo en el momento de la compilación. Por lo tanto, el procesador tiene que poner menos esfuerzo en su tiempo de ejecución.

Supongamos que tiene un conjunto ordenado, que también desea modificar agregando y eliminando elementos. Además, necesita la capacidad de retener una referencia a un elemento de tal manera que luego pueda obtener un elemento anterior o siguiente. Por ejemplo, una lista de tareas o un conjunto de párrafos en un libro.

Primero, debemos tener en cuenta que si desea retener referencias a objetos fuera del conjunto, es probable que termine almacenando punteros en la matriz, en lugar de almacenar objetos en sí mismos. De lo contrario, no podrá insertar en la matriz: si los objetos están incrustados en la matriz, se moverán durante las inserciones y cualquier puntero a ellos será inválido. Lo mismo es cierto para los índices de matriz.

Su primer problema, como ha señalado usted mismo, es la inserción: la lista vinculada permite insertar en O (1), pero una matriz generalmente requeriría O (n). Este problema se puede superar parcialmente: es posible crear una estructura de datos que proporcione una interfaz de acceso ordinal en forma de matriz donde la lectura y la escritura son, en el peor de los casos, logarítmicas.

Su segundo y más grave problema es que, dado que un elemento encuentra el siguiente elemento, es O (n). Si el conjunto no se modificó, podría retener el índice del elemento como referencia en lugar del puntero, lo que hace que find-next sea una operación O (1), pero como todo lo que tiene es un puntero al objeto en sí mismo y de ninguna manera para determinar su índice actual en la matriz que no sea escaneando toda la "matriz". Este es un problema insuperable para las matrices: incluso si puede optimizar las inserciones, no hay nada que pueda hacer para optimizar la operación de encontrar el siguiente tipo.

En una matriz, tiene el privilegio de acceder a cualquier elemento en O (1) tiempo. Por lo tanto, es adecuado para operaciones como Binary search Quick sort, etc. La lista vinculada, por otro lado, es adecuada para la eliminación de inserción ya que está en el tiempo O (1). Ambos tienen ventajas y desventajas, y preferir uno sobre el otro se reduce a lo que desea implementar.

- La pregunta más importante es si podemos tener un híbrido de ambos. Algo así como lo que Python y Perl implementan como listas.

Lista enlazada

¡Es más preferible cuando se trata de inserción! Básicamente lo que hace es que trata con el puntero

1 -> 3 -> 4

Insertar (2)

1 ........ 3 ...... 4
..... 2

Finalmente

1 -> 2 -> 3 -> 4

Una flecha de los 2 puntos en 3 y la flecha de 1 puntos en 2

¡Sencillo!

Pero de la matriz

El | 1 | 3 | 4 |

Insertar (2) | 1 | 3 | El | 4 | El | 1 | El | 3 | 4 | El | 1 | 2 | 3 | 4 |

Bueno, cualquiera puede visualizar la diferencia! Solo para 4 índices estamos realizando 3 pasos

¿Qué pasa si la longitud de la matriz es un millón entonces? ¿Es eficiente la matriz? ¡La respuesta es no! :)

¡Lo mismo ocurre con la eliminación! ¡En Linked List podemos simplemente usar el puntero y anular el elemento y el siguiente en la clase de objeto! Pero para la matriz, necesitamos realizar shiftLeft ()

¡Espero que ayude! :)

La lista vinculada es más una sobrecarga para mantener que una matriz, también requiere almacenamiento de memoria adicional, todos estos puntos están de acuerdo. Pero hay algunas cosas que array no puede hacer. En muchos casos, suponga que desea una matriz de 10 ^ 9 de longitud que no puede obtener porque obtener una ubicación de memoria continua debe estar allí. La lista vinculada podría ser un salvador aquí.

Supongamos que desea almacenar varias cosas con datos, entonces se pueden extender fácilmente en la lista vinculada.

Los contenedores STL generalmente tienen una implementación de lista vinculada detrás de escena.

1- lista vinculada es una estructura de datos dinámica para que pueda crecer y reducirse en tiempo de ejecución asignando y desasignando memoria. Por lo tanto, no es necesario dar un tamaño inicial de la lista vinculada. La inserción y eliminación de nodos son realmente más fáciles.

2- el tamaño de la lista vinculada puede aumentar o disminuir en el tiempo de ejecución, por lo que no hay desperdicio de memoria. En el caso de la matriz, hay un gran desperdicio de memoria, como si declaramos una matriz de tamaño 10 y almacenamos solo 6 elementos, entonces se desperdicia espacio de 4 elementos. No existe tal problema en la lista vinculada ya que la memoria se asigna solo cuando es necesario.

3- Las estructuras de datos como la pila y las colas se pueden implementar fácilmente mediante una lista vinculada.

La única razón para usar la lista vinculada es que insertar el elemento es fácil (eliminar también).

La desventaja podría ser que los punteros ocupan mucho espacio.

Y sobre eso, la codificación es más difícil: por lo general, no necesita una lista enlazada de código (o solo una vez), se incluyen en STL y no es tan complicado si aún tiene que hacerlo.

También creo que esa lista de enlaces es mejor que las matrices. porque hacemos un recorrido en la lista de enlaces pero no en matrices

Dependiendo de su idioma, se podrían considerar algunas de estas desventajas y ventajas:

Lenguaje de programación C : cuando se usa una lista vinculada (a través de punteros de estructura normalmente), se debe tener especial consideración para asegurarse de que no se pierda memoria. Como se mencionó anteriormente, las listas vinculadas son fáciles de barajar, porque todo lo que hacíamos era cambiar los punteros, pero ¿vamos a recordar liberar todo?

Java : Java tiene una recolección de basura automática, por lo que la pérdida de memoria no será un problema, pero los detalles de implementación de lo que es una lista vinculada ocultan al programador de alto nivel. Métodos como eliminar un nodo del medio de la lista es un procedimiento más complicado de lo que algunos usuarios del lenguaje esperarían que fuera.

¿Por qué una lista vinculada sobre una matriz? Bueno, como algunos ya han dicho, mayor velocidad de inserciones y eliminaciones.

Pero tal vez no tengamos que vivir con los límites de ninguno de los dos, y obtener lo mejor de ambos, al mismo tiempo ... ¿eh?

Para las eliminaciones de matrices, puede usar un byte 'Eliminado', para representar el hecho de que se ha eliminado una fila, por lo que ya no es necesario reorganizar la matriz. Para aliviar la carga de las inserciones, o el cambio rápido de datos, use una lista vinculada para eso. Luego, cuando se refiera a ellos, haga que su lógica primero busque uno, luego el otro. Por lo tanto, usarlos en combinación le brinda lo mejor de ambos.

Si tiene una matriz realmente grande, puede combinarla con otra matriz mucho más pequeña o una lista vinculada donde la más pequeña contenga los 20, 50, 100 elementos utilizados más recientemente. Si el que necesita no está en la lista o matriz vinculada más corta, vaya a la matriz grande. Si se encuentra allí, puede agregarlo a la lista / matriz vinculada más pequeña bajo la presunción de que 'las cosas utilizadas más recientemente son las más adecuadas para ser reutilizadas' (y sí, posiblemente eliminando el elemento utilizado menos recientemente de la lista). Lo cual es cierto en muchos casos y resolvió un problema que tuve que abordar en un módulo de verificación de permisos de seguridad .ASP, con facilidad, elegancia y velocidad impresionante.

Si bien muchos de ustedes se han referido a los principales adv./dis de la lista vinculada frente a la matriz, la mayoría de las comparaciones son cómo uno es mejor / peor que el otro. puede hacer acceso aleatorio en la matriz, pero no es posible en la lista vinculada y otros. Sin embargo, esto supone que las listas de enlaces y la matriz se aplicarán en una aplicación similar. Sin embargo, una respuesta correcta debería ser cómo se preferiría la lista de enlaces sobre la matriz y viceversa en una implementación de aplicación particular. Supongamos que desea implementar una aplicación de diccionario, ¿qué usaría? Matriz: mmm permitiría una recuperación fácil a través de la búsqueda binaria y otros métodos de búsqueda ... pero pensemos cómo la lista de enlaces puede ser mejor ... Di que quieres buscar "Blob" en el diccionario. ¿Tendría sentido tener una lista de enlaces de A-> B-> C-> D ---->

A -> B -> C -> ...Z
|    |    |
|    |    [Cat, Cave]
|    [Banana, Blob]
[Adam, Apple]

¿Ahora es mejor el enfoque anterior o un conjunto plano de [Adam, Apple, Banana, Blob, Cat, Cave]? ¿Sería posible con una matriz? Por lo tanto, una gran ventaja de la lista de enlaces es que puede tener un elemento no solo apuntando al siguiente elemento sino también a otra lista de enlaces / matriz / montón / o cualquier otra ubicación de memoria. La matriz es una memoria unica plana dividida en bloques del tamaño del elemento que va a almacenar. La lista de enlaces, por otro lado, es un trozo de unidades de memoria que no son tuyas (puede ser de cualquier tamaño y puede almacenar cualquier cosa) y apunta a cada otro de la manera que quieras. Del mismo modo, digamos que está haciendo una unidad USB. ¿Ahora le gustaría guardar los archivos como una matriz o como una lista de enlaces? Creo que te haces una idea de lo que estoy señalando :)