Struktury danych/Listy

Spis treści
Wstęp	Wstęp - Konwencje
Struktury danych	Podstawy - Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Kopce - Find-Union - Tablice z haszowaniem - Grafy
Dodatki	Złożoność obliczeniowa - Implementacje w C++ - Implementacje w Pascalu - Bibliografia - Dla twórców podręcznika

Listy

Poznane w poprzednim rozdziale tablice doskonale nadają się do przechowywania nieznacznie zmieniających się danych. Jednak weźmy na warsztat program do odtwarzania muzyki. Zazwyczaj wyposażony jest on w playlistę będącą zbiorem naszych ulubionych utworów, które chcemy odsłuchiwać. Playlista może mieć dowolną długość: można na niej trzymać zarówno 20, jak i 2000 piosenek, w dodatku w każdej chwili mamy możliwość dodania dowolnej ilości nowych. Ciężko sobie wyobrazić, by program przydzielał przy uruchomieniu kilka megabajtów "na wszelki wypadek", aby zabezpieczyć się przed sytuacją braku miejsca. Jednym ze sposobów rozwiązania tego problemu jest wykorzystanie nowej struktury danych - list. Ich zasadniczą cechą jest to, że zawsze zajmują w pamięci dokładnie tyle miejsca, ile potrzeba i zawsze można bezproblemowo dodać do nich nowe elementy.

Budowa listy

Każdy rekord w liście, oprócz przechowywanych przez siebie danych, zawiera również przynajmniej jedno dodatkowe pole zawierające adres/położenie następnego w kolejności rekordu. Powstaje w ten sposób łańcuch, w którym rekordy znają jedynie swoje następniki. Ilustruje to poniższy schemat:

Oprócz tego musimy wydzielić też specjalny rekord zawierający tzw. korzeń listy, czyli odnośnik do pierwszego elementu. Ostatni rekord na liście posiada pusty wskaźnik, dzięki czemu możliwe jest powiadomienie o końcu łańcucha. Zauważmy, że w takiej strukturze bezpośredni dostęp do dowolnego elementu jest niemożliwy. Odszukanie interesującego nas rekordu zajmuje rosnącą liniowo ilość czasu. Najpierw musimy ustawić się na początku listy, a następnie przechodzić do kolejnych elementów, dopóki nie natrafimy na nasz właściwy.

Pokazana powyżej lista jest w zasadzie tylko jedną z jej odmian, zwaną listą jednokierunkową, ponieważ możemy po niej poruszać się tylko w jednym kierunku: do przodu. Inne rodzaje list to:

Listy dwukierunkowe - każdy rekord zawiera dodatkowo drugi wskaźnik pokazujący poprzedni element listy.
Listy cykliczne - pierwszy i ostatni rekord listy są ze sobą połączone, tworząc zamknięty cykl.

Lista

CREATE(l: List) - tworzy nową listę
INSERT(l: List; d: Data) - dodaje na końcu listy l rekord d. Zauważmy, że w przedstawionej powyżej naiwnej implementacji listy operacja ta wymaga czasu liniowego, ponieważ tyle zajmuje dotarcie na jej koniec. Istnieje jednak możliwość zaimplementowania tej operacji działającej w stałym czasie. Wystarczy, aby nagłówek listy przechowywał także adres ostatniego z rekordów.
DELETE(l: List; n: Integer) - usuwa n-ty w kolejności rekord z listy. Usunięcie pierwszego i ostatniego rekordu można wykonać w czasie stałym. Dla pozostałych będzie to czas liniowy.
FIND(l: List; n: Integer) - pobiera n-ty w kolejności rekord z listy.
RESET(l: List, n: Integer) - ustawia kursor na podanym rekordzie listy.
NEXT(l: List) - zwraca rekord, na którym aktualnie ustawiony jest kursor, po czym przesuwa się na kolejny element listy.
PREV(l: List) - analogiczna operacja do NEXT() dla list dwukierunkowych umożliwiająca przesuwanie się w tył.
MAKENULL(l: List) - czyści listę, usuwając wszystkie rekordy.

W operacjach wyszukiwania elementów na liście przyjmujemy, że 1 identyfikuje pierwszy rekord na liście, 2 drugi (itd.), n-1 przedostatni, n ostatni.

Operacje RESET(), NEXT() oraz PREV() umożliwiają samodzielne poruszanie się po liście. Na początek musimy ustawić się tam, gdzie potrzebujemy, a następnie dwoma pozostałymi operacjami przesuwamy się w żądanym przez nas kierunku, pobierając po kolei wszystkie napotkane tam rekordy.

