Formación y Lista enlazada son las dos formas de organizar los datos en la memoria. Antes de comprender las diferencias entre Formación y el Lista enlazada , primero miramos en una matriz y una lista enlazada .

excepción personalizada en java

¿Qué es una matriz?

Una estructura de datos que contiene los elementos del mismo tipo. Una estructura de datos es una forma de organizar los datos; una matriz es una estructura de datos porque organiza los datos secuencialmente. Una matriz es una gran porción de memoria en la que la memoria se divide en bloques pequeños y cada bloque es capaz de almacenar algún valor.

Supongamos que hemos creado una matriz que consta de 10 valores, luego cada bloque almacenará el valor de un tipo entero. Si intentamos almacenar el valor en una matriz de diferentes tipos, entonces no es una matriz correcta y arrojará un error en tiempo de compilación.

Declaración de matriz

Una matriz se puede declarar como:

 data_type name of the array[no of elements] 

Para declarar una matriz, primero debemos especificar el tipo de matriz y luego el nombre de la matriz. Dentro de los corchetes, debemos especificar la cantidad de elementos que debe contener nuestra matriz.

Entendamos a través de un ejemplo.

 int a[5]; 

En el caso anterior, hemos declarado una matriz de 5 elementos con ' a ' nombre de un entero tipo de datos.

¿Qué es la lista enlazada?

Una lista enlazada es una colección de nodos que se almacenan aleatoriamente. Cada nodo consta de dos campos, es decir, datos y enlace . Aquí, los datos son el valor almacenado en ese nodo en particular y el enlace es el puntero que contiene la dirección del siguiente nodo.

cadena de entrada java

Diferencias entre matriz y lista enlazada

No podemos decir qué estructura de datos es mejor, es decir, matriz o lista enlazada . Puede existir la posibilidad de que una estructura de datos sea mejor para un tipo de requisito, mientras que la otra estructura de datos sea mejor para otro tipo de requisito. Hay varios factores, como cuáles son las operaciones frecuentes que se realizan en la estructura de datos o el tamaño de los datos, y otros factores también sobre qué base se selecciona la estructura de datos. Ahora veremos algunas diferencias entre la matriz y la lista vinculada en función de algunos parámetros.

1. Costo de acceso a un elemento

En el caso de una matriz, independientemente del tamaño de la matriz, una matriz tarda un tiempo constante en acceder a un elemento. En una matriz, los elementos se almacenan de manera contigua, por lo que si conocemos la dirección base del elemento, podemos obtener fácilmente la dirección de cualquier elemento en una matriz. Necesitamos realizar un cálculo simple para obtener la dirección de cualquier elemento de una matriz. Entonces, acceder al elemento en una matriz es O(1) en términos de complejidad temporal.

En la lista enlazada, los elementos no se almacenan de forma contigua. Consta de varios bloques y cada bloque está representado como un nodo. Cada nodo tiene dos campos, es decir, uno es para el campo de datos y otro almacena la dirección del siguiente nodo. Para encontrar cualquier nodo en la lista vinculada, primero debemos determinar el primer nodo conocido como nodo principal. Si tenemos que encontrar el segundo nodo en la lista, entonces debemos atravesar desde el primer nodo y, en el peor de los casos, para encontrar el último nodo, atravesaremos todos los nodos. El caso promedio para acceder al elemento es O(n).

Concluimos que el costo de acceder a un elemento de la matriz es menor que el de la lista vinculada. Por lo tanto, si tenemos algún requisito para acceder a los elementos, entonces la matriz es una mejor opción.

2. Costo de insertar un elemento

Puede haber tres escenarios en la inserción:

Insertando el elemento al principio:Para insertar el nuevo elemento al principio, primero debemos mover el elemento hacia la derecha para crear un espacio en la primera posición. Entonces, la complejidad del tiempo será proporcional al tamaño de la lista. Si n es el tamaño de la matriz, la complejidad temporal sería O(n).

En el caso de una lista vinculada, para insertar un elemento al comienzo de la lista vinculada, crearemos un nuevo nodo y la dirección del primer nodo se agregará al nuevo nodo. De esta forma, el nuevo nodo se convierte en el primer nodo. Entonces, la complejidad del tiempo no es proporcional al tamaño de la lista. La complejidad del tiempo sería constante, es decir, O(1).

Insertar un elemento al final

Si la matriz no está llena, podemos agregar directamente el nuevo elemento a través del índice. En este caso, la complejidad del tiempo sería constante, es decir, O(1). Si la matriz está llena, primero debemos copiar la matriz en otra matriz y agregar un nuevo elemento. En este caso, la complejidad temporal sería O(n).

Para insertar un elemento al final de la lista enlazada, tenemos que recorrer toda la lista. Si la lista enlazada consta de n elementos, entonces la complejidad temporal sería O (n).

Insertar un elemento en el medio

Supongamos que queremos insertar el elemento en la i^thposición de la matriz; Necesitamos desplazar los n/2 elementos hacia la derecha. Por tanto, la complejidad del tiempo es proporcional al número de elementos. La complejidad temporal sería O(n) para el caso promedio.

tamaño de pitón

En el caso de una lista enlazada, tenemos que recorrer hasta esa posición donde tenemos que insertar el nuevo elemento. Sin embargo, no tenemos que realizar ningún tipo de cambio, pero tenemos que atravesar la posición n/2. El tiempo necesario es proporcional al n número de elementos, y la complejidad temporal para el caso promedio sería O(n).

La lista enlazada resultante es:

Facilidad de uso

La implementación de una matriz es fácil en comparación con la lista vinculada. Al crear un programa utilizando una lista vinculada, el programa es más propenso a errores como fallas de segmentación o pérdida de memoria. Por lo tanto, se debe tener mucho cuidado al crear un programa en la lista vinculada.

Dinámico en tamaño

La lista vinculada tiene un tamaño dinámico mientras que la matriz es estática. Aquí, estático no significa que no podamos decidir el tamaño en tiempo de ejecución, pero no podemos cambiarlo una vez que se decide el tamaño.

3. Requisitos de memoria

Como los elementos de una matriz se almacenan en un bloque contiguo de memoria, la matriz tiene un tamaño fijo. Supongamos que tenemos una matriz de tamaño 7 y la matriz consta de 4 elementos, entonces el resto del espacio no se utiliza. La memoria ocupada por los 7 elementos:

Espacio de memoria = 7*4 = 28 bytes

Donde 7 es el número de elementos de una matriz y 4 es el número de bytes de un tipo entero.

En el caso de una lista enlazada, no hay memoria no utilizada, pero la memoria adicional está ocupada por las variables de puntero. Si los datos son de tipo entero, entonces la memoria total ocupada por un nodo es de 8 bytes, es decir, 4 bytes para datos y 4 bytes para variable de puntero. Si la lista enlazada consta de 4 elementos, entonces el espacio de memoria ocupado por la lista enlazada sería:

controlador web

Espacio de memoria = 8*4 = 32 bytes

La lista vinculada sería una mejor opción si la parte de datos fuera de mayor tamaño. Supongamos que los datos son de 16 bytes. El espacio de memoria ocupado por la matriz sería 16*7=112 bytes mientras que la lista enlazada ocupa 20*4=80, aquí hemos especificado 20 bytes como 16 bytes para el tamaño de los datos más 4 bytes para la variable de puntero. Si elegimos un tamaño de datos más grande, entonces la lista vinculada consumiría menos memoria; en caso contrario, depende de los factores que estemos adoptando para determinar el tamaño.

Veamos las diferencias entre la matriz y la lista vinculada en forma tabular.