Collection interface – co warto wiedzieć?

Interfejs „java.util.Collection” to najwyższy w hierarchii interfejs kolekcji. Kolekcja reprezentuje grupę obiektów, które możemy nazwać elementami. Java nie dostarcza żadnej bezpośredniej implementacji dla tego interfejsu. Dostarcza za to interfejsy rozszerzające Collection: List, Set oraz Queue oraz Deque, które mają swoje implementacje. Omówimy je szerzej w tym artykule.

List

Lista jest interfejsem dedykowanym do uporządkowanego przechowywania obiektów. Pozwala na dodawanie i usuwanie elementów jak w tablicy. Elementy są indeksowane – możemy dzięki temu pobrać obiekt znajdujący się na konkretnej pozycji. W listach dozwolone są duplikaty elementów.

Dużym ułatwieniem w stosunku do tablic jest to, że nie musimy deklarować rozmiaru listy na początku jej używania. Oczywiście możemy to zrobić i to się zaleca, kiedy wiemy, jakiego rozmiaru listy potrzebujemy. W listach nie możemy przechowywać typów prymitywnych.

Aby użyć listy musimy zaimportować pakiet:

import java.util.List;

Przykładowe użycie listy, tworzymy instancje klasy ArrayList:

               Java 7+

List<Integer> list = new ArrayList<>();

               Java 10+

var items = new ArrayList<String>();

Możemy także utworzyć listę poprzez statyczną metodę dostępną w interfejsie List:

List<Integer> list = List.of(1, 2, 3, 4);

Metoda of() zwraca niemodyfikowalną listę zawierającą podane w argumencie elementy. Próba modyfikacji takiej listy skończy się rzuceniem wyjątku „UnsupportedOperationException”, jako argumentu metody nie można użyć nulla.

Dobrą praktyką przy używaniu list jest deklaracja typu obiektu, jaki będzie używany. Zapewnia nam to, że jeśli spróbujemy dodać do listy nieodpowiedni typ, to już na etapie kompilacji otrzymamy błąd. Możemy tworzyć listę z dowolnych obiektów.

Najważniejsze metody

Do najważniejszych metod należą:

• add() – dodaje element na koniec listy

list.add(5); // [5]

• addAll() – dodaje wszystkie elementy listy do innej listy

List<Integer> list2 = List.of(1, 2);
list.addAll(list2); // [5, 1, 2]

• size() – zwraca ilość elementów w liście

int size = list.size(); // 3

• get() – umożliwia pobranie elementu z listy, do metody podajemy indeks, na jakim znajduje się element (numeracja listy zaczyna się od 0)

Integer = list.get(0); // 5

• iterator() – zwraca obiekt iteratora, który umożliwia dostęp do elementów

Iterator<Integer> iterator = list.iterator();

• set() – aktualizuje element w danej pozycji listy(zastępuje go)

list.set(0, 9); // [9, 1, 2]

• isEmpty() – zwraca „true” kiedy lista nie posiada elementów

boolean isEmpty = list.isEmpty(); // false

• toArray() – konwertuje listę na tablicę

Object[] objects = list.toArray();
// Arrays.toString(objects) [9, 1, 2]

• contains() – zwraca „true” kiedy lista posiada podany element

boolean contains = list.contains(2); // true

• remove() – usuwa element z listy

list.remove(1); // [9, 2]

• removeAll() – usuwa wszystkie elementy z listy

list.removeAll(list2); // [9]

• clear() – usuwa wszystkie elementy z listy (bardziej wydajne od removeAll)

list.clear(); // []

Rodzaje list

Poniżej przybliżę rodzaje list.

• ArrayList – implementuje listę jako dynamiczną tablicę. Jej rozmiar zostanie automatyczne rozszerzony, jeśli nie będzie wystarczającej ilości miejsca, aby dodać kolejny element. Możemy ustawić domyślny rozmiar listy podczas jej tworzenia:

List<Integer> list = new ArrayList<>(5);

Nie jest to obowiązkowe, jednak jest wydajniejsze niż automatyczne rozszerzanie listy. Kiedy lista jest rozszerzana to zwiększa swoją pojemność o 50%.

Zalety ArrayListy to szybie wyszukiwanie elementów i ich pobieranie. Możemy w niej przechowywać wiele wartości null oraz duplikaty, co w niektórych sytuacjach może być widziane jako wada. Nie zaleca się używania ArrayListy w sytuacji, kiedy często dodajemy i usuwamy elementy z listy. Kiedy usuwamy środkowy element z listy musimy przesunąć wszystkie kolejne w stronę początku.

