Bevezetés a linkelt listák használatába a Java -ban

Az adatstruktúra különböző előre meghatározott módszereket használ az adatok tárolására, visszakeresésére és törlésére, ami hatékony programok létrehozásában végződik. A linkelt lista egy népszerű adatstruktúra, amely összekapcsolt (vagy összekapcsolt) csomópontok listájából áll.

De hogyan hozhat létre linkelt listát a Java -ban? Lássuk.

Minden linkelt lista egy speciális csomóponttal kezdődik, amelyet gyakran "fejnek" neveznek, és amelynek feladata, hogy mindenkor a lista elejére mutasson. A fej azért fontos, mert a hivatkozott lista minden csomópontjának nem kell fizikailag követnie az utódját (vagyis az elődnek és az utódnak nem kell fizikailag szomszédosnak lenniük).

Mint minden adatstruktúra, a linkelt lista is megkönnyíti a létrehozást, visszakeresést, beillesztést és megsemmisítést az előre meghatározott függvények révén, amelyeket bármely fejlesztő használhat.

A hivatkozott listák létrehozására és kezelésére tervezett Java programnak három megkülönböztető szakasza lesz; a csomópont osztály, a linkelt lista osztály és az illesztőprogram. Bár ez a három szakasz egy fájlban egyesíthető, a számítástechnikában van egy tervezési elv, amelyet "aggodalmak szétválasztásának" neveznek, és amelyet minden fejlesztőnek tudnia kell.

Az aggályok szétválasztása elve azt írja elő, hogy a kód minden olyan részét el kell különíteni, amely egy adott problémát kezel. Ez az elv segít tisztább (olvashatóbb) kód létrehozásában, és ideális adatstruktúrák létrehozásához.

Az összekapcsolt lista létrehozásának első lépése a Java -ban egy csomópont -osztály létrehozása. Egy csomópont osztálynak két attribútummal kell rendelkeznie; az egyik attribútum a csomópont adatrészét, míg a másik attribútum a kapcsolt részt képviseli. A csomópontosztálynak rendelkeznie kell konstruktorral, getterekkel és setterekkel is.

Összefüggő: Ismerje meg, hogyan hozhat létre osztályokat Java -ban

A getters és a setters lehetővé teszi, hogy más osztályok (például a linkelt lista osztály) hozzáférjenek a linkelt listán belüli különböző csomópontokhoz.

Példa csomópont osztályra

Az alábbiakban bemutatunk egy csomópont osztály példát, hogy megértsük, mire gondolunk:

public class Node {
privát int Adatok;
privát csomópont NextNode;
//constructor
public Node () {
Adatok = 0;
NextNode = null;
}
// getters és setters
public int getData () {
adatok visszaadása;
}
public void setData (int adatok) {
Adatok = adatok;
}
public Node getNextNode () {
return NextNode;
}
public void setNextNode (Node nextNode) {
NextNode = nextNode;
}
}

Ebben a példában az adatattribútum egész számokat tárol. Most, hogy megvan a csomópont -osztály, ideje továbblépni a linkelt listára.

Az alábbiakban egy példa a Java -ban található linkelt listára.

public class LinkedList {
privát csomópontfej;
//constructor
public LinkedList () {
Fej = null;
}
}

A fenti kód létrehoz egy összekapcsolt listaosztályt, azonban különféle műveletek nélkül az osztály egy üres héj megfelelőjének tekinthető. Az összekapcsolt lista adatstruktúrája számos műveletet tartalmaz a kitöltéséhez:

• Betét az elején.
• Helyezze be a közepébe.
• Helyezze be a hátsó részbe.

Összefüggő: Adatstruktúrák létrehozása JavaScript ES6 osztályokkal

A beillesztési módszerek összekapcsolt listagyűjteménye az egyik ok, amiért a fejlesztő úgy dönthet, hogy ezeket az adatokat használja struktúrát egy másik adatstruktúra, például verem fölött (amely csak felülről teszi lehetővé a beillesztést és törlést).

Az Insert in the Front módszer használata

A beillesztés az elülső metódusban, ahogy a neve is sugallja, új adatokat (vagy új csomópontokat) szúr be a linkelt lista elejére.

