– Może trochę treningu dla Twojego umysłu? Mam nadzieję, że jeszcze on jakoś działa!

– W tablicy kontenerów i kolekcji widziałeś/aś, że ten sam interfejs może mieć różne implementacje. Opowiem Ci teraz, dlaczego jest to nam potrzebne. Oraz jak ArrayList różni się od LinkedList.

– Prawdą jest, że kolekcje mogą być zaimplementowane na różne sposoby i żadna z implementacji nie jest zawsze idealna. Niektóre z nich są szybkie, inne wolne. Każda z nich może być odpowiednia pod jakimś względem. Nie istnieje tu żadne perfekcyjne-zawsze-uniwersalne rozwiązanie.

– Dlatego postanowiono, by zaimplementować kilka wersji tej samej kolekcji. Każda implementacja powinna zostać zoptymalizowana dla pewnego wąskiego zestawu operacji. Oto, jak powstały różne kolekcje. Przestudiujmy dwie klasy: ArrayList i LinkedList.

ArrayList a LinkedList - 1

– Wewnętrznie, ArrayList jest zaimplementowana jako zwyczajna tablica. Dlatego też wstawienie elementu do środka wymaga, byśmy najpierw przesunęli wszystkie następne elementy o jeden i wstawili nowy element w wolne miejsce. Pobieranie i zapisywanie elementów (get, set) jest szybkie, ponieważ te operacje odnoszą się po prostu do właściwych elementów tablicy.

LinkedList ma inną wewnętrzną strukturę. Jest zaimplementowany jako lista z wewnętrznie połączonymi elementami: zestaw odrębnych elementów, z których każdy przechowuje odniesienia do następnych i poprzednich elementów w liście. By wstawić element do środka takiej listy, potrzebujesz jedynie zmienić odniesienia do jego przyszłych sąsiadów. Jednakże, by uzyskać element numer 130, musisz przejść przez wszystkie elementy od 0 do 130. Innymi słowy, operacje get i set będą wolne. Spójrz na następującą tabelę:

Opis Operacja ArrayList LinkedList
Pobierz element get Szybko Wolno
Zapisz element set Szybko Wolno
Dodaj element (na końcu listy) add Szybko Szybko
Wstaw element (na dowolną pozycję) add(i, wartość) Wolno Szybko
Usuń element remove Wolno Szybko

– Rozumiem. Teraz zaczynam łapać. Czy są jakieś kryteria lub zasady, które pomogłyby mi rozpoznać, która kolekcja jest lepsza w konkretnej sytuacji?

– By uprościć, dam Ci następującą zasadę: jeśli zamierzasz często wstawiać (lub usuwać) elementy w środku kolekcji, lepiej jest używać LinkedList. W pozostałych przypadkach ArrayList sprawdza się lepiej.

– W to, jak one są zbudowane, zagłębimy się w bardziej zaawansowanych lekcjach, ale w tej chwili po prostu poćwiczymy ich użycie.