En general, la array se considera una estructura de datos cuyo tamaño se fija en el momento de la compilación, y la memoria de la array se asigna desde la sección de datos (p. ej., array global) o la sección de pila (p. ej., array local).
De manera similar, una lista enlazada se considera una estructura de datos para la cual el tamaño no es fijo y la memoria se asigna desde la sección Heap (por ejemplo, usando malloc(), etc.) cuando sea necesario. En este sentido, la array se toma como una estructura de datos estática (que reside en la sección Datos o Pila) mientras que la lista enlazada se toma como una estructura de datos dinámica (que reside en la sección Heap). La representación de memoria de la array y la lista vinculada se puede visualizar de la siguiente manera:
Se ha inicializado una array de 4 elementos (tipo entero) con 1, 2, 3 y 4. Supongamos que estos elementos se asignan en las direcciones de memoria 0x100, 0x104, 0x108 y 0x10C respectivamente.
[(1)] [(2)] [(3)] [(4)] 0x100 0x104 0x108 0x10C
Una lista enlazada con 4 Nodes donde cada Node tiene un número entero como datos y estos datos se inicializan con 1, 2, 3 y 4. Supongamos que estos Nodes se asignan a través de malloc() y la memoria asignada para ellos es 0x200, 0x308, 0x404 y 0x20B respectivamente.
[(1), 0x308] [(2),0x404] [(3),0x20B] [(4),NULL] 0x200 0x308 0x404 0x20B
Cualquiera que tenga un conocimiento mínimo de la array y la lista enlazada podría no estar interesado en la explicación anterior. Quiero decir, es bien sabido que a los elementos de la array se les asigna memoria en secuencia, es decir, memoria contigua, mientras que los Nodes de una lista vinculada no son contiguos en la memoria. Aunque suene trivial, esta es la diferencia más importante entre una array y una lista enlazada. Cabe señalar que debido a esta memoria contigua versus no contigua, la array y la lista vinculada son diferentes. ¡Esta diferencia es lo que hace que la array sea la lista enlazada! En las siguientes secciones, trataremos de explorar esta misma idea más a fondo.
Dado que los elementos de una array son contiguos en la memoria, podemos acceder a cualquier elemento aleatoriamente usando un índice, por ejemplo, intArr[3] accederá directamente al cuarto elemento de la array. (Para los novatos, la indexación de arrays comienza desde 0 y es por eso que el cuarto elemento está indexado con 3). Además, debido a la memoria contigua para elementos sucesivos en la array, no se necesita almacenar información adicional en elementos individuales, es decir, no hay sobrecarga de metadatos en las arrays. Al contrario de esto, los Nodes de la lista enlazada no son contiguos en la memoria. Significa que necesitamos algún mecanismo para atravesar o acceder a los Nodes de la lista enlazada. Para lograr esto, cada Node almacena la ubicación del siguiente Node y esto forma la base del enlace de un Node al siguiente Node. Por lo tanto, se llama lista enlazada. Aunque almacenar la ubicación del siguiente Node es una sobrecarga en la lista vinculada, es obligatorio.
C
struct llNode
{
int dataInt;
/* nextNode is the pointer to next node in linked list*/
struct llNode * nextNode;
};
Por lo tanto, los elementos de la array son contiguos en la memoria y, por lo tanto, no requieren ningún metadato. Y los Nodes de la lista enlazada no son contiguos en la memoria, por lo que requieren metadatos en forma de la ubicación del siguiente Node. Aparte de esta diferencia, podemos ver que la array podría tener varios elementos sin usar porque la memoria ya se ha asignado. Pero la lista enlazada solo tendrá el número requerido. de elementos de datos. Toda la información anterior sobre la array y la lista enlazada se ha mencionado en varios libros de texto, aunque de diferentes maneras.
¿Qué sucede si necesitamos asignar memoria de array desde la sección Heap (es decir, en tiempo de ejecución) y memoria de lista vinculada desde la sección Data/Stack? En primer lugar, ¿es posible? Antes de eso, uno podría preguntarse por qué alguien necesitaría hacer esto. Ahora, espero que el artículo restante te haga reconsiderar la idea de array frente a lista enlazada 🙂
Ahora considere el caso en el que necesitamos almacenar ciertos datos en una array (porque la array tiene la propiedad de acceso aleatorio debido a la memoria contigua) pero no sabemos el tamaño total a priori. Una posibilidad es asignar memoria de esta array desde Heap en tiempo de ejecución. Por ejemplo, de la siguiente manera:
/*En tiempo de ejecución, supongamos que conocemos el tamaño requerido para una array de enteros (por ejemplo, el tamaño de entrada del usuario). Digamos que el tamaño de la array se almacena en la variable arrSize. Asigne esta array desde Heap de la siguiente manera*/
C
int * dynArr = (int *)malloc(sizeof(int)*arrSize);
Aunque la memoria de esta array se asigna desde Heap, aún se puede acceder a los elementos a través del mecanismo de índice, por ejemplo, dynArr[i]. Basándonos en el problema de programación, hemos combinado un beneficio de la array (es decir, acceso aleatorio de elementos) y un beneficio de la lista enlazada (es decir, retrasar la asignación de memoria hasta el tiempo de ejecución y asignar memoria desde Heap). Otra ventaja de tener este tipo de array dinámica es que este método de asignación de array desde Heap en tiempo de ejecución podría reducir el tamaño del código (por supuesto, depende de otros factores, por ejemplo, el formato del programa, etc.)
Ahora considere el caso cuando necesitamos almacenar datos en una lista enlazada (porque el número de Nodes en una lista enlazada sería igual a los elementos de datos reales almacenados, es decir, no hay espacio adicional como una array) pero no podemos obtener esta memoria de Heap una y otra vez para cada Node. Esto puede parecer una situación hipotética para algunas personas, pero no es un requisito poco común en los sistemas integrados. Básicamente, en varios programas integrados, la asignación de memoria a través de malloc(), etc. no está permitida por múltiples razones. Una razón obvia es el rendimiento, es decir, asignar memoria a través de malloc() es costoso en términos de complejidad de tiempo porque se requiere que su programa integrado sea determinista la mayor parte del tiempo. Otra razón podría ser la gestión de memoria específica del módulo, es decir, cada módulo del sistema integrado puede gestionar su memoria. En definitiva, si necesitamos realizar nuestra gestión de memoria, en lugar de depender de las API proporcionadas por el sistema de malloc() y free(), podríamos elegir la lista vinculada que se simula mediante una array. Espero que tenga una idea de por qué podríamos necesitar simular la lista enlazada usando una array. Ahora, primero veamos cómo se puede hacer esto. Supongamos que el tipo de un Node en la lista enlazada (es decir, la array subyacente) se declara de la siguiente manera:
C
struct sllNode
{
int dataInt;
/*Here, note that nextIndex stores the location of next node in
linked list*/
int nextIndex;
};
struct sllNode arrayLL[5];
Si inicializamos esta lista enlazada (que en realidad es una array), se vería de la siguiente manera en la memoria:
[(0),-1] [(0),-1] [(0),-1] [(0),-1] [(0),-1] 0x500 0x508 0x510 0x518 0x520
Lo importante a tener en cuenta es que todos los Nodes de la lista enlazada son contiguos en la memoria (cada uno ocupa 8 bytes) y el siguiente índice de cada Node se establece en -1. Esto (es decir, -1) se hace para indicar que cada Node de la lista enlazada está vacío a partir de ahora. Esta lista enlazada se denota con el índice principal 0.
Ahora, si esta lista enlazada se actualiza con cuatro elementos de las partes de datos 4, 3, 2 y 1 sucesivamente, se vería de la siguiente manera en la memoria. Esta lista enlazada se puede ver como 0x500 -> 0x508 -> 0x510 -> 0x518.
[(1),1] [(2),2] [(3),3] [(4),-2] [(0),-1] 0x500 0x508 0x510 0x518 0x520
Lo importante a tener en cuenta es que el índice siguiente del último Node (es decir, el cuarto Node) se establece en -2. Esto (es decir, -2) se hace para indicar el final de la lista enlazada. Además, el Node principal de la lista vinculada es el índice 0. Este concepto de simulación de listas vinculadas mediante una array parecería más interesante si eliminamos, por ejemplo, el segundo Node de la lista vinculada anterior. En ese caso, la lista enlazada se verá de la siguiente manera en la memoria:
[(1),2] [(0),-1] [(3),3] [(4),-2] [(0),-1] 0x500 0x508 0x510 0x518 0x520
La lista enlazada resultante es 0x500 -> 0x510 -> 0x518. Aquí, debe tenerse en cuenta que aunque hemos eliminado el segundo Node de nuestra lista vinculada, la memoria de este Node todavía está allí porque la array subyacente todavía está allí. Pero el siguiente índice del primer Node ahora apunta al tercer Node (para el cual el índice es 2).
Con suerte, los ejemplos anteriores habrían dado una idea de que para la lista enlazada simulada, necesitamos escribir nuestra API similar a malloc() y free() que se usaría para insertar y eliminar un Node. Ahora, esto es lo que se llama gestión de memoria propia. Veamos cómo se puede hacer esto algorítmicamente.
Hay varias formas de hacerlo. Si tomamos el enfoque simplista de crear una lista enlazada usando una array, podemos usar la siguiente lógica. Para insertar un Node, recorra la array subyacente y busque un Node cuyo siguiente índice sea -1. Significa que este Node está vacío. Utilice este Node como un nuevo Node. Actualice la parte de datos en este nuevo Node y establezca el siguiente índice de este Node en el Node principal actual (es decir, el índice principal) de la lista enlazada. Finalmente, haga que el índice de este nuevo Node sea el índice principal de la lista enlazada. Para visualizarlo, pongamos un ejemplo. Supongamos que la lista vinculada es la siguiente, donde el índice principal es 0, es decir, la lista vinculada es 0x500 -> 0x508 -> 0x518 -> 0x520
[(1),1] [(2),3] [(0),-1] [(4),4] [(5),-2] 0x500 0x508 0x510 0x518 0x520
Después de insertar un nuevo Node con datos 8, la lista enlazada se vería de la siguiente manera con el índice principal como 2.
[(1),1] [(2),3] [(8),0] [(4),4] [(5),-2] 0x500 0x508 0x510 0x518 0x520
Entonces, los Nodes de la lista enlazada estarían en las direcciones 0x510 -> 0x500 -> 0x508 -> 0x518 -> 0x520
Para eliminar un Node, debemos establecer el siguiente índice del Node como -1 para que el Node se marque como el Node vacío. Pero, antes de hacerlo, debemos asegurarnos de que el siguiente índice del Node anterior se actualice correctamente al índice del siguiente Node de este Node que se eliminará. Podemos ver que hemos realizado nuestra gestión de memoria para crear una lista enlazada a partir de la memoria de array. Pero esta es una forma de insertar y eliminar Nodes en esta lista enlazada. Se puede notar fácilmente que encontrar un Node vacío no es tan eficiente en términos de complejidad de tiempo. Estamos buscando la array completa linealmente para encontrar un Node vacío.
Veamos si podemos optimizarlo aún más. También podemos mantener una lista vinculada de Nodes vacíos en la misma array. En ese caso, la lista enlazada se denotaría mediante dos índices: un índice sería para la lista enlazada que tiene los valores de datos reales, es decir, los Nodes que se han insertado hasta el momento, y los otros índices para una lista enlazada de Nodes vacíos. Al hacerlo, siempre que necesitemos insertar un nuevo Node en la lista vinculada existente, podemos encontrar rápidamente un Node vacío. Tomemos un ejemplo:
[(4),2] [(0),3] [(5),5] [(0),-1] [(0),1] [(9),-1] 0x500 0x508 0x510 0x518 0x520 0x528
La lista enlazada arriba que se representa usando dos índices (0 y 5) tiene dos listas enlazadas: una para valores reales y otra para Nodes vacíos. La lista enlazada con valores reales tiene Nodes en la dirección 0x500 -> 0x510 -> 0x528 mientras que la lista enlazada con Nodes vacíos tiene Nodes en las direcciones 0x520 -> 0x508 -> 0x518. Se puede ver que encontrar un Node vacío (es decir, escribir nuestra API similar a malloc()) debería ser relativamente más rápido ahora porque podemos encontrar rápidamente un Node libre. En los programas integrados del mundo real, un módulo fija una porción fija de la memoria (normalmente llamada grupo de memoria) usando malloc() solo una vez. Y luego, la administración de este grupo de memoria (que es una array) la realiza el propio módulo utilizando las técnicas mencionadas anteriormente. A veces, hay varios grupos de memoria, cada uno con diferentes tamaños de Node. Por supuesto, hay varios otros aspectos de nuestra gestión de memoria, pero los dejaremos aquí. Pero vale la pena mencionar que existen varios métodos mediante los cuales la inserción (que requiere nuestra asignación de memoria) y la eliminación (que requiere nuestra liberación de memoria) se pueden mejorar aún más.
Si observamos detenidamente, se puede notar que la sección Heap de la memoria es una gran array de bytes que está siendo administrada por el sistema operativo (SO) subyacente. Y OS proporciona este servicio de administración de memoria a los programadores a través de malloc(), free(), etc. ¡Ajá!
Los puntos importantes de este artículo se pueden resumir de la siguiente manera:
A) Array significa memoria contigua. Puede existir en cualquier sección de memoria, ya sea Data, Stack o Heap.
B) Lista enlazada significa memoria enlazada no contigua. Puede existir en cualquier sección de memoria, ya sea Montón, Datos o Pila.
C) Como programador, observar una estructura de datos desde la perspectiva de la memoria podría brindarnos una mejor perspectiva para elegir una estructura de datos en particular o incluso diseñar una nueva estructura de datos. Por ejemplo, podríamos crear una array de listas enlazadas, etc.
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