Spájaný zoznam

Po anglicky linked list je (spájaná) dátová štruktúra, ktorá sa oplatí použiť napríklad ako základ zásobníkov a radov. Od zoznamov (list) slovníkov (dict) a stringov, ktoré ste na vytvorenie zásobníka a radu skúsili použiť je o čosi efektívnejší.

Spomeňte si, aké operácie vyžadujeme od radu a zásobníka. Potrebujeme, aby do nich bolo možné prvky vkladať a následne ich v špecifickom poradí vyberať. Líšia sa v tom, z ktorého konca prvky vyberáme. Buď ich chceme vyberať v poradí, v akom boli vložené (rad, queue) alebo v opačnom poradí (zásobník, stack). Na niečo takéto nie je použite zoznamu, slovníka alebo stringu vhodné, hlavne pre to, že tieto štruktúry sú v pamäti "v celku", je pre ne vyhradený kus pamäte, ktorý sa po naplnení musí niekedy celý premiestniť (a to môže byť pomalé). Ak napríklad spravíme pop(0) zo zoznamu, musia sa všetky prvky o jedno miesto posunúť! Zo zásobníka a radu neustále niečo vyberáme a do nich pridávame a pritom vôbec nevyužívame jednu s najväčších výhod zoznamov a slovníkov - to, že k ich prvkom (aj tým, čo sú "v strede") sa dá rýchlo pristúpiť pomocou indexu (zoznam) alebo kľúča (slovník). V radoch a zásobníkoch potrebujeme rýchlo pristupovať (pozrieť sa na, pridávať a uberať) len prvky z konca a začiatku, nie zo stredu...

Vrchol - Node

Základným prvkom spájanej štruktúry je "vrchol" alebo "uzol", po anglicky "Node". Node je objekt, ktorý v sebe uchováva jednu z hodnôt celej dátovej štruktúry spájaného zoznamu a navyše vie, ktorý ďalší Node patrí do zoznamu. Node budeme implementovať v OOP ako triedu, ktorá má dva atribúty, jeden reprezentuje hodnotu v zozname a druhý atribút uchováva ďalší Node v zozname. Ak by sme teda vytvárali spájaný zoznam, ktorý v sebe uchová hodnoty "A", "B", "C" a "D", mal by tento zoznam štyri inštancie triedy Node. V každej z nich by bolo ako hodnota uložené jedno z písmeniek ABCD a navyše referencia na ďalší Node. Prvý node n1 by mal teda napríklad v sebe uloženú hodnotu "A" a informáciu o tom, že ďalšia hodnota je v Node n2. Node n2 má v sebe hodnotu "B" a vie, že ďalší Node je... No a posledný Node má v sebe hodnotu "D" a namiesto referencie na ďalší Node si pamätá, že ďalší už neexistuje, a.k.a. ďalší je None.

V OOP by sme to robili takto:

class Node():
    def __init__(self, hodnota, dalsiNode):
        self.hodnota = hodnota
        self.dalsiNode = dalsiNode

n1 = Node("A", None)
n2 = Node("B", None)
n3 = Node("C", None)
n4 = Node("D", None)

n1.dalsiNode = n2
n2.dalsiNode = n3
n3.dalsiNode = n4

# celý spájaný zoznam je reprezentovaný prvým prvkom,
# cez prvý prvok (Node) sa viem dostať k druhému cez .dalsiNode, z druhého k tretiemu...
zoznam = n1

# hodnota prvého prvku v zozname
print(zoznam.hodnota)

# hodnota druhého
print(zoznam.dalsiNode.hodnota)

# hodnota tretieho
print(zoznam.dalsiNode.dalsiNode.hodnota)

Spájaný zoznam v OOP

Pre prehľadnosť sa oplatí štruktúru spájaného zoznamu implementovať ako triedu v OOP. Trieda Node môže byť vnútornou triedou triedy SpajanyZoznam, nakoľko k nej nie je potrebné mať prístup nikde inde. Ak by sa nám podarilo pekne naprogramovať triedu SpajanyZoznam, mohli by sme ju používať bez akejkoľvek práce s Node, napríklad takto:

zoznam = SpajanyZoznam()
zoznam.addFirst("B")
zoznam.addLast("C")
zoznam.addFirst("A")
print("zoznam ma v sebe", zoznam.size(), "prvkov")

Trieda SpajanyZoznam

class SpajanyZoznam():

    # ############################################################################

    # trieda Node je vnutorna trieda triedy SpajanyZoznam
    # nie je k nej treba pristup nikde inde, len vnutri triedy SpajanyZoznam

    class Node():
        def __init__(self, hodnota, dalsiNode):
            self.hodnota = hodnota
            self.dalsiNode = dalsiNode

    # ############################################################################

    # konstruktor triedy SpajanyZoznam, cely zoznam je reprezentovany len prvym Node
    # z prveho vieme pomocou .dalsiNode zistit druhy, z druheho treti...
    def __init__(self):
        self.prvyNode = None

    # do zoznamu pridavame Node, tento novy node bude odteraz prvy,
    # node, ktory bol doteraz prvy sa zaradi ako "dalsi" za tento novy...
    def addFirst(self, hodnota):
        # vytvorim novy Node s hodnotou *hodnota*
        novyPrvyNode = self.Node(hodnota, None)

        # ako *dalsiNode* nastavim tomuto novemu Node ten, ktory bol doteraz prvy
        novyPrvyNode.dalsiNode = self.prvyNode

        # prvym Node je od teraz novo vytvoreny Node s najnovsie pridanou hodnotou
        self.prvyNode = novyPrvyNode  

Inštancie Node v pamäti

Takto nejako to vyzerá v pamäti, každá inštancia Node má v sebe hodnotu a tiež "ukazuje" na ďalšiu inštanciu, ktorá má v sebe ďalšiu hodnotu a ukazuje na ďalšiu inštanciu... posledná inštancia už neukazuje na nikoho (ukazuje na NULL = v Pythone na None)

Viac info o spájaných štruktúrach

Ak sa vám z tohoto všetkého točí hlava, pekne je to "po lopate" vysvetlené napríklad na tejto stránke. Dá sa tam aj čo to opísať, tak sa nezabudnite pri všetkom aj uistiť, že rozumiete prečo a ako daná operácia/príkaz funguje 🤓 Veľmi užitočná je stránka pythontutor.com, na ktorej je možné nahliadnuť do "usporiadania" pamäte, ktorú zaberajú premenné, čo je pri spájanej štruktúre obzvášť nápomocné a miestami aj zaujímavé.