Struktury danych – podstawy algorytmów

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 są struktury danych?

Strukturę danych można postrzegać jako swego rodzaju pojemnik na dane, który gromadzi informacje i układa je w odpowiedni sposób.

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.

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ć.

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ą). Dlatego powinniśmy najpierw odpowiednio ustandaryzować informacje i dopiero wtedy przekazać je w postaci zrozumiałych algorytmów.

Rekord – statyczna struktura danych

Rekord jest jedną z prostszych struktur danych, świetnie nadaje się do prezentowania informacji o jednym obiekcie. Ponieważ w trakcie działania algorytmu nie zmienia on swego rozmiaru ani struktury, mówimy, że jest to statyczna struktura danych.

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

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

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.

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.

Indeks 0 1 2 3 4
Wartość v1 v2 v3 v4 v5

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.

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

Struktury danych lista

Istnieją dwie popularne realizacje struktury listy: tablicowa oraz wskaźnikowa. W Javie obie implementują interfejs List, zatem w wielu przypadkach mogą być one używane zamiennie, natomiast na ostateczny wybór wdrożeń wpływ będą miały poszczególne parametry dostosowane do konkretnego projektu i naszych potrzeb.

1. 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.

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.

2. 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. W związku z tym 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.

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.

1. 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.

2. 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ół.

3. 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 – TAIL).

Stos (Stack) – LIFO

Stos nazywany jest również kolejką LIFO, czyli ‘ostatni na wejściu, pierwszy na wyjściu’ (z ang. Last In, First Out). Bardzo dobrze nadaje się do sytuacji, gdy chcemy przeprowadzać operacje najpierw na najnowszych danych, a dopiero później – na starszych.

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.

Kolejka (Queue) – FIFO

Przeciwieństwem stosu LIFO jest kolejka typu FIFO (ang. First In, First Out), czyli ‘pierwszy na wejściu, pierwszy na wejś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.

Szczególną odmianą tej struktury danych jest kolejka priorytetowa. W tej implementacji konkretne rekordy dodatkowo posiadają przypisany priorytet, który wpływa na kolejność późniejszego pobierania elementów z listy. Najpierw przetwarzane są najpilniejsze elementy (o najwyższym priorytecie), a dopiero potem te mniej ważne.

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.

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.

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ć.

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

Linki

Programista – Pytania rekrutacyjne

Lista pytań rekrutacyjnych, które pozwolą przygotować Ci się na rozmowę kwalifikacyjną.

2 komentarze
Share:

2 Comments

Dodaj komentarz

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