Увод у употребу повезаних листа у Јави

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

Али како створити повезану листу у Јави? Хајде да погледамо.

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

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

Јава програм који је дизајниран за креирање и управљање повезаним листама имаће три карактеристична одељка; класа чвора, класа повезане листе и управљачки програм. Иако се ова три одељка могу комбиновати у једној датотеци, у рачунарској науци постоји принцип дизајна познат као "раздвајање брига" који би сваки програмер требао знати.

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

Први корак у креирању повезане листе у Јави је креирање класе чвора. Класа чвора треба да има два атрибута; један од атрибута представљаће део података чвора, док ће други атрибут представљати повезани део. Класа чвора такође треба да има конструктор, геттере и сеттере.

Повезан: Научите како да креирате класе у Јави

Добављачи и постављачи ће омогућити другим класама (попут класе повезане листе) да приступе различитим чворовима унутар повезане листе.

Пример класе чвора

Испод је пример класе чворова да бисте стекли представу о томе шта мислимо:

чвор јавне класе {
привате инт Подаци;
приватни чвор НектНоде;
//constructor
јавни чвор () {
Подаци = 0;
НектНоде = нулл;
}
// преузимачи и постављачи
публиц инт гетДата () {
ретурн Дата;
}
публиц воид сетДата (инт дата) {
Подаци = подаци;
}
јавни чвор гетНектНоде () {
ретурн НектНоде;
}
публиц воид сетНектНоде (Ноде нектНоде) {
НектНоде = нектНоде;
}
}

У овом примеру, атрибут података чуваће целобројне вредности. Сада када имате класу чворова, време је да пређете на повезану листу.

Испод је пример повезане листе у Јави.

јавна класа ЛинкедЛист {
привате Ноде Хеад;
//constructor
јавна ЛинкедЛист () {
Хеад = нулл;
}
}

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

• Уметните на предњој страни.
• Уметните у средину.
• Уметните позади.

Повезан: Како изградити структуре података помоћу ЈаваСцрипт ЕС6 класа

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

Коришћењем методе Инсерт ат тхе Фронт

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

Уметните на предњој страни Пример методе

Испод је пример како бисте уметнули нове податке испред своје листе.

 // метода уметања чвора на предњој страни
публиц воид инсертАтФронт (инт кључ) {
// креирање новог чвора помоћу класе чвора
Ноде Темп = нев Ноде ();
// проверавамо да ли је чвор Темп успешно креиран
// додељујемо податке које је дао корисник
иф (Темп! = нулл) {
Темп.сетДата (кључ);
Темп.сетНектНоде (нулл);
// проверавамо да ли је глава повезане листе празна
// додељује чвор који је управо креиран на положај главе
иф (Хеад == нулл) {
Хеад = Темп;
}
// ако је чвор већ у положају главе
// додајемо му нови чвор и постављамо га као главу
елсе {
Темп.сетНектНоде (Хеад);
Хеад = Темп;
}
}
}

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

Примена уметка на предњем примеру

Испод је пример како бисте применили уметак на предњој страни.

возач јавне класе {
// извршава програм
публиц статиц воид маин (Стринг [] аргс) {
// креирање нове повезане листе под називом Листа
ЛинкедЛист Лист = нев ЛинкедЛист ();
// додамо сваку вредност на предњу страну повезане листе као нови чвор
Лист.инсертАтФронт (10);
Лист.инсертАтФронт (8);
Лист.инсертАтФронт (6);
Лист.инсертАтФронт (4);
Лист.инсертАтФронт (2);
}
}

Тхе Дривер цласс (што је име које се често додељује извршној класи у Јави), користи класу ЛинкедЛист за креирање повезане листе од пет парних бројева. Гледајући горњи код, требало би бити лако видети да је број "2" на челу позиције на повезаној листи. Али како то можете потврдити?

Користећи методу Прикажи све чворове

Метода приказа свих чворова је битна метода повезане листе. Без тога, програмер неће моћи да види чворове на повезаној листи. Путује кроз повезану листу (почевши од главе) штампајући податке ускладиштене у сваком чвору који чини листу.

Пример приказа свих чворова

Испод је пример коришћења методе приказа свих напомена у Јави.

// приказује метод свих чворова
публиц воид дисплаиАллНодес () {
// креирамо нови чворни позив Темп и додељујемо га глави повезане листе
// ако глава има нулту вредност онда је повезана листа празна
Ноде Темп = Хеад;
иф (Хеад == нулл) {
Систем.оут.принтлн ("Листа је празна.");
ретурн;
}
Систем.оут.принтлн ("Листа:");
вхиле (Темп! = нулл) {
// исписује податке у сваком чвору на конзолу (почевши од главе)
Систем.оут.принт (Темп.гетДата () + "");
Темп = Темп.гетНектНоде ();
} 
}

Сада када је дисплаиАллНодес метода је додата у ЛинкедЛист класе можете погледати повезану листу додавањем једне линије кода у класу управљачког програма.

Употреба примера методе Прикажи све чворове

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

// штампамо чворове на повезаној листи
Лист.дисплаиАллНодес (); 

Извршавање горње линије кода ће произвести следећи излаз у конзоли:

Листа:

2 4 6 8 10

Коришћењем методе Финд Ноде

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

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

Стога, уместо да користите дисплаиАллНодес метода, ефикаснији метод је проналажење једног чвора који садржи потребне податке. Због тога је тражење методе једног чвора важно у структури података повезане листе.

Пример методе проналажења чвора

Испод је пример коришћења методе финд ноде.

// претражујемо један чвор помоћу кључа
јавни логички финдНоде (инт кључ) {
// креирамо нови чвор и постављамо га на чело повезане листе
Ноде Темп = Хеад;
// док тренутни чвор није празан
// проверавамо да ли се његови подаци подударају са кључем који је дао корисник
вхиле (Темп! = нулл) {
иф (Темп.гетДата () == кеи) {
Систем.оут.принтлн ("Чвор је на листи"); 
ретурн труе;
}
// прелазак на следећи чвор
Темп = Темп.гетНектНоде ();
}
// ако кључ није пронађен на повезаној листи
Систем.оут.принтлн ("Чвор није на листи"); 
ретурн фалсе;
}

Са дисплаиАллНодес методом, потврдили сте да ЛинкедЛист садржи 5 парних бројева од 2 до 10. Тхе финдНоде горњи пример може потврдити да ли је један од тих парних бројева број 4 једноставним позивањем методе у класи управљачких програма и давањем броја као параметра.

Пример примене методе Финд Ноде

Испод је пример како бисте у пракси користили методу проналажења чвора.

// проверавамо да ли је чвор на повезаној листи
Лист.финдНоде (4);

Горњи код ће произвести следећи излаз у конзоли:

Чвор је на листи

Употреба методе Делете а Ноде Метход

Користећи исти пример банке одозго, клијент у бази података банке могао би пожелети да затвори свој рачун. Овде ће метода брисања чвора бити корисна. То је најсложенији метод повезане листе.

Метода Делете а Ноде тражи дати чвор, брише га и повезује претходни чвор са оним који следи иза чвора који је избрисан.

Избришите пример методе чвора

Испод је пример методе брисања чвора.

публиц воид финдАндДелете (инт кључ) { 
Ноде Темп = Хеад; 
Чвор прев = нулл; 
// проверавамо да ли чвор хеад садржи податке 
// и обришите га 
иф (Темп! = нулл && Темп.гетДата () == кеи) { 
Хеад = Темп.гетНектНоде (); 
ретурн; 
} 
// претражујемо остале чворове на листи 
// и обришите га 
вхиле (Темп! = нулл) { 
иф (Темп.гетНектНоде (). гетДата () == кључ) { 
прев = Темп.гетНектНоде (). гетНектНоде (); 
Темп.сетНектНоде (претходна); 
ретурн; 
} 
Темп = Темп.гетНектНоде (); 
} 
} 

Коришћење примера Методе брисања чвора

Испод је пример коришћења методе брисања чвора у пракси.

// брисање чвора који садржи податке 4
Лист.финдАндДелете (4);
// штампа све чворове на повезаној листи
Лист.дисплаиАллНодес ();

Коришћење два горња реда кода у већ постојећој класи Дривер ће произвести следећи излаз у конзоли:

Листа:
2 6 8 10

Ако сте дошли до краја овог водича, научићете:

• Како креирати класу чвора.
• Како да креирате класу повезане листе.
• Како попунити класу повезане листе унапред дефинисаним методама.
• Како креирати класу управљачких програма и користити различите методе повезане листе да бисте постигли жељени резултат.

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

Како креирати и изводити операције над низовима у Јави

Учење Јаве? Допустите низовима да са лакоћом обрађују ваше податке.

Прочитајте следеће

О аутору