Spojové datové struktury

Pokud potřebujeme ukládat data do paměti a nevíme 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, pointer), 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). Díky tomu je vyhledávání ve spojových datových strukturách pomalejší než v polích (kde je O(1)), ale zato není potřeba předem alokovat velké množství paměti, kterou si spojová datová struktura bere až za běhu programu (na rozdíl od statickéého pole, kde se alokuje při spuštění).

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
• spojové seznamy (jednosměrné, obousměrné, cyklické, s hlavou, bez hlavy)
• stromy
• skip-list
• ...