ANT_39: no ano, realloc() je o tom, že nakonec stejně asi použiju pole místo nějakého "vylepšeného spojového seznamu" - na tuhle strukturu SAMOZŘEJMĚ vliv nemá, je to o diskuzi, co použít MÍSTO ní.
spojový seznam je ale pořád výborný, pokud se ti může stát, že přidáváš prvek někam náhodně doprostřed: tam je "posouvání" části toho pole pointerů pořád operace která může mít režii - zvlášť při vkládání na začátek. pole pointerů je skvělé, pokud víš kolik toho bude, a pokud víš, že všechny prvky dostaneš hned na začátku, a pak už žádný bud nepřibude, nebo (diskutabilně) přibude jen na konec.
tenhle "indexovaný spojový seznam" je také dobrý, pokud bys ho vybudoval na začátku, a pak věděl, že potřebuješ jen sem tam něco ubrat nebo přidat: pak by si s ním pracoval jako se spojovým seznam (a pouze odmázaval ty indexy, které případně odkazují na vymazaný prvek). místo pro přidání nového prvku taky krásně najdeš s logaritmickou složitostí (srovnej to s O(N) složitostí operace "pošoupávání všeho" u pole pointerů...)
od začátku mám jen jeden jediný problém: jak sakra jednoduše udržovat ty indexy použitelné i pro přidání nového prvku ? kdybych na tohle měl trik, tak je tahle struktura fakt bomba (ok, sice zabere 2x tolik paměti, než prosté pole pointerů - ale právě proto, že je tam tenhle tradeoff, mi přijde, že bych obětováním této paměti - a případně uložením nějaké "hint" informace do těch seek pointerů - např. odkazy na začátek, odkazy na NULL, odkazy na smluvené hodnoty NIL, kterých nesmí nabývat žádný prvek seznamu, apod. - mohl získat jako bonus nějakou úsporu strojového času...)