Struktury odwołujące się do samych siebie

Struktura może mieć pola będące strukturami, muszą to jednak być struktury zdefiniowane wcześniej. Chcąc utworzyć rekurencyjny typ danych możemy jako pole struktury umieścić wskaźnik do definiowanego typu, na przykład: 
typedef struct lista{
  Elem e;
  struct lista *nast; 
} Lista;
Powyższa deklaracja tworzy nowy typ struct lista, który zawiera dwa pola: e typu Elem oraz nast będący wskaźnikiem na definiowany typ struct lista. Nowemu typowi zostaje nadany synonim Lista. Tak zdefiniowany typ pozwala tworzyć strukturę danych nazywaną listą jednokierunkową.

Listowe struktury danych

Dwa poniższe przykłady pokazują użycie listy jednokierunkowej jako kolejki FIFO (pierwszy przyszedł pierwszy został obsłużony) oraz kolejki LIFO (pierwszy przyszedł ostatni został obsłużony).

fifo.cpp

lifo.cpp

Interpretacja graficzna

Kolejkę złożoną z trzech elementów można sobie wyobrażać tak, jak na rysunku poniżej:

Rekurencyjnie prościej?

Kolejny przykład pokazuje rekurencyjny sposób operacji na strukturach dynamicznych. (Uwaga! Zwykle rekurencja pochłania więcej czasu procesora i więcej pamięci).

lista.cpp

Przykładowe zadania