• Vector – implementuje interfejs „List” tak samo jak „ArrayList” i zapewnia podobną funkcjonalność. Różnią się one jednak kilkoma rzeczami:
  • Vector jest zsynchronizowany.
  • Kiedy zapełnimy Vector, powiększa on swoją wielkość o 100%, a nie tak jak ArrayList o 50%.
  • Vector jest starą klasą tzw. Legacy class.
  • Vector jest wolniejszy od ArrayList, ponieważ jest zsynchronizowany. Przy użyciu wielu wątków wstrzymuje kolejne operacje, dopóki nie zakończy poprzednich.

Tworzenie wektora:

Vector<Integer> vector = new Vector<>();

Możemy też przy tworzeniu podać rozmiar:

Vector<Integer> vector = new Vector<>(5);

Nie zaleca się używania klasy Vector, ponieważ w aplikacji jednowątkowej jest wolniejsza od ArrayList, a w wielowątkowej nie zapewnia pełnego bezpieczeństwa.

• Stack – działa zgodnie z zasadą „Last In First Out (LIFO)” czyli element, który dodaliśmy jako ostatni, znajdzie się na górze stosu.

Tworzenie stosu:

Stack<Integer> stack = new Stack<>();

Stack posiada te same metody co Vector oraz dodatkowo pięć swoich:

• push() – dodanie elementu na szczyt stosu

Stack<Integer> stack = new Stack<>();
 
stack.push(1);
stack.push(2);
stack.push(3);
// [1, 2, 3]

• pop() – usunięcie elementu ze szczytu stosu

Integer pop = stack.pop(); // [1, 2]

• peek() – zwraca obiekt ze szczytu stosu

Integer peek = stack.peek(); // 2

• search() – wyszukuje element na stosie, zwraca jego pozycje od góry stosu

int search = stack.search(1); // 2

• empty() – sprawdza czy stos jest pusty

boolean empty = stack.empty(); // false

Stosu używamy, gdy chcemy zachować kolejność naszych działań lub stworzyć listę, która obrazuje relacje ojciec – dziecko (parent – child). Zamiast klasy Stack zaleca się używanie ArrayDeque. Jednym z powodów jest to, że Stack jest klasą, a Deque interfejsem.

Umożliwia to kontrolę i daje większe możliwości przy użyciu na korzyść interfejsu. Dodatkowo, poprzez rozszerzenie klasy Vector, możliwe jest pobieranie elementów przez ich indeks, co jest zaprzeczeniem podstawowego działania stosu.

• LinkedList – przechowuje elementy w strukturze danych w postaci podwójnie połączonej listy.

Każdy element listy składa się z trzech węzłów:

• PREV – przechowuje adres w pamięci do poprzedniego elementu listy, dla pierwszego elementu będzie to null.
• NEXT ­– przechowuje adres w pamięci do następnego elementu listy, dla ostatniego elementu będzie to null.
• DATA – przechowuje dane, które dodaliśmy do listy.

Tworzenie nowej listy:

LinkedList<Integer> linkedList = new LinkedList<>();

LinkedList oprócz interfejsu „List” implementuje również „Queue” i „Deque”.

Pozwala to na implementację metod pochodzących z tych interfejsów, takich jak:

Queue<Integer> queueList = new LinkedList<>();
 
queueList.add(1);
queueList.add(2);
queueList.add(3); 
        // [1, 2, 3]

• poll() – Queue – zwraca i usuwa pierwszy element listy

Integer poll = queueList.poll(); // 1

• peek() – Queue – zwraca pierwszy element listy (head)

Integer peek = queueList.peek(); // 2
 
 
Deque<Integer> dequeList = new LinkedList<>();
dequeList.add(1);
dequeList.add(2);
dequeList.add(3);
// [1, 2, 3]

• addFirst() – Deque – dodaje element na początek listy

dequeList.addFirst(4); // [4, 1, 2, 3]

• addLast() – Deque – dodaje element na koniec listy

dequeList.addLast(5); // [4, 1, 2, 3, 5]

• getFirst() – Deque – zwraca pierwszy element

Integer first = dequeList.getFirst(); // 4

• getLast() – Deque – zwraca ostatni element

Integer last = dequeList.getLast(); // 5

• removeFirst() – Deque – usuwa pierwszy element

dequeList.removeFirst(); // [1, 2, 3, 5]

• removeLast() – Deque – usuwa ostatni element

dequeList.removeLast(); // [1, 2, 3]

• offer() – Deque – dodaje element na koniec listy

dequeList.offer(6); // [1, 2, 3, 6]

Zaletą tej listy jest szybkie dodawanie i usuwanie elementów. Wadą szybkość pobierania elementów. Podczas usuwania elementu ze środka listy muszą zaktualizować się tylko elementy po obu stronach usuwanego obiektu.

Set

Set jest kolejnym interfejsem wchodzącym w skład „Collection”. Charakteryzuje się on tym, że przechowuje unikalne elementy. Nie możemy odwoływać się do konkretnego elementu zbioru, ponieważ nie wiadomo, na jakiej pozycji się on znajduje. Zależnie od interpretacji Set możemy sortować.

Przykładowa implementacja zbioru:

Set<Integer> set = new HashSet<>();

Najważniejsze metody

• add() – dodaje elementy do zbioru

set.add(1);
set.add(2);
set.add(3); // [1, 2, 3]

• addAll() – dodaje wszystkie elementy z kolekcji do zbioru

List<Integer> list = List.of(5, 6, 7);
 
set.addAll(list); // [1, 2, 3, 5, 6, 7]

• iterator() – zwraca iterator, którego możemy użyć do dostępu do elementu

Iterator<Integer> iterator = set.iterator();

• remove() – usuwa element ze zbioru, jako parametr podajemy element, który chcemy usunąć, a nie, jak w przypadku listy, indeks

set.remove(1); // [2, 3, 5, 6, 7]

• retainAll() – zachowuje wszystkie elementy zbioru, które są zawarte w innej kolekcji

set.retainAll(list); // [5, 6, 7]

• size() – zwraca ilość elementów zbioru

int size = set.size(); // 3

• toArray() – zwraca tablicę zawierającą elementy zbioru

Object[] objects = set.toArray();

• contains() – zwraca true, jeśli zbiór zawiera podany element

boolean contains = set.contains(7); // true

• containsAll() – zwraca true, jeśli zbiór zawiera wszystkie podane elementy

boolean b = set.containsAll(list); // true

• hashCode() – zwraca wartość hasz zbioru

int i = set.hashCode(); // 18

• removeAll() – usuwa wszystkie elementy ze zbioru zawarte w podanej kolekcji

set.removeAll(list); // []

• clear() – usuwa wszystkie elementy ze zbioru

set.clear(); // []

Rodzaje

W interfejsie Set wyróżniamy poniższe rodzaje.

• HashSet – podstawowa implementacja zbioru. Zapewnia unikalność elementów, ale nie gwarantuje kolejności elementów. Wewnętrznie wykorzystuje tablice mieszającą, co wymaga implementacji metod „hashCode” i „equals()”. W HashSet możemy przechowywać wartość null. HashSet jest zbiorem niesynchronizowanym. Jeśli chcemy używać go w wielowątkowości, sami musimy zapewnić synchronizacje.

Set<Integer> set = new HashSet<>();

• LinkedHashSet – implementacja zbioru, która zapewnia funkcjonalność tablicy mieszającej oraz listy połączonej. Elementy zbioru są przechowywane podobnie jak w HashSet, ale zachowuje kolejność ich dodawania. Tak samo jak HashSet możemy przechowywać wartość null.

Tworzenie LinkedHashSet z podaną pojemnością (capacity) oraz współczynnikiem określającym, kiedy lista ma zwiększyć swoją pojemność (loadFactor):

LinkedHashSet<Integer> numbers = new LinkedHashSet<>(8, 0.6);

Podana lista może przechować 8 elementów oraz zwiększy swoją pojemność dwukrotnie, kiedy zapełni się w 60%.

• EnumSet – jest implementacją zbioru, która działa wyłącznie z typami wyliczeniowymi. Przechowujemy w nim obiekty, które są enumami. Nie możemy przechowywać wartości null, a zbiór nie jest bezpieczny do użycia w wielowątkowości. Elementy są przechowywane w kolejności, w jakiej zadeklarowane są enumy.

EnumSet używa iteratora, który działa na kopii zbioru, więc nie wyrzuci wyjątku, jeśli coś zmieni się w zbiorze podczas jego iteracji. EnumSet powinien być zawsze używany, kiedy chcemy stworzyć zbiór enumów, ponieważ jest bardziej wydajny od innych rodzajów zbiorów m.in. przez to, że nie trzeba porównywać zahaszowanych wartości, aby z niego korzystać.

EnumSet jest klasą abstrakcyjną, JDK dostarcza dwie implementacje tej klasy, jednak nie korzystamy z nich bezpośrednio. Są to klasy package-private:

• RegularEnumSet – dla zbiorów do 64 elementów
• JumboEnumSet – dla zbiorów powyżej 64 elementów

Klasa dostarcza również kilka metod statycznych pozwalających tworzyć zbiór. W takim przypadku tworzona jest implementacja zależna od ilości elementów w enumie.

enum Size {
                    SMALL, MEDIUM, LARGE, EXTRALARGE
            }
 
            Set<Size> set = EnumSet.allOf(Size.class);

• TreeSet – przechowuje zbiór pod postacią drzewa. Ta implementacja nie zapewnia zapamiętania kolejności dodawania elementów, za to przechowuje je w posortowany sposób (rosnąco). Nie możemy w nim przechowywać nulli oraz obiektów, które nie implementują interfejsu „Comparable”, nie jest bezpieczny przy używaniu wątków.

W porównaniu do HashSet ten zbiór zapewnia wolniejsze przetwarzanie danych, ponieważ każdy dodany element musi zostać posortowany. TreeSet posiada też kilka metod zaimplementowanych z NavigableSet oraz SortedSet:

TreeSet<Integer> treeSet = new TreeSet<>();
 
            treeSet.add(1);
            treeSet.add(2);
            treeSet.add(3); // [1, 2, 3]

• lower() – zwraca ze zbioru największy element, który jest mniejszy od podanego

Integer lower = treeSet.lower(2); // 1

• floor() ­– zwraca najmniejszy element pośród tych, które są mniejsze od podanego elementu, jeśli podany element istnieje w zbiorze, to go zwróci

Integer floor = treeSet.floor(2); // 2

• ceiling() – zwraca najmniejszy element pośród tych, które są większe od podanego elementu, jeśli podany element istnieje w zbiorze, to go zwróci

Integer ceiling = treeSet.ceiling(2); // 2

• higher() – zwraca ze zbioru najmniejszy element, który jest większy od podanego

Integer higher = treeSet.higher(2); // 3

• pollFirst() – zwraca i usuwa pierwszy element zbioru

Integer poolFirst = treeSet.pollFirst(); // 1

• pollLast() – zwraca i usuwa ostatni element zbioru

Integer poolLast = treeSet.pollLast(); // 3

• first() – zwraca pierwszy element zbioru

Integer first = treeSet.first(); // 2

• last() – zwraca ostatni element zbioru

Integer last = treeSet.last(); // 2

Queue/Deque

Queue<Integer> queue = new PriorityQueue<>();

Interfejs Queue wchodzi w skład Collection. Charakteryzuje się tym, że mamy dostęp do danych jedynie z początku i końca zbioru. Głównym zadaniem kolejek jest porządkowanie zbioru w określonej wcześniej kolejności.

Możemy wyróżnić dwa podstawowe typy kolejek:

• FIFO – first in, first out – wstawiamy element na koniec listy, a zdejmujemy go z początku

• LIFO – last in, first out – wstawiamy element na początek kolejki i zdejmujemy też pierwszy element

• Deque natomiast to kolejka pozwala na dodawanie i usuwanie elementów z obu jej stron.

Najważniejsze metody

Queue:

Queue<Integer> queue = new PriorityQueue<>();
 
        queue.add(1);
        queue.add(2);
        queue.add(3); // [1, 2, 3]

• add() – dodaje element do kolejki, jeśli operacja się powiedzie– zwraca true, jeśli nie – rzuca wyjątek

boolean add = queue.add(4); // true

• offer() – dodaje element do kolejki, jeśli operacja się powiedzie – zwraca true, jeśli nie – zwraca false

boolean offer = queue.offer(5); // true

• element() – zwraca pierwszy element kolejki, rzuca wyjątek, jeśli kolejka jest pusta

Integer element = queue.element(); // 1

• peek() – zwraca pierwszy element kolejki, zwraca null, jeśli kolejka jest pusta

Integer peek = queue.peek(); // 1

• remove() – zwraca i usuwa pierwszy element kolejki, rzuca wyjątek, jeśli kolejka jest pusta

Integer remove = queue.remove(); // 1 // [2, 4, 3, 5]

• poll() – zwraca i usuwa pierwszy element kolejki, zwraca null, jeśli kolejka jest pusta

Integer poll = queue.poll(); // 2 // [3, 4, 5]

Deque:

Deque<Integer> deque = new ArrayDeque<>();
 
        deque.add(1);
        deque.add(2);
        deque.add(3); // [1, 2, 3]

• addFirst() – dodaje element na początek kolejki

deque.addFirst(4); // [4, 1, 2, 3]

• addLast() – dodaje element na koniec kolejki

deque.addLast(5); // [4, 1, 2, 3, 5]

• offerFirst() – dodaje element na początek kolejki, jeśli operacja się powiodła zwraca true

deque.offerFirst(6); // [6, 4, 1, 2, 3, 5]

• offerLast() – dodaje element na koniec kolejki, jeśli operacja się powiodła – zwraca true

deque.offerLast(7); // [6, 4, 1, 2, 3, 5, 7]

• getFirst() – zwraca pierwszy element z kolejki

Integer first = deque.getFirst(); // 1

• getLast() – zwraca ostatni element z kolejki

Integer last = deque.getLast(); // 3

• peekFirst() – zwraca pierwszy element kolejki

Integer peekFirst = deque.peekFirst(); // 1

• peekLast() – zwraca ostatni element kolejki

Integer peekLast = deque.peekLast(); // 3

• removeFirst() – zwraca i usuwa pierwszy element kolejki

Integer removeFirst = deque.removeFirst(); // [4, 1, 2, 3, 5, 7]

• removeLast() – zwraca i usuwa ostatni element kolejki

Integer removeLast = deque.removeLast(); // [4, 1, 2, 3, 5]

• pollFirst() – zwraca i usuwa pierwszy element kolejki, zwraca null, jeśli kolejka jest pusta

Integer pollFirst = deque.pollFirst();// [1, 2, 3, 5]

• pollLast() – zwraca i usuwa ostatni element kolejki, zwraca null, jeśli kolejka jest pusta

Integer pollLast = deque.pollLast(); // [1, 2, 3]

Rodzaje

• Queue:
  • PriorityQueue – bazuje na implementacji stosu. Elementy są układane w naturalnym porządku, poprzez porównanie przez zapewniony Comparator. Kolejka nie pozwala na przechowywanie wartości null oraz obiektów, których nie da się ze sobą porównać.
    Kolejka układa dodane elementy w kolejności od najmniejszego do największego, tak więc jej początkiem jest najmniejszy element. PriorityQueue nie jest bezpieczna w przypadku programów wielowątkowych, do tego zadania Java zapewnia klasę PriorityBlockingQueue.

• Deque:
  • ArrayDeque – jest implementowana jako dynamiczna tablica, do której możemy dodawać elementy z przodu i z tyłu kolejki. Nie możemy dodawać nulli. Kolejka nie jest bezpieczna w aplikacjach wielowątkowych. Jeżeli początek kolejki i jej koniec wskazują na siebie po dodaniu nowego elementu, tablica automatycznie podwaja swoją wielkość.

Interfejs Iterator

Interfejsem związanym z „Collection” jest „java.util.Iterator”. Pozwala on na dostęp do elementów kolekcji. Każda z nich posiada metodę „iterator”, która zwraca instancje iteratora używanego do poruszania się po kolekcji.

Metody Iteratora

ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(3);
numbers.add(2);
// [1, 3, 2]
 
Iterator<Integer> iterate = numbers.iterator();

• hasNext() – zwraca „true” jeśli istnieje element w kolekcji

boolean b = iterate.hasNext(); // true

• next() – zwraca następny element kolekcji

int number = iterate.next(); // 1

• remove() – usuwa ostatni element zwrócony przez next()

iterate.remove(); // numbers [3, 2]

• forEachRemaining() – wykonuje akcje dla każdego elementu kolekcji

while(iterate.hasNext()) {
		iterate.forEachRemaining(System.out::print);
}
// 32

Źródła

1. Java 11 Cookbook – Nick Samoylov, Mohamed Sanaulla
2. Java podstawy – Cay S. Horstmann

***

Jeśli interesuje Was obszar Javy, polecamy inne artykuły naszych ekspertów m.in. Wyrażenie lambda w Javie oraz Java 2.0 czyli Kotlin.