Category Archive Kolekcje

Implementacja listy jednokierunkowej w Javie

Implementacja listy jednokierunkowej w Javie

Nasza lista jest zbudowana z dwóch klas.

  • Wezel – klasa wewnętrzna – reprezentuje pojedynczy węzeł na liście.
  • Lista – klasa zewnętrzna – zawiera algorytmy dodawania, usuwania oraz wyświetlania elementów oraz przechowuje pierwszy element listy.

Aby pokazać różnice pomiędzy listami dwukierunkowymi a jednokierunkowymi postanowiliśmy opracować własną implementację. Ponownie naszym celem jest pokazanie działania tej struktury danych, a nie możliwości interfejsów, takich jak Comparable lub Iterable. Aby maksymalnie uprościć kod przechowywanym typem danych będzie int.

Naszym celem było napisanie jak najprostszego algorytmu, aby pokazać jak operować na listach jednokierunkowych. Tak, aby w praktyczny sposób przekazać wiedzę z naszego teoretycznego wstępu odnośnie list jednokierunkowych. Na pierwszy rzut oka implementacja jest bardzo podobna do listy dwukierunkowej, jednakże w przypadku usuwania węzła jesteśmy zmuszeni utworzyć tymczasową zmienną, która będzie go przechowywać. W przeciwnym wypadku stracimy możliwość np. zmiany referencji w poprzednim ogniwie listy, gdyż aktualnie usuwany element „nie zna” położenie swojego poprzednika.

Aby uruchomić poniższy kod należy skopiować kod, a następnie skompilować.

Wewnętrzna klasa Wezel

Powyższy program można podzielić na dwie części. Pierwszą jest obiekt, który przechowuje dane i jest nią klasa Wezel. Ze względu na to, że ta struktura danych jest mało elastyczna umieściliśmy ją wewnątrz klasy Lista, gdyż i tak nie wykorzystamy jej nigdzie indziej. Takie podejście jest wygodnie, ponieważ mamy ułatwiony dostęp do pól obu klas.

Pola

Obiekt klasy Wezel zawiera jedną referencję do kolejnego obiektu oraz zmienną przechowującą dane. Jeśli dany węzeł jest ostatni (ogon), to jego referencją na następny obiekt jest wartość null.

Konstruktor

Inicjuje dane – referencję do następnego obiektu na null, a pole z danymi uzupełnia wartością przekazaną w argumencie.

Zewnętrzna klasa Lista

Obiekt klasy Lista przechowuje referencję do pierwszego elementu listy, czyli głowę (ang. head). Zawiera również niezbędne algorytmy, takie jak:

  • dodawanie elementów do listy,
  • usuwanie elementów z listy,
  • szukanie elementu o konkretnym indeksie,
  • wypisanie wszystkich elementów listy.

W metodzie main znajduje się przykładowy przebieg programu. Wykonanie metody main spowoduje wyświetlenie następujących komunikatów w konsoli.

Zachęcamy do eksperymentów z kodem.

Metody

Podstawową różnicą między implementacją listy dwukierunkowej jest algorytm usuwania elementu. Żaden węzeł nie zna położenia swojego poprzednika zatem przy przechodzeniu listy musimy utworzyć zmienną pomocniczą, którą będzie przechowywała jego referencję.

Czemu jednak nie postąpić jak w  przypadku list dwukierunkowych i do zmiennej pomocniczej nie użyć po prostu argumentu n-1? Przecież byłoby to dużo wygodniejsze i kod zajmowałby mniej linii. Powodem jest wydajność. Zwróćmy uwagę, że metoda getWezel() byłaby wywołana dwa razy – raz z argumentem n, a za drugim razem n-1. Jednakże dwukrotnie przejście przez listę zaczynałoby się od głowy listy. Oznacza to podwojenie liczby wykonywanych operacji. W przypadku małej kolekcji oczywiście nie ma to znaczenia, ale kolekcja może składać się z bardzo wielu elementów.

Wyjątek IndexOutOfBoundException

Jeżeli spróbujemy wpisać do metody szukającej indeks ujemny lub spoza naszej listy zostanie wyrzucony wyjątek.

System zbierania nieużytków (ang. Garbage collector)

W Javie nie ma potrzeby ręcznego czyszczenia pamięci. Jeśli nie mamy już referencji do obiektu, to nie musimy z tym nic robić. System zbierania nieużytków oczyści pamięć ze zbędnych obiektów.

Kolekcje Javy – Interfejs Map

Przechodzimy do ostatniego typu kolekcji, który będzie omawiać czyli interfejs Map. Mapy to obiekty, które przechowują dane w postaci dwójki klucz-wartość. To najważniejsza zmiana w stosunku do poprzednio przedstawionych kolekcji. Klucz jest swego rodzaju identyfikatorem i to na jego podstawie zwracana jest wartość. Artykuł jest częścią wpisów o kolekcjach w Javie.

Read More

Kolekcje Javy – Interfejs Set