Példa beszúrásra az elülső módszerre

Az alábbiakban egy példa látható arra, hogyan illeszthet be új adatokat a lista elejére.

 // csomópont beszúrása az elülső metódusba
public void insertAtFront (int kulcs) {
// hozzon létre egy új csomópontot a csomópont -osztály használatával
Node Temp = new Node ();
// ellenőrizze, hogy a Temp csomópont sikeresen létrejött -e
// rendelje hozzá a felhasználó által megadott adatokat
if (Temp! = null) {
Temp.setData (kulcs);
Temp.setNextNode (null);
// ellenőrizze, hogy a linkelt lista feje üres -e
// rendelje hozzá az éppen létrehozott csomópontot a fej pozíciójához
if (Head == null) {
Fej = Hőmérséklet;
}
// ha egy csomópont már a fej pozíciójában van
// add hozzá az új csomópontot, és állítsd be fejként
más {
Temp.setNextNode (Head);
Fej = Hőmérséklet;
}
}
}

Az insertAtFront módszer a fenti példában lehetővé teszi a felhasználó számára, hogy új csomópontokat adjon hozzá egy adott linkelt listához.

Példa a betét alkalmazására az elülső oldalon

Az alábbiakban egy példa látható arra, hogyan kell a betétet elöl alkalmazni.

