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 programistom. W tym artykule zapoznamy się z listami jako strukturami do przechowywania pewnych informacji.

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:

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.

Strony: 1 2 3 4 5

Abstrakcyjne struktury danych, Java, Lista cykliczna, Lista dwukierunkowa, Lista jednokierunkowa