Czym są struktury danych?

Zaczynając przygodę z programowaniem, warto zaznajomić się z kilkoma podstawowymi pojęciami, które są uniwersalne dla wszystkich języków programowania. Jednym z takich pojęć jest właśnie struktura danych. Nie ważne czy będziesz programował w pythonie, c, c++, java script, swift czy objective c zawsze spotkasz się z tym pojęciem. Zastosowanie odpowiedniej struktury danych może przyśpieszyć działanie aplikacji (oczywiście zły wybór takowej może ją spowolnić). Każdy język programowania dostarcza kilka podstawowych struktur danych, dodatkowe mogą zostać dostarczone przez zewnętrzne biblioteki.

Więc czym właściwie są te struktury danych? Najprościej mówiąc, jest to sposób, w jaki przechowywane są dane w pamięci komputera. Każdy z tych sposobów ma swoje plusy i minusy, niestety nie można mieć wszystkiego :).

Jak można sobie wyobrazić takie różne struktury danych? Wyobraź sobie 50 książek oraz cztery osoby z różnym podejściem do kolejności ich czytania.

  • Tomek trzyma książki na kupce w kącie pokoju. Każdą nową pozycję po prostu kładzie “gdzieś” losowo na tej właśnie kupce. Kiedy chce przeczytać kolejną książkę, po prostu bierze pierwszą lepszą z brzegu i czyta.
  • Marian, z drugiej story, woli czytać książki takiej kolejności, w jakiej je kupił. Więc trzyma je ułożone równo na półce. Nowe pozycje dokłada zawsze na końcu, a kiedy chce przeczytać kolejną książkę, bierze po prostu tą “najstarszą”. Dodatkowo Marian może szybko sprawdzić jaką książkę przeczyta następną, patrząc na koniec swojej kolejki ;).
  • Ania, podobnie jak Marian trzyma książki równo ułożone na półce, z tym że gdy chce przeczytać kolejną, zgaduje sobie jakąś liczbę od 1 do 50. Potem odlicza ją od prawej strony i wyciąga książkę z tej pozycji.
  • Gosia z kolei czyta książki bazując na rekomendacjach znajomych. Pyta ich o kolejny tytuł do przeczytania, a potem na podstawie tego tytułu odnajduje daną książkę na półce i ją czyta.

Każde z powyższych podejść można zaimplementować z wykorzystaniem prostej tablicy. Niestety przy każdym z nich będziemy musieli się “namęczyć” (tj. napisać dużo wlanego kodu), żeby osiągnąć dany efekt.

Pierwszy problem, jaki napotkamy przy każdej implementacji to to, że tablica ma określny rozmiar, którego w Java nie można zmienić “w locie”. Trzeba najpierw zdeklarować nową tablicę o większym lub mniejszym rozmiarze, a potem przepisać wszystkie elementy (plus lub minus jeden) do nowej tablicy.

  • W przypadku Tomka dodatkowo będziemy musieli losować liczbę po to, żeby wiedzieć, w które miejsce włożyć nową książkę oraz żeby “wiedzieć” jaką książkę przeczytać następną.
  • Jeżeli chodzi o Mariana, to zawsze będziemy przepisywać naszą tablicę książek. Przy każdym dołożeniu nowej książki będziemy musieli zwiększyć jej rozmiar o jeden i dodać na końcu nową pozycję. Natomiast w przypadku wzięcia nowej lektury do czytania, będziemy brać tą z pozycji 0, a potem usuwać ją z tablicy… czyli znowu musimy przepisać całość, tym razem bez pierwszego elementu.
  • Podobnie jest w przypadku Ani, z tym że nie wiemy którą pozycję weźmie ona jako następną, więc nasza operacja przepisania będzie jeszcze bardziej skomplikowana.
  • Natomiast w przypadku Gosi, najlepiej będzie nam mieć drugą tablicę, w której będziemy trzymać tytuły książek w takiej samej kolejności, w jakiej są one w tablicy, która przechowuje “całe” książki… oczywiście w tym przypadku musimy “opiekować” się obiema tablicami oraz pilnować, żeby nie rozjechała się nam kolejność.

