Spojové datové struktury

Pokud potřebujeme ukládat data do paměti, a nevíme-li předem, kolik jich bude (kolik prvků bude nutné uložit), nebo mění li se v runtimu jejich počet, používáme spojové datové struktury. Každý prvek - záznam - struktury je reprezentován např. jako objekt, který ukazuje na svého následovníka (ukazatel), případně na další objekty (předchozí, začátek...) Ukazatel je vlastně adresa objektu, takže pomocí něho můžeme k jiným objektům přistupovat.

Vyhledávání prvků struktury je většinou iterační, posunujeme se z jednoho objektu na druhou (na rozdíl od pole, kde přistupujeme přímo, indexem).

Jednotlivé záznamy mohou obsahovat metody pro operace se strukturou (zápis, vložení, čtení, posun po prvcích) a, pokud vyžadujeme dědičnost, je možné implementovat spojové struktuře rozhraní, které potřebné operace implementuje.

Příkladem jsou fronty, zásobníky, seznamy (jednosměrné, obojsměrné), stromy, skip-list...