Lista jednokierunkowa o n rekordach zajmuje w pamięci n(4 + d) + h bajtów przy założeniu, że d oznacza wielkość danych rekordu, h wielkość nagłówka listy, a wskaźniki są czterobajtowe (długość charakterystyczna dla 32-bitowych aplikacji).

Implementacja

Implementacje w C++

Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Tablice haszujące - Grafy

Pierwszą z omówionych implementacji list będzie implementacja tablicowa. Do przechowywania rekordów wykorzystywane są tu poznane w poprzednim rozdziale tablice. Wskaźniki rekordów są tutaj zwyczajnymi indeksami wskazującymi komórkę, pod którą znajduje się kolejny rekord. Nasuwa się tutaj pytanie, jaki jest sens implementacji listy za pomocą tablic. Wbrew pozorom pomysł ten jest całkiem sensowny. Przypomnij sobie zaproponowane w poprzednim rozdziale sposoby na oznaczanie w tablicach "wolnych" komórek. Listy na tablicach to jedna z metod rozwiązania tego problemu.

Alternatywą dla tablic jest implementacja wskaźnikowa, gdzie wykorzystuje się wskaźniki z prawdziwego zdarzenia oraz dynamiczny przydział pamięci dla nowych rekordów. Posiada ona wszystkie opisane wyżej cechy: zajmuje dokładnie tyle pamięci, ile potrzebujemy, oraz umożliwia przechowywanie dowolnie dużej ilości danych. Aby prawidłowo wybrać metodę implementacji, zastanówmy się, jakie są nasze potrzeby. Listy na tablicach są często wybierane przez uczestników olimpiad informatycznych. Pojawiające się tam zadania dokładnie precyzują rozmiar maksymalnych danych oraz dostępną do wykorzystania pamięć. Nie bez znaczenia jest tu również fakt, że alokacja pamięci dla jednego ogromnego bloku jest znacznie szybsza, niż dla setek małych o identycznym sumarycznym rozmiarze.

Omówienie implementacji wskaźnikowej w C++

Przyjrzyjmy się teraz przykładowej implementacji listy opartej o struktury wskaźnikowe dołączonej do tego podręcznika. Poniżej widać nieco okrojony kod deklaracji naszego kontenera. Pierwszą sprawą, która powinna być zauważalna na pierwszy rzut oka jest fakt wykorzystywania szablonów, które są świetnym mechanizmem służącym do wielokrotnego wykorzystywania kodu. W tym wypadku nasz generyczny typ może być wszystkim, co ma zdefiniowane konwersje do podstawowych typów liczbowych.

template <typename typ>
class lista
{
	struct Node {...};
	Node* head;
	Node* tail;

public:
        lista();
	~lista();
 
	void insert(typ data);
	void remove(int n);
	typ find(int n);
	void makeNull();
	void display();
};

W ciele klasy znajdują się dwa wskaźniki - head na początek listy oraz tail wskazujący na jej koniec. Ten drugi wskaźnik znajduje się tam, aby uprościć operację dodawania. Jest to niewielki naddatek pamięciowy, który bardzo przyspiesza dodawanie elementów do tej kolekcji. W 4 podświetlonej linijce klasy zadeklarowaliśmy pomocniczą strukturę Node zagnieżdżoną wewnątrz klasy bazowej. Przyjrzyjmy się jej od środka.

struct Node
{
    typ wartosc;
    Node* next;
	
    Node(typ d) 
    {
        wartosc = d;
        next = NULL;
    }
};

Node, czyli z angielskiego węzeł ma wewnątrz dwa pola - jedno przechowujące wartość oraz drugie będące wskaźnikiem na kolejną strukturę tego typu. Ponadto umieściliśmy tam również konstruktor przyjmujący jeden argument, w celu prostszego tworzenia nowych obiektów z zainicjalizowaną wartością.

Insert liniowo

W przypadku gdybyśmy nie korzystali ze wskaźnika tail musielibyśmy przejść przez wszystkie elementy znajdujące się na naszej liście, żeby znaleźć jej koniec i dopiero wtedy dodać nowy element. Zastanówmy się jak wtedy wyglądałby kod funkcji odpowiedzialnej za dodawanie.

template <typename typ>
void lista<typ>::insert(typ data)
{

W tym miejscu dodajemy warunek sprawdzający czy jest to pierwszy element, który będziemy dodawać do listy. Instrukcje, gdy ten warunek jest spełniony omówimy po omówieniu kodu dla pierwszego elementu.

if (head != NULL)
{

Gdy jest to pierwszy element, który dodajemy po prostu podpinamy pod head nowo utworzony obiekt klasy Node.

}
else head = new Node(data);
}

