¿Cuáles son las listas vinculadas en Java y qué las hace mejores que las matrices normales?

Lo que voy a decir no solo es cierto sobre Java, es cierto sobre cualquier lenguaje de programación que tenga listas vinculadas como una opción.

Supongamos que tiene una serie de enteros:

int [] arr = {2, 3, 4, 5, 6};

y date cuenta de que olvidaste el número [math] 1 [/ math]. Desea colocarlo al comienzo de los números porque desea mantener los números en orden.

¿Cómo lo haces? Bueno, (suponiendo que tenga espacio) tiene que deslizar todos los números a la posición correcta, y los números escriben un [matemático] 1 [/ matemático] al principio. Me gusta esto:

para (int i = 4; i> = 0; i–)
arr [i + 1] = arr [i];
arr [0] = 1;

¿Cuántas operaciones lleva esto? Toma aproximadamente [math] 5 [/ math] operaciones en este caso, porque la matriz era de longitud [math] 5 [/ math]. En general, esto tomará aproximadamente [math] n [/ math] pasos (escrito [math] \ Theta (n) [/ math] donde [math] n = [/ math] arr.length .

Ahora, una lista vinculada no funciona de esta manera. En una lista vinculada, cada vez que desee agregar un elemento a la lista, lo asignó dinámicamente sobre la marcha y lo adjuntó a la lista actualizando las referencias.

Define una clase ListNode:

clase ListNode {
datos int públicos; // podría ser cualquier typr
ListNode público siguiente;
}

En realidad, podría abarcar esta clase dentro de la otra clase.

Una clase de Lista debería mantener una referencia al primer nodo, generalmente llamado cabeza.

Lista de clase {
privada ListNode head = null;
}

public void addToFront (valor int) {

// crea un nuevo nodo con el valor “valor”

ListNode newOne = new ListNode ();
newOne.data = value;

// si no hay nodos, entonces haga el
// apunta al nuevo nodo
// y establece newOne’s junto a null
if (head == null) {
newOne.next = null;
head = newOne;
más {
newOne.next = head;
head = newOne;
} // de lo contrario, establezca newOne’s junto a
// ser lo que solía ser la cabeza de la
// lista, y hacer newOne la nueva cabeza.
}

¿Cuánto tiempo addToFront() ejecución de addToFront() ? Tenga en cuenta que no tenemos ningún bucle. Hacemos aproximadamente el mismo número de operaciones, independientemente de cuántos números almacenamos. Esto lleva tiempo constante, o tiempo [matemático] \ Theta (1) [/ matemático].

Si la matriz tuviera un millón de elementos, la operación addToFront () tomaría aproximadamente un millón de operaciones, mientras que en una lista vinculada, tomaría algunas operaciones.

Las listas no son mejores que las matrices, son más flexibles, pero si se trabaja con una cantidad específica de elementos, una matriz es más efectiva porque los datos se almacenan en una línea de memoria, la lista contiene elementos distribuidos aleatoriamente en la memoria asignada.

En las matrices normales, debe definir su tamaño antes de usarlo, pero en la lista vinculada, su tamaño aumenta automáticamente según sus necesidades. No tiene que preocuparse por el tamaño de la lista vinculada, se aumenta o disminuye automáticamente según sus operaciones.

Las listas enlazadas son buenas para insertar elementos en el medio de la lista (O (1)), que la matriz no puede manejar bien. Las matrices son buenas para el acceso aleatorio del elemento k-ésimo (O (1)), que es O (k) para las listas.

Una lista vinculada es algo que no tiene límite de cuántos valores va a almacenar. Puede almacenar 5 o 50 o 500, depende de usted. Pero en la matriz, debe declarar cuántos valores va a almacenar al máximo. Me gusta:

int arr [60];

significa que vas a almacenar como máximo 60 enteros. No puedes exceder el límite.

En la lista vinculada cada vez que almacena un valor, también almacena un puntero donde se almacenará su próximo valor si desea almacenar más. De esa manera no tiene límite para almacenar valores.