1. Czym w ogóle jest Framework Java Collections?
Jest to zbiór klas i interfejsów służących do różnego rodzaju operacji na zbiorach danych takich jak ich magazynowanie, przeszukiwanie, dodawanie, usuwanie, sortowanie itd. W zależności do określonych potrzeb i złożoności danych które chcemy przechowywać wykorzystujemy inny rodzaj kolekcji. Poniżej znajduje się graficzna ilustracja hierarchii klas w Java Collections:
Jak widzimy głównym interfejsem jest tutaj Collection (on z kolei implementuje jeszcze interfejs iterable, który nie jest tutaj przedstawiony), który zawiera wszystkie główne metody na zbiorach takie jak add(), remove(), isEmpty(), size() itd.
Następnie dzieli się on na 3 podstawowe interfejsy List, Set oraz Queue. Dodatkowo warto zauważyć, że mamy tutaj interfejs Map, który nie implementuje interfejsu Collection, ale formalnie jest częścią Frameworku Collections. Przejdźmy teraz po kolei przez wszystkie te 4 bazowe interfejsy, zdefiniujmy jak działa każdy z nich oraz wyjaśnimy już poszczególne klasy danych interfejsów.
2. List
Listy to zbiory które trzymają dane w postaci uporządkowanej kolekcji w zależności od kolejności dodawania elementów do niej. W praktyce działają podobnie jak tablice Array, lecz mają tę zalete, że dynamicznie mogą zmieniać rozmiar, można dodawać lub usuwać z niej elementy na danej pozycji. Listy mogą zawierać w sobie duplikaty. Klasy które implementują interfejs List to ArrayList oraz LinkedList które opiszę poniżej. Niestety nie są one zsynchronizowane, dlatego dla użytku wielowątkowego istnieją także takie klasy jak Vector i Stack.
2.1 ArrayList
Jak sama nazwa wskazuje, ArrayLista wewnątrz korzysta ze zwykłej Array. Dynamicznie zmienia jej wielkość, gdy uzyska ona swój maksymalny rozmiar przez przepisanie elementów do tymczasowej tablicy i nadpisaniu istniejącej. Co za tym idzie dostęp do n-tego elementu tablicy mają złożoność stałą, lecz operacje dodawania i usuwania z tablicy mają złożoność O(n).
2.2 LinkedList
Klasa LinkedList działa na podstawie tzw. DoubleLinkedList, czyli każdy n-ty elementy tablicy przechowuje referencje do następnego oraz poprzedniego elementu. Wygląda to następująco:
Jak już można wywnioskować dla tej kolekcji operacja dostania się do n-tego elementu ma złożoność O(n), ponieważ Lista musi przeiterować po indeksach, aby dojść do danego elementu. Natomiast operacja dodania i usuwania mają złożoność stała, ponieważ wystarczy nam wtedy usuwać tylko referencje z poprzedniego i następnego obiektu, aby wskazywały na nowy obiekt.
3. Set
Kolejnym z interfejsów Java Collections jest Set. Różnice między Set a List są znaczące. Set w przeciwieństwie do List nie zezwala na przechowywanie duplikatów. Dodatkowo Set z reguły nie gwarantuje nam kolejności w zbiorze (możemy jednak to uzyskać przy niektórych jego klasach, lecz odbija się to na złożoności obliczeniowej). Niestety w setach nie możemy bezpośrednio uzyskiwać dostępu do danego indeksu tablicy, musimy robić to przez iterator.
3.1 HashSet
Jest to klasa implementująca Set, która wewnątrz działa na bazie HashMapy. Zezwala ona na dodanie elementu Null. Kolejność w HashSet nie jest zachowywana. Wszystkie podstawowe operacje (add, remove, contains and size) mają złożoność stałą.
3.2 LinkedHashSet
Klasa ma podobne zastosowanie jak HashSet z tą różnicą, że wykorzystywana tutaj dodatkowo Linked Lista pozwala na zachowanie kolejności dodawania elementów do zbioru.
3.3 TreeSet
Ostatnia z klas składowych Set to TreeSet. TreeSet opiera się na strukturze drzewa co za tym idzie daje nam kolejność naturalną elementów dodawanych (bądź kolejność wg zastosowanych przez nas Comparable/Comparator w obiektach magazynowanych). Różnicą między TreeSet a rodziną HashSet jest to, że nie pozwala ono na dodanie elementu Null do zbioru. Niestety podstawowe operacje na tym zbiorze maja złożonosc O(logn).
4. Queue
Kolejki do kolejny interfejs, który opiera się na tzw. strukturze FIFO (First In, First Out). Zazwyczaj stosowany do kolejkowania danych przed procesem przetworzenia.
4.1 PriorityQueue
Kolejka priorytetowa, nieco łamie nam zasadę FIFO. W kolejce takiej niektóre obiekty mają większy priorytet co za tym idzie będą ustawiane wyżej w kolejce. Możemy sobie to porównać, np. do kolejki u lekarzy gdzie inwalidzi czy kobiety w ciąży będą mieli pierwszeństwo. W programie pierwszeństwo takie możemy deklarować przez zastosowanie Comparable bądź Comparator.
4.2 Deque
Ta kolejka zachowuje właściwość FIFO, ale dodatkowo operacje w niej można wykonywać z dwóch stron kolejki, czyli od początku i końca czy też bardziej prawidłowo od głowy bądź ogona. Przedrostek DE bierze się od skrótu Double-End (podwójny koniec).
5. Map
Mapy to interfejs nie implementujący interefjsu Collection, ale znajdujący się w Frameworku Collections Java. Mapa służy do przechowywania danych klucz -> wartość. Klucze w zbiorze muszą być unikalne, natomiast wartości mogą się duplikować. Wszystkie poniżej opisane klasy implementujące map, swoimi właściwościami są odwzorowaniem z Set. W HashMap i LinkedHashMap możemy mieć jeden klucz o wartości Null, natomiast w TreeMap nie możemy mieć klucza Null.