Javowe kolekcje, część 1

W poprzednim wpisie opisałem podstawy typów generycznych. Dziś chciałbym kontynuować ten temat i zacząć cykl artykułów o jednym z podstawowych zastosowań typów generycznych – kolekcjach.

Co jest złego w tablicach?

Tablice istniały w językach programowania wysokiego poziomu, w zasadzie, od zawsze. Przez tyle lat stosowania ich działanie zostało maksymalnie zoptymalizowane. Ale mimo to, wszyscy zauważają wady użycia tablic. Moim zdaniem najpoważniejszym jest niezmienny rozmiar. Jak stworzysz tablicę pięcioelementową, to nie dasz rady tam włożyć 6 elementów. W niektórych zastosowaniach taka wada jest nie do przeskoczenia…

Inną poważną niewygodą stosowania tablic, jest utrudnione wstawianie elementu „w środku” tablicy. Rozważ przykład tablicy:

Indeks 0 1 2 3 4
Wartość 3 2 8 6 19

Jeżeli chcesz zastąpić element pod indeksem 2, to robisz to natychmiast, ale jeżeli chcesz wstawić element pod indeks 2, ale chcesz zachować wszystkie elementy, to najpierw musisz przepisać część tablicy, żeby zrobić miejsce i dopiero potem wstawić element we właściwe miejsce. Podobnie jest w przypadku wstawiania elementu na początek tablicy. Trzeba przesunąć wszystkie elementy, żeby zrobić miejsce na początku…

Abstrakcyjne typy danych

Oczywiście, jest cały dział informatyki teoretycznej, który opisuje abstrakcyjne typy danych, które możemy zastosować, aby rozwiązać obydwa problemy, o których napisałem powyżej (oraz do rozwiązania wielu innych problemów).

Do pierwszego z nich możemy użyć dynamicznie zwiększających się tablic. Jak one działają? Podajemy jakąś początkową wielkość tablicy, tworzymy zwykłą tablicę i zwyczajnie dodajemy elementy na jej koniec. Gdy zacznie brakować miejsca, po prostu tworzy się tablicę dwa razy większą, do której przepisuje się elementy i usuwa się starą tablicę. Oczywiście, czas wstawiania elementów do takiej struktury danych nie zawsze będzie taki sam – ponieważ raz na jakiś czas przy wstawieniu elementu do tablicy trzeba będzie wykonać operację alokacji nowej tablic i przepisania elementów do niej. Można jednak pokazać, że średnio (rozważając więcej operacji na takiej strukturze danych) wydajność takiej struktury danych jest zadowalająco dobra. Taka struktura danych ma jeszcze jedną, wielką zaletę. W związku z tym, że korzystamy z tablicy, mamy szybki dostęp do elementu na zadanej pozycji.

Do rozwiązania drugiego problemu możemy użyć struktury, która nazywa się listą wiązaną. Lista taka, to jest zbiór obiektów, które są ze sobą powiązane za pomocą wskaźników (w przypadku Javy – referencji). Co to oznacza? Mamy obiekt węzła w takiej liście (czyli podstawowy element składowy), który przechowuje wartość oraz referencję na następny węzeł w liście. Jeżeli nie ma następnego elementu w liście, to referencja na następny element ma wartość null. Całą listę pamiętamy w referencji głównej, którą nazywamy głową listy. Mamy więc natychmiastowy dostęp do pierwszego elementu na liście. Jeżeli chcemy poznać wartość elementu na miejscu n, to musimy przejść po n-1 wcześniejszych węzłach. Tracimy tutaj szybkość dostępu, ale zyskujemy stały czas dodawania elementów na początek listy. Często stosuje się listę podwójnie wiązaną – czyli taką, w której każdy węzeł dodatkowo przechowuje referencję na poprzedni na liście węzeł. W takiej liście mamy też dodatkową referencję na ostatni element listy, którą zwyczajowo nazywa się ogonem. Jeżeli chodzi o dodawanie elementów w środek listy, to nie ma potrzeby przepisywania elementów, po prostu przepina się kilka referencji. Takie postępowanie sprawia, że taka lista nie zajmuje spójnego obszaru w pamięci, jak tablica. Oznacza to, że przeglądanie kolejnych elementów takiej listy, jest nieco mniej wydajne, niż przeglądanie kolejnych elementów tablicy.

Te dwie struktury danych pokazują jedną, bardzo ważną rzecz w informatyce. Zazwyczaj nie ma idealnych rozwiązań. Gdy jest kilka rozwiązań do wyboru, zawsze musimy rozważyć wady i zalety, aby dokonać przemyślanego wyboru.

Kolekcje w Javie

Zaimplementowanie dwóch powyższych struktur danych, to jedne z pierwszych zadań, jakie daje się do rozwiązania studentom pierwszego roku informatyki. Jeżeli nigdy tego, nie robiłeś, spróbuj sam dla siebie takie klasy zaimplementować.