public class Driver {
// végrehajtja a programot
public static void main (String [] args) {
// hozzon létre egy új összekapcsolt listát Lista néven
LinkedList List = új LinkedList ();
// minden érték hozzáadása a csatolt lista elejéhez új csomópontként
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

Az Sofőr osztály (ez az a név, amelyet gyakran a Java futtatható osztályához rendelnek), a LinkedList osztályt használva öt páros számból álló hivatkozott listát hoz létre. Ha megnézzük a fenti kódot, könnyen belátható, hogy a "2" szám a fejlécben van a linkelt listában. De hogyan tudod ezt megerősíteni?

Az Összes csomópont megjelenítése módszer használata

Az összes csomópont megjelenítése módszer lényeges hivatkozott listamódszer. Enélkül a fejlesztő nem fogja látni a csomópontokat a linkelt listában. Végigjárja a linkelt listát (a fejtől kezdve), és kinyomtatja a listát alkotó minden csomópontban tárolt adatokat.

Példa az összes csomópont megjelenítésére

Az alábbiakban bemutatunk egy példát az összes jegyzet megjelenítése módszer használatára a Java -ban.

// az összes csomópont megjelenítése módszer
public void displayAllNodes () {
// hozzon létre egy új csomópont -hívást Temp, és rendelje hozzá a linkelt lista fejéhez
// ha a fej null értékű, akkor a linkelt lista üres
Node Temp = Fej;
if (Head == null) {
System.out.println ("A lista üres.");
Visszatérés;
}
System.out.println ("A lista:");
while (Temp! = null) {
// az egyes csomópontok adatainak nyomtatása a konzolra (a fejtől kezdve)
System.out.print (Temp.getData () + "");
Temp = Temp.getNextNode ();
} 
}

Most, hogy a displayAllNodes módszer került hozzáadásra a LinkedList osztályban megtekintheti a linkelt listát egyetlen kódsor hozzáadásával a vezetőosztályhoz.

Példa az Összes csomópont megjelenítése módszer használatára

Az alábbiakban láthatja, hogyan használja az összes csomópont megjelenítése módszert.

// a csomópontok kinyomtatása egy linkelt listában
List.displayAllNodes (); 

A fenti kódsor végrehajtása a következő kimenetet eredményezi a konzolban:

A lista:

2 4 6 8 10

A Find Node módszer használata

Előfordulhatnak olyan esetek, amikor a felhasználó egy adott csomópontot szeretne megtalálni a linkelt listában.

Például nem lenne praktikus, ha egy millió millió ügyféllel rendelkező bank kinyomtatná az összes ügyfél adatait az adatbázisában, amikor csak egy adott ügyfél adatait kell látnia.

Ezért ahelyett, hogy a displayAllNodes módszer, hatékonyabb módszer a szükséges adatokat tartalmazó egyetlen csomópont megkeresése. Ezért fontos az egyetlen csomópont -módszer keresése a linkelt lista adatszerkezetében.

Példa a csomópont keresésére

Az alábbiakban egy példa található a find node módszer használatára.

// egyetlen csomópont keresése kulcs segítségével
public boolean findNode (int kulcs) {
// hozzon létre egy új csomópontot, és helyezze a linkelt lista élére
Node Temp = Fej;
// míg az aktuális csomópont nem üres
// ellenőrizze, hogy az adatok megegyeznek -e a felhasználó által megadott kulccsal
while (Temp! = null) {
if (Temp.getData () == kulcs) {
System.out.println ("A csomópont szerepel a listában"); 
return true;
}
// lépés a következő csomópontra
Temp = Temp.getNextNode ();
}
// ha a kulcs nem található a linkelt listában
System.out.println ("A csomópont nincs a listában"); 
hamis visszatérés;
}

A... val displayAllNodes módszerrel megerősítette, hogy a LinkedList 5 páros számot tartalmaz 2 -től 10 -ig. Az findNode A fenti példa megerősíti, hogy a páros számok egyike a 4 -es szám, ha egyszerűen meghívja a metódust a vezetőosztályban, és megadja a számot paraméterként.

Példa a csomópont keresése módszerre

Az alábbiakban bemutatunk egy példát arra, hogyan használhatja a find node metódust a gyakorlatban.

// ellenőrizze, hogy egy csomópont szerepel -e a linkelt listában
List.findNode (4);

A fenti kód a következő kimenetet eredményezi a konzolban:

A csomópont szerepel a listában

A Csomópont törlése módszer használata

Ugyanezt a banki példát használva felülről, a bank adatbázisában lévő ügyfél esetleg bezárja a fiókját. Itt lesz hasznos a csomópont törlése módszer. Ez a legösszetettebb linkelt listamódszer.

A Csomópont törlése módszer egy adott csomópontot keres, törli azt, és összekapcsolja az előző csomópontot a törölt csomópontot követő csomóponttal.

Példa csomópont -módszer törlésére

Az alábbiakban egy példa a csomópont törlése módszerre.

public void findAndDelete (int kulcs) { 
Node Temp = Fej; 
Node prev = null; 
// ellenőrizze, hogy a fejcsomópont tartalmazza -e az adatokat 
// és törölje 
if (Temp! = null && Temp.getData () == kulcs) { 
Fej = Temp.getNextNode (); 
Visszatérés; 
} 
// keresés a lista többi csomópontjában 
// és törölje 
while (Temp! = null) { 
if (Temp.getNextNode (). getData () == kulcs) { 
prev = Temp.getNextNode (). getNextNode (); 
Temp.setNextNode (előző); 
Visszatérés; 
} 
Temp = Temp.getNextNode (); 
} 
} 

Példa a Csomópont törlése módszerre

Az alábbiakban egy példa látható a csomópont törlése módszer gyakorlatban történő használatára.

// az adatokat tároló csomópont törlése 4
List.findAndDelete (4);
// a linkelt lista összes csomópontjának kinyomtatása
List.displayAllNodes ();

A fenti két kódsor használata a meglévő Driver osztályban a következő kimenetet eredményezi a konzolon:

A lista:
2 6 8 10

Ha az oktató cikk végére ért, megtanulta:

• Csomópont -osztály létrehozása.
• Linkelt listaosztály létrehozása.
• Hogyan lehet feltölteni egy összekapcsolt listaosztályt az előre meghatározott módszerekkel.
• Hogyan hozhat létre illesztőprogram osztályt, és hogyan használhatja a különböző linkelt listamódszereket a kívánt eredmény eléréséhez.

A linkelt lista csak egy a sok adatstruktúrából, amelyekkel adatokat tárolhat, visszakereshet és törölhet. Mivel minden megvan, amire szüksége van az induláshoz, miért nem próbálja ki ezeket a példákat saját maga Java -ban?

Műveletek létrehozása és végrehajtása tömbökön Java -ban

Java tanulás? Hagyja, hogy a tömbök könnyedén kezeljék adatait.

Olvassa tovább

A szerzőről