Licenca
To delo je na voljo pod pogoji slovenske licence Creative Commons 2.5:
priznanje avtorstva - nekomercialno - deljenje pod enakimi pogoji.
Celotna licenca je na voljo na spletu na naslovu http://creativecommons.org/licenses/by-nc-sa/2.5/si/. V skladu s to licenco je dovoljeno vsakemu uporabniku delo razmnoževati, distribuirati, javno priobčevati, dajati v najem in tudi predelovati, vendar samo v nekomercialne namene in ob pogoju, da navede avtorja oziroma avtorje in izdajatelja tega dela. Če uporabnik delo predela, kar pomeni, da ga spremeni, preoblikuje, prevede ali uporabi to delo v svojem delu, lahko predelavo dela ponudi na voljo le pod pogoji, ki so enaki pogojem iz te licence oziroma pod enako licenco.
*Implementacija s povezanim seznamom
Uvod
Kot smo videli, lahko zaporedje neposredno predstavimo s tabelo njegovih elementov, slabost te implementacije pa sta neučinkoviti operaciji vstavljanja in odstranjevanja elementov na nekončnem mestu. V tem razdelku si bomo ogledali implementacijo zaporedja, ki to slabost odpravlja.
Z izrazom položaj bomo odslej označevali mesto v zaporedju. Domenimo se, da ima prvi element položaj 0, drugi položaj 1 itd. Recimo v zaporedju z elementi 'O', 'D', 'E' in 'R' se na položaju 0 nahaja element 'O', na položaju 1 element 'D' itd. Element na položaju 0 bomo imenovali tudi začetni element zaporedja, elementu na zadnjem položaju (torej na položaju, ki je za 1 manjši od dolžine zaporedja) pa bomo rekli končni element zaporedja. Če zaporedje predstavimo s tabelo njegovih elementov, je indeks elementa v tabeli enak kar položaju elementa v zaporedju.
Za hip ostanimo pri implementaciji zaporedja s tabelo njegovih elementov in si oglejmo, kako bi lahko učinkovito (s časovno zahtevnostjo O(1)) implementirali dodajanje elementov na koncu in začetku tabele. To lahko dosežemo tako, da element vedno dodamo na konec tabele (tudi pri dodajanju na začetek zaporedja), obenem pa si zapomnimo, na katerem indeksu se trenutno nahaja začetni in na katerem končni element zaporedja.
Vendar pa to ni dovolj: ker se nam pri hkratni uporabi obeh operacij lahko elementi v tabeli med seboj poljubno pomešajo, moramo za vsak element hraniti indeks njegovega naslednika in (to nam bo koristilo pri številnih operacijah) indeks njegovega predhodnika. Podatkovno strukturo, ki hrani navedene podatke, imenujemo (dvojno) povezani seznam.
Predstavitev povezanega seznama v pythonu
Povezani seznam je možno sprogramirati na več načinov. Izbrali bomo možnost, ki najbolj ustreza našemu trenutnemu znanju. Povezani seznam bomo predstavili s tabelo vozlišč. Vsako vozlišče je tabela s tremi elementi. Vozlišče na indeksu 0, imenovano glava, vsebuje:
- število elementov zaporedja;
- indeks začetnega vozlišča (vozlišča, ki hrani začetni element zaporedja);
- indeks končnega vozlišča (vozlišča, ki hrani končni element zaporedja).
Če je seznam prazen, so vsi trije elementi glave enaki 0. Vsako izmed preostalih vozlišč pa vsebuje:
- enega od elementov zaporedja;
- indeks vozlišča, ki hrani naslednji element v zaporedju (0, če vozlišče nima naslednika);
- indeks vozlišča, ki hrani predhodni element v zaporedju (0, če vozlišče nima predhodnika).
Sedaj indeksi in položaji niso več eno in isto. Indeks vozlišča je njegov indeks v tabeli vozlišč: glava ima indeks 0, vozlišče v tabeli desno od nje ima indeks 1 itd. Pojem položaj pa se še vedno nanaša na položaj v zaporedju. Začetno vozlišče hrani element na položaju 0, v tabeli pa se lahko nahaja na poljubnem indeksu (razen na indeksu 0). Naslednik začetnega vozlišča hrani element na položaju 1, v tabeli pa se lahko nahaja tudi pred začetnim vozliščem.