Java ArrayList vs LinkedList

1. Panoramica

Quando si tratta di collezioni, la libreria standard Java offre molte opzioni tra cui scegliere. Tra queste opzioni ci sono due famose implementazioni di List note come ArrayList e LinkedList, ciascuna con le proprie proprietà e casi d'uso.

In questo tutorial, vedremo come questi due sono effettivamente implementati. Quindi, valuteremo diverse applicazioni per ciascuna.

2. ArrayList

Internamente, ArrayList utilizza un array per implementare l' interfaccia List . Poiché gli array sono di dimensioni fisse in Java, ArrayList crea un array con una certa capacità iniziale. Lungo il percorso, se abbiamo bisogno di immagazzinare più articoli rispetto alla capacità predefinita, sostituirà quell'array con uno nuovo e più spazioso.

Per comprenderne meglio le proprietà, valutiamo questa struttura dati rispetto alle sue tre operazioni principali: aggiungere elementi, ottenerne uno per indice e rimuovere per indice.

2.1. Inserisci

Quando creiamo un ArrayList vuoto , inizializza il suo array di supporto con una capacità predefinita (attualmente 10):

Aggiungere un nuovo elemento mentre l'array non è ancora pieno è semplice come assegnare quell'elemento a uno specifico indice dell'array. Questo indice dell'array è determinato dalla dimensione dell'array corrente poiché stiamo praticamente aggiungendo all'elenco:

backingArray[size] = newItem; size++;

Quindi, nei casi migliori e medi, la complessità temporale per l'operazione di aggiunta è O (1) , che è piuttosto veloce. Man mano che l'array di supporto diventa pieno, tuttavia, l'implementazione dell'aggiunta diventa meno efficiente:

Per aggiungere un nuovo elemento, dovremmo prima inizializzare un nuovo array con più capacità e copiare tutti gli elementi esistenti nel nuovo array. Solo dopo aver copiato gli elementi correnti possiamo aggiungere il nuovo elemento. Quindi, la complessità temporale è O (n) nel caso peggiore poiché dobbiamo prima copiare n elementi.

Teoricamente parlando, l'aggiunta di un nuovo elemento viene eseguito in tempo costante ammortizzato. Cioè, l'aggiunta di n elementi richiede O (n) tempo. Tuttavia, alcune singole aggiunte potrebbero funzionare male a causa del sovraccarico della copia.

2.2. Accesso per indice

L'accesso agli elementi in base ai loro indici è il punto in cui ArrayList brilla davvero. Per recuperare un elemento all'indice i, dobbiamo solo restituire l'elemento che risiede all'indice i- esimo dall'array di supporto. Di conseguenza, la complessità temporale per l'accesso tramite l'operazione sugli indici è sempre O (1).

2.3. Rimuovi per indice

Supponiamo di rimuovere l'indice 6 dal nostro ArrayList, che corrisponde all'elemento 15 nel nostro array di supporto:

Dopo aver contrassegnato l'elemento desiderato come eliminato, dovremmo spostare tutti gli elementi dopo di esso indietro di un indice. Ovviamente, più l'elemento è vicino all'inizio dell'array, più elementi dovremmo spostare. Quindi la complessità temporale è O (1) nel caso migliore e O (n) in media e nei casi peggiori.

2.4. Applicazioni e limitazioni

Di solito, ArrayList è la scelta predefinita per molti sviluppatori quando hanno bisogno di un'implementazione di List . È un dato di fatto, in realtà è una scelta sensata quando il numero di letture è molto superiore al numero di scritture .

A volte abbiamo bisogno di letture e scritture altrettanto frequenti. Se disponiamo di una stima del numero massimo di elementi possibili, ha comunque senso utilizzare ArrayList . In tal caso, possiamo inizializzare ArrayList con una capacità iniziale:

int possibleUpperBound = 10_000; List items = new ArrayList(possibleUpperBound);

Questa stima può impedire molte copie non necessarie e allocazioni di array.

Inoltre, gli array sono indicizzati da valori int in Java. Quindi, non è possibile memorizzare più di 232 elementi in un array Java e, di conseguenza, in ArrayList .

3. LinkedList

LinkedList , come suggerisce il nome, utilizza una raccolta di nodi collegati per archiviare e recuperare elementi . Ad esempio, ecco come si occupa l'implementazione Java dopo l'aggiunta di quattro elementi:

Ogni nodo mantiene due puntatori: uno che punta all'elemento successivo e un altro che fa riferimento a quello precedente. Espandendo questo, la lista doppiamente collegata ha due puntatori che puntano al primo e all'ultimo elemento.

Anche in questo caso, valutiamo questa implementazione rispetto alle stesse operazioni fondamentali.

3.1. Inserisci

Per aggiungere un nuovo nodo, prima dovremmo collegare l'ultimo nodo corrente al nuovo nodo:

E poi aggiorna l'ultimo puntatore:

Poiché entrambe queste operazioni sono banali, la complessità temporale per l'operazione di aggiunta è sempre O (1) .

3.2. Accesso per indice

LinkedList, a differenza di ArrayList, non supporta l'accesso casuale veloce. Quindi, per trovare un elemento per indice, dovremmo attraversare manualmente una parte della lista .

Nel migliore dei casi, quando l'elemento richiesto è vicino all'inizio o alla fine della lista, la complessità temporale sarebbe veloce quanto O (1). Tuttavia, negli scenari nella media e nel peggiore dei casi, potremmo ritrovarci con un tempo di accesso O (n) poiché dobbiamo esaminare molti nodi uno dopo l'altro.

3.3. Rimuovi per indice

Per rimuovere un elemento, dobbiamo prima trovare l'elemento richiesto e quindi scollegarlo dall'elenco . Di conseguenza, il tempo di accesso determina la complessità temporale, ovvero O (1) nel migliore dei casi e O (n) in media e negli scenari peggiori.

3.4. Applicazioni

Le LinkedList sono più adatte quando la velocità di aggiunta è molto più alta della velocità di lettura .

Inoltre, può essere utilizzato in scenari di lettura intensa quando la maggior parte delle volte si desidera il primo o l'ultimo elemento. Vale la pena ricordare che LinkedList implementa anche l' interfaccia Deque , supportando un accesso efficiente a entrambe le estremità della raccolta.

In generale, se conosciamo le differenze di implementazione, potremmo facilmente sceglierne uno per un particolare caso d'uso.

Ad esempio, supponiamo di memorizzare molti eventi di serie temporali in una struttura dati simile a un elenco. Sappiamo che avremmo ricevuto esplosioni di eventi ogni secondo.

Inoltre, dobbiamo esaminare periodicamente tutti gli eventi uno dopo l'altro e fornire alcune statistiche. Per questo caso d'uso, LinkedList è una scelta migliore perché la velocità di aggiunta è molto più alta della velocità di lettura.

Inoltre, leggeremmo tutti gli elementi, quindi non possiamo battere il limite superiore O (n) .

4. Conclusione

In questo tutorial, per prima cosa, ci siamo tuffati nel modo in cui ArrayList e LinkLists sono implementati in Java.

Abbiamo anche valutato diversi casi d'uso per ciascuno di questi.