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.

binary-139841_1920

Spis treści:

  1. Lista wiązana jednokierunkowa,
  2. Lista wiązana dwukierunkowa,
  3. Lista cykliczna wiązana dwukierunkowa,
  4. 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
  • Łatwa implementacja,
  • Możliwość wykonywania efektywnych operacji na przechowywanych danych,
  • Możliwość przechowywania dowolnej liczby elementów.
  • Nie mamy szybkiego dostępu do poszczególnych elementów za pośrednictwem indeksów, jak w tablicach,
  • Usunięcie danego elementu nie zwalnia zajmowanej pamięci.

Skoro zapoznaliśmy się już z teorią to pora napisać swoją własną listę. Zacznijmy oczywiście od szkieletu programu:

Powyższego kodu, chyba nie trzeba nikomu tłumaczyć, można go wygenerować w dobrym IDE do Java.

Strony: 1 2 3 4 5

, , , , , , ,

  • Kamil Lis

    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 ;)

  • asdf

    Napisz poprawnie wyraz „dopóki” w ostatniej linijce drugiego akapitu, bo aż kłuje w oczy.

    • Dzięki za informację, poprawione ;)

  • q1w2e3

    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…