Kolekcje implementujące interfejs Set posiadają cechę wyróżniającą ją od innych poznanych wcześniej kolekcji – elementy nie mogą się powtarzać. Dodatkowo użytkownik nie ma wpływu na pozycję przy dodawaniu elementów, jednak konkretna implementacja może porządkować zbiory. Dozwolona jest wartość null, jednakże tylko raz.

W stosunku do sekwencyjnego przeszukiwania listy wykorzystanie interfejsu Set może okazać się bardziej wydajne. Artykuł jest częścią wpisów o kolekcjach w Javie.

Read More

Implementacja drzewa BST w Javie

Przykładowa implementacja drzewa poszukiwań binarnych (BST) w Javie

Nasza implementacja drzewa BST składa się z dwóch klas.

  • Wezel – jest klasą wewnętrzną. Reprezentuje pojedynczy węzeł w drzewie. Przechowywanym kluczem jest wartość int.
  • Drzewo – zawiera algorytmy dodawania, usuwania, wyświetlania elementów, odnajdywania poprzednika i następnika węzła oraz przechowuje korzeń. Jest klasą zewnętrzną.

Drzewa BST są ważną strukturą danych. Pozwalają o wiele skrócić czas wyszukiwania elementów, co jest szczególnie zauważalne przy dużych zbiorach. Oczywiście zakładając, że drzewo jest zrównoważone – w przeciwnym wypadku liczba operacji może wzrosnąć do poziomu zwykłej listy. Dużo lepszą wydajność zapewnią drzewa AVL lub drzewa czerwono-czarne. Te struktury poprzez rotacje potrafią zapewnić zrównoważenie poziomu obu poddrzew korzenia. Aby jednak je poznać warto najpierw poznać dokładnie drzewa BST, gdyż ta wiedza jest niezbędna, aby potem stosować dodatkowe zasady umieszczania węzłów.

Teoretyczna część znajduje się w naszym artykule odnośnie drzew BST. Tutaj skupimy się na praktycznej implementacji podanych tam algorytmów.

Klasa Drzewo

Wewnętrzna klasa Wezel

Klasa Wezel przechowuje informację o dwóch potomkach, o rodzicu oraz klucz. Ze względu na to, że ta struktura danych jest mało elastyczna umieściliśmy ją wewnątrz klasy Drzewo, gdyż i tak nie wykorzystamy jej nigdzie indziej.

Pola

Obiekt klasy Wezel zawiera trzy referencje:

  • do lewego potomka,
  • do prawego potomka,
  • oraz do rodzica.

Dodatkowym polem jest przechowywana wartość czyli zmienna key.

Konstruktor

Inicjuje dane – referencje do innych węzłów na null, a pole z danymi uzupełnia wartością przekazaną w argumencie.

Zewnętrzna klasa Drzewo

Obiekt klasy Drzewo przechowuje referencję do korzenia (ang. root). Zawiera również niezbędne algorytmy, takie jak:

  • dodawanie elementów do drzewa,
  • usuwanie elementów z drzewa,
  • szukanie elementu o konkretnej wartości,
  • znalezienie największej wartości w drzewie,
  • znalezienie najmniejszej wartości w drzewie,
  • wskazanie następnika węzła,
  • wskazanie poprzednika węzła.

Wykonanie metody main() spowoduje wyświetlenie następujących komunikatów w konsoli.

System zbierania nieużytków (ang. Garbage collector)

W Javie nie ma potrzeby ręcznego czyszczenia pamięci. Wystarczy odłączyć usuwany obiekt od struktury drzewa.

Drzewa poszukiwań binarnych BST

Drzewo – definicja

Pojęcie drzewa wywodzi się z teorii grafów. Jest to graf nieskierowany, acykliczny i spójny. Oznacza to, że do każdego wierzchołka prowadzi krawędź, a graf nie posiada cykli (każde dwa wierzchołki łączy tylko jedna droga prosta). Wpis jest częścią artykułów o kolekcjach w Javie.

Read More

Kolekcje Javy – Interfejs Queue

W artykule o kolejkach przedstawiliśmy podstawowe operacje oraz budowę kolejek. Podobnie jak w przypadku list nie trzeba implementować algorytmów na własną rękę i można skorzystać z biblioteki udostępnionej przez Javę. Istnieje wiele implementacji interfejsów Queue oraz Deque.

Read More

Implementacja listy wiązanej dwukierunkowej

Struktura listy dwukierunkowej

Nasza lista jest zbudowana z dwóch klas.

  • Wezel – klasa wewnętrzna – reprezentuje pojedynczy węzeł na liście.
  • Lista – klasa zewnętrzna – zawiera algorytmy dodawania, usuwania oraz wyświetlania elementów oraz przechowuje pierwszy element listy.

Lista ta powstała w celu dydaktycznym, aby pokazać jak wygląda własne opracowanie algorytmu. W związku z tym nie implementujemy żadnych interfejsów, takich jak Comparable, który mógłby posłużyć do sortowania elementów. Z tego samego powodu nie jest to również klasa generyczna, dlatego nie można w tej kolekcji przechowywać żadnych typów własnych, ani innych typów prostych niż int.

