Las arrays almacenan elementos en ubicaciones de memoria contiguas, lo que da como resultado direcciones fácilmente calculables para los elementos almacenados y esto permite un acceso más rápido a un elemento en un índice específico. Las listas vinculadas son menos rígidas en su estructura de almacenamiento y los elementos generalmente no se almacenan en ubicaciones contiguas, por lo que deben almacenarse con etiquetas adicionales que proporcionen una referencia al siguiente elemento. Esta diferencia en el esquema de almacenamiento de datos decide qué estructura de datos sería más adecuada para una situación determinada.
Esquema de almacenamiento de datos de una array
Esquema de almacenamiento de datos de una lista enlazada
Las principales diferencias se enumeran a continuación:
- Tamaño: dado que los datos solo se pueden almacenar en bloques contiguos de memoria en una array, su tamaño no se puede modificar en tiempo de ejecución debido al riesgo de sobrescribir otros datos. Sin embargo, en una lista enlazada, cada Node apunta al siguiente, de modo que los datos pueden existir en direcciones dispersas (no contiguas); esto permite un tamaño dinámico que puede cambiar en tiempo de ejecución.
- Asignación de memoria: para arrays en tiempo de compilación y en tiempo de ejecución para listas vinculadas. pero una array asignada dinámicamente también asigna memoria en tiempo de ejecución.
- Eficiencia de la memoria: para la misma cantidad de elementos, las listas enlazadas usan más memoria ya que la referencia al siguiente Node también se almacena junto con los datos. Sin embargo, la flexibilidad de tamaño en las listas vinculadas puede hacer que usen menos memoria en general; esto es útil cuando hay incertidumbre sobre el tamaño o hay grandes variaciones en el tamaño de los elementos de datos; se debe asignar memoria equivalente al límite superior del tamaño (incluso si no se usa toda) mientras se usan arrays, mientras que las listas vinculadas pueden aumentar su tamaño paso a paso proporcionalmente a la cantidad de datos.
- Tiempo de ejecución: se puede acceder directamente a cualquier elemento de una array con su índice; sin embargo, en el caso de una lista enlazada, se deben recorrer todos los elementos anteriores para llegar a cualquier elemento. Además, una mejor localidad de caché en arrays (debido a la asignación de memoria contigua) puede mejorar significativamente el rendimiento. Como resultado, algunas operaciones (como modificar un determinado elemento) son más rápidas en arrays, mientras que otras (como insertar/eliminar un elemento en los datos) son más rápidas en listas enlazadas.
- Inserción: en una array, la operación de inserción lleva más tiempo, pero en una lista vinculada, estas operaciones son rápidas. Por ejemplo, si queremos insertar un elemento en la array en la posición final de la array y la array está llena, copiamos la array en otra array y luego podemos agregar un elemento, mientras que si la lista vinculada está llena, encontramos el último Node y hacerlo al lado del nuevo Node
- Dependencia : en la array, los valores son independientes entre sí, pero en el caso de la lista vinculada, los Nodes dependen entre sí. un Node depende de su Node anterior. Si el Node anterior se pierde, no podemos encontrar sus siguientes Nodes posteriores.
Array vs lista enlazada
Los siguientes son los puntos a favor de las Listas Enlazadas.
(1) El tamaño de las arrays es fijo: por lo tanto, debemos conocer el límite superior del número de elementos por adelantado. Además, generalmente, la memoria asignada es igual al límite superior independientemente del uso y, en los usos prácticos, rara vez se alcanza el límite superior.
(2) Insertar un nuevo elemento en una array de elementos es costoso porque se debe crear una habitación para los nuevos elementos y para crear una habitación se deben cambiar los elementos existentes.
Por ejemplo, supongamos que mantenemos una lista ordenada de ID en una array id[].
id[ ] = [1000, 1010, 1050, 2000, 2040, …..].
Y si queremos insertar un nuevo ID 1005, entonces para mantener el orden ordenado, tenemos que mover todos los elementos después de 1000 (excluyendo 1000).
La eliminación también es costosa con arrays a menos que se utilicen algunas técnicas especiales. Por ejemplo, para eliminar 1010 en id[], todo lo que esté después de 1010 debe moverse.
Entonces, la lista enlazada proporciona las siguientes dos ventajas sobre las arrays
1) Tamaño dinámico
2) Facilidad de inserción/eliminación
Las listas enlazadas tienen los siguientes inconvenientes:
1) No se permite el acceso aleatorio. Tenemos que acceder a los elementos de forma secuencial a partir del primer Node. Entonces no podemos hacer una búsqueda binaria con listas enlazadas.
2) Se requiere espacio de memoria adicional para un puntero para cada elemento de la lista.
3) Las arrays tienen una mejor localidad de caché que puede marcar una gran diferencia en el rendimiento.
4) Lleva mucho tiempo atravesar y cambiar los punteros.
5) Será confuso cuando trabajemos con punteros.
La array tiene los siguientes inconvenientes:
1) La array es de naturaleza estática. Una vez que se declara el tamaño de la array, no podemos modificarla.
2) Las operaciones de inserción y eliminación son difíciles en una array ya que los elementos se almacenan en ubicaciones de memoria contiguas y las operaciones de cambio son costosas.
3) La cantidad de elementos que deben almacenarse en una array debe conocerse de antemano.
4) El desperdicio de memoria es el principal problema de la array. Si el tamaño de la array es grande, la menor asignación de memoria conduce al desperdicio de memoria.
Referencias:
http://cslibrary.stanford.edu/103/LinkedListBasics.pdf
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA