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

С Википедије, слободне енциклопедије
Иди на навигацију Иди на претрагу
Пример повезане листе

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

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

Концепт[уреди | уреди извор]

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

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

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

Врсте[уреди | уреди извор]

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

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

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

Двоструко повезане листе[уреди | уреди извор]

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

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

Цикличне листе[уреди | уреди извор]

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

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

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

Празна листа[уреди | уреди извор]

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

Напредна повезана листа[уреди | уреди извор]

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

Однос низа, динамичког блока и повезане листе[уреди | уреди извор]

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

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

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

Референце[уреди | уреди извор]

  1. ^ Живковић, Миодраг (2000). Алгоритми (ПДФ). ИСБН 978-86-7589-020-1. 
  2. ^ Јаничић, Предраг; Марић, Филип (2014). Основе програмирања кроз програмски језик C – Део II (ПДФ). стр. 109—110. [мртва веза]

Литература[уреди | уреди извор]