Разлика између низова и повезаних листа

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

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

Приказано на слици 1, је део кода који се обично користи за декларирање и додељивање вредности пољу. Слика 2 приказује како би низ изгледао у меморији.

Горњи код дефинира низ који може похранити 5 цјелобројних бројева и њима се приступа помоћу индекса 0 до 4. Једно важно својство матрице је да је цијели низ додијељен као један блок меморије и сваки елемент добија свој властити простор у пољу. Једном када се дефинира низ, фиксира се његова величина. Дакле, ако нисте сигурни у величину матрице током компајлирања, морали бисте дефинирати довољно велики низ да бисте били на сигурној страни. Али већину времена ћемо заправо користити мањи број елемената него што смо их издвојили. Тако да је значајна количина меморије заправо изгубљена. С друге стране, ако „довољно велики низ“ у ствари није довољно велик, програм би се срушио.

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

Слика 3: Елемент повезане листе

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

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