Współczesne języki, posiadają implementację tych dwóch (oraz wielu innych) struktur danych w swoich bibliotekach standardowych. To oznacza, że klasy te nie są częścią składni języka, ale można z nich skorzystać bez dodawania żadnych zewnętrznych zależności.

Java również posiada szeroki zbiór różnych struktur danych, które nazywamy kolekcjami. Wszystkie te klasy znajdują się w pakiecie java.util. Twórcy Javy, zadbali o porządek w pakiecie z kolekcjami. Istnieje hierarchia interfejsów i klas, które pozwalają pisać programy na wielu różnych poziomach szczegółowości

Mamy więc główny interfejs Collection<E>, który zawiera następujące metody:

  • int size() – zwraca liczbę elementów w kolekcji
  • boolean isEmpty() – pozwala sprawdzić, czy kolekcja jest pusta
  • boolean contains(Object o) – pozwala sprawdzić, czy zadany obiekt znajduje się w kolekcji
  • Object[] toArray() – pozwala przekonwertować kolekcję na tablicę
  • boolean add(E e) – pozwala dodać element do kolekcji
  • boolean remove(Object o) – pozwala usunąć element z kolekcji
  • boolean containsAll(Collection<?> c) – pozwala sprawdzić, czy wszystkie elementy z innej kolekcji znajdują się w zadanej kolekcji
  • boolean addAll(Collection<? extends E> c) – pozwala dodać wiele elementów na raz
  • boolean removeAll(Collection<?> c) – pozwala usunąć wiele elementów na raz
  • void clear() – pozwala wyczyścić zawartość kolekcji

I jeszcze kilka innych, których pozwoliłem sobie teraz nie wymienić. Zwróć uwagę, że te metody, które wymieniłem opisują abstrakcję pojemnika na dane. Nieważne, jak elementy przechowujemy w środku. Ważne, że elementy możemy dodać, usunąć i przejrzeć. Za to ostatnie odpowiada interfejs Iterable<T>, który jest interfejsem bazowym dla interfejsu Collection.

Kolejne interfejsy służą wyspecyfikowaniu konkretniejszych zadań, ale wciąż bez wchodzenia w szczegóły implementacyjne.

Dziś omówię interfejs List i dwie jego najpopularniejsze implementacje. Kolejnymi typami kolekcji zajmę się w kolejnych artykułach.

Listy

Lista jest to przykład uporządkowanej kolekcji (czasami nazywanej ciągiem, albo bardziej z angielskiego, sekwencją). Do wszystkich metod, które specyfikuje interfejs Collection, lista dodaje metody związane z dostępem do elementu na zadanej pozycji, lub też szukania pozycji zadanego elementu. W liście kolejność elementów jest kluczowa, więc przeglądanie zawartości listy, odbywa się zgodnie z ustalonym porządkiem (najczęściej związanym z kolejnością dodawania elementów do listy).

Powinieneś dostrzec pewne podobieństwo interfejsu listy, z dwiema strukturami danych, o których pisałem na samym początku. W przypadku dynamicznie zwiększanej tablicy, jak również w przypadku listy wiązanej – kolejność elementów była kluczowa. W przypadku listy wiązanej pobranie wartości na zadanej pozycji, jest wymagające obliczeniowo, ale możliwe. Elementy w liście wiązanej, mają ściśle określony porządek.

W Javie obie te struktury danych są zaimplementowane. Są one ze sobą ściśle powiązane, ponieważ klasy opisujące dynamicznie powiększaną tablicę oraz listę wiązaną implementują interfejs List. Są to klasy:

  • ArrayList<E> – implementacja dynamicznie zwiększanej tablicy
  • LinkedList<E> – implementacja listy podwójnie wiązanej

W większości przypadków, pierwszym wyborem jest klasa ArrayList. Sprawdza się dobrze w większości przypadków.

Ale pamiętaj, że wybór konkretnej implementacji interfejsu List powinna być świadomym wyborem, poprzedzonym analizą – jakie operacje będą na liście wykonywane, aby wybrać implementację lepiej pasującą do czekających ją zadań.

Pamiętaj też, że pisząc program, wskazane jest używanie interfejsu zamiast konkretnej implementacji. Mam na myśli, że lepiej aby funkcja zwracała obiekt typu List, zamiast obiektu typu ArrayList – w ten sposób Twój program jest ogólniejszy. Poza tym, w łatwy sposób możesz zmienić wtedy ArrayListę na LinkedListę bardzo łatwo, bez modyfikowania swojego kodu.

Podsumowanie

Dzisiejszy wpis jest krótszy i bardziej teoretyczny. Mam nadzieję, że taki też przypadnie Ci do gustu. Jak pewnie się domyślasz, nie wyczerpałem tematu Javowych list. Do tematu wrócę już wkrótce. Opiszę, jakie nowe funkcjonalności do list wprowadziła ósma wersja Javy. Zachęcam do śledzenia mnie w mediach społecznościowych, aby nie przegapić moich następnych wpisów.

Aspirujący twórca internetowy, który zna się na programowaniu i chce się dzielić wiedzą

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *

Scroll to top