Uvod v uporabo povezanih seznamov v Javi

Podatkovna struktura uporablja različne vnaprej določene metode za shranjevanje, pridobivanje in brisanje podatkov, kar doseže vrhunec pri ustvarjanju učinkovitih programov. Povezani seznam je priljubljena podatkovna struktura, ki jo sestavlja seznam vozlišč, ki so povezana (ali povezana).

Kako pa ustvarite povezan seznam v Javi? Poglejmo.

Vsak povezan seznam se začne s posebnim vozliščem, ki se pogosto imenuje "glava", ki ima odgovornost, da ves čas kaže na začetek seznama. Glava je pomembna, ker vsakemu vozlišču na povezanem seznamu ni treba fizično slediti svojemu nasledniku (kar pomeni, da predhodniku in nasledniku ni treba fizično sosediti).

Tako kot vsaka struktura podatkov tudi povezani seznam olajša ustvarjanje, iskanje, vstavljanje in uničenje prek nabora vnaprej določenih funkcij, ki jih lahko uporablja vsak razvijalec.

Program Java, ki je zasnovan za ustvarjanje in upravljanje povezanih seznamov, bo imel tri značilne razdelke; razred vozlišča, razred povezanega seznama in gonilnik. Čeprav se ti trije odseki lahko združijo v eno datoteko, obstaja načelo oblikovanja v računalništvu, znano kot "ločevanje skrbi", ki bi ga moral poznati vsak razvijalec.

Načelo ločevanja skrbi narekuje, da je treba ločiti vsak del kodeksa, ki obravnava posebno skrb. To načelo vam bo pomagalo ustvariti čistejšo (bolj berljivo) kodo in je idealno za ustvarjanje podatkovnih struktur.

Prvi korak pri ustvarjanju povezanega seznama v Javi je ustvarjanje razreda vozlišč. Razred vozlišča mora imeti dva atributa; eden od atributov bo predstavljal podatkovni del vozlišča, drugi atribut pa bo povezan del. Razred vozlišča mora imeti tudi konstruktor, getter in setter.

Povezano: Naučite se ustvarjati razrede v Javi

Pridobivalci in nastavitelji bodo drugim razredom (na primer razredu povezanih seznamov) omogočili dostop do različnih vozlišč na povezanem seznamu.

Primer razreda vozlišč

Spodaj je primer razreda vozlišč, da dobite predstavo o tem, kaj mislimo:

vozlišče javnega razreda {
zasebni int Podatki;
zasebno vozlišče NextNode;
//constructor
javno vozlišče () {
Podatki = 0;
NextNode = ničelno;
}
// pridobivalci in nastavitelji
public int getData () {
vrniti podatke;
}
public void setData (int data) {
Podatki = podatki;
}
javno vozlišče getNextNode () {
vrni NextNode;
}
public void setNextNode (Node nextNode) {
NextNode = nextNode;
}
}

V tem primeru bo atribut podatkov shranil celoštevilčne vrednosti. Zdaj, ko imate razred vozlišč, je čas, da se premaknete na povezan seznam.

Spodaj je primer povezanega seznama v Javi.

javni razred LinkedList {
zasebna glava vozlišča;
//constructor
javni LinkedList () {
Glava = nič;
}
}

Zgornja koda bo ustvarila povezan razred seznama, vendar pa je brez različnih operacij razred lahko enakovreden prazni lupini. Podatkovna struktura povezanega seznama ima več operacij, ki jih je mogoče uporabiti za izpolnitev:

• Vstavite spredaj.
• Vstavite na sredino.
• Vstavite na zadnji strani.

Povezano: Kako zgraditi podatkovne strukture z razredi JavaScript ES6

Zbirka načinov vstavljanja povezanih seznamov je eden od razlogov, zakaj se razvijalec lahko odloči za uporabo teh podatkov strukturo nad drugo podatkovno strukturo, kot so skladi (ki dovoljuje samo vstavljanje in brisanje od zgoraj).

Z uporabo metode Vstavi na sprednji strani

Metoda vstavljanja na sprednji strani, kot že ime pove, vstavi nove podatke (ali nova vozlišča) na sprednji strani povezanega seznama.

Vstavi na sprednji strani Primer metode

Spodaj je primer, kako bi v sprednji del seznama vstavili nove podatke.

 // metoda vstavljanja vozlišča spredaj
public void insertAtFront (int ključ) {
// ustvarimo novo vozlišče z uporabo razreda vozlišč
Node Temp = novo vozlišče ();
// preverimo, ali je bilo vozlišče Temp uspešno ustvarjeno
// dodelimo podatke, ki jih je dal uporabnik
if (Temp! = ničelno) {
Temp.setData (ključ);
Temp.setNextNode (ničelno);
// preverite, ali je glava povezanega seznama prazna
// dodelimo pravkar ustvarjeno vozlišče položaju glave
if (Head == null) {
Glava = Temp;
}
// če je vozlišče že v položaju glave
// mu dodamo novo vozlišče in ga nastavimo kot glavo
drugače {
Temp.setNextNode (glava);
Glava = Temp;
}
}
}

The insertAtFront metoda v zgornjem primeru omogoča uporabniku, da na določen povezan seznam doda nova vozlišča.

Primer vstavljanja na sprednji strani

Spodaj je primer, kako bi uporabili vložek spredaj.

šofer javnega razreda {
// izvaja program
public static void main (String [] args) {
// ustvarite nov povezan seznam, imenovan List
LinkedList List = nov LinkedList ();
// dodamo vsako vrednost na sprednji del povezanega seznama kot novo vozlišče
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

The Voznik class (ki je ime, ki je pogosto dodeljeno izvedljivemu razredu v Javi), uporablja razred LinkedList za ustvarjanje povezanega seznama petih parnih številk. Če pogledamo zgornjo kodo, bi moralo biti enostavno videti, da je številka "2" na vrhu glave na povezanem seznamu. Kako pa lahko to potrdite?

Z uporabo metode Prikaži vsa vozlišča

Metoda prikaza vseh vozlišč je bistvena metoda povezanega seznama. Brez tega razvijalec ne bo mogel videti vozlišč na povezanem seznamu. Potuje po povezanem seznamu (začenši z glave) in natisne podatke, shranjene v vsakem vozlišču, ki tvori seznam.

Primer prikaza vseh vozlišč

Spodaj je primer uporabe metode prikaza vseh zapiskov v Javi.

// prikaže metodo vseh vozlišč
public void displayAllNodes () {
// ustvarite nov klic vozlišča Temp in ga dodelite glavi povezanega seznama
// če ima glava ničelno vrednost, je povezan seznam prazen
Node Temp = Head;
if (Head == null) {
System.out.println ("Seznam je prazen.");
vrnitev;
}
System.out.println ("Seznam:");
medtem ko (Temp! = null) {
// natisnemo podatke v vsakem vozlišču na konzolo (začenši z glave)
System.out.print (Temp.getData () + "");
Temp = Temp.getNextNode ();
} 
}

Zdaj, ko je displayAllNodes je bila dodana metoda LinkedList razred, si lahko ogledate povezani seznam tako, da razredu gonilnikov dodate eno vrstico kode.

Z uporabo metode prikaza vseh vozlišč

Spodaj boste videli, kako bi uporabili metodo prikaza vseh vozlišč.

// natisnemo vozlišča na povezanem seznamu
List.displayAllNodes (); 

Izvajanje zgornje vrstice kode bo v konzoli ustvarilo naslednje rezultate:

Seznam:

2 4 6 8 10

Z uporabo metode Najdi vozlišče

Obstajali bodo primeri, ko bo uporabnik želel najti določeno vozlišče na povezanem seznamu.

Na primer, banka, ki ima na milijone strank, ne bi bilo praktično natisniti vseh strank v njihovo bazo podatkov, ko morajo videti le podatke o določeni stranki.

Zato namesto uporabe displayAllNodes metoda, učinkovitejša metoda je iskanje enotnega vozlišča, ki vsebuje zahtevane podatke. Zato je iskanje metode enega vozlišča pomembno v podatkovni strukturi povezanega seznama.

Primer metode najdi vozlišča

Spodaj je primer uporabe metode find node.

// poiščemo eno samo vozlišče s ključem
javno logično findNode (int ključ) {
// ustvarite novo vozlišče in ga postavite na čelo povezanega seznama
Node Temp = Head;
// medtem ko trenutno vozlišče ni prazno
// preverimo, ali se njegovi podatki ujemajo s ključem, ki ga je dal uporabnik
medtem ko (Temp! = null) {
if (Temp.getData () == ključ) {
System.out.println ("Vozlišče je na seznamu"); 
vrni true;
}
// premaknite se na naslednje vozlišče
Temp = Temp.getNextNode ();
}
// če ključa ni bilo na povezanem seznamu
System.out.println ("Vozlišče ni na seznamu"); 
return false;
}

Z displayAllNodes metodo, ste potrdili, da je LinkedList vsebuje 5 parnih številk od 2 do 10. The findNode zgornji primer lahko potrdi, da je ena od teh parnih številk številka 4, tako da preprosto pokličete metodo v razredu gonilnikov in navedete številko kot parameter.

Z uporabo metode metode Find Node

Spodaj je primer, kako bi v praksi uporabili metodo najdišča vozlišča.

// preverimo, ali je vozlišče na povezanem seznamu
List.findNode (4);

Zgornja koda bo ustvarila naslednji izhod v konzoli:

Vozlišče je na seznamu

Uporaba metode Izbriši vozlišče

Z istim primerom banke od zgoraj bi stranka v bančni zbirki morda želela zapreti svoj račun. Tu bo uporabna metoda brisanja vozlišča. To je najbolj zapletena metoda povezanega seznama.

Metoda Delete a Node išče določeno vozlišče, to vozlišče izbriše in poveže prejšnje vozlišče s tistim, ki sledi izbrisanemu vozlišču.

Brisanje primera metode vozlišča

Spodaj je primer metode brisanja vozlišča.

public void findAndDelete (int ključ) { 
Node Temp = Head; 
Vozlišče prev = nič; 
// preverimo, ali glavno vozlišče vsebuje podatke 
// in ga izbrišemo 
if (Temp! = null && Temp.getData () == ključ) { 
Head = Temp.getNextNode (); 
vrnitev; 
} 
// poiščite druga vozlišča na seznamu 
// in ga izbrišemo 
medtem ko (Temp! = null) { 
if (Temp.getNextNode (). getData () == ključ) { 
prev = Temp.getNextNode (). getNextNode (); 
Temp.setNextNode (prejšnja); 
vrnitev; 
} 
Temp = Temp.getNextNode (); 
} 
} 

Z uporabo primera metode brisanja vozlišča

Spodaj je primer uporabe metode brisanja vozlišča v praksi.

// izbrišemo vozlišče, ki vsebuje podatke 4
List.findAndDelete (4);
// natisnemo vsa vozlišča na povezanem seznamu
List.displayAllNodes ();

Z uporabo zgornjih dveh vrstic kode v že obstoječem razredu Driver bo v konzoli ustvarjen naslednji izhod:

Seznam:
2 6 8 10

Če ste prišli do konca tega učnega članka, se boste naučili:

• Kako ustvariti razred vozlišča.
• Kako ustvariti povezan razred seznama.
• Kako napolniti povezani seznam seznamov s svojimi vnaprej določenimi metodami.
• Kako ustvariti razred gonilnikov in z različnimi metodami povezanih seznamov doseči želeni rezultat.

Povezani seznam je le ena od številnih podatkovnih struktur, ki jih lahko uporabite za shranjevanje, pridobivanje in brisanje podatkov. Ker imate vse, kar potrebujete za začetek, zakaj ne bi sami preizkusili teh primerov v Javi?

Kako ustvariti in izvesti operacije nad nizi v Javi

Se učite Jave? Naj matrike z lahkoto ravnajo z vašimi podatki.

Preberite Naprej

O avtorju