arrays - programacion - listas simples estructura de datos

Matriz versus lista enlazada (30)

¿Por qué una lista vinculada en 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 cualquiera, y obtener lo mejor de ambos, al mismo tiempo ... ¿eh?

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

Si tiene una matriz realmente grande, podría combinarla con otra matriz mucho más pequeña o lista vinculada donde la más pequeña contenga los 20, 50, 100 elementos usados más recientemente. Si el que se necesita no está en la lista o matriz vinculada más corta, vas a la matriz grande. Si se encuentra allí, puede agregarlo a la lista / matriz vinculada más pequeña con la presunción de que "las cosas más recientemente usadas son más fáciles de reutilizar" (y sí, posiblemente topando con el elemento usado menos recientemente de la lista). Lo cual es cierto en muchos casos y resolvió un problema que tuve que resolver en un módulo de verificación de permisos de seguridad .ASP, con facilidad, elegancia y velocidad impresionante.

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

Codificar una lista enlazada 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 enlazada, pero es una gran tarea en una matriz. ¿Hay otras ventajas en utilizar 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.

Además de agregar y eliminar desde el medio de la lista, me gustan más las listas vinculadas porque pueden crecer y reducirse de forma dinámica.

Además de insertar en el medio de la lista es más fácil, también es mucho más fácil eliminar desde el 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ápida, también necesitaba una búsqueda rápida, así que fui a un HashSet o un Diccionario.

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 apuntados por a en b y c .

Esta es la razón por la que son tan populares en los lenguajes funcionales, que usan variables inmutables, tail operaciones de prepend y tail pueden ocurrir libremente sin tener que copiar los datos originales, características muy importantes cuando se trata a los datos como inmutables.

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

Arrays Vs Linked List:

La asignación de memoria de matriz fallará a veces debido a la memoria fragmentada.
El almacenamiento en caché es mejor en Arrays ya que a todos los elementos se les asigna espacio de memoria contiguo.
La codificación es más compleja que las matrices.
Sin restricción de tamaño en la lista vinculada, a diferencia de las matrices
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.
Linked List mejor desde el punto de vista de multi-threading.

Dos cosas:

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

Nunca codifique una lista vinculada al usar C ++. Solo usa el STL. Lo difícil que es implementar nunca debe 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 planeas utilizar la estructura. Usaré el término vector ya que ese es el término para una matriz de tamaño variable 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í utilizando el cálculo del puntero.

Anexar 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 volver a unirlos. Eliminar un artículo de un vector puede ser más rápido o más lento, dependiendo de si le importa el orden. Al intercambiar en el último elemento por encima, el elemento que desea eliminar es más rápido, mientras que al desplazarlo todo lo hace más lento, pero conserva el orden.

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

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

En una matriz, tiene el privilegio de acceder a cualquier elemento en O (1) vez. Por lo tanto, es adecuado para operaciones como búsqueda binaria, clasificación rápida, etc. La lista vinculada, por otro lado, es adecuada para la eliminación de inserción como su 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.

Eric Lippert publicó recientemente una de las razones por las que las matrices deberían usarse de forma conservadora.

Es realmente una cuestión de eficiencia, los gastos generales para insertar, eliminar o mover (donde no se está simplemente intercambiando) los elementos dentro de una lista vinculada son mínimos, es decir, la operación en sí es O (1), versos O (n) para una matriz. Esto puede hacer una gran diferencia si está trabajando mucho en una lista de datos. Usted eligió sus tipos de datos en función de cómo va a operar en ellos y elige el más eficiente para el algoritmo que está utilizando.

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

Desventaja podría ser que los indicadores toman mucho espacio.

Y sobre esa codificación es más difícil: por lo general no necesita una lista de códigos vinculados (o solo una vez) que están incluidos en STL y no es tan complicado si aún tiene que hacerlo.

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 la matriz no puede hacer. En muchos casos, supongamos que quiere una matriz de 10 ^ 9 de longitud, pero no puede obtenerla porque debe estar presente una ubicación de memoria continua. La lista enlazada podría ser un salvador aquí.

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

Los contenedores STL generalmente tienen implementaciones de listas vinculadas detrás de la escena.

