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.
*Primerjava tabele elementov in povezanega seznama
Odločitev za implementacijo zaporedja s tabelo elementov ali s povezanim seznamom je odvisna od operacij, ki jih želimo izvajati na zaporedju. Ugotovili smo, da je tabela učinkovita pri dostopanju do poljubnega elementa ter pri dodajanju in odvzemanju na koncu, a neučinkovita pri dodajanju in odvzemanju na drugih položajih. V nasprotju s tabelo je povezani seznam učinkovit pri odvzemanju in dodajanju na poljubnih položajih, njegova slabost pa se pokaže pri dostopu do elementov. Seznam je učinkovit za zaporeden dostop do elementov, torej po vrsti od začetnega do končnega elementa ali pa od končnega do začetnega, ne pa za naključen dostop – torej za dostop do elementa na poljubnem položaju neodvisno od prejšnjih dostopov. V takem primeru je potreben sprehod po seznamu do vozlišča na iskanem položaju, kar (v povprečju prek vseh možnih položajev) zahteva časovno zahtevnost O(n).
Primerjajmo časovne zahtevnosti posameznih operacij:
| Operacija | Tabela elementov | Povezani seznam |
|---|---|---|
| izdelava | O(1) | O(1) |
| ugotavljanje števila elementov | O(1) | O(1) |
| naključen dostop do elementa | O(1) | O(n) |
| dodajanje na začetek | O(n) | O(1) |
| dodajanje na konec | O(1) | O(1) |
| vstavljanje | O(n) | O(1) |
| odstranjevanje na začetku | O(n) | O(1) |
| odstranjevanje na koncu | O(1) | O(1) |
| odstranjevanje na poljubnem mestu | O(n) | O(1) |
Če pri zaporedju, ki ga želimo implementirati, pričakujemo veliko dodajanj in odvzemanj na nekončnih mestih, je torej bolje izbrati povezani seznam. V nasprotnem primeru pa se tabela elementov v teoriji obnese enako dobro, v praksi pa zaradi manjše porabe pomnilniškega prostora in enostavnejših operacij celo bolje od povezanega seznama. Povezani seznam namreč potrebuje približno trikrat toliko prostora kot tabela z istim številom elementov, saj za vsak element potrebujemo tudi prostor za hranjenje indeksa njegovega naslednika in predhodnika.
Vrsta in sklad
Vrsta in sklad sta posebna primera zaporedij, ki nam pri programiranju večkrat prideta prav. Vrsta je zaporedje, pri katerem se elementi dodajajo samo na koncu, odvzemajo pa samo na začetku. Predstavljamo si jo lahko kot vrsto pred blagajno, v katero se nihče ne vriva in iz katere nihče predčasno ne izstopa. Sklad pa je zaporedje, v katerem se elementi tako dodajajo kot odvzemajo samo na koncu. Predstavljamo si ga lahko kot skladovnico enakih krožnikov, saj krožnik vedno postavimo na vrh, z vrha pa ga tudi vzamemo. Zaradi te analogije imenujemo začetek sklada tudi dno, konec pa vrh.
Vaja
V prazno vrsto dodamo elemente 'P', 'R', 'O', 'G', 'R', 'A' in 'M' (v tem vrstnem redu), nato pa iz nje odstranimo tri elemente. Kakšna je sedaj vsebina vrste?
Vaja
Na prazen sklad dodamo elemente 'P', 'R', 'O', 'G', 'R', 'A' in 'M' (v tem vrstnem redu), nato pa z njega odstranimo tri elemente. Kakšna je sedaj vsebina sklada?