Struktury danych » Algorytmy i Struktury Danych

Praktycznie każdy program, czy nawet algorytm, operuje na różnego rodzaju danych. Wydajność oraz prostota tych systemów zależy w dużej mierze od postaci przetwarzanych informacji, a co za tym idzie – także wykorzystanych do tego celu struktur danych.

Przyjrzymy się dzisiaj wspólnie podstawowym strukturom danych, które są jednym z podstawowych narzędzi programisty oraz napiszemy proste przykłady z wykorzystaniem gotowych implementacji w Javie.

Co to jest algorytm❓

Algorytm możemy rozumieć jako jednoznaczny przepis postępowania, gdzie zamieniamy jakieś informacje wejściowe na oczekiwany wynik.
Czyli:

• dostajemy coś na wejściu – np. użytkownik wprowadza dane do naszego systemu,
• przetwarzamy te informacje – np. sprawdzając ich poprawność, usuwając duplikaty i ostatecznie zapisujemy je w pewnej strukturze danych do późniejszej  obróbki.
  Taka obróbka to może być np. wyciągnięcie najnowszych danych – w zależności od wybranej wcześniej struktury danych możemy to zrobić stosunkowo łatwo lub nie. 🙂
  Dlatego właśnie struktury danych są tak istotne.

Co to są struktury danych? 🤔

Zobaczmy, jak mogłoby to wyglądać w praktyce. Wyobraź sobie algorytm, który przetwarza informacje o polskich miastach, a do przechowywania informacji wykorzystuje zwykły tekst, np.

Gdańsk to miasto w północnej części Polski,
w województwie pomorskim, 
położone nad Morzem Bałtyckim. 
Populacja pod koniec 2017 roku wyniosła prawie pięćset tysięcy osób.

Dla człowieka zrozumienie powyższego tekstu nie stanowi większego problemu, jednak komputery nie myślą w tak abstrakcyjny sposób. Bardzo ciężko byłoby przygotować program, który zrozumiałby takie informacje i później mógłby je jeszcze przetwarzać.

Struktura danych

Komputery potrzebują bardziej jednoznacznych komunikatów, nie są też w stanie wywnioskować informacji z kontekstu (na ten moment pomijamy zagadnienia związane ze sztuczną inteligencją). W związku z tym powinniśmy najpierw odpowiednio ustandaryzować informacje i dopiero wtedy przekazać je w postaci zrozumiałej dla algorytmów.

Rekord – statyczna struktura danych

Uporządkujmy teraz dane z poprzedniego przykładu w formie prostego rekordu danych:

{
    name:       "Gdańsk",
    province:   "Pomorskie",
    population: 500000
}

W Javie możemy w tym celu wykorzystać klasę:

public class City {

    private String name;
    private String province;
    private long population;

    public City(String name, String province, long population) {
        this.name = name;
        this.province = province;
        this.population = population;
    }
}

City gdansk = new City("Gdańsk", "Pomorskie", 500000);

Dane zebrane w tej formie są już w pewien sposób uporządkowane, dzięki czemu można je łatwiej przetwarzać i analizować. Rekord bardzo dobrze sprawdza się, gdy chcemy przechować dane na temat tylko jednego obiektu. Jednak co zrobić, kiedy takich obiektów będzie więcej: dziesiątki lub nawet tysiące?

Tablice (Array)

Powiedzieliśmy sobie wcześniej, że chcemy przetwarzać informacje o wszystkich polskich miastach. W takim wypadku sam pojedynczy rekord nie wystarczy.

Z pomocą może przyjść kolejna struktura danych – tablica.
Tablice bardzo dobrze sprawdzają się w sytuacji, gdy mamy pewien zbiór danych tego samego typu, który nie będzie modyfikowany podczas działania algorytmu. Rozmiar tego typu struktur musimy jednak określić już na samym początku, podczas podawania wstępnych parametrów.

City[] cities = new City[100];
cities[0] = new City("Gdańsk", "Pomorskie", 500000);

Inną charakterystyczną cechą tablicy, poza jej stałym rozmiarem, jest umiejscowienie kolejnych jej elementów obok siebie w pamięci, dzięki czemu mamy możliwość prostego i szybkiego dostępu do nich przy pomocy indeksów.

Tablice mają jednak jedną zasadniczą wadę, mianowicie – jak już wspomniałem – ich rozmiar musi być zdefiniowany już na samym początku, w momencie tworzenia. Wskutek tego przechowywanie w nich zmiennej ilości elementów jest kłopotliwe i może być mało wydajne.

Ten problem nie dotyczy kolejnej struktury, którą za chwilę poznamy.

 ZOBACZ : Tablice

Listy (List)

