Spojový seznam
anglicky:
linked list
Jedna ze základních datových struktur. Plní podobnou funkci jako pole, ale někdy je výhodnější, především proto, že umožňuje provádět některé operace v konstantním čase (např. vypuštění prvního prvku, v poli bych pak musel následující prvky “sesypat”). Například
Frontu i
Zásobník lze implementovat pomocí spojového seznamu.
Prvky seznamu jsou spojené pomocí
ukazatelů, bývají
dynamicky alokované, což se v Pascalu může jevit jako další výhoda oproti poli (pole sice mohu dynamicky alokovat, ale jakmile zaplním všechny alokované prvky, nemohu k nim přidat další — aspoň ne v
Borland Pascalu).
Základní typy
- lineární / kruhový
- směr
- jednosměrný (prvek ukazuje na následníka)
- obousměrný (každý prvek ukazuje na následníka a předchůdce)
- s hlavou / bez hlavy
- řeší problém prvního prvku (hlavu mám vždycky;))
Pozor na paměťovou režii oproti poli (ukazatel má typicky aspoň tolik, co základní typy, v Borland Pascalu shodu okolností více).
Odkazy
Spojový seznam na anglické Wikipedii — tady určitě najdete další detaily, o kterých se na přednášce mluvilo.