Vse funkcije združimo v modul povezaniSeznam.py
:
Če modul poženemo kot samostojen program, se bo poklicala funkcija main
, ki ustvari povezani seznam in na njem preizkusi posamezne funkcije. Modul vsebuje tudi pomožne funkcije Zaporedje
, ZaporedjeNazaj
in IzpisiVse
, ki olajšajo preverjanje delovanja glavnih funkcij. Funkcija Zaporedje
na primer vrne tabelo elementov povezanega seznama, v kateri so elementi zapisani po naraščajočih položajih.
Z izjemo pomožnih funkcij Zaporedje
, ZaporedjeNazaj
in IzpisiVse
je časovna zahtevnost funkcij v modulu povezaniSeznam.py
neodvisna od števila elementov v povezanem seznamu, torej O(1). Časovna zahtevnost pomožnih funkcij pa seveda znaša O(n), saj se moramo pri vseh treh sprehoditi po celotnem seznamu.
Izdelaj graf porabe časa v odvisnosti od števila klicev funkcije DodajNaZacetek
in DodajNaKonec
na enak način, kot si to naredil(-a) pri tabeli. Primerjaj dobljena grafa z grafoma pri tabeli.
Kljub enaki časovni zahtevnosti je funkcija DodajNaKonec
pri povezanem seznamu nekoliko počasnejša kot pri tabeli. Zakaj?