Naszym celem było napisanie jak najprostszego algorytmu, aby skupić się na działaniu tej konkretnej struktury danych. Tak, aby w praktyczny sposób przekazać wiedzę z naszego teoretycznego wstępu odnośnie list dwukierunkowych.

Typem danych do przechowywania jest int. Aby uruchomić poniższy kod należy skopiować kod, a następnie skompilować.

Wewnętrzna klasa Wezel

Powyższy program można podzielić na dwie części. Pierwszą jest obiekt, który przechowuje dane i jest nią klasa Wezel. Ze względu na to, że ta struktura danych jest mało elastyczna umieściliśmy ją wewnątrz klasy Lista, gdyż i tak nie wykorzystamy jej nigdzie indziej. Takie podejście jest wygodnie, ponieważ mamy ułatwiony dostęp do pól obu klas.

Pola

Obiekt klasy Wezel zawiera dwie referencje do innych obiektów oraz zmienną przechowującą dane.

Konstruktor

Inicjuje dane – pola obiektowe czyli referencje do poprzednie i następnego obiektu ustawia na null, a pole z danymi uzupełnia wartością przekazaną w argumencie.

Zewnętrzna klasa Lista

Obiekt klasy Lista przechowuje referencję do pierwszego elementu listy, czyli głowę (ang. head). Zawiera również niezbędne algorytmy, takie jak:

  • dodawanie elementów do listy,
  • usuwanie elementów z listy,
  • szukanie elementu o konkretnym indeksie,
  • wypisanie wszystkich elementów listy.

W metodzie main() znajduje się przykładowy przebieg programu. Dane zostały dobrane w taki sposób, aby nie spowodować wyjątku. Wykonanie metody main() spowoduje wyświetlenie następujących komunikatów w konsoli.

Zachęcamy do eksperymentów z kodem.

Metody

Wielokrotne wykorzystanie kodu pozytywnie wpływa na jego objętość. Lista dwukierunkowa pozwala na ponowne wykorzystanie metody getWezel() w celu znalezienia usuwanego węzła zamiast pisać ponownie kod, który robi tę samą czynność.

Wyjątek IndexOutOfBoundException

Jeżeli spróbujemy wpisać do metody szukającej indeks ujemny lub spoza naszej listy zostanie wyrzucony wyjątek.

System zbierania nieużytków (ang. Garbage collector)

Być może programiści innych języków zwrócili uwagę na to, że po usunięciu elementów nie czyścimy ręcznie pamięci. W językach z rodziny C oprócz zmiany wskaźników na odpowiednie elementy należy użyć funkcji free(), która czyści pamięć – w przeciwnym wypadku po wyjściu z funkcji usuwania elementu stracimy wskaźnik na usuwany element i nigdy już go nie będziemy w stanie usunąć – do restartu maszyny.

W Javie jeśli nie mamy dostępu do obiektu, to nie musimy z tym nic robić. System zbierania nieużytków zrobi wszystko za nas i oczyści pamięć ze zbędnych obiektów.

Polecamy również zapoznać się z implementacją listy jednokierunkowej. Pozornie obie wydają się podobne, jednakże różnią się znacznie przy samej budowie.

Kolejki FIFO, LIFO i priorytetowe

Kolejki są kolejnym abstrakcyjnym typem danych, który należy poznać. Ich główną cechą jest dostęp do danych możliwy jedynie z jej początku lub końca – nigdy ze środka. Ich zastosowanie w informatyce jest szerokie – od użycia w algorytmach, po wykorzystanie w pracy systemu np. czas procesora dla poszczególnych procesów, albo kolejka do wydruku na jednej drukarce, gdy obsługuje ona całe piętro. Głównym ich zadaniem jest porządkowanie zbioru w określonej wcześniej kolejności (np. kolejne punkty zadania, które nie mogą być wykonane współbieżnie). Artykuł jest częścią wpisów o kolekcjach w Javie.

Read More

Kolekcje Javy – Interfejs List – LinkedList

W jednym z naszych wpisów poznaliśmy bliskiego krewnego tablic, a mianowicie klasę ArrayList. Jej budowę, sposób działania oraz metody, które pozwalają na praktyczne korzystanie z niej. Implementacja klasy ArrayList daje świetne efekty jeśli chodzi o wyszukiwanie elementów(wszystkie są obok siebie) oraz zamortyzowany koszt dodawania elementów (pojemność kolekcji jest nieco większa niż liczba elementów). Jednak problemem jest dodawanie wielu elementów oraz usuwanie ze środka listy. Wpis jest częścią artykułów o kolekcjach w Javie.

Read More

Kolekcje Javy – Interfejs List – ArrayList

W tym artykule przyjrzymy się gotowym kolekcjom opartych na interfejsie List. Obie omawiane klasy implementują go oraz interfejs Iterable w związku z tym ich obsługa z puntu widzenia programisty będzie bardzo podobna. Różnice polegają głównie na sposobie reprezentacji danych w pamięci i algorytmów obsługi takich jak dodawanie elementów, odczyt czy też usuwanie. Wpis jest częścią artykułów o kolekcjach w Javie.

Read More