Chyba standardowe pytanie, ale juz sam złupiałem. Linkedlist jest tablicą wiązaną, a ArrayList dynamiczną. Czy dobrze rozumiem, że jeżeli często dodaje i usuwam elementy to warto brać LinkedList, a we wszystkich innych przypadkach ArrayList?
0
1
Najlepiej zajrzyj sobie do źródła i zobacz jak to jest napisane. Poza tym ogarnij jakieś podstawy struktur danych.
- LinkedList to lista dwukierunkowa czyli każdy element przechowuje odniesienie do poprzedniego i kolejnego elementu listy.
- ArrayList to tablica o zmiennym rozmiarze.
Nie da się jednoznacznie wskazać co jest lepsze, ponieważ oba te rozwiązania mają swoje plusy i minusy. Używanie tych struktur "gołych" może doprowadzić do takich wniosków jak powyżej, tzn. że jak często dodajesz i usuwasz to lepszy będzie LinkedList, a ArrayList zajmuje mniej pamięci.
Zainteresuj się ArrayDeque.
Żeby nie wejść w niepotrzebne wywody, dodam tylko, że w 95% przypadków lepiej sprawdzi się ArrayList i tej struktury w praktyce będziesz używał najczęściej lub tylko.
2
Po pierwsze:
premature optimization is the root of all evil.. W 99% użycia list nie ma to znaczenia - i tak te listy są puste lub maja po kilka elementów :-)
Po drugie: często względem czego. Dużo zmian, względem odczytów - wskazuje, że LinkedList może być wydajniejsze. Dużo więcej odczytów niż zmian wskazuje na ArrayList.
Ale prawdę trzeba w konkretnym wypadku zmierzyć (jeśli naprawdę potrzebujesz jakiejś szybkości) - przez 20 lat chyba nie spotkałem przypadku, żeby wydajność aplikacji była słaba przez nie tą listę użytą. Raczej przez to, że ktoś przypadek do tej listy wrzuca całą baze danych, w pętli.
Po trzecie -jak już opanujesz javę to zachęcam do korzystania z list i struktur z vavr.io https://static.javadoc.io/io.vavr/vavr/0.9.0/io/vavr/collection/List.html, to jest lista niemutowalna i przez to łatwiejsza i bezpieczniejsza w użyciu.
0
Ja chyba nigdzie nie widziałem użycia LinkedListy :D
2
Listy jednokierunkowe są podstawową strukturą danych w programowaniu funkcyjnym (ale LinkedList z Javy się do nich nie zalicza). W imperatywnym świecie Javy natomiast rządzi ArrayList.
0
LinkedList używasz wtedy, gdy do listy będziesz dodawał (lub usuwał) elementy do środka listy. Przy ArrayList te operacje są nieefektywne, mają złożoność liniową.
Drugi koniec kija jest taki, że LinkedList ma nieefektywny dostęp do elementu o i-tym indeksie (get(i)). Jest to opisane w javadocu tych struktur.
Jeżeli listy będą krótkie, to nie ma znaczenia, której użyjesz.
0
"LinkedList używasz wtedy, gdy do listy będziesz dodawał (lub usuwał) elementy do środka listy. Przy ArrayList te operacje są nieefektywne, mają złożoność liniową." Hm...?
Dodawanie lub usuwanie elementów, nie na końca lub początku, do LinkedListy, też ma złożoność liniową.
0
Żeby zyskać na czasach usuwania i dodawania elementów w środku LinkedListy trzeba skorzystać z java.util.ListIterator i jego metod add oraz remove. Mało kto to stosuje.
Dodawanie lub usuwanie elementów, nie na końca lub początku, do LinkedListy, też ma złożoność liniową.
Złożoność zależy od odległości od końców listy:
All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.