Tablice dynamiczne w Javie

Tworząc programy o różnym stopniu złożoności, każdy programista wykorzystuje wiele typów danych, w tym tablice. Taka konstrukcja doskonale nadaje się do przechowywania zestawu jednego typu, zapewnia doskonałą wydajność i jest ogólnie wygodna. Istotną wadą tablic jest to, że są statyczne: ich rozmiar należy wcześniej określić. Jednak programiści nie wiedzą jeszcze, jak przewidzieć przyszłość (chyba że oczywiście pojawi się sztuczna inteligencja, która będzie przetwarzać informacje niewiarygodnie szybko i będzie w stanie przewidzieć dowolne zdarzenia). Z tego powodu stworzyliśmy strukturę, która może zmieniać swój rozmiar w trakcie działania programu. Nazywa się to tablicą dynamiczną .

Tablice dynamiczne w kursie JavaRush

Temat ten jest omówiony bardzo zrozumiale i przejrzyście na poziomie 7 i częściowo na poziomie 8 kursu JavaRush w zadaniu Java Syntax. W trakcie kilku wykładów i aż 18 zagadnień poruszane są kluczowe zagadnienia, rodzaje tablic dynamicznych oraz różnice między nimi, w tym także wydajnością. Temat ten jest niezwykle ważny, ponieważ tablice dynamiczne łagodzą depresję, bóle głowy i oszczędzają niesamowitą ilość czasu.

Co to jest tablica dynamiczna?

Tablica dynamiczna to tablica, która może zmieniać swój rozmiar podczas wykonywania programu. W Javie rolę tę pełnią głównie klasy ArrayList i LinkedList. W przeciwieństwie do tablic, ArrayList i LinkedList zawierają tylko referencyjne typy danych, to znaczy mogą przechowywać tylko obiekty. Na szczęście Java posiada mechanizmy autoboxingu i autounboxingu, które pozwalają na przechowywanie typów pierwotnych w tablicach dynamicznych. Podobnie jak tablica statyczna, tablica dynamiczna jest jednorodna, to znaczy może przechowywać jeden typ danych. Jednak dzięki mechanizmowi dziedziczenia i odpowiedniemu wykorzystaniu interfejsów możliwe jest przechowywanie w jednej tablicy dynamicznej całej gamy różnych klas, które są dziedziczone z jednej wspólnej, ale o tym poniżej. Oznacza to, że tablica statyczna działa w następujący sposób: Natomiast tablica dynamiczna w Javie będzie działać w następujący sposób (kontynuując diagram z kroku trzeciego): Java używa specjalnej natywnej funkcji do kopiowania tablicy, więc takie „przesunięcie” nie jest zbyt drogi.

Dlaczego potrzebujemy tablicy dynamicznej?

Tablica dynamiczna w Javie służy do przetwarzania zbiorów jednorodnych danych, których rozmiar nie jest znany w momencie pisania programu. Na przykład możesz chcieć buforować dane każdego klienta, który aktualnie korzysta z aplikacji. Nie da się z góry przewidzieć liczby takich klientów. Bez tablic dynamicznych problem ten można rozwiązać za pomocą następujących opcji:

1. Utwórz dużą tablicę, która na 100% zaspokoi potrzeby;
2. Utwórz tablicę statyczną, która będzie działać jako bufor;
3. Zastosuj inne struktury dynamiczne, takie jak zestawy.

Pierwsza opcja jest odpowiednia tylko w przypadku ściśle ograniczonego asortymentu. W innych przypadkach taka tablica zajmie dużą ilość miejsca w pamięci, co jest wyjątkowo nieefektywne. Drugi będzie wymagał wdrożenia dodatkowej mechaniki czyszczenia bufora, odczytu i tak dalej. Trzeci ma również wady wynikające z różnic w funkcjonalności.

Co robi tablica dynamiczna w Javie?

W języku Java klasy ArrayList i LinkedList działają jak tablica dynamiczna. Najczęściej używaną jest ArrayList, ponieważ działa jak klasyczna tablica, w przeciwieństwie do LinkedList, która implementuje koncepcję listy podwójnie połączonej. Porozmawiamy o tym nieco później.

