Низ и Повезана листа су два начина организовања података у меморији. Пре него што схватите разлике између Низ анд тхе Повезана листа , прво погледамо у низу и повезана листа .
основе за убунту изградњу
Шта је низ?
Структура података која садржи елементе истог типа. Структура података је начин организовања података; низ је структура података јер секвенцијално организује податке. Низ је велики комад меморије у коме је меморија подељена на мале-мале блокове, а сваки блок је способан да ускладишти неку вредност.
Претпоставимо да смо креирали низ који се састоји од 10 вредности, тада ће сваки блок чувати вредност целобројног типа. Ако покушамо да сачувамо вредност у низу различитих типова, онда то није исправан низ и изазваће грешку у време компајлирања.
Декларација низа
Низ се може декларисати као:
data_type name of the array[no of elements]
Да бисмо декларисали низ, прво треба да наведемо тип низа, а затим и име низа. Унутар угластих заграда треба да наведемо број елемената које наш низ треба да садржи.
Хајде да разумемо кроз пример.
int a[5];
У горњем случају, декларисали смо низ од 5 елемената са ' а 'име ан цео број тип података.
Шта је повезана листа?
Повезана листа је колекција чворова који се насумично чувају. Сваки чвор се састоји од два поља, тј. података и линк . Овде су подаци вредност која се чува на том одређеном чвору, а веза је показивач који садржи адресу следећег чвора.
Разлике између низа и повезане листе
Не можемо рећи која је структура података боља, тј. низ или повезана листа . Може постојати могућност да је једна структура података боља за једну врсту захтева, док је друга структура података боља за другу врсту захтева. Постоје различити фактори као што су честе операције које се изводе на структури података или величина података, као и други фактори на основу којих се бира структура података. Сада ћемо видети неке разлике између низа и повезане листе на основу неких параметара.
1. Цена приступа елементу
У случају низа, без обзира на величину низа, низу је потребно константно време за приступ елементу. У низу, елементи се чувају на континуални начин, тако да ако знамо основну адресу елемента, онда лако можемо добити адресу било ког елемента у низу. Морамо да извршимо једноставан прорачун да бисмо добили адресу било ког елемента у низу. Дакле, приступ елементу у низу је О(1) у погледу временске сложености.
У повезаној листи, елементи се не чувају на непрекидан начин. Састоји се од више блокова, а сваки блок је представљен као чвор. Сваки чвор има два поља, то јест, једно је за поље података, а друго чува адресу следећег чвора. Да бисмо пронашли било који чвор на повезаној листи, прво морамо да одредимо први чвор познат као главни чвор. Ако морамо да пронађемо други чвор на листи, онда морамо да пређемо од првог чвора, ау најгорем случају, да бисмо пронашли последњи чвор, прећи ћемо све чворове. Просечан случај за приступ елементу је О(н).
Закључујемо да је цена приступа елементу у низу мања од повезане листе. Стога, ако имамо било какав захтев за приступ елементима, онда је низ бољи избор.
2. Трошкови уметања елемента
У уметању могу бити три сценарија:
јава принт
У случају повезане листе, да бисмо убацили елемент на почетак повезане листе, креираћемо нови чвор, а адреса првог чвора се додаје новом чвору. На овај начин, нови чвор постаје први чвор. Дакле, временска сложеност није пропорционална величини листе. Временска сложеност би била константна, тј. О(1).
Ако низ није пун, онда можемо директно додати нови елемент преко индекса. У овом случају, временска сложеност би била константна, тј. О(1). Ако је низ пун, прво треба да копирамо низ у други низ и додамо нови елемент. У овом случају, временска сложеност би била О(н).
Да бисмо убацили елемент на крај повезане листе, морамо да пређемо целу листу. Ако се повезана листа састоји од н елемената, онда би временска сложеност била О(н).
Претпоставимо да желимо да убацимо елемент на итхположај низа; треба да померимо н/2 елемената удесно. Дакле, временска сложеност је пропорционална броју елемената. Временска сложеност би била О(н) за просечан случај.
је протеинска маст
У случају повезане листе, морамо да пређемо до те позиције где морамо да убацимо нови елемент. Иако не морамо да вршимо било какву врсту померања, већ морамо да пређемо на н/2 позицију. Потребно време је пропорционално н броју елемената, а временска сложеност за просечан случај би била О(н).
Добијена повезана листа је:
Имплементација низа је лака у поређењу са повезаном листом. Док креирате програм помоћу повезане листе, програм је склонији грешкама као што су грешка сегментације или цурење меморије. Дакле, потребно је много пажње при креирању програма на повезаној листи.
Везана листа је динамичке величине док је низ статичан. Овде, статичност не значи да не можемо да одлучимо о величини у време извођења, али не можемо да је променимо када се величина одлучи.
3. Захтеви за меморијом
Како се елементи у низу чувају у једном суседном блоку меморије, тако је низ фиксне величине. Претпоставимо да имамо низ величине 7, а низ се састоји од 4 елемента, онда је остатак простора неискоришћен. Меморија коју заузимају 7 елемената:
Меморијски простор = 7*4 = 28 бајтова
Где је 7 број елемената у низу, а 4 број бајтова целобројног типа.
У случају повезане листе, нема неискоришћене меморије, али додатну меморију заузимају променљиве показивача. Ако су подаци целобројног типа, онда је укупна меморија коју заузима један чвор 8 бајтова, односно 4 бајта за податке и 4 бајта за променљиву показивача. Ако се повезана листа састоји од 4 елемента, тада би меморијски простор који повезана листа заузима био:
вебдривер
Меморијски простор = 8*4 = 32 бајта
Повезана листа би била бољи избор ако је део података већи. Претпоставимо да су подаци од 16 бајтова. Меморијски простор који заузима низ био би 16*7=112 бајтова док повезана листа заузима 20*4=80, овде смо навели 20 бајтова као 16 бајтова за величину података плус 4 бајта за променљиву показивача. Ако бирамо већу величину података, онда би повезана листа заузела мање меморије; иначе, зависи од фактора које усвајамо да одредимо величину.
Погледајмо разлике између низа и повезане листе у табеларном облику.
| Низ | Повезана листа |
|---|---|
| Низ је колекција елемената сличног типа података. | Повезана листа је колекција објеката познатих као чвор где се чвор састоји од два дела, тј. података и адресе. |
| Елементи низа се чувају на суседној меморијској локацији. | Повезани елементи листе могу бити ускладиштени било где у меморији или насумично ускладиштени. |
| Низ ради са статичком меморијом. Овде статичка меморија значи да је величина меморије фиксна и да се не може променити у време извођења. | Повезана листа ради са динамичком меморијом. Овде, динамичка меморија значи да се величина меморије може променити у време рада у складу са нашим захтевима. |
| Елементи низа су независни један од другог. | Елементи повезане листе зависе једни од других. Пошто сваки чвор садржи адресу следећег чвора, да бисмо приступили следећем чвору, морамо приступити његовом претходном чвору. |
| Низу је потребно више времена док обавља било коју операцију као што је уметање, брисање итд. | За брисање повезане листе потребно је мање времена за обављање било које операције попут уметања, брисања итд. |
| Приступ било ком елементу у низу је бржи јер се елементу у низу може директно приступити преко индекса. | Приступ елементу на повезаној листи је спорији јер почиње да прелази од првог елемента повезане листе. |
| У случају низа, меморија се додељује у време компајлирања. | У случају повезане листе, меморија се додељује у време извршавања. |
| Коришћење меморије је неефикасно у низу. На пример, ако је величина низа 6, а низ се састоји само од 3 елемента, онда ће остатак простора бити неискоришћен. | Коришћење меморије је ефикасно у случају повезане листе јер се меморија може доделити или ослободити у време извршавања у складу са нашим захтевима. |