Oglejmo si primer povezanega seznama, predstavljenega s tabelo vozlišč (glava je označena z rumenim ozadjem):
V pythonu bi ta povezani seznam zapisali takole:
ps = [[4,3,1], ['A', 0, 2], ['Z', 1, 4], ['M', 4, 0], ['I', 2, 3]]
Glava pove, da je seznam sestavljen iz štirih vozlišč (ps[0][0]
) in da se začetno vozlišče nahaja na indeksu 3 (ps[0][1]
). Vozlišče na indeksu 3 hrani element 'M'
; to je torej začetni element zaporedja. Ker je vrednost ps[3][1]
enaka 4, ima naslednje vozlišče indeks 4. Drugi element zaporedja (element na položaju 1) je torej 'I'
. Naslednje vozlišče ima indeks 2 (element 'Z'
), nato pa nas povezava vodi do vozlišča na indeksu 1 (element 'A'
). Ker velja ps[1][1] == 0
, je to vozlišče končno. Prikazani seznam torej hrani zaporedje <'M', 'I', 'Z', 'A'>
.
Sprehodi se po seznamu še od končnega vozlišča do začetnega.
Povezani seznam si marsikdaj lažje predstavljamo, če je prikazan tako:
Vozlišča na zgornji sliki so urejena po položajih, ne po indeksih v tabeli. Puščica predstavlja indeks ciljnega vozlišča, križ pa indeks 0.
Katero zaporedje znakov predstavlja spodnji povezani seznam?
[[5, 3, 4], ['A', 4, 5], ['B', 5, 3], ['C', 2, 0], ['D', 0, 1], ['E', 1, 2]]
V prazna polja vpiši indekse naslednikov in predhodnikov tako, da bo povezani seznam predstavljal zaporedje <'P','Y','T','H','O','N'>
.
0 | 1 | 2 | 3 | 4 | 5 | 6 | indeksi |
6 | 'T' | 'N' | 'O' | 'P' | 'H' | 'Y' | elementi |
indeksi naslednikov | |||||||
indeksi predhodnikov | |||||||
glava |