Lista, podobnie jak tablica, przeznaczona jest do przechowywania większej ilości danych. Z tym wyjątkiem, że lista umożliwia łatwe dodawanie nowych elementów.

Listę można postrzegać jako łańcuszek połączonych ze sobą danych. Wiedząc, gdzie znajduje się początek, możemy znaleźć kolejne ogniwa takiej struktury.

Struktury danych lista

Lista tablicowa – ArrayList

Już sama nazwa wskazuje, że do implementacji tej listy została wykorzystana tablica. Jest to tak naprawdę zwykła tablica wyposażona w dodatkowe funkcje, które ukrywają złożoną logikę i umożliwiają np. usunięcie elementu ze środka listy, czy zwiększenie jej rozmiaru.

Dopisanie elementu na końcu listy, gdy rozmiar wewnętrznej tablicy został już wykorzystany, wymusza utworzenie nowego większego obszaru roboczego i przekopiowanie do niego wszystkich bieżących wartości. Natomiast usunięcie elementu ze środka listy wymaga przesunięcia wszystkich kolejnych segmentów w wewnętrznej tablicy o jedną pozycję do tyłu. Natomiast – gdy korzystamy z ArrayList, te wszystkie skomplikowane operacje są wykonywana za nas automatycznie i często nawet nie jesteśmy ich świadomi.

Największą zaletę listy tablicowej stanowi jej prosta nawigacja z wykorzystaniem indeksu. Natomiast wadą jest niska elastyczność i wydajność w przypadku częstych zmian rozmiaru i usuwania elementów. W związku z tym ArrayList świetnie sprawdza się w sytuacjach, kiedy elastyczność odgrywa mniejszą rolę, a potrzebna jest szybka i prosta nawigacja po poszczególnych elementach listy.

List list = new ArrayList();
list.add("A");
list.add("B");
String b = (String) list.get(1);

Lista wskaźnikowa – LinkedList

Implementacja wskaźnikowa wymusza dodanie do każdego elementu listy nowej wartości: wskaźnika, czyli referencji, dzięki czemu zrealizowana jest lokalna nawigacja w liście. W przeciwieństwie do tablicy logiczna kolejność elementów w liście wskaźnikowej może być inna niż jej fizyczne ułożenie w pamięci.

Dodanie nowego elementu do listy w tej implementacji wymaga utworzenia kolejnej wartości i aktualizacji wskaźników. Podobnie wygląda usuwanie elementów. Nawet jeżeli usuniemy komponent ze środka listy, to wystarczy, że zostaną zaktualizowane wskaźniki z pominięciem usuniętego elementu. Nie ma zatem konieczności zmieniania wszystkich pozostałych rekordów. Dlatego tego typu listy bardzo dobrze sprawdzają się w przypadku, gdy często modyfikujemy (dodajemy i usuwamy) elementy z listy. W konsekwencji tracimy jednak możliwość uzyskania szybkiego dostępu do konkretnej wartości przy pomocy indeksu.

List list = new java.util.LinkedList();
list.add("A");
list.add("B");
String b = (String) list.get(1);

Ciekawe jest, że implementacja LinkedList dalej oferuje nam możliwość pobierania elementów przy pomocy indeksu, jednak żeby to zrealizować i odnaleźć odpowiedni rekord – musi przeiterować po jej elementach.

W zależności od ilości wskaźników oraz sposobu ich wykorzystania w liście możemy wyróżnić kilka szczególnych przypadków jej implementacji.

Lista jednokierunkowa

Najprostszą formą listy jest lista jednokierunkowa, w której każdy element zawiera  referencję do kolejnego (lub poprzedniego) komponentu w liście lub do wartości pustej (NULL), jeżeli jest to ostatni jej element.

Lista dwukierunkowa

Lista dwukierunkowa jest rozwinięciem listy jednokierunkowej. W tym wypadku poszczególny rekord w liście zawiera referencję do poprzedniego i kolejnego elementu. Dzięki takiej implementacji można swobodnie poruszać się po liście w górę i w dół.

Lista cykliczna

W tej liście ostatni element jest powiązany z pierwszym, a pierwszy – z ostatnim. Dzięki temu tworzy się zamknięty cykl i możemy poruszać się wkoło. W związku z tym taka lista charakteryzuje się również brakiem początkowego wskaźnika (głowa listy – HEAD) oraz ostatniego (ogon listy – TAIL).

Stos (Stack) – LIFO

Najłatwiej wyobrazić sobie tę strukturę jako stos talerzy do pozmywania ułożonych jeden na drugim. Zaczynamy od obiektów znajdujących się na samej górze, jednak gdy ktoś w trakcie wykonywania przez nas czynności przyniesie jeszcze brudne naczynia, to wylądują one na samym szczycie stosu.

