Dlaczego zawsze powinieneś używać ArrayList w Javie?

Jest wiele implementacji interfejsu List dostępnych w języku Java. Implementacje zawarte w bibliotece standardowej to ArrayList, LinkedList, CopyOnWriteArrayList, Vector i Stack. Niektóre z nich są bardziej specyficzne od innych, np. Vector jest synchronizowaną listą. Przyjrzyjmy się im wszystkim i zastanówmy się nad tym, dlaczego powinniśmy „zawsze” używać właśnie ArrayList.

Rodzaje list w Javie

ArrayList – jest to podstawowa implementacja listy w Javie. Można też ją określić jako samo-rozszerzalną tablicę, ponieważ jej implementacja bazuje na tablicy, która jest powiększana wraz ze wzrostem rozmiaru listy. Dzięki temu, jest to najwydajniejsza implementacja listy w Javie (w bibliotece standardowej).

Charakteryzuje się szybkim losowym dostępem do poszczególnych elementów poprzez metodę get(int index).

LinkedList – jest to podwójnie powiązana lista. Każdy element tej listy jest osobnym obiektem, który posiada referencję do poprzedniego i następnego elementu listy.

Implementacja ta pozawala dodawać i usuwać elementy w stałym czasie (dodawanie elementu w dowolnym miejscu listy jest bardzo szybkie), ale losowy dostęp do elementów jest sekwencyjny (żeby dostać się do odpowiedniego elementu, trzeba iterować po elementach listy).

CopyOnWriteArrayList – jest to ulepszona implementacja ArrayList, w której operacje takie jak: add(...), set(...), remove(...), powodują utworzenie świeżej kopii wewnętrznej tablicy  przechowującej elementy. Lista ta jest przeznaczona do zastosowań wielowątkowych.

Wszystkie operacje modyfikujące jej stan są bardzo kosztowne, dlatego najlepiej jest używać jej tylko w sytuacjach, gdzie potrzebujemy częstych odczytów i sporadycznych modyfikacji listy.

Vector – jest implementacją, bardzo podobny do ArrayList, jednak z tą zasadniczą różnicą, że wszystkie jego operacje są synchronizowane. Co sprawia, że jest on bardziej odpowiedni do środowiska wielowątkowego.

Podobnie jak ArrayList pozwala na losowy dostęp do elementów w stałym czasie poprzez metodę get(int index).

Stack – stos jest strukturą danych typu LIFO (last in first out) – element, który jest dodawany jako ostatni opuszcza stos jako pierwszy. Jest to implementacja rozszerzająca Vector, więc tak samo jak Vector jest kolekcją synchronizowaną. W przypadku kiedy nie potrzebujemy synchronizacji, zalecane jest użycie ArrayDeque (Double ended queue). Stos to bardzo specyficzny typ kolekcji i bardzo rzadko przydatny. Często można użyć ArrayList zamiast stosu. Z racji tego, że jest synchronizowany, w większości przypadków nie należy go używać.

Dlaczego powinieneś używać ArrayList?

