Matriz versus lista vinculada

Otra buena razón es que las listas enlazadas se prestan muy bien a implementaciones multihilo eficientes. 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 bloqueos pesados por completo.

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

Con una matriz, cualquier cambio que modifique el tamaño de la matriz es probable que 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 detener los asuntos del mundo.

Wikipedia tiene una sección muy buena sobre las diferencias.

Las listas enlazadas tienen varias ventajas sobre arreglos. Los elementos se pueden insertar en listas enlazadas indefinidamente, mientras una matriz eventualmente completar o necesitan ser redimensionados, un costoso operación que ni siquiera puede ser posible si la memoria está fragmentada. Del mismo modo, una matriz de la que muchos los elementos que se eliminan pueden convertirse en desperdiciar vacío o necesidad de ser hecho más pequeño.

Por otra mano, matrices permiten al azar acceso, mientras que las listas enlazadas solo permiten acceso secuencial a los elementos. Listas de enlaces individuales, de hecho, solo puede ser atravesado en una dirección. Este hace que las listas enlazadas no sean adecuadas para aplicaciones donde es útil buscar un elemento por su índice rápidamente, como heapsort. Acceso secuencial en arrays también es más rápido que en linked listas en muchas máquinas debido a la localidad de referencia y cachés de datos. Ligado listas reciben casi ningún beneficio de el cache.

Otra desventaja de las listas enlazadas es el almacenamiento adicional necesario para referencias, que a menudo las hace poco práctico para listas de datos pequeños elementos como caracteres o booleanos valor. También puede ser lento, y con un asignador ingenuo, derrochador, asignar memoria por separado para cada nuevo elemento, un problema en general 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ñalado por a en b y c.

Esta es la razón por la que son tan populares en los lenguajes funcionales, que utilizan variables inmutables - prepend y tail las operaciones pueden ocurrir libremente sin tener que copiar los datos originales - características muy importantes cuando estás tratando datos como inmutables.

Fusionar dos listas enlazadas (especialmente dos listas doblemente enlazadas) 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).

EDIT: Para aclarar, quise decir "fusionar" aquí en el sentido desordenado, no como en merge sort. Tal vez" concatenar " hubiera sido una palabra mejor.

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

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

En primer lugar, en C++ las listas enlazadas no deberían ser mucho más difíciles de trabajar que una matriz. Puede usar el std::list o el boost pointer list para las listas enlazadas. Los problemas clave con las listas vinculadas frente a los arrays son el espacio adicional requerido para los punteros y el terrible acceso aleatorio. Usted debe utilizar una lista vinculada si

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

Un argumento muy poco apreciado para ArrayList y contra LinkedList es que Las listas de enlaces son incómodas al depurar. El tiempo empleado por los desarrolladores de mantenimiento para entender el programa, por ejemplo, para encontrar errores, aumenta y IMHO 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 unos pocos bytes pero tener un aplicación que es más mantenible o más fácil 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 una lista de enlaces y encontrar objetos específicos se convierte en una pesadilla de clic en Expandir el Árbol, por no mencionar la sobrecarga cognitiva necesaria para filtrar el funcionamiento interno de la Lista de enlaces:

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>

Para mí es así,

1. Acceso

   • Las listas enlazadas solo permiten el acceso secuencial a los elementos. Por lo tanto, las complejidades algorítmicas son del orden de O (n)
   • Los arrays permiten el acceso aleatorio a sus elementos y por lo tanto la complejidad es el orden de O(1)

2. Almacenamiento

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

3. Tamaño

   • El tamaño de Las listas enlazadas son dinámicas por naturaleza.
   • El tamaño de array está restringido a la declaración.

4. Inserción / Supresión

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

Dos cosas:

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

Nunca codifique una lista enlazada cuando use C++. Usa el STL. Lo difícil que es implementarlo 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 importante para mí es cómo planifique el uso de la estructura. Usaré el término vector ya que es el término para una matriz redimensionable en C++.

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