Tak jak pisałem wcześniej, wszystko da się zrobić, tylko po co się męczyć… jeżeli wiemy, co chcemy osiągnąć oraz znamy właściwości kilku struktur danych, powyższe problemy rozwiążemy, stosując odpowiedni typ zmiennej w Java (czyli wybierając odpowiedni typ danych). Stosując odpowiednią strukturę danych, nie musimy pisać sami kodu związanego z dodawaniem, usuwaniem oraz pobieraniem elementów. Dodatkowo nie musimy się też martwić o rozmiar danej struktury. Wszystkie te rzeczy zrobione są za nas przez innych programistów. Dodatkowo są one przetestowane oraz zaimplementowane w najbardziej wydajny sposób.

Korzystając ze struktur danych dostępnych w Java, biblioteczki naszych poszczególnych bohaterów można zaimplementować używając:

  • java.util.HashSet – korzystamy tutaj ze struktury danych znanej jako set, która to jest takim workiem, do którego można bardzo szybko coś włożyć, oraz szybko wyciągnąć losowy element. Jeżeli nie obchodzi nas kolejność elementów oraz nigdy nie będziemy chcieli pobrać konkretnego elementu jest to idealna struktura danych.
  • java.util.Stack – czyli stos. Jego podstawowymi właściwościami jest to, że dodawane elementy zawsze lądują na końcu oraz to, umożliwia on łatwy (szybki) dostęp do najstarszego elementu (tego, który został umieszczony tam jako pierwszy) oraz można podejrzeć (bez pobierania/ściągania ze stosu) element, jaki jest na samej górze (tj. najstarszy włożony).
  • java.util.ArrayList – struktura danych, z jakiej korzystamy tutaj to lista. Umożliwia ona szybki dostęp do dowolnego elementu po jego liczbie porządkowej. Porządek w liście trzymany jest według kolejności wkładania elementów tj. kolejne elementy dodawane są na końcu listy.
  • java.util.HashMap – czyli mapa… umożliwia ona mapowanie (łączenie) dowolnego elementu w formie klucz-wartość. W przypadku Gosi kluczem będzie tytuł książki (typ String), a wartością obiekt samej książki.

Reasumując, czym są struktury danych? Jest to sposób, w jaki dane przechowywane są w pamięci komputera, oraz algorytmy umożliwiające wykonywanie operacji takich jak dodawanie, usuwanie oraz pobieranie elementów w najbardziej wydajny sposób. Zastosowanie odpowiedniej struktury danych może przyśpieszyć działanie aplikacji oraz zmniejszy ilość kodu, jaki musimy napisać w celu osiągnięcia działania aplikacji. Biblioteka standardowa Java zawiera wiele różnych struktur danych, jako dobry programista powinieneś znać je wszystkie plus dodatkowo kilka dostarczanych przez zewnętrzne biblioteki jak na przykład Google Guava.

Wyjątki w Java – wstęp

W programowaniu, jak w życiu codziennym zdarzają się sytuacje wyjątkowe, ot chociażby takie jak brak wody pod prysznicem kiedy to właśnie zacząłeś myć twarz… lub brak miejsca na dysku gdy program właśnie chciał na nim zapisać wynik kilkugodzinnych obliczeń.

Z jednej strony jako programiści jesteśmy niepoprawnymi optymistami, zakładamy że nigdy się nam nie skończy miejsce na dysku, że nie zabraknie nam pamięci RAM oraz, że zawsze będziemy mieli dostęp do internetu.

Z drugiej jednak strony sytuacje wyjątkowe zdarzają się… i to zdarzają się zawsze! Więc musimy być na nie przygotowani.

Jeżeli przed każdym zapisem danych na dysk mielibyśmy sprawdzać czy jest na nim odpowiednia ilość wolnego miejsca lub przed każdą alokacją zmiennej mielibyśmy sprawdzać czy jest na nią wystarczająca ilość pamięci. Kod stał by się bardzo nie czytelny, więcej było w nim “zapytań” o aktualny stan “świata zewnętrznego” niż właściwego kodu. Co więcej zamiast rozwiązywać nasze zadanie, zajmowalibyśmy się ciągłym sprawdzaniem czy możemy daną operację wykonać. Dodatkowo, ułamek sekundy po sprawdzeniu danego stanu (czy to wolnego miejsca na dysku czy wolnej pamięci) może okazać się, że nie jest on już aktualny gdyż inny program zajął “nasze” miejsce w pamięci bądź na dysku.

