Повезана листа

Пример повезане листе

Повезана листа је структура података, која је у основи представљена као вектор парова (елемент, показивач), при чему показивач садржи адресу наредног пара. Тако постављени парови називају се чворовима. Пролазак кроз листу могућ је једино линеарно - редом од почетка, елемент по елемент, пратећи показиваче. Недостаци ове структуре података су у томе што захтева додатни простор у меморији (уз сваки елемент иде и показивач), а к-том (к>1) елементу се може приступити само преко свих предходних. Предност повезане листе је у томе што се упис и брисање лако реализују, потребно је мењање само показивача (једног у случају брисања, два у случају уписивања).

Због тога повезане листе се најчешће користе за имплементирање других структура података, као што су стек и мапе.

Концепт

Сваки део повезане листе се назива елемент повезане листе или чвор.

Поље у чвору које садржи адресу следећег чвора се најчешће назива следећи показивач. Друго поље је познато као податак, вредност или информација.

Глава је први чвор у повезаној листи. Репом се може назвати или низ елемената повезане листе (чворова) који не садржи главу или последњи чвор у листи. Крај листе се означава тако што последњи чвор листе показује на празан чвор или нил.

Врсте

Једноструко повезане листе

Једноструке повезане листе имају чворове који садрже само вредност и показивач на следећи чвор.

Једноструко повезана листа

Двоструко повезане листе

У двоструко повезаним листама сваки чвор осим вредности и показивача на следећи чвор садржи још један показивач, на претходни елемент.

Двоструко повезана листа

Цикличне листе

Код цикличних листи последњи чвор не показује на нил, већ на главу листе.

Циклична листа

Ако је листа двоструко повезана осим што последњи чвор показује на главу, и глава својим показивачем на предходи елемент показује на последњи чвор.

Празна листа

Празна листа је листа без података, за њих се каже да су то листе без чворова.

Напредна повезана листа

Главни чланак: Напредна повезана листа

Код напредних повезаних листи сваки чвор има више поља за вредност.

Однос низа, динамичког блока и повезане листе

Повезана листа се по више питања разликује од (статички алоцираног) низа. Листа се може произвољно смањивати и проширивати (тј. број њених елемената се може смањивати и повећавати). Додавање елемента у листу захтева време О(1) (мада, због фрагментисања меморије, конкретно време може да расте како се програм извршава). Елементи низа су смештени у узастопним меморијским локацијама и позиција у меморији и-тог елемента се може једноставно израчунати на основу и и позиције почетног елемента. Због тога се и-том елементуа низа приступа у времену О(1). С друге стране, елементи листе су смештени у меморијским локацијама које нису нужно узастопне и могу бити разбацане по меморији. Да би се приступило једном елементу листе, потребно је кренути од почетног елемента и пратити показиваче све док се не наиђе на тражени елемент, те је време потребно за приступ О(н) (где је н број елемената листе).

Повезана листа се по више питања разликује и од динамички алоцираних блокова меморије (који могу да садрже низове елемената истог типа). Алокација динамичког блока захтева постојање у меморији повезаног блока слободне меморије (величине довољне да прими задати скуп елемената). С друге стране, коришћење листа захтева алоцирање меморије само за један по један елемент. Брисање елемената се такође врши појединачно (та честа додавања и брисања елемената листе доводе до фрагментисања меморије). Величина динамичког блока се може мењати само од његовог краја (а и то може да буде захтевна операција). Величина листе се мења једноставно додавањем нових појединачних елемената. Елементима у динамичком блоку се приступа, као елементима низа, у времену О(1), а елементима листе у времену О(н).

Све у свему — ниједна од наведених структура података (повезане листе, низови, динамички блокови) није увек најбољи избор и нема својства увек боља од друга два. Најбољи избор је везан за специфичности конкретног проблема и најважније захтеве.

Литература

• Живковић, Миодраг (2000). Алгоритми (ПДФ). ИСБН 978-86-7589-020-1.