Añadir al final o al principio de una lista enlazada 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 sobre.

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 elemento de un vector puede ser más rápido o más lento, dependiendo de si le importa el orden. Cambiar en el último elemento por encima del elemento que desea eliminar es más rápido, mientras que cambiar todo después de que hacia abajo es más lento, pero conserva el orden.

Eric Lippert recientemente tuvo un post en una de las razones por las que los arrays deben usarse de manera conservadora.

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

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

Las listas enlazadas son especialmente útiles cuando la colección está en constante crecimiento y reducción. Por ejemplo, es difícil imaginar intentar implementar una cola (agregar al final, eliminar del frente) usando una matriz using estarías gastando todo tu tiempo cambiando las cosas hacia abajo. Por otro lado, es trivial con una lista vinculada.

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

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

En estos días, construir una lista enlazada es solo un ejercicio para que los estudiantes puedan entender el concepto. En su lugar, todo el mundo utiliza una lista pre-construida. En C++, basado en la descripción en nuestra pregunta, eso probablemente significaría un vector stl (#include <vector>).

Por lo tanto, elegir una lista vinculada vs un array es enteramente sobre pesar la diferentes características de cada estructura en relación a las necesidades de tu app. La superación de la carga adicional de programación no debería tener ningún impacto en la decisión.

Es realmente una cuestión de eficiencia, la sobrecarga para insertar, eliminar o mover (donde no se está simplemente intercambiando) 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 hacer una diferencia significativa si está operando mucho en una lista de datos. Usted eligió sus tipos de datos basados en cómo va a operar en ellos y elegir el más eficiente para el algoritmo que está utilizando.

Los arrays 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 con datos de manera efectiva.

Matrices Vs Lista Enlazada:

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 todos los elementos se asignan espacio de memoria contiguo.
3. La codificación es más compleja que las matrices.
4. No hay restricción de tamaño en la Lista vinculada, a diferencia de los arrays
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 multi-threading.

Como los arrays son estáticos en naturaleza, por lo tanto todas las operaciones al igual que la asignación de memoria se producen en el momento de la compilación solo. Así que el procesador tiene que poner menos esfuerzo en su tiempo de ejecución .

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

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

Su primer problema, como usted mismo ha señalado, es que la lista vinculada a la inserción 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 da 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 fue modificado, podría retener el índice del elemento como referencia en lugar del puntero, haciendo así que find-next sea una operación O(1), pero como es todo lo que tiene es un puntero al objeto en sí y no hay forma de determinar su índice actual en el array que no sea escaneando todo el "array". Este es un problema insuperable para matrices-incluso si puede inserciones optimizadas, no hay nada que pueda hacer para optimizar la operación de tipo find-next.

En un array tienes el privilegio de acceder a cualquier elemento en O(1) time. Por lo tanto, es adecuado para operaciones como Búsqueda binaria de clasificación rápida, etc. La lista enlazada, por otro lado, es adecuada para la eliminación de inserción, ya que está en O(1) tiempo. Ambos tienen ventajas y desventajas y preferir uno sobre el otro se reduce a lo que desea implementar.

Bigger La pregunta más grande es si podemos tener un híbrido de ambos. Algo así como lo que python y perl implementan como listas.

Lista vinculada

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

1 -> 3 -> 4

Insértese (2)

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

Finalmente

1 -> 2 -> 3 -> 4

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

Simple!

Pero desde Array

| 1 | 3 | 4 |

Insértese (2) | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |

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

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

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

Espero que eso ayude! :)

La lista enlazada es más una sobrecarga de 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 supongamos que desea una matriz de longitud 10^9 no se puede obtener porque obtener una ubicación de memoria continua tiene que estar allí. La lista enlazada podría ser un salvador aquí.

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

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

Diferencia entre ArrayList y LinkedList

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

