Propojené seznamy (aneb spojové seznamy) jsem se pokoušel pochopit někdy v době, kdy jsem začínal programovat v céčku. Kapitola o nich byla úplně jako poslední a připadala mi nezáživná, tak jsem ji vynechal. Potom jsem si léta žil, aniž bych takovou věc potřeboval. Asi před měsícem jsem ale pomáhal Lucce s její semestrálkou a narazil jsem tam na problém běžného pole užitého jako databáze, a to jest těžkopádnost a náročnost procesu vyhledání a odstranění určité položky. Jde to, ale je to pěkně hnusné. Nevěděl jsem, že problém by jednoduše vyřešil propojený seznam.
Propojený seznam je datová struktura, která zcela doslova tvoří rětěz. Článek řetězu – uzel – node – obsahuje data a vidí na své dva sousedy (levého a pravého dejmetomu). Pokud chytíme řetěz za jakýkoliv článek, dostaneme se přes něj na začátek, na konec i na jakýkoliv jiný článek řetězu. Když chceme za nějakým článkem přidat nový, vezmeme kleště, v tom místě rozpojíme řetěz, vložíme článek a připojíme k němu rozpojené konce. Když chceme nějaký článek odebrat, prostě rozpojíme řetěz, odebereme článek a řetěz opět spojíme. Nevýhoda řetezu je, že nemůžeme držet celý. Jsme slabí a zvládneme ho držet pouze na jednom místě. To znamená, že pokud chceme najít článek s konkrétní informací, musíme udělat nejhůře n zbytečných kroků, kde n je vzdálenost od nejbližšího konce.
Jak takovou strukturu implementovat v počítači? Ukažme si v jazyce C++/CLI.
Je občas výhodné tvořit řetězy z různorodých článků (například vánoční řetězy :))…), definujme si tedy něco „řetězitelného“. Řetězitelná věc bude taková, která umí udržet kromě dat i ukazatel na svoje dva sousedy (přičemž oba dva nebo jeden mohou být nulloví) a bude porovnatelná na základě něčeho:
public interface class ILink
{
public:
property ILink ^next;
property ILink ^previous;
String ^ToString();
bool Equals(Object ^o);
};
Buďme nyní konkrétnější a vytvořme si třeba řetězitelný typ String:
public ref class LSTR : public ILink, Object
{
protected:
String ^_data;
ILink ^_next;
ILink ^_previous;
public:
LSTR(String ^data)
{
_data = data;
}
property ILink ^next
{
virtual ILink ^get()
{
return _next;
}
virtual Void set(ILink ^next)
{
_next = next;
}
}
property ILink ^previous
{
virtual ILink ^get()
{
return _previous;
}
virtual Void set(ILink ^previous)
{
_previous = previous;
}
}
virtual String ^ToString() override
{
return _data->ToString();
}
virtual bool Equals(Object ^o) override
{
if(this==o)
{
return true;
}
if(o->GetType() != this->GetType())
{
return false;
}
if(((LSTR ^)o)->_data == _data)
{
return true;
}
}
};
Co by vás na předchozím kódu mohlo překvapit (co neznáte z jiných jazyků) jsou takzvané vlastnosti (properties). Vlastnosti elegantně řeší malý kosmetický problém jiných jazyků (například Javy). Problém spočívá ve skutečnosti, že s jednou proměnnou pracujete dvěmi metodami (getterem a setterem). Pomocí vlastnosti lze tyto funkce sjednotit tak, že se ve výsledku chovají jako jedna členská proměnná, čili ji lze používat na levé (definujete set), pravé (definujete get) nebo obou stranách (definujete get i set) přiřazovacího příkazu.
Nyní po kouskách sestavíme samotný propojený seznam (respektive obsluhující datovou strukturu – propojený seznam není v této struktuře uložen a není v programu ničím reprezentován – nemůžete si na něj „sáhnout“; tato struktura obsahuje vždy a pouze právě jeden aktuální článek řetězu – hlavu – head):
ref class LL
{
private:
ILink ^_head;
public:
property ILink ^Head
{
virtual ILink ^get()
{
return _head;
}
}
Nyní naprogramujeme metodu vkládání. Vkládáme nový článek řetězu, obsahuje pouze svoje data — „sousedy“ má nullové. Musíme mu je tedy přiřadit a zároveň sdělit jeho sousedům, že se nový článek stal jejich novým pravým nebo levým „sousedem“. Pokud se dohodneme, že bude vkládat ZA aktuální článek, máme k dispozici pouze levého (v blízké budoucnosti předřazeného) souseda v hlavě. Sdělíme tedy novému článku jeho předřazeného souseda (aktuální hlavu), ale článek ještě nezapojujeme (zatím ho necháme ležet někde vedle a jenom mu povídáme o jeho nových sousedech). Zkontrolujeme, jestli aktuální hlava vůbec existuje (můžeme se vyskytovat v prázdném řetězu) a zároveň zkontrolujeme, jestli má aktuální hlava pravého (následujícího) souseda. Pokud obě podmínky splňuje (tj. řetěz obsahuje minimálně dva články), sdělíme novému článku i jeho pravého souseda. Jak ale sdělit pravému sousedovi, že má nového levého souseda, když na něj jaksi nemáme handle? Pomocí drbů :). Řekneme hlavě, aby svému pravému sousedovi řekl, že má nového levého souseda. Tím se hlava odlinkuje od bývalého souseda a už si s ním nedokáže povídat (jeho směrem). Nakonec ještě sdělíme současné hlavě jeho nového pravého souseda (nový článek) a nového souseda učiníme aktuálním článkem (hlavou). Tím je nový článek úspěšně vložen do řetězu.
Void insert(ILink ^node)
{
node->previous = _head;
if(_head!=nullptr && _head->next!=nullptr)
{
node->next = _head->next;
_head->next->previous = node;
}
if(_head!=nullptr)
{
_head->next = node;
}
_head = node;
}
Stane se, že se článek se svými sousedy nepohodne nebo si vezme hypotéku od nebankovního subjektu, nebude ji moci splácet a zabaví mu dům. V takovém případě chceme mít možnost nepohodlný článek vymazat :). Článek vymažeme tak, že jeho umístění jeho domu vymažeme okolním sousedům z hlavy a místo toho jim řekneme, že spolu sousedí navzájem už léta :). Ve skutečnosti tak to, co si pojmenujeme „deleteActual“ články nemaže, ale pouze odstraněje ze řetězu. Články se potom mohou dále používat (třeba přeřadit do méně luxusní čtvrti). To se mi na propojených seznamech líbí. Nikoho nezabíjí :).
Boolean ^deleteActual()
{
if(_head==nullptr)
{
return false;
}
_head->previous->next = _head->next;
_head = _head->previous;
}
Dále budeme chtít cestovat od jednoho domu ke druhému, abychom mohli všechny sousedy obejít a zjistit, co jsou zač. V programu existují na pevno vždy maximálně 3 sousedé. Hlava, jeho levý soused a jeho pravý soused. Pomocí drbů se lze ale doslechnout, co zrovna dělá soused o tři domy dál :). Zeptáte se pravého souseda, ten se zeptá svého pravého souseda a tak dále. To je ovšem těžko programovatelné (leda rekurzivně). Potřebujeme tedy přemísťovat titul hlava. Tu uděláme prostě tak, že titul předáváme ze souseda na souseda. Souseda, který zrovna hlavu má, můžeme ovládat (je to něco jako mozkový implantát).
Boolean stepForth()
{
if(_head->next==nullptr)
{
return false;
}
_head->next->previous = _head;
_head = _head->next;
return true;
}
Boolean stepBackward()
{
if(_head->previous==nullptr)
{
return false;
}
_head->previous->next = _head;
_head = _head->previous;
return true;
}
Potom se občas budeme chtít dostat na konec nebo na začátek vesnice.
Void rewind()
{
while(stepBackward());
}
Void fastFwd()
{
while(stepForth());
}
Nebo taky třeba může chtít zjistit, jestli ve vesnici nebydlí nějaký náš příbuzný. Jak to poznáme? No, že se jmenuje Flannery, ne :)? Vytvoříme si obraz našeho příbuzného, stoupneme si na začátek vesnice a chodíme od domu k domu, ptaje se, jestli tam nebydlí někdo, kdo odpovídá našemu vzoru. Sousedi ale nebudou mluvit. Zvlášť, když někoho bude hledat policie. Proto je nutno každému přidělit hlavu a odpvěď z nich dostat násilím. Budeme tedy přidělovat hlavu jednomu po druhém a vybírat z jejich mozků požadovanou informaci.
Boolean seek(ILink ^node)
{
rewind();
do
{
if(_head->Equals(node))
{
return true;
}
}
while(stepForth());
return false;
}
To je vpodstatě všechno, co potřebujeme s naší vesnicí dělat. Ještě jsem přidal dvě orientační metody, abyste věděli, jste-li na začátku nebo na konci vesnice (ono to občas nejde poznat ani v těch skutečných vesnicích, ale místní vždycky mají nějaké povědomí o tom, který z konců je vlastně začátek).
Boolean isAtStart()
{
if(_head->previous==nullptr)
{
return true;
}
return false;
}
Boolean isAtEnd()
{
if(_head->next==nullptr)
{
return true;
}
return false;
}
Na závěr jeeště malé otestování.
Ve vesnici bydlí 9 holek. Alice je Mášina kamarádka, tak se nastěhuje vedle ní (navzdoru tomu, že vedle Máši bydlí Olja — prostě posune všechny baráky a postaví si tam svůj… nevím, jak jí tohle mohlo projít na stavebním úřadu). Na okraji vesnice bydlí Klára. Tu ale obtěžují medvědi, vlci, netopíři a hadi fnadi, takže se rozhodne odstěhovat. Potom se nepohodne Olja s Alicí, psyhicky to nezvládne a odstěhuje se taky. Nakonec se přistěhuje Jaroslava, a to na místo, kde dřív bydlela Klára, protože je to vášnivá lovkyně.
int main(array ^args)
{
LL ^ll = gcnew LL();
ll->insert(gcnew LSTR("Lucie"));
ll->insert(gcnew LSTR("Jana"));
ll->insert(gcnew LSTR("Lenka"));
ll->insert(gcnew LSTR("Petra"));
ll->insert(gcnew LSTR("Máša"));
ll->insert(gcnew LSTR("Olja"));
ll->insert(gcnew LSTR("Bára"));
ll->insert(gcnew LSTR("Eliška"));
ll->insert(gcnew LSTR("Klára"));
ll->rewind();
ll->seek(gcnew LSTR("Máša"));
ll->insert(gcnew LSTR("Alice"));
ll->seek(gcnew LSTR("Klára"));
ll->deleteActual();
ll->seek(gcnew LSTR("Olja"));
ll->deleteActual();
ll->rewind();
ll->seek(gcnew LSTR("Eliška"));
ll->insert(gcnew LSTR("Jaroslava"));
ll->rewind();
do
{
Console::WriteLine(ll->Head->ToString());
}
while(ll->stepForth());
Console::ReadKey();
return 0;
}