ArrayList, LinkedList - pojęcia i zasady działania

ArrayList to klasyczna tablica, którą można rozwijać w trakcie wykonywania programu. Opiera się na zwykłej tablicy: jej rozmiar po utworzeniu wynosi 10 elementów. Wraz ze wzrostem rozmiaru zwiększa się pojemność. Zasady działania ArrayList:

• Podobnie jak tablica statyczna, jest ona indeksowana od 0;
• Wstawienie na końcu i dostęp według indeksu są bardzo szybkie - O(1);
• Aby wstawić element na początku lub w środku, należy skopiować wszystkie elementy o jedną komórkę w prawo, a następnie wkleić nowy element w wymaganym miejscu;
• Dostęp według wartości zależy od liczby elementów - O(n);
• W przeciwieństwie do klasycznej tablicy może przechowywać wartość null;

W przypadku LinkedList wszystko jest trochę bardziej skomplikowane: opiera się na podwójnie połączonej liście. Oznacza to, że strukturalnie ta dynamiczna tablica Java to liczba rozproszonych obiektów, które odnoszą się do siebie. Łatwiej to wytłumaczyć obrazami. Wewnątrz LinkedList mamy obiekt główny Head, w którym przechowywana jest informacja o liczbie elementów, a także link do pierwszego i ostatniego elementu: Teraz pole size = 0to , firsti last = null. Każdy element dodawany do tej listy jest treścią odrębnego obiektu wewnętrznego. Dodajmy element Johnny: Teraz mamy węzeł o wartości „Johnny”. W przypadku głównego elementu łącza do pierwszego i ostatniego elementu wskazują nowy węzeł. Obiekt ten posiada także odnośniki do poprzednich i następnych elementów. Link do poprzedniego zawsze będzie miał wartość null, ponieważ jest to pierwszy element, a link do następnego zawsze będzie miał wartość null, ponieważ jeszcze nie istnieje. Naprawmy to: dodano nowy element o wartości „Watson”, który stał się drugim. Należy pamiętać, że pierwszy element ma pole nextwskazujące na następny element, a nowy element ma pole previouswskazujące na poprzedni. W przypadku głównego elementu łącze do ostatniego elementu wskazuje teraz nowy węzeł. Poniższy diagram przedstawia sposób dodawania elementów na środek listy: Dodano nowy element „Hamish”. Aby wstawić go na środek listy, wystarczy ponownie przypisać linki do elementów, jak pokazano na rysunku. Te ilustracje wyjaśniają proces tworzenia podwójnie połączonej listy na najwyższym poziomie, bez wchodzenia w szczegóły. Podsumowując historię o LinkedList, możemy wyprowadzić kilka zasad jego działania:

• Podobnie jak tablica, jest ona indeksowana od 0;
• Dostęp do pierwszego i ostatniego elementu nie jest zależny od liczby elementów - O(1);
• Pobranie elementu według indeksu, wstawienie lub usunięcie ze środka listy zależy od liczby elementów - O(n);
• Można zastosować mechanizm iteratora: wtedy wstawianie i usuwanie będzie następowało w stałym czasie;
• W przeciwieństwie do klasycznej tablicy może przechowywać wartość null.

Przykłady kodu

Przeanalizujmy kilka przykładów. Fragmenty kodu zawierają przykłady zarówno ArrayList, jak i LinkedList.

kreacja

// Создаем новый список
ArrayList<String> arrayList = new ArrayList<>();
// Создается новый список и указывается начальный размер внутреннего массива
ArrayList<String> arrayListLarge = new ArrayList<>(100000);

// Создаем новый LinkedList
LinkedList<String> linkedList = new LinkedList<>();

Dodanie elementu

// Новый элемент добавляется в конец
arrayList.add("Johhny");
// Новый элемент добавляется в указанную позицию (в данном случае — в начало)
arrayList.add(0, "Watson");