Obecnie większość projektów z jakimi mamy do czynienia to aplikacje działające w środowisku webowym, gdzie aplikacja jest uruchamiana w ramach jakiegoś serwera aplikacji (czy kontenera servletów). Nie jest ważne, czy nasz serwer jest stand-alone (osadzony jako osobna aplikacja, do której wgrywamy paczkę zwykle w formacie pliku war) czy embeded (osadzony wewnątrz jar'a zawierającego aplikację).

Stack i Vector

Server aplikacji (w większości przypadków) załatwia nam temat związany z wielowątkowością, co sprawia, że piszemy nasze aplikacje tak, jakby to były aplikacje jedno wątkowe. W tym kontekście (w większości przypadków) odpadają nam synchronizowane implementacje listy, czyli Stack (powinniśmy zamiast niego użyć ArrayDeque) i Vector (powinniśmy zamiast niego użyć ArrayList).

Kolejną rzeczą, która dotyczy klas Vector i Stack jest to, że operacje (get(...), put(...), remove(...) etc.) są synchronizowane, każda osobno. A często zależy nam na tym by synchronizować sekwencję operacji na danej strukturze.

CopyOnWriteArrayList

Kolejną strukturą, która jest przeznaczona do środowiska wielowątkowego jest CopyOnWriteArrayList. I z racji jej specyfiki, w ogóle jest rzadko używaną strukturą danych.

ArrayList vs LinkedList

Główna różnicą pomiędzy tymi listami jest oczywiście implementacja. ArrayList oparta jest na tablicy, przez co jest bardziej wydajna.

LinkedList jest oparta na powiązanych między sobą obiektach, przez co jest o wiele bardziej pamięciożerna. Dla każdego elementu w liście jest utworzony obiekt Node, który go przechowuje. Wraz ze zwiększeniem liczby elementów w liście znacząco wzrasta też zużycie pamięci.

Większość operacji wykonywanych na listach to dodawanie i odczytywanie. Jeśli chodzi o dodawanie elementów do ArrayList, to jest ono tak samo wydajne jak w LinkedList, gdy dodajemy elementy na końcu listy. Co właściwie ma miejsce w większości przypadków. W uproszczeniu możemy przyjąć, że pod tym względem obie listy są równoważne.

Aktualizacja: Ponieważ wiele osób sugerowało, że dodawanie elementów na końcu ArrayList i LinkedList nie jest tak samo wydajne postanowiłem to doprecyzować.

Dodawanie elementów na końcu LinekdList ma złożoność O(1), natomiast dodawanie na końcu ArrayList ma złożoność O(1) zamortyzowaną.

Co to oznacz, że złożoność jest zamortyzowana?

To znaczy, że na operację dodawania wpływa jeszcze jakaś inna operacja. W przypadku ArrayList jet to operacja skopiowania wewnętrznej tablicy, w której przechowywane są elementy do nowej większej tablicy. Dzieje się to wtedy gdy wewnętrzna tablica zostanie zapełniona. Operacja ta jednak nie jest, aż tak znacząca i wraz ze wzrostem tablicy coraz rzadsza. Dlatego złożoność to O(1) zamortyzowane a nie O(n).

Wewnętrzna tablica jest „powiększana” dopiero w momencie gdy zostanie całkowicie zapełniona i dzieje się to według wzoru:

int newCapacity = oldCapacity + (oldCapacity >> 1); // JDK8

Co oznacza, że nowa tablica jest większa od starej o mniej więcej połowę. Sprawia to, że wraz ze wzrostem listy operacje rozszerzania (kopiowania) tablicy są coraz rzadsze.

Jeśli chodzi o odczytywanie losowych elementów poprzez metodę get(int index), to w ArrayList jest to zrealizowane poprzez odczytywanie konkretnego indexu w tablicy (złożoność O(1)).

Poniżej fragment kodu z klasy ArrayList:

E elementData(int index) {
  return (E) elementData[index];
}

Natomiast w LinkedList metoda get(int index) działa sekwencyjnie, iteruje wszystkie (maksymalnie połowę listy) elementy do danego indeksu (złożoność O(n)).

Poniżej fragment kodu z klasy LinkedList:

Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

ArrayList w większości przypadków zapisuje elementy tak samo wydajnie jak LinkedList. Jest szybsza, jeżeli chodzi o odczyty pojedynczych elementów i zużywa o wiele mniej pamięci niż LinkedList.

Jedyna przewaga LinkedList to szybsze usuwanie i dodawanie elementów do środka listy.

Podsumowanie

Używając różnych implementacji list trzeba szczegółowo znać ich zalety i wiedzieć w jakich sytuacjach sprawdzają się najlepiej. Da Ci to dodatkowe możliwości i pozwoli na bardziej elastycznie programowanie swoich aplikacji. Natomiast jeśli masz jakieś wątpliwości jakiej listy używać, powinieneś zawsze skorzystać z ArrayList, która sprawdza się w 99,9% przypadków.

Żródła:

https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html

https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html

https://docs.oracle.com/javase/8/docs/api/java/util/Vector.html

https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html

https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/CopyOnWriteArrayList.html