Los arrays almacenan elementos en ubicaciones de memoria contiguas, lo que resulta en 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 enlazadas son menos rígidas en su estructura de almacenamiento y los elementos no suelen almacenarse en ubicaciones contiguas, por lo que deben almacenarse con etiquetas adicionales que den 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 un array

Esquema de almacenamiento de datos de una lista enlazada

Las principales diferencias se enumeran a continuación:

• Tamaño: Dado que los datos sólo pueden ser almacenados en bloques contiguos de memoria en un array, su tamaño no puede ser alterado en tiempo de ejecución debido al riesgo de sobrescribir sobre otros datos. Sin embargo, en una lista enlazada, cada nodo 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 los arrays en tiempo de compilación y en tiempo de ejecución para las listas enlazadas.
• Eficiencia de la memoria: Para el mismo número de elementos, las listas enlazadas utilizan más memoria ya que la referencia al siguiente nodo también se almacena junto con los datos. Sin embargo, la flexibilidad de tamaño en las listas enlazadas puede hacer que utilicen 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 los datos; la memoria equivalente al límite superior del tamaño tiene que ser asignada (incluso si no se está utilizando toda) mientras se utilizan matrices, mientras que las listas enlazadas 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 un array con su índice; sin embargo, en el caso de una lista enlazada, hay que recorrer todos los elementos anteriores para llegar a cualquier elemento. Además, la mejor localización de la caché en los arrays (debido a la asignación de memoria contigua) puede mejorar significativamente el rendimiento. Como resultado, algunas operaciones (como la modificación de un determinado elemento) son más rápidas en los arrays, mientras que otras (como la inserción/eliminación de un elemento en los datos) son más rápidas en las listas enlazadas.

Los siguientes son los puntos a favor de las listas enlazadas.
(1) El tamaño de las matrices es fijo: Así que debemos conocer el límite superior del número de elementos por adelantado. Además, por lo general, la memoria asignada es igual al límite superior independientemente del uso, y en los usos prácticos, el límite superior rara vez se alcanza.

(2) Insertar un nuevo elemento en un array de elementos es caro porque hay que crear un espacio para los nuevos elementos y para crear espacio hay que desplazar los elementos existentes.

Por ejemplo, supongamos que mantenemos una lista ordenada de IDs en un array id.

id = .

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 los arrays hasta que se utilicen algunas técnicas especiales. Por ejemplo, para borrar 1010 en id, hay que mover todo lo que está después de 1010.

Así que las listas enlazadas proporcionan las siguientes dos ventajas sobre los arrays
1) Tamaño dinámico
2) Facilidad de inserción/borrado

Las listas enlazadas tienen los siguientes inconvenientes:
1) No se permite el acceso aleatorio. Tenemos que acceder a los elementos secuencialmente empezando por el primer nodo. Así que no podemos hacer una búsqueda binaria con listas enlazadas.
2) Se requiere espacio de memoria extra para un puntero con cada elemento de la lista.
3) Los arrays tienen una mejor localidad de caché que puede hacer una diferencia bastante grande en el rendimiento.