Teraz przejdźmy do instrukcji kiedy mamy już jakieś elementy w kolekcji. Tutaj w pętli będziemy przepinać wskaźniki prev oraz temp, który będzie nam służył podobnie jak zmienna pomocnica pętli for.

        Node* temp = head;
        Node* prev = NULL;
while(temp != NULL)	
{	
	prev = temp;
	temp = temp->next;
}

Po ostatnim obrocie tej pętli prev wskazuje na ostatni element w liście, z kolei temp wskazuje na NULL, więc można go bez przeszkód wykorzystać ponownie.

        temp = new Node(data);
        if (temp == NULL) throw "Błąd alokacji pamięci, przy dodawaniu elementu do listy!";

W końcu tworzymy nowy obiekt, który będzie przechowywał nasze dane. Dodatkowo zabezpieczamy się tutaj przed niepoprawnym zaalokowaniem pamięci za pomocą wyjątków.

	prev->next = temp;
}

Nareszcie podpinamy do "wskaźnika na następny" ostatniego obiektu nasz nowo utworzony obiekt.

Za liniową złożoność tej metody odpowiada pętla while z 8 linijki służąca w tym wypadku do tego, żeby wyszukać ostatni element w liście. Jest to operacja dominująca tej funkcji, więc asymptotycznie będzie to funkcja rzędu $O(n)$ .

Insert w implementacji z dodatku

template <typename typ>
void lista<typ>::insert(typ data)
{
	if (head != NULL) // w przypadku gdy mamy jakieś elementy w liście
	{
		Node* temp = new Node(data);
		if (temp == NULL) throw "Błąd alokacji pamięci, przy dodawaniu elementu do listy!";
		tail->next = temp;
		tail = temp;
	}
	else
        {
                head = new Node(data);
                tail = head;
        }
}

Spróbujmy ustalić teraz złożoność tej funkcji. Mamy tutaj dwa przypadki ze względu na instrukcję warunkową. Z każdym wywołaniem będziemy musieli wyewaluować head != NULL, które ma pewną stałą złożoność $O(1)$ . Dalej mamy w przypadku, gdy warunek był prawdziwy utworzenie nowego obiektu, które powinno się zachowywać również w czasie stałym, następnie kolejna instrukcja warunkowa też w czasie stałym. Na koniec dwie operacje przypisania, które również są wykonywane w czasie stałym. Póki co mamy więc więc $(O(1)+O(1)+O(1)+O(1)+O(1))\in O(1)$ . W przypadku, gdy warunek jest nieprawdziwy mamy utworzenie nowego obiektu i operacje przypisania, obie zachowujące się jak $O(1)$ . Z tego wynika, że ta funkcja faktycznie wykonuje się w czasie stałym.

Typy list

Lista dwukierunkowa

W jej wypadku dodany jest dodatkowy wskaźnik pokazujący na wcześniejszy element. Dzięki temu można na przykład bardzo efektywnie zaimplementować operacje SUCCESSOR i PREDECESSOR.

Lista cykliczna

W tym wypadku ostatni wskaźnik w liście wskazuje na jej głowę, a nie na NULL. W praktyce dodaje się wtedy dodatkowy element - wartownika, który jako niezmienny element znacznie upraszcza kod listy cyklicznej.

Ćwiczenia

Ta sekcja jest zalążkiem. Jeśli możesz, rozbuduj ją.

Podstawowe

Ćwiczenie 1: Napisz program wypisujący wszystkie elementy listy.

Ćwiczenie 2: Napisz pełną implementację listy:

Na tablicach
Na wskaźnikach

Ćwiczenie 3: Zastanów się, jak w liście dwukierunkowej o długości n zmniejszyć pesymistyczny czas wyszukiwania rekordu x z czasu n do n/2. Wprowadź stosowne poprawki do implementacji.

Zaawansowane

Ćwiczenie 1: Napisz implementację listy dwukierunkowej cyklicznej na wskaźnikach, gdzie będzie możliwe łączenie list (co ważne nie będziemy "naprawiać" wskaźników, jeżeli będą na odwrót) oraz bezproblemowe wypisywanie takich list. Utrudnienie zastanowów się jak to zrobić bez wykorzystywania dodatkowej pamięci.

« Tablice

Spis treści

Stosy »