Kolekcje w Javie

Poprzedni wpis dotyczył interfejsów.

W języku C standardowo jesteśmy ograniczeni do tablic, które w momencie kompilacji muszą mieć zdefiniowany rozmiar. Java w swojej bibliotece standardowej posiada wiele implementacji interfejsów kolekcji np. List, które mogą przyjmować elementy różnych typów. Są to implementacje różnych znanych struktur danych, takich jak lista łączona dwukierunkowa (ang. Linked List) i lista tablicowa (ang. Array List).

W poniższym artykule wyjaśnimy jakie rozwiązania dostarcza biblioteka Javy, która jest bardzo bogata i początkujący programiści mogą czuć się zagubieni. Różne struktury są przez przeznaczone do rozmaitych zastosowań. Użycie nieodpowiedniej może znacznie zwiększyć złożoność obliczeniową aplikacji.

Oczywiście przy małym zestawie danych (liczba mała jest dość umowna, można uznać, że 1000 to niedużo) nie ma znaczenia, którą strukturę wybierzemy, natomiast przy milionach rekordów (teoretyczna wartość sięga 2^31 -1 lub pojemności pamięci) każda zaoszczędzona milisekunda może pozytywnie wpłynąć na czas przeprowadzenia operacji.

W tym wpisie skupimy się na poznaniu dostępnych kolekcji, gdyż ich znajomość znacznie upraszcza wybór konkretnego rozwiązania do własnych zastosowań. W przyszłości jednak zrobimy własną implementację różnych znanych struktur danych, aby zobaczyć od strony algorytmu i czystej teorii jak one działają.

Dostępne kolekcje w Javie

Zacznijmy od przedstawienia wszystkich rodzajów kolekcji dostępnych w bibliotece standardowej. Każdy z typów kolekcji implementuje jeden z czterech dostępnych interfejsów.

Lista (ang. List)

Listy to kolekcje, które implementują interfejs List. Dostęp do elementów możliwy jest po wpisaniu indeksu. Elementy dodawane są na koniec lub początek listy oraz mogą się powtarzać. Ważnym elementem jest referencja do kolejnego (lub w niektórych implementacjach również poprzedniego) elementu.

Zbiór/zestaw (ang. Set)

Zestaw, który nie pozwala na powtarzanie się elementów. Nie jest również wymagane zachowanie kolejności (choć odpowiednia implementacja może jej pilnować). Można to traktować jako zestaw unikalnych elementów danego typu.

Kolejka (ang. Queue)

Zbiór elementów, które oczekują na swoje zastosowanie w zaimplementowanym porządku (jest kilka rodzajów kolejek). Najważniejszą cechą jest to, że nie ma swobodnego dostępu do każdego elementu, tylko najpierw należy zdjąć wszystkie elementy poprzedzające.

Mapa (ang. Map)

Struktura przechowująca elementy w postaci dwójki klucz-element. Każdy klucz jest jednoznaczny, w związku z tym nie istnieje możliwość powtarzania wartości jak np. w liście.

Hierarchia dziedziczenia wśród kolekcji

Powyższe elementy implementują różne interfejsy. List, Set oraz Queue korzysta z interfejsów Iterable oraz Collection. Jak dowiedzieliśmy się w poprzednim wpisie o interfejsach oznacza to, że każda klasa implementująca te interfejsy musi zapewnić funkcjonalność tych interfejsów. Poniżej znajduje się diagram pokazujący relacje między wymienionymi interfejsami.

Hierarchia kolejek
Hierarchia interfejsów kolekcyjnych

Typy generyczne

Wszystkie interfejsy są sparametryzowane tzn. obok swojej nazwy posiadają dopisek <E>.

Oznacza to, że klasy implementujące dany interfejs nie są ograniczone do konkretnych typów, a mogą przyjąć dowolny typ obiektowy. Zauważmy, że również znacznik E znajduje się jako argument metody. Dzięki temu do listy możemy dopisać znany już z poprzednich lekcji obiekt klasy Zywnosc.

W kolejnych wpisach będziemy dokładnie przyglądać się danym podanym strukturom danych. Do większości zastosowań polecamy korzystać z gotowych rozwiązań, które zostały dostarczone wraz z pakietem Javy. Jest mało prawdopodobne, żeby udało się samemu lepiej zaimplementować podane algorytmy choć w celach dokładnego zrozumienia problemu warto niektóre algorytmy napisać samemu.

Polecamy również zaglądać do dostępnej w sieci dokumentacji, dzięki której można znaleźć różne szczegóły implementacyjne.

Struktury danych.

Przegląd wpisów dotyczących kolekcji w Javie.

Implementacje algorytmów.

Następnym tematem są wyjątki w Javie.