Uvod u korištenje povezanih popisa u Javi

Struktura podataka koristi različite unaprijed definirane metode za pohranu, dohvaćanje i brisanje podataka što kulminira stvaranjem učinkovitih programa. Povezani popis popularna je struktura podataka koja se sastoji od popisa čvorova koji su povezani (ili povezani).

Ali kako stvoriti povezani popis u Javi? Pogledajmo.

Svaki povezani popis započinje posebnim čvorom koji se često naziva i "glava", koji ima odgovornost da u svakom trenutku pokazuje na početak popisa. Zaglavlje je važno jer svaki čvor na povezanom popisu ne mora fizički pratiti svog nasljednika (što znači da prethodnik i nasljednik ne moraju biti fizički susjedni).

Kao i svaka struktura podataka, povezani popis olakšava stvaranje, dohvaćanje, umetanje i uništavanje putem skupa unaprijed definiranih funkcija koje može koristiti svaki programer.

Java program koji je dizajniran za stvaranje i upravljanje povezanim popisima imat će tri posebna odjeljka; klasa čvora, klasa povezanog popisa i upravljački program. Iako se ta tri odjeljka mogu kombinirati u jednu datoteku, u računalnoj znanosti postoji princip dizajna poznat kao "razdvajanje briga" koji bi svaki programer trebao znati.

Načelo razdvajanja zabrinutosti nalaže da se svaki dio koda koji se bavi određenom zabrinutošću treba odvojiti. Ovo načelo pomoći će vam u stvaranju čistijeg (čitljivijeg) koda i idealno je za stvaranje struktura podataka.

Prvi korak u stvaranju povezanog popisa u Javi je stvaranje klase čvora. Klasa čvora trebala bi imati dva atributa; jedan od atributa predstavljat će dio podataka čvora, dok će drugi atribut predstavljati povezani dio. Klasa čvora također treba imati konstruktor, gettere i settere.

Povezano: Saznajte kako stvoriti klase u Javi

Dobavljači i postavljači dopustit će drugim klasama (poput klase povezanog popisa) pristup različitim čvorovima unutar povezanog popisa.

Primjer klase čvora

Ispod je primjer klase čvora kako biste stekli uvid u to što mislimo:

čvor javne klase {
private int Podaci;
privatni čvor NextNode;
//constructor
javni čvor () {
Podaci = 0;
NextNode = null;
}
// preuzimatelji i postavljači
public int getData () {
vratiti podatke;
}
public void setData (int podaci) {
Podaci = podaci;
}
javni čvor getNextNode () {
return NextNode;
}
public void setNextNode (Čvor nextNode) {
NextNode = nextNode;
}
}

U ovom primjeru atribut podataka pohranit će cjelobrojne vrijednosti. Sada kada imate klasu čvora, vrijeme je da prijeđete na povezani popis.

Ispod je primjer povezanog popisa u Javi.

LinkedList javne klase {
privatna glava čvora;
//constructor
javni LinkedList () {
Glava = nula;
}
}

Gornji kôd će stvoriti povezanu klasu popisa, međutim, bez različitih operacija, klasa se može smatrati ekvivalentom prazne ljuske. Struktura podataka povezanog popisa ima nekoliko operacija koje se mogu upotrijebiti za njezino popunjavanje:

• Umetnite sprijeda.
• Umetnite u sredinu.
• Umetnite sa stražnje strane.

Povezano: Kako izgraditi strukture podataka s JavaScript ES6 klasama

Zbirka metoda umetanja povezanog popisa jedan je od razloga zašto se razvojni programer može odlučiti za korištenje ovih podataka strukturu nad drugom strukturom podataka kao što su hrpe (što dopušta samo umetanje i brisanje s vrha).

Korištenjem metode Insert at the Front

Metoda umetanja na prednjoj strani, kako naziv govori, ubacuje nove podatke (ili nove čvorove) na prednjoj strani povezanog popisa.

Umetnite na prednjoj strani Primjer metode

Ispod je primjer kako biste umetnuli nove podatke na prednju stranu popisa.

 // metoda umetanja čvora na prednjoj strani
public void insertAtFront (int ključ) {
// kreiranje novog čvora pomoću klase čvora
Čvor Temp = novi čvor ();
// provjeravamo je li Temp čvor uspješno kreiran
// dodjeljuje podatke koje je dao korisnik
if (Temp! = null) {
Temp.setData (ključ);
Temp.setNextNode (null);
// provjeravamo je li glava povezanog popisa prazna
// dodjeljuje čvor koji je upravo stvoren položaju glave
if (Head == null) {
Glava = Temp;
}
// ako je čvor već u položaju glave
// dodajemo mu novi čvor i postavljamo ga kao glavu
drugo {
Temp.setNextNode (glava);
Glava = Temp;
}
}
}

The insertAtFront metoda u gornjem primjeru omogućuje korisniku dodavanje novih čvorova na zadani povezani popis.

Primjena Umetanja na prednjoj strani Primjer

Dolje je primjer kako biste primijenili umetak na prednjoj strani.

