Abstrakcyjne struktury danych: Lista
Pewnie początkujący programiści po przeczytaniu tytułu tego wpisu zaczęli się zastanawiać o co właściwie chodzi, więc spieszę z wyjaśnieniem. Dane w programach komputerowych, możemy przechowywać w zwykłych zmiennych lub na przykład za pomocą stosu, który w pewnych przypadkach jest bardzo pomocny. Na tym jednak nie kończą się możliwości programowania zorientowanego obiektowo, które daje znacznie więcej pola do popisu programistą. W tym artykule zapoznamy się z listami jako strukturami do przechowywania pewnych informacji.
Spis treści:
- Lista wiązana jednokierunkowa,
- Lista wiązana dwukierunkowa,
- Lista cykliczna wiązana dwukierunkowa,
- Implementacja listy wbudowanej w Java.
Lista jako struktura danych ideowo nie różni się właściwie niczym od na przykład listy produktów z którą chodzimy na zakupy. W programowaniu wyróżniamy jednak kilka jej typów. Mamy więc listy jednokierunkowe, listy dwukierunkowe, listy cykliczne, listy z głową itd. Na pierwszy rzut oka, może się wydawać to trochę skomplikowane (co to za głowa?) ale w rzeczywistości implementacja tej struktury danych przynosi naprawdę wiele korzyści, a czasem okazuje się jedyną drogą do rozwiązania danego problemu programistycznego. Wyobraźmy sobie sytuację, że piszemy aplikację obsługującą klientów banku. Każda osoba chce wykonać przelew, a my możemy zrobić tylko jeden na raz. Jak więc zapisać dane o wszystkich osobach czekających w kolejce? Teoretycznie możemy użyć po prostu tablicy ale niestety nie wiemy ile osób będzie chciało przelać swoje oszczędności. Oczywiście możemy założyć, że będzie ich milion, dwa miliony, albo trzydzieści osiem – co jeśli jednak pomyliliśmy się i brakło dla kogoś miejsca? Ten właśnie problem rozwiązuje lista, którą możemy wydłużać i wydłużać dopóki wystarczy nam pamięci na dysku twardym. Ale na to jako programiści nie mamy już niestety wpływu.
Zalety i wady używania list:
| ZALETY | WADY |
|
|
Skoro zapoznaliśmy się już z teorią to pora napisać swoją własną listę. Zacznijmy oczywiście od szkieletu programu:
public class Main {
public static void main(String[] args) {
}
}Powyższego kodu, chyba nie trzeba nikomu tłumaczyć, można go wygenerować w dobrym IDE do Java.
W pierwszych kilku fragmentach kodu w klasie Value masz next typu List zamiast Value, poza tym takie coś jak:
List()
{
first = null;
}
jest nadmiarowe w Javie gdyż domyślnie zmienne składowe klasy będące obiektami inicjalizowane są nullami.
Faktycznie wkradł mi się drobny błąd, dzięki za info ;) Natomiast co do inicjalizacji to faktycznie w Java pola tego typu będą domyślnie wypełniane nullami więc nie ma potrzeby ich inicjalizacji w konstruktorze jednak w innych technologiach oraz przy innym typie zmiennych (np. int gdzie do zmiennej domyślnie zapisywane jest 0) będzie inaczej, a dobrą praktyką jest zawsze inicjalizowanie zmiennych ;)
Napisz poprawnie wyraz „dopóki” w ostatniej linijce drugiego akapitu, bo aż kłuje w oczy.
Dzięki za informację, poprawione ;)
Witam ;)
W 3 kodzie na stronie jest „mały błąd” – w konstruktorze jako jeden z argumentów bierzemy Next typu List, a przypisujemy go do next typu Value.
Świetna strona, pozdrawiam :)
Dzięki za czujność ;) Poprawione…
Witam,
czy mógłby mi ktoś wytłumaczyć dlaczego element 11 znajduje się na końcu listy?
A dokładniej, o co chodzi?
Nie bardzo rozumiem dlaczego element 11 znajduje się na końcu listy skoro metoda z 13 wywoływana jest później.
O który przykład chodzi?
2 strona (lista jednokierunkowa wiązana), na samym dole w metodzie main (wiersz 80-81)
W momencie dodawania elementu 11 do listy znajduje się on na jej końcu ;)