Implementirajmo nekaj osnovnih operacij za seznam. Vse operacije bomo zapisali kot funkcije v modul povezaniSeznam.py
, da jih bomo lahko uporabljali tudi v drugih pythonovih programih. Napisali bomo te funkcije:
Ustvari()
: Ustvari prazen povezani seznam.SteviloElementov(povSeznam)
: Vrne število elementov (vozlišč) v podanem povezanem seznamu.IndeksZacetnega(povSeznam)
: Vrne indeks začetnega vozlišča povezanega seznama.IndeksNaslednika(povSeznam, indeks)
: Vrne indeks naslednika vozlišča na podanem indeksu.IndeksKoncnega(povSeznam)
: Vrne indeks končnega vozlišča povezanega seznama.IndeksPredhodnika(povSeznam, indeks)
: Vrne indeks predhodnika vozlišča na podanem indeksu.Element(povSeznam, indeks)
: Vrne element vozlišča na podanem indeksu.DodajNaKonec(povSeznam, element)
: Doda vozlišče s podanim elementom na konec seznama.Vstavi(povSeznam, indeks, element)
: Ustvari novo vozlišče s podanim elementom in ga v seznam poveže tako, da bo vozlišče na podanem indeksu njegov naslednik.DodajNaZacetek(povSeznam, element)
: Doda vozlišče s podanim elementom na začetek seznama.Izloci(povSeznam, indeks)
: Iz seznama izloči vozlišče na podanem indeksu.IzlociZacetnega(povSeznam)
: Iz seznama izloči začetno vozlišče.IzlociKoncnega(povSeznam)
: Iz seznama izloči končno vozlišče.Te funkcije nam omogočajo, da se sprehajamo po elementih povezanega seznama ter da elemente v seznam dodajamo in iz njega izločamo (odstranjujemo) na poljubnih mestih. Naj opozorimo, da funkcije delujejo z indeksi vozlišč v tabeli vozlišč, ne s položaji elementov v zaporedju.
Zapišimo prve štiri funkcije. Prazen povezani seznam vsebuje samo glavo brez predhodnikov in naslednikov, torej samo vozlišče [0, 0, 0]
. Število elementov povezanega seznama je zapisano v prvem, indeks začetnega vozlišča pa v drugem elementu glave. Indeks naslednika vozlišča je zapisan v njegovem drugem elementu. Funkcije torej sprogramiramo takole:
Napiši še funkcije IndeksKoncnegaVozlisca
, IndeksPredhodnika
in Element
. Napiši jih v svoj računalnik ali pa na list papirja, da jih boš lahko pozneje enostavno preveril(-a).