vozač javne klase {
// izvršava program
public static void main (String [] args) {
// izrada novog povezanog popisa pod nazivom List
LinkedList List = novi LinkedList ();
// dodamo svaku vrijednost na prednju stranu povezanog popisa kao novi čvor
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

The Vozač class (što je naziv koji se često dodjeljuje izvršnoj klasi u Javi), koristi klasu LinkedList za stvaranje povezanog popisa od pet parnih brojeva. Gledajući gornji kôd, trebalo bi biti lako vidjeti da je broj "2" na čelu pozicije na povezanom popisu. Ali kako to možete potvrditi?

Korištenjem metode Prikaži sve čvorove

Metoda prikaza svih čvorova bitna je metoda povezane liste. Bez toga programer neće moći vidjeti čvorove na povezanom popisu. Putuje kroz povezani popis (počevši od glave) ispisujući podatke pohranjene u svakom čvoru koji čini popis.

Primjer metode prikaza svih čvorova

Ispod je primjer korištenja metode prikaza svih bilješki u Javi.

// metoda prikaza svih čvorova
public void displayAllNodes () {
// izraditi novi poziv čvora Temp i dodijeliti ga zaglavlju povezanog popisa
// ako glava ima null vrijednost tada je povezani popis prazan
Čvor Temp = Glava;
if (Head == null) {
System.out.println ("Popis je prazan.");
povratak;
}
System.out.println ("Popis:");
while (Temp! = null) {
// ispisuje podatke u svakom čvoru na konzolu (počevši od glave)
System.out.print (Temp.getData () + "");
Temp = Temp.getNextNode ();
} 
}

Sada kada je displayAllNodes metoda je dodana u LinkedList klase možete pogledati povezani popis dodavanjem jednog reda koda u klasu upravljačkog programa.

Primjer metode Prikaz svih čvorova

U nastavku ćete vidjeti kako biste koristili metodu prikaza svih čvorova.

// ispisuje čvorove na povezanom popisu
List.displayAllNodes (); 

Izvođenje gornje linije koda proizvest će sljedeći izlaz u konzoli:

Popis:

2 4 6 8 10

Korištenjem metode Find Node

Bit će slučajeva kada će korisnik htjeti pronaći određeni čvor na povezanom popisu.

Na primjer, ne bi bilo praktično da banka koja ima milijune klijenata ispisuje sve klijente u svoju bazu podataka samo kad trebaju vidjeti pojedinosti o određenom klijentu.

Stoga, umjesto korištenja displayAllNodes Metoda, učinkovitija metoda je pronaći pojedinačni čvor koji sadrži potrebne podatke. Zbog toga je traženje metode s jednim čvorom važno u strukturi podataka povezanog popisa.

Primjer metode pronalaženja čvora

Dolje je primjer korištenja metode čvora za pronalaženje.

// traženje jednog čvora pomoću ključa
javni logički findNode (int ključ) {
// stvoriti novi čvor i postaviti ga na čelo povezanog popisa
Čvor Temp = Glava;
// dok trenutni čvor nije prazan
// provjerava odgovaraju li njegovi podaci ključu koji je dao korisnik
while (Temp! = null) {
if (Temp.getData () == ključ) {
System.out.println ("Čvor je na popisu"); 
return true;
}
// prelazak na sljedeći čvor
Temp = Temp.getNextNode ();
}
// ako ključ nije pronađen na povezanom popisu
System.out.println ("Čvor nije na popisu"); 
return false;
}

Uz displayAllNodes metodom, potvrdili ste da LinkedList sadrži 5 parnih brojeva od 2 do 10. The findNode gornji primjer može potvrditi je li jedan od tih parnih brojeva broj 4 jednostavnim pozivanjem metode u klasi upravljačkog programa i davanjem broja kao parametra.

Primjer metode Find Node Method

Ispod je primjer kako biste u praksi koristili metodu pronalaženja čvora.

// provjeravamo je li čvor na povezanom popisu
List.findNode (4);

Gornji kôd će proizvesti sljedeći izlaz u konzoli:

Čvor je na popisu

Korištenje metode Brisanje čvora

Koristeći isti primjer banke odozgo, klijent u bazi podataka banke mogao bi poželjeti zatvoriti svoj račun. Ovdje će metoda brisanja čvora biti korisna. To je najsloženija metoda povezanog popisa.

Metoda Delete a Node traži određeni čvor, briše ga i povezuje prethodni čvor s onim koji slijedi iza čvora koji je izbrisan.

Brisanje primjera metode čvora

Ispod je primjer metode brisanja čvora.

public void findAndDelete (int ključ) { 
Čvor Temp = Glava; 
Čvor prev = null; 
// provjerava sadrži li glavni čvor podatke 
// i izbrisati ga 
if (Temp! = null && Temp.getData () == ključ) { 
Head = Temp.getNextNode (); 
povratak; 
} 
// pretražujemo ostale čvorove na popisu 
// i izbrisati ga 
while (Temp! = null) { 
if (Temp.getNextNode (). getData () == ključ) { 
prev = Temp.getNextNode (). getNextNode (); 
Temp.setNextNode (prethodna); 
povratak; 
} 
Temp = Temp.getNextNode (); 
} 
} 

Primjer metode Brisanje čvora

Dolje je primjer primjene metode brisanja čvora u praksi.

// brisanje čvora koji sadrži podatke 4
List.findAndDelete (4);
// ispisati sve čvorove na povezanom popisu
List.displayAllNodes ();

Korištenje dva gornja retka koda u već postojećoj klasi Driver će proizvesti sljedeće rezultate u konzoli:

Popis:
2 6 8 10

Ako ste došli do kraja ovog vodičkog članka, naučit ćete:

• Kako stvoriti klasu čvora.
• Kako stvoriti povezanu klasu popisa.
• Kako popuniti povezanu klasu popisa sa svojim unaprijed definiranim metodama.
• Kako stvoriti klasu upravljačkih programa i koristiti različite metode povezanih popisa za postizanje željenog rezultata.

Povezani popis samo je jedna od mnogih struktura podataka koje možete koristiti za spremanje, dohvaćanje i brisanje podataka. Budući da imate sve što vam je potrebno za početak, zašto ne biste sami isprobali ove primjere u Javi?

Kako stvoriti i izvesti operacije nad nizovima u Javi

Učenje Jave? Dopustite nizovima da s lakoćom obrađuju vaše podatke.

Pročitajte Dalje

O autoru