La fusión de dos listas vinculadas (especialmente dos listas doblemente vinculadas) es mucho más rápida que la fusión de dos matrices (suponiendo que la fusión es destructiva). El primero toma O (1), el último 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.

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

Las listas vinculadas son especialmente útiles cuando la colección crece y se reduce constantemente. Por ejemplo, es difícil imaginar el intento de implementar una cola (agregar al final, eliminar desde el frente) usando una matriz: pasarías todo el tiempo cambiando las cosas. Por otro lado, es trivial con una lista enlazada.

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 los 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

¡Es más preferible cuando se trata de inserción! Básicamente lo que hace es que se trata del 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 desde Array

| 1 | 3 | 4 |

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

¡Bien, cualquiera puede visualizar la diferencia! Solo para el índice 4 estamos realizando 3 pasos

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

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

¡Espero que ayude! :)

Nadie codifica su propia lista enlazada nunca más. Eso sería tonto. La premisa de que usar una lista vinculada requiere más código es simplemente incorrecta.

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

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

Otra buena razón es que las listas vinculadas se prestan muy bien a las implementaciones eficaces de subprocesos múltiples. La razón para 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 cerradura usando operaciones de tipo CAS y evitar por completo las cerraduras de gran peso.

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

Con una matriz, cualquier cambio que modifique el tamaño de la matriz probablemente requiera el bloqueo de una gran parte de la matriz y, de hecho, es raro que esto se realice sin un bloqueo global en toda la matriz, por lo que las modificaciones detienen los asuntos mundiales.

Para mí es así,

Acceso
- Las listas vinculadas solo permiten el acceso secuencial a los elementos. Por lo tanto, las complejidades algorítmicas son orden de O (n)
- Las matrices permiten el acceso aleatorio a sus elementos y, por lo tanto, la complejidad es orden de O (1)
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. Cada elemento se puede acceder a través de índices.
tamaño
- El tamaño de las listas vinculadas es dinámico por naturaleza.
- El tamaño de la matriz está restringido a la declaración.
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.

Según su idioma, se pueden considerar algunas de estas desventajas y ventajas:

C Lenguaje de programación : cuando se utiliza una lista vinculada (a través de punteros struct normalmente), se debe tener especial consideración para asegurarse de no tener pérdidas de memoria. Como se mencionó anteriormente, las listas enlazadas son fáciles de mezclar, porque lo único que hacen es cambiar los indicadores, pero ¿vamos a recordar liberar todo?

Java : Java tiene un recolector de basura automático, por lo que la pérdida de memoria no será un problema, pero el programador de alto nivel oculta los detalles de implementación de lo que es una lista vinculada. Los métodos como eliminar un nodo del medio de la lista son más complicados que los que un usuario del lenguaje esperaría.

Si bien muchos de ustedes han tocado los principales adv./dis de la lista vinculada frente a la matriz, la mayoría de las comparaciones muestran cómo uno es mejor / peor que el otro.Eg. 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 aplicaciones en particular. Supongamos que desea implementar una aplicación de diccionario, ¿qué usaría? Array: mmm permitiría una fácil recuperación a través de búsqueda binaria y otros algoritmos de búsqueda ... pero pensemos cómo la lista de enlaces puede ser mejor ... Diga que quiere buscar "Blob" en el diccionario. ¿Tendría sentido tener una lista de enlaces de A-> B-> C-> D ----> Z y luego cada elemento de lista también apunta a una matriz u otra lista de todas las palabras que comienzan con esa letra ...

Ahora, ¿es mejor el enfoque anterior o una matriz plana de [Adam, Apple, Banana, Blob, Cat, Cave]? ¿Sería posible con array? Entonces, una gran ventaja de la lista de enlaces es que puede tener un elemento que no solo apunte al siguiente elemento sino también a otra lista de enlaces / array / heap / o cualquier otra ubicación de memoria. Array es una memoria contigua y plana dividida en bloques del tamaño del elemento que va a almacenar. La lista de enlaces, por otro lado, es una porción de unidades de memoria no contiguas (puede tener cualquier tamaño y puede almacenar cualquier cosa) y apunta a cada de la manera que quieras De manera similar, digamos que está haciendo una unidad USB. Ahora, ¿desea que los archivos se guarden como una matriz o como una lista de enlaces? Creo que entiendes a qué me refiero :)

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

