3.4.2. Implementace jednosměrně vázaného seznamu

S jednosměrně vázaným seznamem jsme se vlastně setkali již při implementaci zásobníku a fronty. V obou případech jsme použili položky nesoucí data a odkaz na následující prvek. Pokud budeme chtít s touto datovou strukturou pracovat jako s obecným seznamem, je třeba se opět zamyslet nad složitostí jednotlivých operací.

Obrázek 3.6. Jednosměrně vázaný seznam

Při vkládání na konkrétní pozici jednosměrně vázaného seznamu musíme nejprve vyhledat požadovanou pozici, na což potřebujeme čas úměrný délce seznamu. Samotné vložení, případně odstranění prvku je již proveditelné v konstantním čase, neboť vyžaduje pouze přesměrování odkazů. Máme-li však již k dispozici referenci na konkrétní prvek seznamu (např. po úspěšném vyhledávání), jsme schopni za něj vložit nový prvek v konstantním čase. Vložení prvku před tuto pozici nebo odstranění aktuálního prvku je ale podstatně složitější, neboť potřebujeme nejprve vyhledat předcházející prvek, abychom mohli aktualizovat jeho odkaz na následníka. K vyhledání tohoto prvku však potřebujeme opět lineární čas. Jak bychom tuto operaci mohli urychlit?

Řešením je zřejmě rozšíření položky seznamu o odkaz na předcházející prvek. To nám umožní jednak provést vkládání nebo rušení na aktuální pozici i před ní, jednak se můžeme v seznamu lehce pohybovat nejen směrem vpřed, ale i zpět.