Differenze tra ArrayList e LinkedList

[Dreamer89]

Salve. Vorrei sapere qual è la differenza tra queste 2 classi, dato che ho provato a modificare un programma e andava bene con entrambe o_O

[andbin]

Originariamente inviato da Dreamer89
Salve. Vorrei sapere qual è la differenza tra queste 2 classi, dato che ho provato a modificare un programma e andava bene con entrambe o_O

Sono entrambe implementazioni "concrete" della interfaccia List. Solo che ArrayList è basata su un array, mentre LinkedList è basata su una lista linkata. Questo porta ad una differenza nella complessità (e quindi nelle "performance") delle varie operazioni. Il get() per ArrayList ha una complessità O(1) mentre per LinkedList è O(n). Con un array se chiedi l'elemento all'indice 10, lo ottieni subito, mentre con una lista linkata deve scansionare tutta la lista fino a quel punto!

Quindi una collezione non la si sceglie così "a caso" o solo notando che "funzionano" entrambe. Bisogna vedere cosa devi fare e come la devi utilizzare. Ci sono questioni di performance. Se poi non ti interessa nemmeno questo ... beh, ok, scegli quella che vuoi.

[Dreamer89]

Quindi un ArrayList è più performante? Perchè allora scegliere una LinkedList? E quali sono le differenze con Vector?

[Alex'87]

Originariamente inviato da Dreamer89
Quindi un ArrayList è più performante? Perchè allora scegliere una LinkedList?

Dipende da quello che devi fare...

Esempio.
Hai 1000 elementi da mettere in una struttura dati.

Dopo averli inseriti devo solo leggerli in maniera "random"? ArrayList
Dopo averli inseriti devo continuare ad aggiungere/togliere elementi? Dipende (se devo togliere un elemento da un array devo poi ricompattare tutto mentre in una lista basta aggiornare un puntatore):
devo leggere ed inserire sempre in fondo? ArrayList
devo leggere ed inserire sempre in testa? LinkedList

Originariamente inviato da Dreamer89
E quali sono le differenze con Vector?

Vector mi pare sia simile ad ArrayList però è sincronizzato ed ha un diverso fattore di crescita :master:

[andbin]

Originariamente inviato da Dreamer89
Quindi un ArrayList è più performante? Perchè allora scegliere una LinkedList? E quali sono le differenze con Vector?

Nessuna delle due è "meglio" dell'altra, ognuna ha le sue caratteristiche e i suoi vantaggi/svantaggi e quindi bisogna vedere esattamente come la devi usare.

Se devi usare moltissimo l'accesso "casuale" agli elementi (tante get()), allora è meglio ArrayList. Se devi fare tanti inserimenti in testa allora è meglio LinkedList. In una lista linkata, aggiungere in testa è facilissimo (complessità O(1) ), mentre in un array devi spostare tutti gli elementi seguenti ed eventualmente riallocare l'array se la sua "capacity" non basta! Idem per il remove in testa.
Quindi come vedi nessuna è meglio dell'altra, ognuna delle varie operazioni ha complessità diversa, quindi cosa è meglio usare ... dipende da come la userai!

Vector concettualmente è esattamente come ArrayList (salvo una leggera differenza nella API) ma è la "vecchia" collezione "legacy" mantenuta per compatibilità. Ed è "synchronized".

[Dreamer89]

Ma cosa intendete per "aggiungere in testa"? Intendete dall'inizio? Perchè io su un libro trovo un esempio in cui una LinkedList viene aggiunta ad un'altra e viene aggiunta alla fine e non all'inizio.

[Alex'87]

Originariamente inviato da Dreamer89
Ma cosa intendete per "aggiungere in testa"? Intendete dall'inizio?

Si, all'inizio.

Originariamente inviato da Dreamer89
Perchè io su un libro trovo un esempio in cui una LinkedList viene aggiunta ad un'altra e viene aggiunta alla fine e non all'inizio.

E quindi? In una LinkedList puoi anche aggiungere elementi in coda... anche in mezzo volendo.

[Dreamer89]

Credo di aver capito... grazie mille a tutti

[Javino89]

Originariamente inviato da andbin
Sono entrambe implementazioni "concrete" della interfaccia List. Solo che ArrayList è basata su un array, mentre LinkedList è basata su una lista linkata. Questo porta ad una differenza nella complessità (e quindi nelle "performance") delle varie operazioni. Il get() per ArrayList ha una complessità O(1) mentre per LinkedList è O(n). Con un array se chiedi l'elemento all'indice 10, lo ottieni subito, mentre con una lista linkata deve scansionare tutta la lista fino a quel punto!

Quindi una collezione non la si sceglie così "a caso" o solo notando che "funzionano" entrambe. Bisogna vedere cosa devi fare e come la devi utilizzare. Ci sono questioni di performance. Se poi non ti interessa nemmeno questo ... beh, ok, scegli quella che vuoi.

Scusa una curiosità. Se faccio:

private static int _somma3Aux(List<Integer> lista) {
int somma = 0;
for (int i = 0; i < lista.size(); i++) {
somma += lista.get(i);
}
return somma;
}

Cosa cambia in termini di complessità se passo un ArrayList o una LinkedList?

[andbin]

Originariamente inviato da Javino89

private static int _somma3Aux(List<Integer> lista) {
int somma = 0;
for (int i = 0; i < lista.size(); i++) {
somma += lista.get(i);
}
return somma;
}

Cosa cambia in termini di complessità se passo un ArrayList o una LinkedList?

Che se è una LinkedList il get() deve scorrersi tutta la lista fino a trovare l'indice voluto.

Se invece di fare il for per indice, usassi l'Iterator della lista (o visto che usi almeno Java 5 il "for-each" che usa di nascosto l'iteratore), non cambierebbe più (praticamente) nulla tra fare la iterazione su ArrayList o su LinkedList.