// Новый элемент добавляется в конец двусвязного списка
linkedList.add("Java");
// Новый элемент добавляется в нулевую позицию списка:
linkedList.addFirst("I think");
// Новый элемент добавляется в конец списка
linkedList.addLast("language");
// Новый элемент добавляется в указанную позицию
linkedList.add(2, "is a terrific");

// Получение размера списков
int arraySize = arrayList.size(); // 2
int linkedSize = linkedList.size(); // 4

Na pierwszy rzut oka metody add()AND addLast()pełnią tę samą funkcję, ale metoda add()przyszła do LinkedList z interfejsu List, a metoda addLastz interfejsu Deque. LinkedList implementuje oba te interfejsy. Dobrą praktyką w tym przypadku byłoby zastosowanie metody najodpowiedniejszej w danym kontekście. Jeśli jako kolejka używana jest LinkedList, najlepiej użyć addLast. Jeśli jako lista używana jest LinkedList, właściwym rozwiązaniem byłoby użycie add().

Usuwanie elementu

// Удаление element по индексу
arrayList.remove(0);
// Удаление element по значению
arrayList.remove("Johnny");

// Удаление первого element в списке
linkedList.removeFirst();
// Удаление первого element в списке, фактически вызов предыдущего метода
linkedList.remove();
// Удаление последнего element в списке
linkedList.removeLast();
// Удаление первого вхождения element в список
linkedList.removeFirstOccurrence("language");
// Удаление последнего вхождения element в список
linkedList.removeLastOccurrence("Java");
// Удаление по индексу
linkedList.remove(2);

Jeśli obiekt zostanie usunięty przez indeks, metoda zwraca usunięty obiekt. Jeśli obiekt zostanie usunięty przez wartość (lub pierwszy lub ostatni element LinkedList zostanie usunięty), metoda zwraca wartość true , jeśli obiekt zostanie znaleziony i usunięty, lub false w przeciwnym razie.

Dostęp do elementu i przeszukiwanie listy

// Доступ к элементу по индексу
String arrayElement = arrayList.get(2);
// Поиск element по значению
int arrayIndex = arrayList.indexOf("Watson");
// Поиск последнего индекса вхождения element в список
int lastArrayIndex = arrayList.lastIndexOf("Watson");

// Доступ по индексу
String linkedElement = linkedList.get(3);
// Получение первого element
String firstLinkedElement = linkedList.getFirst();
// Получение последнего element
String lastLinkedElement = linkedList.getLast();

// Поиск element по значению
int linkedIndex = linkedList.indexOf("Java");
// Поиск последнего индекса вхождения element в список
int lastLinkedIndex = linkedList.lastIndexOf("Java");

Chodzenie w pętli

// Использование обычного цикла
for(int i = 0; i<arrayList.size(); i++) {
  String value = arrayList.get(i);
  System.out.println(value);
}

for(int i = 0; i<linkedList.size(); i++) {
  String value = linkedList.get(i);
  System.out.println(value);
}

// Использование цикла for-each
for(String s : arrayList) {
  System.out.println(s);
}

for(String s : linkedList) {
  System.out.println(s);
}

W tym miejscu warto powiedzieć kilka słów o wyszukiwaniu. Wielu początkujących programistów szukając elementu na liście rozpoczyna wyszukiwanie w pętli, porównując wszystkie elementy z szukanym, pomimo obecności metod indexOf()i lastIndexOf(). Możesz także użyć tej metody, contains()aby uzyskać fakt, że element znajduje się na liście:

boolean isContainsSherlock = arrayList.contains("Sherlock");
boolean isContainsPhp = linkedList.contains("Php");

Linki do dalszej lektury

1. Jest tu doskonały artykuł na temat usuwania elementów z ArrayList. Ze względu na to, że jest to dynamiczna tablica Java , usuwanie elementów wiąże się z wieloma subtelnościami.
2. Działanie ArrayList zostało szczegółowo zilustrowane tutaj .
3. Trochę więcej o LinkedList.
4. Kilka artykułów z Habr na temat ArrayList i LinkedList .