Java ArrayList na zdjęciach

Cześć! Dzisiejszy wykład ArrayListbędzie z jednej strony prostszy, z drugiej trudniejszy niż poprzednie. To trudniejsze, bo dziś zajrzymy „pod maskę” ArrayListi sprawdzimy, co się z nią dzieje podczas operacji. Z drugiej strony, w tym wykładzie prawie nie będzie kodu - głównie zdjęcia i wyjaśnienia. No to jedziemy :) Jak już wiesz, wewnątrz ArrayList'a znajduje się zwykła tablica, która pełni rolę magazynu danych. W większości przypadków nie określamy dokładnej wielkości listy. Ale tablica wewnętrzna musi mieć pewien rozmiar! To prawda. Jego domyślny rozmiar to [10] .

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
}

Na początek przyjrzyjmy się jak wygląda dodanie nowego elementu. Przede wszystkim sprawdzane jest, czy w tablicy wewnętrznej jest wystarczająco dużo miejsca i czy zmieści się jeszcze jeden element. Jeśli jest miejsce, nowy element zostanie dodany na końcu listy. Kiedy mówimy „do końca”, nie mamy na myśli ostatniej komórki tablicy (byłoby to dziwne). Odnosi się to do komórki znajdującej się obok ostatniego bieżącego elementu. Jego indeks będzie równy cars.size(). Nasza lista jest obecnie pusta ( cars.size() = 0). Odpowiednio do komórki o indeksie zostanie dodany nowy element 0.

ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);

Tutaj wszystko jest jasne. Co się stanie, jeśli wstawienie nastąpi pośrodku, czyli pomiędzy kilkoma elementami?

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");
   Car ford = new Car("Ford Modneo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);

   cars.add(1, ford);//добавляем ford в ячейку 1, которая уже занята
}

Ponownie najpierw sprawdza, czy w tablicy jest wystarczająco dużo miejsca. Jeśli jest wystarczająco dużo miejsca, elementy przesuwamy w prawo zaczynając od komórki, w której wstawiamy nowy element. Wklejamy do komórki o indeksie 1. Oznacza to, że element z komórki 3 jest kopiowany do komórki 4, element 2 do komórki 3, element 1 do komórki 2. Następnie nasz nowy element jest wklejany na miejsce. Poprzedni element ( bugatti) został już stamtąd skopiowany do nowej lokalizacji. Zastanówmy się teraz, jak przebiegałby ten proces, gdyby w tablicy nie było miejsca na wstawienie. Najpierw oczywiście sprawdza się, czy jest wystarczająco dużo miejsca. Jeśli okaże się, że nie ma wystarczającej ilości miejsca, ArrayListwewnątrz 'a tworzona jest nowa tablica o rozmiarze (rozmiar OldArray * 1,5) + 1. W naszym przypadku nowa tablica będzie miała rozmiar 16 komórek. Wszystkie bieżące elementy zostaną tam natychmiast skopiowane. Stara tablica zostanie usunięta przez moduł zbierający elementy bezużyteczne i pozostanie tylko nowa, rozszerzona. Teraz jest wolne miejsce na nowy element. Wklejamy go do komórki 3, która jest zajęta. Teraz rozpoczyna się znana procedura. Wszystkie elementy zaczynające się od indeksu 3 są przesuwane o jedną komórkę w prawo i po cichu dodawany jest nowy element. A teraz wstawienie zakończyło się sukcesem! Uporządkowaliśmy wstawianie. Porozmawiajmy teraz o usuwaniu elementów . Jak pamiętacie, pracując z tablicami napotkaliśmy problem: kiedy je usunęliśmy, pozostały w nich „dziury”. Jedynym rozwiązaniem było przesunięcie elementów w lewo za każdym razem, gdy zostały usunięte, i trzeba było samemu napisać kod przesunięcia. ArrayListdziała na tej samej zasadzie, ale w nim ten mechanizm jest już zaimplementowany automatycznie. Tak to wygląda: I na koniec otrzymujemy pożądany rezultat: Element lambozostał pomyślnie usunięty. Tutaj zrobiliśmy usunięcie ze środka. Oczywiste jest, że usunięcie z końca listy będzie szybsze, ponieważ żądany element zostanie usunięty bez przesuwania wszystkich pozostałych. Przyjrzyjmy się jeszcze raz rozmiarowi tablicy wewnętrznej i jej przechowywaniu w pamięci. Ekspansja tablicy to proces wymagający określonej ilości zasobów. Dlatego nie powinieneś tworzyć ArrayListz domyślnym rozmiarem, jeśli wiesz na pewno, że będzie on miał co najmniej 100 elementów. Zanim dojdziesz do wstawienia setnego elementu, tablica wewnętrzna powiększy się 6 razy , za każdym razem przenosząc wszystkie elementy.

• od 10 elementów do 16
• z 16 elementów do 25
• od 25 do 38
• od 38 do 58
• od 58 do 88
• od 88 do 133 (wg wzoru (wielkość Starej Tablicy * 1,5) + 1)

Oczywiście jest to dość kosztowne pod względem zasobów. Dlatego jeśli znasz już jakąś (przynajmniej przybliżoną) liczbę przechowywanych elementów, lepiej od razu utworzyć listę z tablicą o określonej wielkości:

ArrayList<Car> cars = new ArrayList<>(100);

Teraz w pamięci zostanie od razu przydzielona tablica 100 elementów, co będzie bardziej wydajne, bo zasoby nie będą marnowane na rozbudowę. Jest też druga strona medalu. Kiedy obiekty są usuwane z ArrayListszyku wewnętrznego, rozmiar nie jest automatycznie zmniejszany. Przykładowo mamy ArrayListwewnętrzną tablicę składającą się z 88 elementów, która jest całkowicie wypełniona: W trakcie działania programu usuwamy z niej 77 elementów, a zostaje w niej tylko 11: Czy domyśliłeś się już w czym tkwi problem? Oczywiście nieefektywne wykorzystanie pamięci! Wykorzystujemy tylko 11 komórek, a pamięć mamy przydzieloną na 88 elementów – to 8 razy więcej, niż potrzebujemy! Aby przeprowadzić optymalizację w tym przypadku, możesz użyć specjalnej metody klasy ArrayList- trimToSize(). „Przycina” długość tablicy wewnętrznej do ilości aktualnie w niej przechowywanych elementów. Teraz przydzielana jest tyle pamięci, ile potrzeba! :)