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

Przeczytaj również

, , , , , , ,