En primer lugar, debemos tener en cuenta que si desea retener las referencias a los objetos fuera del propio conjunto, es probable que termine almacenando punteros en la matriz, en lugar de almacenar los objetos ellos 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 se volverá inválido. Lo mismo es cierto para los índices de matriz.

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

Su segundo y más grave problema es que dado un elemento que encuentra el siguiente elemento es O (n). Si el conjunto no se modificó, se puede 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 es lo único que tienes es un puntero al objeto 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 búsqueda del siguiente tipo.

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

Un argumento ampliamente desaprovechado para ArrayList y contra LinkedList es que LinkedLists es incómodo durante la depuración . El tiempo invertido 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 mejoras de rendimiento o 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 comprender.

Por ejemplo, en un entorno Java y utilizando el depurador Eclipse, la depuración de 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 los contenidos de una LinkedList y encontrar objetos específicos se convierte en una pesadilla de clic de Expand-The-Tree, sin mencionar la sobrecarga cognitiva necesaria para filtrar los componentes internos 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>

Wikipedia tiene muy buena sección sobre las diferencias.

Las listas vinculadas tienen varias ventajas sobre las matrices. Los elementos se pueden insertar en las listas vinculadas indefinidamente, mientras que una matriz eventualmente se llenará o se tendrá que redimensionar, una operación costosa que incluso puede no ser posible si la memoria está fragmentada. Del mismo modo, una matriz a partir de la cual se eliminan muchos elementos puede convertirse en un desperdicio de espacio vacío o reducirse.
Por otro lado, las matrices permiten el acceso aleatorio, mientras que las listas enlazadas permiten solo el acceso secuencial a los elementos. De hecho, las listas enlazadas al azar solo pueden atravesarse en una dirección. Esto hace que las listas vinculadas no sean aptas para aplicaciones en las que es útil buscar rápidamente un elemento por su índice, como heapsort. 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 ubicación de las memorias caché de referencia y datos. Las listas vinculadas casi no reciben ningún beneficio de la memoria caché.
Otra desventaja de las listas vinculadas es el almacenamiento adicional necesario para las referencias, 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, dispendioso, asignar memoria por separado para cada nuevo elemento, un problema que generalmente se resuelve usando pools de memoria.

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

ya que las matrices son de naturaleza estática, por lo tanto, todas las operaciones, como la asignación de memoria, se producen en el momento de la compilación únicamente. Por lo tanto, el procesador debe poner menos esfuerzo en su tiempo de ejecución.

Diferencia entre ArrayList y LinkedList

ArrayList y LinkedList implementan la interfaz de List y mantienen el orden de inserción. Ambas son clases no sincronizadas. Pero existen muchas diferencias entre las clases ArrayList y LinkedList que se detallan a continuación.

Lista de arreglo -

ArrayList internamente utiliza una matriz dinámica para almacenar los elementos .
La manipulación con ArrayList es lenta porque internamente usa una matriz. Si se elimina algún elemento de la matriz, todos los bits se desplazan en la memoria.
ArrayList clase ArrayList puede actuar como una lista porque implementa solo la List .
ArrayList es mejor para almacenar y acceder a los datos.

Lista enlazada -

LinkedList internamente utiliza una lista doblemente enlazada para almacenar los elementos .
La manipulación con LinkedList es más rápida que ArrayList porque usa una lista doblemente enlazada, por lo que no se requieren cambios de bit en la memoria.
LinkedList clase LinkedList puede actuar como una lista y hacer cola porque implementa interfaces de List y Deque.
LinkedList es mejor para manipular datos.

Es más fácil almacenar datos de diferentes tamaños en una lista vinculada. Una matriz asume que cada elemento tiene exactamente el mismo tamaño.
Como mencionó, es más fácil para una lista vinculada crecer orgánicamente. El tamaño de una matriz debe conocerse con anticipación o volverse a crear cuando sea necesario.
Mezclar una lista vinculada es solo una cuestión de cambiar lo que apunta a qué. Mezclar una matriz es más complicado y / o requiere más memoria.
Siempre que sus iteraciones ocurran en un contexto "foreach", no perderá ningún rendimiento en la iteración.