W Java sytuacje które zazwyczaj się nie zdarzają, bądź ich możliwość wystąpienia jest niewielka, są reprezentowane za pomocą wyjątków (ang. exception). Przykładami takich sytuacji są:

  • brak wolnej pamięci.
  • brak wolnego miejsca na dysku,
  • zły format danych,
  • brak referencji do obiektu,
  • a nawet brak połączenia z internetem.

Zacznijmy od teorii związanej z wyjątkami w Java.

“Operacje” na wyjątkach

W Java wyjątki się:

  • deklaruje możliwość wystąpienia (ang. throws) – konstruktory oraz metody w Java mogą “powiedzieć” (zdeklarować), że mogą rzucić dany typ wyjątku, osoba używająca takiej metody lub konstruktora jest zmuszona do obsługi tego wyjątku,
  • rzuca (ang. throw) – kiedy zachodzi sytuacja wyjątkowa, po prostu “rzucamy wyjątkiem w ciemno”, w ten sposób przenosimy odpowiedzialność za zachowanie się aplikacji w sytuacji wyjątkowej na osobę która będzie korzystała z naszego kodu,
  • łapie (ang. catch) – “żadna” sytuacja wyjątkowa w Java nie może zostać pominięta, jesteśmy wręcz zmuszeni to “łapania” zdeklarowanych wyjątków oraz ich obsłużenia.

Jeżeli metoda lub konstruktor deklaruje wyjątek jesteś jako programista zmuszony go obsłużyć, inaczej kompilator nie zaakceptuje twojego kodu (czyt. będziesz miał błędy kompilacji). Zanim przejdziemy do tego jak się deklaruje oraz obsługuje wyjątki w Java warto poznać ich strukturę oraz typy.

Struktura wyjątków w Java

Klasą bazową dla wszystkich rodzajów “sytuacji wyjątkowych” w Java jest klasa Throwable (“rzutliwy”, nie wiem jak to lepiej przetłumaczyć). Klasa ta nigdy nie powinna znaleść się w Twoim kodzie, nie powinieneś z niej dziedziczyć,  jej”rzucać” ani “łapać”. Z racji tego, że Java jest językiem obiektowym jest potrzebna jedna klasa z której różne rodzaje sytuacji wyjątkowych będą dziedziczyć.

Z klasy Throwable dziedziczą dwie inne klasy:

  • Error – “amba fatima”, wyjątki tego typu oznaczają nieodwracalny błąd, zazwyczaj związany z błędem maszyny wirtualnej (JVM) lub systemu operacyjnego. Dwoma najczęściej spotykanymi błędami są OutOfMemoryError oraz StackOverflowError,
  • Exception – błąd z którego (teoretycznie) da się wyjść. Zazwyczaj są to błędy programistyczne (NullPointerException), wejścia/wyjścia (IOException) oraz inne (w tym RuntimeExcpetion).

Tak samo jak w przypadku klasy Throwable, z klasy Error również nie dziedziczymy. Można za to łapać zarówno sam Error jak i klasy z niej dziedziczące w celu poprawnej obsługi zdarzeń krytycznych JVM. W tym wypadku będzie to “ratowanie się” w sytuacji kiedy to niebo wali nam się na głowę. Takie ratownie może polegać na zamknięciu otwartych połączeń sieciowych (np. baz danych) czy też zapisaniu (częściowych) wyników obliczeń itp.

To co nas jako programistów najbardziej interesuje to wszystkie klasy dziedziczące z Exception. Dlaczego? Gdyż głównie z takimi wyjątkami będziemy mieli doczynienia. Właśnie tego typu wyjątki są rzucane przez konstruktory i metody. Z klasy Exception (oraz klas pochodnych) możemy śmiało dziedziczyć żeby tworzyć swoje własne typy wyjątków.

Tyle kwestią w stępu teoretycznego do wyjątków w Java. W następnym wpise omówimy instrukcję throws, throw, try, catch i finally; czyli deklaracje, rzucenie wyjątkiem oraz jego złapanie.