Podręcznik

W poprzednich częściach podręcznika wyjaśniliśmy pojęcie wskaźnika oraz w jaki sposób wykorzystać zmienne dynamiczne do deklaracji tablic dynamicznych, czyli podstawowych struktur danych dynamicznych. Stosowanie dynamicznych tablic umożliwia dostosowanie ich rozmiaru do potrzeb w trakcie działania aplikacji. Możemy deklarować tablice o rozmiarze podanym przez użytkownika. Co zrobić jednak w przypadku, gdy w trakcie działania aplikacji istnieje potrzeba zwiększenia rozmiaru zadeklarowanej już tablicy dynamicznej? W języku C++ tablica dynamiczna, której rozmiar został ustalony podczas alokacji pamięci, nie może być bezpośrednio powiększona. Jednak możliwe jest osiągnięcie efektu zwiększenia jej rozmiaru poprzez utworzenie nowej tablicy o większym rozmiarze, skopiowanie istniejących elementów, a następnie zwolnienie pamięci zajmowanej przez starą tablicę. Możemy przedstawić opisaną sytuację na prostym przykładzie. 



Możemy zaobserwować, że nie mamy możliwości zwiększenia rozmiaru zadeklarowanej tablicy dynamicznej. Należy zadeklarować tablice o jeden większą niż poprzednio zadeklarowana oraz przepisać do niej wszystkie elementy. Oczywiście im więcej jest elementów w tablicy, tym więcej czasu będzie potrzebne na wykonanie takiej operacji. Istnieje więc potrzeba deklarowania struktur danych, które umożliwią swobodne zwiększanie rozmiaru przechowywanych elementów i jednocześnie nie powodując zwiększenia narzutu czasowego na wykonanie takiej operacji. W tym celu powstały listy dynamiczne. W porównaniu do tablic dynamicznych, listy dynamiczne pozwalają na łatwe dodawanie i usuwanie elementów w dowolnym miejscu, bez konieczności kopiowania pozostałych danych. Istnieje wiele różnych implementacji list dynamicznych m.in.:

1. Lista dynamiczna jednokierunkowa (ang. Single Linked List).
2. Lista dynamiczna dwukierunkowa (ang. Double Linked List).
3. Lista dynamiczna cykliczna (ang. Circular Linked List).

W kolejnym rozdziale omówimy bardziej szczegółowo listy dynamiczne jednokierunkowe. Będzie to stanowiło idealny wstęp do bardziej złożonych struktur danych.