ArrayList -

1. ArrayList internamente utiliza matriz dinámica para almacenar los elementos de.

2. La manipulación con ArrayList es lenta porque utiliza internamente matriz. Si se elimina cualquier elemento de la matriz, todos los bits se desplazan en memoria.

3. ArrayList la clase puede actuar como una lista solo porque implementa List solamente.
4. ArrayList es mejor para almacenar y accediendo a los datos.

LinkedList -

1. LinkedList internamente usa lista doblemente enlazada para almacenar los elementos.

2. La manipulación con LinkedList es más rápida que ArrayList porque utiliza una lista doblemente vinculada, por lo que no hay bits el cambio es necesario en la memoria.

3. LinkedList la clase puede actuar como una lista y cola porque implementa las interfaces List y Deque.

4. LinkedList es mejor para manipular datos.

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

Disadvatige 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 de enlaces de código (o solo una vez) en la que se incluyen STL y no es tan complicado si todavía tienes que hacerlo.

También creo que la lista de enlaces es mejor que los arrays. porque atravesamos en la lista de enlaces, pero no en matrices

Dependiendo de su idioma, algunas de estas desventajas y ventajas podrían ser consideradas:

Lenguaje de programación C: Cuando se utiliza una lista enlazada (normalmente a través de punteros de estructura), se debe tener una consideración especial para asegurarse de que no se está perdiendo memoria. Como se mencionó anteriormente, las listas enlazadas son fáciles de barajar, porque todo lo que estábamos haciendo es cambiar los punteros, pero ¿vamos a recordar liberar todo?

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

¿Por qué una lista enlazada sobre un array ? Así como algunos ya han dicho, mayor velocidad de inserciones y eliminaciones.

Pero tal vez no tenemos 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 'Deleted', para representar el hecho de que una fila ha sido eliminada, por lo que ya no es necesario reorganizar la matriz. Para aliviar la carga de inserciones, o datos que cambian rápidamente, use una lista vinculada para eso. Entonces cuando se refiera a ellos, haga que su lógica primero busque uno, luego el otro. Por lo tanto, el uso de ellos en combinación le da lo mejor de ambos.

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

Mientras que muchos de ustedes han tocado los principales adv. / dis de la lista vinculada vs matriz, la mayoría de las comparaciones son cómo uno es mejor / peor que el other.Eg. puede hacer el 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 prefiere la lista de enlaces a la matriz y viceversa en una implementación de aplicación en particular. Supongamos que desea implementar un aplicación de diccionario, ¿qué usarías ? Array: mmm permitiría una fácil recuperación a través de la búsqueda binaria y otra búsqueda algo .. pero vamos a pensar cómo la lista de enlaces puede ser mejor..Digamos que quieres buscar "Blob" en el diccionario. Tendría sentido tener una lista de enlaces de A- > B- > C- > D - - - - >Z y luego cada elemento de la lista también apuntando a una matriz u otra lista de todas las palabras que comienzan con esa letra ..

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

Ahora es mejor el enfoque anterior o una matriz plana de [Adán, Manzana, Plátano, Gota, Gato, Cueva] ? ¿Sería posible con array ? Por lo tanto, una ventaja importante de la lista de enlaces es que puede tener un elemento no solo apuntando al siguiente elemento, sino también a alguna otra lista de enlaces/matriz/ montón/ o cualquier otra ubicación de memoria. Array es una memoria contigua plana cortada en bloques de tamaño del elemento que va a almacenar.. Por otro lado, la lista de enlaces es un fragmento de unidades de memoria no contiguas (puede ser de cualquier tamaño y puede almacenar cualquier cosa) y apuntando entre sí de la manera que desee. Del mismo modo permite decir que están haciendo una unidad USB. Ahora le gustaría que los archivos se guarden como cualquier matriz o como una lista de enlaces ? Creo que tienes la idea de lo que estoy señalando:)