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.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *