6 структура података које сваки програмер треба да зна

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

Анкетари више воле да постављају питања у вези са структурама података, тако да ако се припремате за интервју за посао, мораћете да унапредите своје знање о структурама података. Читајте даље док наводимо најважније структуре података за програмере и интервјуе за посао.

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

Елементи унутар повезане листе се чувају у појединачним чворовима који су повезани (повезани) помоћу показивача. Повезану листу можете замислити као ланац чворова повезаних један са другим преко различитих показивача.

Повезан: Увод у коришћење повезаних листа у Јави

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

Свака повезана листа има главни и репни чвор. Чворови листе са једном везом имају само један показивач који показује на следећи чвор у ланцу. Поред следећег показивача, дупло повезани чворови листе имају још један показивач који указује на претходни чвор у ланцу.

Питања за интервју у вези са повезаним листама обично се врте око уметања, претраживања или брисања одређеног елемента. Уметање у повезану листу траје О(1) времена, али брисање и претраживање могу потрајати О(н) времена у најгорем случају. Дакле, повезане листе нису идеалне.

2. Бинарно дрво

Бинарна стабла су најпопуларнији подскуп структуре података породице стабала; елементи у бинарном стаблу су распоређени у хијерархији. Остале врсте дрвећа укључују АВЛ, црвено-црно, Б дрвеће итд. Чворови бинарног стабла садрже елемент података и два показивача на сваки подређени чвор.

Сваки родитељски чвор у бинарном стаблу може имати највише два подређена чвора, а сваки подређени чвор, заузврат, може бити родитељ за два чвора.

Повезан: Водич за почетнике за бинарна стабла

Бинарно стабло претраге (БСТ) складишти податке у сортираном редоследу, где елементи са кључ/вредност мањим од надређеног чвор се чувају на левој страни, а елементи са кључ-вредношћу већом од родитељског чвора се чувају на јел тако.

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

3. Хасх Табле

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

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

Свака хеш табела складишти елементе података у пару вредност-индекс.

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

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

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

4. Стацкс

Стекови су једна од једноставнијих структура података и прилично их је лако савладати. Структура података стека је у суштини било који стек из стварног живота (замислите гомилу кутија или плоча) и ради на ЛИФО (Ласт Ин Фирст Оут) начин.

Својство ЛИФО Стацкс-а значи да ће се први приступити елементу који сте последњи уметнули. Не можете приступити елементима испод горњег елемента у стеку без искакања елемената изнад њега.

Стогови имају две примарне операције—пусх и поп. Пусх се користи за уметање елемента у стек, а поп уклања највиши елемент из стека.

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

5. Редови

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

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

Повезан: Водич за почетнике за разумевање редова и приоритетних редова

Приоритетни редови су интегрална примена редова у многим виталним апликацијама као што је ЦПУ заказивање. У приоритетном реду, елементи су поређани према њиховом приоритету, а не према редоследу доласка.

6. Хрпе

Хрпе су врста бинарног стабла где су чворови распоређени у растућем или опадајућем редоследу. У Мин Хеап-у, кључна вредност родитеља је једнака или мања од оне његове деце, а коренски чвор садржи минималну вредност целе гомиле.

Слично томе, основни чвор Мак Хеап-а садржи максималну вредност кључа гомиле; морате задржати мин/мак својство гомиле у целој хрпи.

Повезан: Хеапс вс. Стацкс: Шта их издваја?

Хрпе имају много апликација због своје веома ефикасне природе; првенствено, приоритетни редови се често имплементирају кроз хрпе. Они су такође основна компонента у алгоритмима хеапсортирања.

Научите структуре података

Структуре података у почетку могу изгледати мучне, али посветите довољно времена и наћи ћете их лаке као колач.

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

7 алгоритама које сваки програмер треба да зна

Ови алгоритми су неопходни за рад сваког програмера.

Реад Нект

О аутору