Podręcznik
1. Wskaźniki, tablice i listy dynamiczne
1.3. Listy dynamiczne
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.:
- Lista dynamiczna jednokierunkowa (ang. Single Linked List).
- Lista dynamiczna dwukierunkowa (ang. Double Linked List).
- Lista dynamiczna cykliczna (ang. Circular Linked List).