Wprowadzenie

Wyobraźmy sobie listę zadań do wykonania. Używając tablicy, na początku dnia trzeba określić dokładnie, że zostanie wykonanych 5 czynności. Jeśli nagle pojawi się szóste zadanie, konieczne byłoby przepisanie całej listy na nową, większą strukturę.

Java rozwiązuje ten problem za pomocą interfejsu List. Zamiast ręcznie zarządzać pamięcią i rozmiarem, wykorzystujemy struktury, które rozszerzają się wraz z danymi. W tej lekcji omówimy najpopularniejsze implementacje list oraz różnice w ich działaniu i wydajności.

Kolekcje

Kolekcje w Javie to struktury danych, które przechowują wiele obiektów i udostępniają gotowe operacje do ich obsługi. Nie trzeba tworzyć własnych metod do dodawania, usuwania czy sprawdzania elementów.

W Javie kolekcje są częścią Collections Framework, czyli zestawu interfejsów i klas do pracy z danymi.

W praktyce kolekcja pozwala przechowywać dane w pamięci, swobodnie je modyfikować i przetwarzać bez zajmowania się szczegółami ich organizacji.

Lista w Javie

Lista (List) w Javie należy do najczęściej używanych kolekcji. Działa w sposób uporządkowany, przypominając listę zakupów. Lista przechowuje elementy w kolejności dodawania, możliwe są duplikaty, a dostęp odbywa się przez indeks – tak samo jak w tablicach. Najważniejsze jest to, że rozmiar listy zmienia się dynamicznie.

Array List

Najczęściej używaną implementacją listy jest ArrayList, która łączy prostotę tablicy z elastycznością kolekcji.

Z punktu widzenia użytkownika działa jak dynamiczna lista, ale wewnętrznie opiera się na tablicy. Gdy zabraknie miejsca, Java tworzy nową, większą tablicę i kopiuje dane automatycznie. Nie trzeba przewidywać rozmiaru listy na początku działania programu.

ArrayList sprawia wrażenie elastycznego kontenera, który przyjmuje kolejne obiekty bez ograniczeń. W rzeczywistości Java zarządza tym w oparciu o tablicę. Gdy liczba elementów przekroczy aktualną pojemność, Java tworzy większą tablicę i kopiuje dane. Java wykonuje ten proces automatycznie.

Największą zaletą ArrayList jest szybki dostęp do danych. Jeśli znamy indeks, Java pobiera element natychmiast. Elementy leżą w pamięci obok siebie, więc dostęp działa w czasie stałym. Usuwanie z początku listy wymaga jednak przesunięcia pozostałych elementów, co może wpływać na wydajność przy dużych danych.

Przykład:

Na początku implementujemy listę List<String> jako ArrayList. Jest to dynamiczna struktura danych, która może przechowywać dowolną liczbę elementów typu String. Nie trzeba określać jej rozmiaru na starcie. Następnie dodajemy dwa elementy: "Jan" oraz "Anna". Metoda add() umieszcza je na końcu listy i automatycznie zwiększa jej rozmiar. Potem odczytujemy wartość get(0). Lista zachowuje kolejność, więc element o indeksie 0 to "Jan". Kolejny krok to remove("Anna"). Metoda remove() wyszukuje obiekt i wycina go z pamięci, a system przelicza rozmiar listy. Metoda size() zwraca aktualną liczbę elementów. Na końcu contains("Jan") sprawdza obecność elementu bez potrzeby pisania własnej pętli.

LinkedList

LinkedList (lista wiązana) to jedna z implementacji interfejsu List, która działa zupełnie inaczej niż ArrayList. Zamiast trzymać dane w tablicy, przechowuje je w formie łańcucha elementów. Każdy element stanowi osobny węzeł (node), który zawiera własną wartość oraz dwie referencje: jedną wskazującą na element poprzedni i drugą na element następny. Taka konstrukcja tworzy łańcuch powiązanych ze sobą obiektów.

Przy usuwaniu elementu ze środka nie ma potrzeby przesuwania pozostałych danych w pamięci. Wystarczy zmienić połączenia tak, aby sąsiednie elementy wskazywały na siebie, pomijając usunięty obiekt. Dzięki temu operacja usuwania jest szybka. Odczyt działa wolniej, ponieważ lista musi przejść po kolei przez elementy, aby dotrzeć do konkretnego miejsca. Przy większej liczbie danych może to wydłużyć czas dostępu.

Przykład:

Na początku implementujemy listę List<String> jako LinkedList. To dynamiczna struktura danych, która nie ma stałego rozmiaru i może rosnąć w trakcie działania programu. LinkedList nie przechowuje danych w tablicy, tylko jako połączone elementy. Każdy element jest osobnym „węzłem”, który wskazuje na poprzedni i następny element, tworząc łańcuch. Do listy dodajemy trzy elementy: "Jan", "Anna" i "Piotr". Metoda add() dopisuje je na końcu łańcucha, bez przesuwania innych danych. System.out.println(imiona) przechodzi po liście i wypisuje elementy w kolejności dodania. Przy remove("Anna") lista wyszukuje element i usuwa go, łącząc bezpośrednio element przed nim z elementem po nim. Nie dochodzi do przesuwania pozostałych danych. Na końcu program wypisuje zaktualizowaną listę już bez "Anna".

Operacje CRUD na listach

Najczęściej używane operacje na listach

Iteracje po listach

Lista w Javie przechowuje zbiór elementów, więc aby coś na nich zrobić, trzeba przejść po nich w pętli albo użyć iteratora – narzędzia, które wykonuje ten proces.

Pętla for-each

Najczęściej używamy pętli for-each, ponieważ jest najprostsza i najbardziej czytelna przy iteracji po listach. Sprawdza się głównie wtedy, gdy potrzebny jest tylko odczyt danych. Nie pozwala jednak na usuwanie elementów w trakcie działania pętli.

for (String imie : imiona) {
    System.out.println(imie);
}

Pętla for

Pętla for daje większą kontrolę nad iteracją, ponieważ umożliwia pracę na indeksach. Jest bardziej elastyczna niż for-each i przydaje się wtedy, gdy potrzebny jest dostęp do pozycji elementu lub porównywanie elementów między sobą.

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

Iterator

Iterator w Javie to narzędzie do bezpiecznego przechodzenia po liście, szczególnie, gdy usuwamy elementy w trakcie iteracji. Klasyczne pętle mogą w takim przypadku zgłaszać błędy.

Iterator działa w oparciu o trzy operacje:

• hasNext() sprawdza, czy istnieje kolejny element
• next() przechodzi do kolejnego elementu i go zwraca
• remove() usuwa aktualnie wskazany element

Przykład:

Na początku tworzymy listę ArrayList, która może przechowywać dowolną liczbę elementów typu String. Jej rozmiar zmienia się dynamicznie. Do listy dodajemy trzy imiona: "Jan", "Anna" i "Piotr". Metoda add() dopisuje je na końcu listy w kolejności dodawania. Następnie tworzymy iterator, który przechodzi po liście element po elemencie. W pętli while (it.hasNext()) system sprawdza, czy istnieją kolejne elementy. Metoda it.next() pobiera aktualny element i przesuwa iterator dalej. Każdy element możemy wypisać, aż program przejdzie całą listę.

Usuwanie elementów:

while (it.hasNext()) {
    if (it.next().equals("Anna")) {
        it.remove();
    }
}

Podsumowanie

Kolekcje i listy w Javie zastępują tablice tam, gdzie dane zmieniają się w trakcie działania programu. Dzięki temu nie trzeba przewidywać rozmiaru struktury, ani ręcznie zarządzać jej przebudową.

ArrayList sprawdza się tam, gdzie liczy się szybki dostęp do elementów po indeksie, natomiast LinkedList lepiej radzi sobie przy częstych operacjach dodawania i usuwania w środku struktury. Różnica wynika z ich wewnętrznej budowy, a nie samego sposobu użycia.

Do pracy z danymi w listach wykorzystywany jest schemat CRUD oraz podstawowe metody takie jak add, get, set i remove. Iteracja odbywa się najczęściej przez for-each, klasyczną pętlę for albo iterator, w zależności od tego, czy potrzebny jest tylko odczyt, kontrola indeksów czy bezpieczne usuwanie elementów w trakcie przechodzenia po liście.

W kolejnych lekcjach pojawiają się struktury, które rozwiązują inne problemy – zbiory i mapy.

O autorze

Adam Mingielewicz

Tester oprogramowania z pasją do jakości i technologii. Łączy doświadczenie w testach manualnych i automatycznych, koncentrując się przede wszystkim na aplikacjach webowych oraz usługach SOAP i REST. Testowanie to dla niego nie tylko szukanie błędów, ale przede wszystkim kwestionowanie przyjętych założeń i usprawnianie tego, co nie działa – również w samym procesie testowym. Lubi zmieniać, angażować się i aktywnie budować proces testowy, tak by miał sens, a nie tylko formę. Prywatnie fan rocka, biwakowania, podróży.