Natomiast – aby dostać się do elementów znajdujących się na samym dole – trzeba najpierw ściągnąć wszystkie inne.

Podstawowe operacje na stosie to:

• push (obiekt) – dodanie obiektu na wierzch stosu;
• pop () – ściągnięcie jednego elementu ze stosu i zwrócenie jego wartości.

Deque<String> stack = new java.util.LinkedList();
stack.push("A");
stack.push("B");

stack.pop();
String a = stack.pop();

 ZOBACZ : Stos (Stack) – 7+ tajników implementacji LIFO

Kolejka (Queue) – FIFO

Przeciwieństwem stosu LIFO jest kolejka typu FIFO (ang. First In, First Out), czyli 'pierwszy na wejściu, pierwszy na wyjściu’. W tym przypadku zaczynamy przetwarzanie danych od elementów, które pojawiły się jako pierwsze. Jest to odpowiednik zwykłej kolejki w sklepie.

java.util.Queue<String> queue = new java.util.LinkedList();
queue.add("A");
queue.add("B");

String a = queue.poll();

Tego typu kolejki spotyka się przede wszystkim w systemach, gdzie przetwarzane są różnego rodzaju zadania i zależy nam na ich odpowiednim uporządkowaniu.

Zbiór (Set)

Zbiór to kolekcja elementów, która nie może zawierać duplikatów.

W Javie najczęściej wykorzystywane są dwie implementacje: HashSet oraz TreeSet.

Set<String> hashSet = new HashSet<>();
hashSet.add("c1");
hashSet.add("a1");
hashSet.add("b1");
hashSet.add("b1");

Set<String> treeSet = new TreeSet<>();
treeSet.add("c1");
treeSet.add("a1");
treeSet.add("b1");
treeSet.add("b1");

System.out.println(hashSet); // [a1, c1, b1]
System.out.println(treeSet); // [a1, b1, c1]

Główna różnica między tymi dwiema implementacjami polega na tym, że TreeSet wyznacza kolejność elementów (domyślnie jest ona rosnąca), a HashSet – nie. W szczególnych przypadkach może się jednak zdarzyć, że HashSet również posortuje elementy rosnąco, jednak implementacja tego nie gwarantuje.

Chcąc dodać do Set’a instancje swej własnej klasy, musisz pamiętać o odpowiednim zaimplementowaniu metod: hashCode oraz equals. Jeżeli nie zachowasz założeń kontraktu między tymi metodami, możesz spodziewać się bardzo dziwnych błędów. Więcej na ten temat przeczytasz w podlinkowanym artykule.

Dodatkowo w przypadku TreeSet klasy przechowywanych obiektów muszą implementować interfejs: java.lang.Comparable.

• Zobacz 👉 hashCode i equals – co grozi Ci za złamanie kontraktu między metodami equals i hashCode?

Dynamiczne struktury danych

Jest to bardzo wygodne, ponieważ na starcie bardzo rzadko kiedy wiemy ile i jakie dokładnie dane będziemy przetwarzać.

Taka swoboda ma jednak swoją cenę – tego typu struktury danych są zwyczajnie bardziej skomplikowane. Dostęp do przechowywanych w nich  danych odbywa się często przy pomocy specjalnych wskaźników, a modyfikacje struktury przy pomocy odpowiednich metod.

Całe szczęście, że o ile sami nie chcemy napisać ręcznie implementacji takiej struktury, to cały niezbędny kod powinien być już gotowy i dla nas zostaje tylko wywołanie odpowiedniej metody.

Przykłady struktur dynamicznych to np. stos, kolejka, lista jedno i dwukierunkowa, drzewo itp.

Mapa (Map) 🗺

Mapa to specyficzna kolekcja, która przechowuje pary danych składające się z klucza oraz przypisanej wartości.

Klucz w obrębie mapy musi być unikatowy, natomiast wartości mogą się powtarzać.

Map<String, Integer> map = new HashMap<>();
map.put("Gdańsk", 10);
map.put("Warszawa", 5);
map.put("Warszawa", 7);

System.out.println(map);    // {Gdańsk=10, Warszawa=7}

Na powyższym przykładzie widać, że ponowne przypisanie wartości dla tego samego klucza powoduje nadpisanie poprzedniej wartości.

Struktury danych – Podsumowanie 💪

Struktury danych są bardzo ważnym narzędziem w rękach każdego programisty. Jednak jak z każdym narzędziem, trzeba wiedzieć kiedy i jak z niego skorzystać.
To od nas jako deweloperów zależy, czy dobrze wykorzystamy te możliwości. Dobrze dobrana struktura danych może w znacznym stopniu wpłynąć na czytelność oraz wydajność naszych aplikacji.