#05 — Kolekcje w Javie

Dzisiejsza lekc­ja poświę­cona jest kolekcjom — spec­jal­nej grupie klas, które służą do tego, żeby prze­chowywać zbio­ry elementów.

Sprawne posługi­wanie się kolekc­ja­mi to jed­na z ważniejszych umiejęt­noś­ci każdego pro­gramisty. W tej lekcji poz­namy pod­sta­wowe rodza­je kolekcji, różnice między nimi oraz jak ich uży­wać. W języku Java wszys­tkie kolekc­je rozsz­erza­ją klasę Col­lec­tion (tajem­niczy zapis <E> wyjaśnię w dal­szej częś­ci lekcji).

Lekcja

Przede wszys­tkim zaczni­jmy od wyjaśnienia czym jest tajem­nicze <E> w doku­men­tacji kolekcji. To wskazu­je, że mamy do czynienia z tzw. gen­eryka­mi. O samych gen­erykach powiemy sobie więcej w jed­nej z dodatkowych lekcji, ale na tą chwilę dwa słowa, co to znaczy w kon­tekś­cie kolekcji.

Kolekc­je mamy zdefin­iowane jako Collection<E>, same metody też mają syg­natu­ry np. add(E ele­ment). Oznacza to, że może­my wskazać jakiego typu dane będziemy prze­chowywali w tej kolekcji. Jed­nocześnie metody będą przyj­mowały tylko argu­men­ty danego typu. Spry­tne, praw­da? Dlat­ego kolekc­ja określona jako Collection<String> będzie miała metodę add(String ele­ment), nato­mi­ast kolekc­ja zdefin­iowana jako Collection<Kot> będzie miała metodę add(Kot element).

Tyle o gen­erykach na ten moment, zapraszam oczy­wiś­cie do dodatkowej lek­tu­ry (w sekcji linków zna­jdziesz więcej infor­ma­cji). Prze­jdźmy ter­az do rodza­jów kolekcji.

Rodzaje kolekcji w Javie

W Javie wyróż­ni­amy trzy pod­sta­wowe rodza­je kolekcji które znaczą­co różnią się od siebie właś­ci­woś­ci­a­mi. Każdy z tych rodza­jów ma kil­ka imple­men­tacji, które z kolei różnią się szczegól­ny­mi cecha­mi (np. jedne są lep­sze do szy­bkiego dostępu, inne do dodawa­nia itp). Poniżej w skró­cie opis głównych różnic, a w dal­szej częś­ci zna­jdziesz szczegółowy opis każdej z nich:

• java.util.List — lista, tj. kolekc­ja o określonej pozy­cji (nie mylmy z sor­towaniem!). Może­my odwołać się do ele­men­tu po numerze kole­jnym, np. ‘podaj ele­ment na pozy­cji 1’. Ten sam obiekt może wys­tępować na kilku pozycjach
• java.util.Set — zbiór, tj. kolekc­ja, która prze­chowu­je obiek­ty bez określe­nia pozy­cji (ale może prze­chowywać je w sposób uporząd­kowany — tj. posor­towany). Ten sam obiekt może wys­tępować tylko raz w danej kolekcji.
• java.util.Queue — kole­j­ka, czyli lista umożli­wia­ją­ca imple­men­tację kole­jek FIFO i FILO. Kole­j­ki dzi­ała­ją ana­log­icznie jak w sklepie, ele­men­ty dodawane trafi­a­ją na koniec kole­j­ki, może­my najpierw ‘obsłużyć’ osobę z początku kole­j­ki (FIFO) lub z jej koń­ca (FILO)
• java.util.Map — mapa, nie jest to stricte kolekc­ja, ale jako taką będziemy ją trak­tować. Mapa prze­chowu­je mapowa­nia klucz-wartość, przy czym klucz musi być unikalny. Moż­na o niej myśleć jak o indek­sie czy spisie treś­ci (spis treś­ci mapu­je nazwę rozdzi­ału na rozdzi­ał, gdzie nazwa rozdzi­ału jest kluczem a sam rozdzi­ał (jego treść) wartością)

java.util.List

Lista to kolekc­ja, w której każdy ele­ment ma przy­porząd­kowany numer kole­jny (indeks). Pod­sta­wowe oper­ac­je na liś­cie to dodaj ele­ment ( add(E ele­ment) ) oraz pobierz ele­ment z pozy­cji i ( E get(int position) ).

Obiek­ty na liś­cie mogą się pow­tarzać — tj. ten sam obiekt może się pojaw­ić na liś­cie kil­ka razy (np. na pozy­c­jach 0, 1 i 2)

Najpopularniejsze implementacje

• ArrayList — prze­chowu­je dane wewnętrznie w tabl­i­cy. Opc­ja opty­mal­na jeśli znamy docelowy rozmi­ar listy lub oper­acji dodawa­nia wykonu­je­my mało w sto­sunku do oper­acji odczy­tu, a oper­ac­je odczy­tu nie są w pętli for-each
• LinkedList — prze­chowu­je dane w postaci pow­iązanej, wyda­jniejsza w sytu­ac­jach w których doda­je­my wiele ele­men­tów, a odczyt odby­wa się sek­wen­cyjnie (odczy­tu­je­my ele­men­ty za pomocą iter­a­to­ra lub pętli for-each)

Przykładowy kod

List<String> lista = new ArrayList<String>();
lista.add("pierwszy");
lista.add("drugi");
System.out.println(lista.get(1)); //wypisze "drugi"

