ArrayList na zdjęciach

Cześć! Dzisiejsza lekcja ArrayListbędzie zarówno łatwiejsza, jak i trudniejsza niż poprzednie lekcje. Będzie trudniej, bo dzisiaj zajrzymy pod maskę ArrayListi zbadamy, co się dzieje podczas różnych operacji. Z drugiej strony ta lekcja nie będzie miała prawie żadnego kodu. To głównie zdjęcia i wyjaśnienia. No to chodźmy :) Jak już wiesz, ArrayListma w środku zwykłą tablicę, która pełni rolę magazynu danych. W większości przypadków nie określamy dokładnego rozmiaru listy. Ale wewnętrzna tablica musi mieć jakiś rozmiar! I tak się dzieje. Jego domyślny rozmiar to 10 .

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

Najpierw zobaczmy, jak wygląda dodawanie nowych elementów. Pierwszym zadaniem jest sprawdzenie, czy wewnętrzna tablica ma wystarczająco dużo miejsca w wewnętrznej tablicy i czy jeszcze jeden element się zmieści. Jeśli jest miejsce, nowy element jest dodawany na końcu listy. Kiedy mówimy „do końca”, nie mamy na myśli ostatniej pozycji w tablicy (byłoby to dziwne). Mamy na myśli pozycję po ostatnim bieżącym elemencie. Jego indeksem będzie cars.size(). Nasza lista jest obecnie pusta ( cars.size() == 0). W związku z tym nowy element zostanie dodany na pozycji 0.

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

To wystarczająco jasne. Co się stanie, jeśli wstawimy w środku, czyli pomiędzy innymi 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);// add ford to cell 1, which is already occupied
}

Ponownie, najpierw sprawdzamy, czy w tablicy jest wystarczająca ilość miejsca. Jeśli jest wystarczająco dużo miejsca, elementy są przesuwane w prawo , zaczynając od miejsca, w którym wstawiliśmy nowy element. Wstawiamy na pozycji 1. Innymi słowy, element z pozycji 3 jest kopiowany na pozycję 4, element 2 na pozycję 3, a element 1 na pozycję 2. Następnie nasz nowy element jest wstawiany w jego miejsce. Poprzedni element (bugatti) został już stamtąd skopiowany na nową pozycję. Przyjrzyjmy się teraz, jak przebiega ten proces, jeśli nie ma miejsc do wstawienia nowych elementów do tablicy. Oczywiście najpierw sprawdza się, czy jest wystarczająco dużo miejsca. Jeśli nie ma wystarczającej ilości miejsca, tworzona jest nowa tablica wewnątrzArrayListktórego rozmiar jest rozmiarem starej tablicy razy 1,5 plus 1 W naszym przypadku rozmiar nowej tablicy wyniesie 16. Wszystkie bieżące elementy zostaną tam natychmiast skopiowane. Stara tablica zostanie usunięta przez moduł wyrzucania elementów bezużytecznych i pozostanie tylko nowa, rozszerzona tablica. Teraz jest miejsce na nowy element. Wstawiamy go na pozycję 3, która jest zajęta. Teraz zaczyna się znajoma procedura. Wszystkie elementy, począwszy od indeksu 3, są przesuwane o jedną pozycję w prawo, a nowy element jest dodawany po cichu. I wstawienie gotowe! I skończyliśmy z wstawianiem. Porozmawiajmy teraz o usuwaniu elementów . Pamiętasz, że napotkaliśmy problem podczas pracy z tablicami: usuwanie elementów powoduje powstawanie „dziur” w tablicy.przy każdym usuwaniu i za każdym razem musieliśmy pisać własny kod, aby wykonać tę zmianę. ArrayList działa na tej samej zasadzie, ale już implementuje ten mechanizm. Tak to wygląda: I w końcu dostajemy to, co chcieliśmy: Element lambozostał usunięty. Tutaj usunęliśmy element ze środka. Oczywiście usunięcie elementu z końca listy jest szybsze, ponieważ element jest po prostu usuwany bez konieczności przesuwania wszystkich pozostałych. Pomówmy jeszcze przez chwilę o wymiarach wewnętrznej tablicy i sposobie jej ułożenia w pamięci. Rozszerzenie tablicy wymaga pewnych zasobów. W związku z tym nie twórz plikuArrayListz domyślnym rozmiarem, jeśli masz pewność, że będzie miał co najmniej 100 elementów. Wewnętrzna tablica musiałaby zostać rozszerzona 6 razy do czasu wstawienia setnego elementu, a wszystkie elementy musiałyby zostać przesunięte za każdym razem.

• od 10 elementów do 16
• od 16 elementów do 25
• od 25 do 38
• od 38 do 58
• od 58 do 88
• od 88 do 133 (tj. rozmiar starej tablicy razy 1,5 plus 1)

Jak możesz sobie wyobrazić, jest to dość pracochłonne. Jeśli więc znasz już (nawet w przybliżeniu) wymaganą liczbę elementów, lepiej stworzyć listę z tablicą o określonym rozmiarze:

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

Teraz pamięć dla tablicy 100 elementów zostanie przydzielona od razu, dzięki czemu tablica będzie bardziej wydajna (nie będzie trzeba jej rozbudowywać). Ta strategia ma też drugą stronę. Kiedy usuwasz obiekty z ArrayList, rozmiar tablicy wewnętrznej nie zmniejsza się automatycznie. Załóżmy, że mamy ArrayListcałkowicie pełną wewnętrzną tablicę 88 elementów: Podczas działania programu usuwamy 77 elementów, więc pozostaje tylko 11: Czy już zgadłeś, na czym polega problem? Masz to, nieefektywne wykorzystanie pamięci! Używamy tutaj tylko 11 pozycji, ale przydzieliliśmy pamięć dla 88 elementów. To 8 razy więcej niż potrzebujemy! W takim przypadku możemy zoptymalizować wykorzystanie pamięci za pomocą jednej ze ArrayListspecjalnych metod klasy:trimToSize(). Ta metoda „przycina” długość wewnętrznej tablicy do liczby aktualnie przechowywanych w niej elementów. Teraz przydzieliliśmy tylko tyle pamięci, ile potrzebujemy! :)