Una guida a Java LinkedList

1. Introduzione

LinkedList è un'implementazione di elenchi a doppio collegamento delle interfacce List e Deque . Implementa tutte le operazioni di elenco facoltative e consente tutti gli elementi (incluso null ).

2. Caratteristiche

Di seguito puoi trovare le proprietà più importanti della LinkedList :

  • Le operazioni che indicizzano nell'elenco attraverseranno l'elenco dall'inizio o dalla fine, a seconda di quale delle due è più vicina all'indice specificato
  • Non è sincronizzato
  • I suoi iteratori Iterator e ListIterator sono veloci (il che significa che dopo la creazione dell'iteratore , se l'elenco viene modificato, verrà generata un'eccezione ConcurrentModificationException )
  • Ogni elemento è un nodo, che mantiene un riferimento a quelli successivi e precedenti
  • Mantiene l'ordine di inserzione

Sebbene LinkedList non sia sincronizzato, possiamo recuperarne una versione sincronizzata chiamando il metodo Collections.synchronizedList , come:

List list = Collections.synchronizedList(new LinkedList(...));

3. Confronto con ArrayList

Sebbene entrambi implementino l' interfaccia List , hanno una semantica diversa, il che influirà sicuramente sulla decisione di quale utilizzare.

3.1. Struttura

Un ArrayList è una struttura dati basata su indice supportata da un Array . Fornisce un accesso casuale ai suoi elementi con una prestazione pari a O (1).

D'altra parte, una LinkedList memorizza i suoi dati come un elenco di elementi e ogni elemento è collegato al suo elemento precedente e successivo. In questo caso, l'operazione di ricerca di un articolo ha tempo di esecuzione pari a O (n).

3.2. Operazioni

Le operazioni di inserimento, aggiunta e rimozione di un elemento sono più veloci in una LinkedList perché non è necessario ridimensionare un array o aggiornare l'indice quando un elemento viene aggiunto in una posizione arbitraria all'interno della raccolta, cambieranno solo i riferimenti negli elementi circostanti.

3.3. Utilizzo della memoria

Un LinkedList consuma più memoria di un ArrayList perché ogni nodo in un LinkedList memorizza due riferimenti, uno per il suo elemento precedente e uno per il suo elemento successivo, mentre ArrayList contiene solo i dati e il suo indice.

4. Utilizzo

Di seguito sono riportati alcuni esempi di codice che mostrano come utilizzare LinkedList :

4.1. Creazione

LinkedList linkedList = new LinkedList();

4.2. Aggiunta di un elemento

LinkedList implementa le interfacce List e Deque , oltre ai metodi standard add () e addAll () puoi trovare addFirst () e addLast () , che aggiungono un elemento rispettivamente all'inizio o alla fine.

4.3. Rimozione dell'elemento

Analogamente all'aggiunta di elementi, l'implementazione di questa lista offre removeFirst () e removeLast ().

Inoltre, esiste un metodo conveniente removeFirstOccurence () e removeLastOccurence () che restituisce booleano (vero se la raccolta conteneva l'elemento specificato).

4.4. Operazioni in coda

L' interfaccia Deque fornisce comportamenti simili a una coda (in realtà Deque estende l' interfaccia Queue ):

linkedList.poll(); linkedList.pop();

Questi metodi recuperano il primo elemento e lo rimuovono dall'elenco.

La differenza tra poll () e pop () è che pop genererà NoSuchElementException () su un elenco vuoto, mentre poll restituisce null. Sono disponibili anche le API pollFirst () e pollLast () .

Ecco ad esempio come funziona l' API push :

linkedList.push(Object o);

Che inserisce l'elemento come capo della collezione.

LinkedList ha molti altri metodi, la maggior parte dei quali dovrebbe essere familiare a un utente che ha già utilizzato Lists . Altri forniti da Deque potrebbero essere una comoda alternativa ai metodi "standard".

La documentazione completa può essere trovata qui.

5. conclusione

ArrayList è in genere l' implementazione predefinita di List .

Tuttavia, ci sono alcuni casi d'uso in cui l'utilizzo di LinkedList si adatta meglio, come le preferenze per il tempo di inserimento / cancellazione costante (ad esempio, frequenti inserimenti / cancellazioni / aggiornamenti), per il tempo di accesso costante e l'utilizzo effettivo della memoria.

Esempi di codice possono essere trovati su GitHub.