Uvod v uporabo povezanih seznamov v Javi

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.



Kako deluje povezan seznam?

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.

Ustvarjanje povezanega seznama v Javi

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 oddelki 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 pomislekov 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:


public class Node {
private int Data;
private Node NextNode;
//constructor
public Node() {
Data = 0;
NextNode = null;
}
//getters and setters
public int getData() {
return Data;
}
public void setData(int data) {
Data = data;
}
public Node getNextNode() {
return NextNode;
}
public void setNextNode(Node nextNode) {
NextNode = nextNode;
}
}

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

Primer povezanega seznama

Spodaj je primer povezanega seznama v Javi.

public class LinkedList {
private Node Head;
//constructor
public LinkedList() {
Head = null;
}
}

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 metod vstavljanja povezanih seznamov je eden od razlogov, zakaj se razvijalec lahko odloči za uporabo te podatkovne strukture nad drugo podatkovno strukturo, na primer nizom (ki dovoljuje samo vstavljanje in brisanje z vrha).

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.

//insert node at front method
public void insertAtFront(int key) {
//create a new node using the node class
Node Temp = new Node();
//check if the Temp node was successfully created
//assign the data that was provides by the user to it
if(Temp != null) {
Temp.setData(key);
Temp.setNextNode(null);

//check if the head of the linked list is empty
//assign the node that was just created to the head position
if(Head == null) {
Head = Temp;
}
//if a node is already at the head position
//add the new node to it and set it as the head
else {
Temp.setNextNode(Head);
Head = 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.

public class Driver {
//executes the program
public static void main(String[] args) {
//create a new linked list called List
LinkedList List = new LinkedList();
//add each value to the front of the linked list as a new node
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?

bližnjica za spanje računalnika

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.

//display all nodes method
public void displayAllNodes() {
//create a new node call Temp and assign it to the head of the linked list
//if the head has a null value then the linked list is empty
Node Temp = Head;
if (Head == null){
System.out.println('The list is empty.');
return;
}
System.out.println('The List:');

while(Temp != null) {
//print the data in each node to the console(starting from the head)
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.

Primer uporabe metode Prikaži vsa vozlišča

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

//print the nodes in a linked list
List.displayAllNodes();

Izvajanje zgornje vrstice kode bo ustvarilo naslednji izhod v konzoli:

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 z enim vozliščem pomembno v podatkovni strukturi povezanega seznama.

Primer metode najdi vozlišče

Spodaj je primer uporabe metode vozlišča find.

//search for a single node using a key
public boolean findNode(int key) {
//create a new node and place it at the head of the linked list
Node Temp = Head;
//while the current node is not empty
//check if its data matches the key provided by the user
while (Temp != null) {
if (Temp.getData() == key) {
System.out.println('The node is in the list');
return true;
}
//move to the next node
Temp = Temp.getNextNode();
}
//if the key was not found in the linked list
System.out.println('The node is not in the list');
return false;
}

Z displayAllNodes metodo, ste potrdili, da je LinkedList vsebuje 5 parnih številk od 2 do 10. findNode zgornji primer lahko potrdi, ali 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.

//check if a node is in the linked list
List.findNode(4);

Zgornja koda bo ustvarila naslednji izhod v konzoli:

The node is in the list

Uporaba metode Izbriši vozlišče

Z istim primerom banke od zgoraj bi lahko stranka v bančni zbirki podatkov zaprla 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, izbriše to vozlišč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 key) {
Node Temp = Head;
Node prev = null;
//check if the head node holds the data
//and delete it
if (Temp != null && Temp.getData() == key) {
Head = Temp.getNextNode();
return;
}
//search the other nodes in the list
//and delete it
while (Temp != null) {
if (Temp.getNextNode().getData() == key ) {
prev = Temp.getNextNode().getNextNode();
Temp.setNextNode(prev);
return;
}
Temp = Temp.getNextNode();
}
}

Z uporabo primera metode brisanja vozlišča

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

wifi 2 nima veljavne konfiguracije ip
//delete the node that holds the data 4
List.findAndDelete(4);
//print all nodes in the linked list
List.displayAllNodes();

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

The List:
2 6 8 10

Zdaj lahko ustvarite povezane sezname v Javi

Č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 izpolniti razred povezanih 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 poskusili teh primerov v Javi?

Deliti Deliti Cvrkutati E-naslov Kako ustvariti in izvesti operacije nad nizi v Javi

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

Preberite Naprej Sorodne teme
  • Programiranje
  • Java
  • Programiranje
  • Nasveti za kodiranje
O avtorju Kadeisha Kean(21 objavljenih člankov)

Kadeisha Kean je razvijalka programske opreme in tehnična/tehnološka pisateljica. Ima izrazito sposobnost poenostavitve nekaterih najbolj zapletenih tehnoloških konceptov; izdelavo materiala, ki ga lahko vsak tehnološki začetnik zlahka razume. Strastno piše, razvija zanimivo programsko opremo in potuje po svetu (skozi dokumentarne filme).

Več od Kadeisha Kean

Naročite se na naše novice

Pridružite se našemu glasilu za tehnične nasvete, ocene, brezplačne e -knjige in ekskluzivne ponudbe!

Kliknite tukaj, da se naročite