Povezani seznam

Iz Wikipedije, proste enciklopedije

Povezani seznam (angleško linked list) je vrsta podatkovne strukture, kjer se element povezuje na prejšnjega oz. naslednjega. Takšne vrste seznamov se uporablja pri implementaciji dinamičnih polj, skladov ali dreves.

Povezani seznam je lahko enojni, dvojni ali krožni. Elementi v enojno povezan seznamu imajo povezavo do samo enega elementa, medtem ko imajo dvojni povezani dve povezavi. Po navadi sta to naslednji in prejšnji element. Oba načina seznamov sta lahko krožna, kar pomeni, da se zadnji element v seznamu povezuje s prvim, ki ustvari neprekinjeno zanko. Nasprotje krožnega je pretrgana povezava elementov.

Povezane sezname so razvili Allen Newell, John Clifford Shaw in Herbert Alexander Simon v think tanku RAND Corporation med letoma 1955 in 1956 kot glavno podatkovno strukturo za svoj programski jezik IPL.

Seznami[uredi | uredi kodo]

Enojno povezani seznam[uredi | uredi kodo]

Single linked list.png

Dvojno povezani seznam[uredi | uredi kodo]

Doubly linked list.png

Krožno povezani seznam[uredi | uredi kodo]

Circurlar linked list.png