Динамички низ

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

Динамички низ није исто што и динамички алоциран низ, који је заправо низ фиксне дужине чија се дужина одређује при алокацији. Ипак, и динамички низ може користити низ фиксне дужине као back end. ^[1]

Динамички низови ограничене дужине и капацитет

Најједноставнији динамички низ може се направити алоцирањем низа фиксне дужине, који ћемо затим поделити на два дела: први чува елементе динамичког низа, а други је резервисан, тј. неискоришћен. Тада је могуће додавати или уклањати елементе са краја динамичког низа у константном времену, користећи резервисан простор, све док се тај простор не попуни. Број елемената који је употребљен за чланове низа је његова дужина, док се величина резервисаног простора назива капацитет динамичког низа. Капацитет низа је његова максимална дужина без реалокације података. ^[2]

У апликацијама где је дужина низа ограничена, могуће је користити структуре података фиксне дужине. Међутим, ово се може испоставити као краткорочно решење уколико касније буде било потребно више простора. Често је боље решење омогућити да сваком низу може да се мења величина, а онда се приликом оптимизације вратити на коришћење низова фиксиране дужине. Промена капацитета је скуп процес, који обично обухвата копирање целокупног садржаја низа.

Геометријско повећање капацитета и амортизована цена

Пошто је промена капацитета скуп процес, цена се може значајно смањити већим проширивањима (на пример, удвостручујући капацитет) и коришћењем резервисаног простора за будућа додавања чланова низа. Операција додавања елемента на крај низа може изгледати овако:

  function insertEnd(dynarray a, element e)
    if (a.size = a.capacity)
        a.capacity ← a.capacity * 2 // udvostručuje kapacitet 
        ... kopiranje podataka na novu memorijsku lokaciju...
    a[a.size] ← e
    a.size ← a.size + 1

Пошто је унето n елемената, капацитети формирају геометријску прогресију. Проширивање капацитета неким константним фактором обезбеђује да је за унос n елемената потребно укупно време O(n),што значи да је за сваки појединачан унос потребно амортизовано константно време. Вредност овог фактора пропорционалности утиче на однос време-простор: просечно време по операцији убацивања елемента је око а/(а-1) док је број утрошених ћелија ограничен одозго са (a-1)n. Избор вредности а зависи од библиотеке или апликације: у неким уџбеницима а=2 док Јавина ArrayList имплементација користи а=3/2.

Многи динамички низови такође деалоцирају део расположивог простора ако величина падне испод неког прага, нпр. 30% капацитета. Потребно је да тај праг обавезно буде мањи од 1/а да би подржао наизменичне секвенце додавања и брисања са амортизованом константном ценом. Динамички низови су уобичајен пример у објашњавању амортизоване анализе.

Одлике

	Повезана листа	Низ	Динамички низ	Балансирано стабло	Листа с директим приступом
Индексирање	Θ(n)	Θ(1)	Θ(1)	Θ(log n)	Θ(log n)
Убаци/Избриши с почетка	Θ(1)	N/A	Θ(n)	Θ(log n)	Θ(1)
Убаци/Избриши с краја	Θ(n) последњи елемент није познат Θ(1) последњи елемент је познат	N/A	Θ(1) амортизовано	Θ(log n)	Θ(log n) освежавање
Убаци/Избриши из средине	време претраге + Θ(1)	N/A	Θ(n)	Θ(log n)	Θ(log n) освежавање
Потрошен простор (просек)	Θ(n)	0	Θ(n)	Θ(n)	Θ(n)

Особине динамичких низова су сличне особинама низова, уз допунске операције додавања и уклањања елемената на крају низа:

Добијање или постављање вредности са одређеним индексом (константно време)
Итерације над елементима у редоследу (линеарно време, добро понашање кеша)
Инсертовање или брисање елемента у средини низа (линеарно време)
Инсертовање или брисање елемента на крају низа (константно амортизовано време)

Динамички низови деле многе предности низова, укључујући локалност референци и ефикасно коришћење кеша, компактност (мало коришћење меморије) и могућност насумичног (директног) приступа. Обично им је потребан само мали додатни простор у коме се чувају подаци о величини и капацитету. Због тога су динамички низови атрактивно решење за креирање структура података са оптималном употребом кеша. У језицима као што су Phyton или Java, који користе семантику референци, динамички низови углавном неће чувати стварне податке, већ референце ка подацима који су смештени у другим деловима меморије. У овом случају, секвенцијални приступ подацима ће у стварности представљати приступање већем броју неповезаних делова меморије, па ће бити изгубљене многе предности које ова структура података има у употреби кеша.

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

Балансирано стабло може ускладиштити листу, истовремено обезбеђујући, уз прихватљиву ефикасност, све операције како динамичких низова тако и повезаних листа, али и додавање на крај и итерације са подацима су спорије него код динамичких низова, због смештаја података у одвојеним блоковима као и због операција балансирања стабла.

Референце

^ Види, на пример: source code of java.util.ArrayList class from OpenJDK 6.
^ Lambert 2009, стр. 510.

Литература

Lambert, Kenneth Alfred (2009). Physical size and logical size. Fundamentals of Python: From First Programs Through Data Structures. Cengage Learning. стр. 510—. ISBN 978-1-4239-0218-8.

[java_util_ArrayList-1] Види, на пример: source code of java.util.ArrayList class from OpenJDK 6.

[FOOTNOTELambert2009510-2] Lambert 2009, стр. 510.

[1]

[2]