Schemat ide­owy — lista

java.util.Set

Set (zbiór) to kolekc­ja, w której ele­men­ty nie mają przy­porząd­kowanego numeru kole­jnego (indek­su), a dostęp do nich odby­wa się za pośred­nictwem iter­a­to­ra. Pod­sta­wowe oper­ac­je na tym zbiorze to dodaj ele­ment ( add(E ele­ment) ) oraz pobierz iter­tor ( Iterator<E> iterator() ).

Obiek­ty w zbiorze nie mogą się pow­tarzać — tj. ten sam obiekt moż­na dodać do zbioru wielokrot­nie, ale będzie on w nim prze­chowywany tylko jeden raz

Najpopularniejsze implementacje

• Hash­Set — pod­sta­wowa imple­men­tac­ja, wyko­rzys­tu­je mech­a­nizm hash­Code() wbu­dowany w język Java do orga­ni­za­cji przechowywania
• TreeSet- prze­chowu­je ele­men­ty w postaci drze­wa, posor­towane, gwaran­towana złożoność przy wstaw­ia­n­iu ele­men­tów (może być to istotne w przy­pad­ku dużych zbiorów)

Przykładowy kod

Set<String> zbior = new HashSet<String>();
zbior.add("pierwszy");
zbior.add("drugi");
for (String ciagZnakow : zbior) { 
    System.out.println(ciagZnakow);
}

Schemat ide­owy — zbiór

java.util.Queue

Kole­j­ki to specy­ficz­na kon­strukc­ja pozwala­ją­ca na imple­men­tację kole­jek typu FIFO (first-in-first-out) i FILO (first-in-last-out, cza­sem nazy­wana stosem).

Kole­j­ki udostęp­ni­a­ją oczy­wiś­cie oper­ację dodawa­nia ( add(E ele­ment) ) oraz pobiera­nia ele­men­tu z głowy bez usuwa­nia go z kole­j­ki ( E peek() ) oraz od razu usuwa­jąc go z kole­j­ki ( E remove() ).

Obiek­ty w kole­jce mogą się powtarzać.

Najpopularniejsze implementacje

• Array­D­eque — kole­j­ka opar­ta o tablice, pozwala na dostęp zarówno od strony głowy ( get­First() ) jak i ogo­na ( get­Last() ). Ele­men­ty prze­chowywane są w kole­jnoś­ci dodawania
• Pri­or­i­tyQueue — pozwala na prze­chowywanie i dostęp do ele­men­tów wg określonego kry­teri­um (kom­para­to­ra), sor­tu­jąc ele­men­ty wg niego w momen­cie doda­nia do kole­j­ki. Przy­dat­na w sytu­ac­jach gdy mamy np. kole­jkę obiek­tów do przetworzenia i chce­my zawsze obsłużyć ważniejsze szy­b­ciej niż te mniej ważne

Przykładowy kod

Queue<String> kolejka = new ArrayDeque<String>();
kolejka.add("pierwszy");
kolejka.add("drugi");
System.out.println(kolejka.remove()); //wypisze "pierwszy"

Schemat ide­owy — kolejka

java.util.Map

Mapy, choć nie są for­mal­nie kolekc­ja­mi z punk­tu widzenia języ­ka Java (nie są typu Col­lec­tion), także służą do prze­chowywa­nia ele­men­tów. Wyróż­nia je to, że prze­chowu­ją nie tyle same ele­men­ty, co mapowanie klucz-wartość, tzn. jeden obiekt (klucz) wskazu­je na inny obiekt (wartość).

W przy­pad­ku map mamy przede wszys­tkim oper­ację dodawa­nia ( put(K key, V val­ue) ) oraz pobiera­nia ele­men­tu ( V get(K key) ).

Obiek­ty w mapie mogą się pow­tarzać, jeśli są wartoś­ci­a­mi. Klucze muszą być unikalne. Wartoś­ci i klucze moga być dowol­nego typu.

Najpopularniejsze implementacje

• HashMap — mapa, której właś­ci­woś­ci są podob­ne do Hash­Set’a, kole­jność oraz prze­chowywanie wynika­ją z imple­men­tacji funkcji hashCode()
• TreeMap — ele­men­ty są prze­chowywane w formie posor­towanej (wg klucza)

Przykładowy kod

Map<String, Integer> mapa = new HashMap<String, Integer>();
mapa.put("pierwszy", 1);
mapa.put("drugi", 2);
System.out.println(map.get("pierwszy")); //wypisze "1"

Schemat ide­owy — mapa

Materiały dodatkowe / dokumentacja

1. Tuto­r­i­al firmy Ora­cle na tem­at kolekcji (EN)
2. Mate­ri­ały wykład­owe z Uni­w­er­syte­tu im. Adama Mick­iewicza (autor: Ravi Chhajlany)

Zadanie

Zmody­fikuj pro­gram który już napisałaś. Utwórz nową klasę o nazwie Kot­DAO, posi­ada­jącą metodę dodajKoa(Kot kot) oraz pole koty będące kolekcją (listą).

Na początku pro­gra­mu utwórz nowy obiekt Kot­DAO. Po tym, jak wypełnisz obiekt Kot wywołaj jego metodę doda­jKo­ta przekazu­jąc jako argu­ment utwor­zony i wypełniony wcześniej obiekt. Meto­da doda­jKo­ta powin­na dodać kot­ka przekazanego w argu­men­cie do kolekcji (listy).

Pobierz rozwiązanie tego zadania