Listy powiązane, rekurencyjne struktury danych, tablice mieszające, tablice i wskaźniki.
Nadszedł czas, by opisać kilka fundamentalnych struktur danych, które posłużą mi następnie jako budulec bardziej złożonych obiektów. Rozpocznę od prezentacji tablicy dynamicznej (na bazie której zdefiniuję stos), listę powiązaną, bufor napisów oraz tablicę mieszającą. Następnie wszystkie te dynamiczne struktury danych wykorzystam do zdefiniowania bardziej złożonego typu -- tablicy napisów, czyli struktury danych służącej do efektywnego przechowywania napisów.
Warto wiedzieć, że w standardowej bibliotece języka C++ dostępne są implementacje niemal wszystkich z omawianych w tym rozdziale struktur danych. Na przykład tablica dynamiczna to nic innego, jak dostępna w bibliotece standardowej klasa std::vector. W bibliotece tej umieszczono też wiele innych bardzo użytecznych klas, np. std::list i std::string. Chciałbym jednak najpierw nauczyć Czytelnika sposobów implementacji takich klas bez korzystania z udogodnień, zawartych w bibliotece standardowej. Mam ku temu kilka powodów. Po pierwsze, poznanie metod implementacji prostych struktur danych jest dobrym sposobem uczenia się języka krok po kroku. Po drugie, chciałbym aby Czytelnik uzyskał pojęcie o możliwych sposobach definiowania implementacji struktury danych, dostępnych w bibliotece standardowej. Po trzecie, biblioteka standardowa wykorzystuje bardzo zaawansowane cechy języka (m.in. szablony i przeciążanie operatorów), których jeszcze nie omówiłem (przedstawię je w dalszej części książki).