Úvod do používania prepojených zoznamov v Jave

Dátová štruktúra používa na ukladanie, získavanie a odstraňovanie údajov rôzne vopred definované metódy, ktoré vyvrcholia vytvorením efektívnych programov. Prepojený zoznam je populárna dátová štruktúra, ktorá pozostáva zo zoznamu uzlov, ktoré sú prepojené (alebo prepojené).

Ako však vytvoríte prepojený zoznam v Jave? Pozrime sa.

Každý prepojený zoznam začína špeciálnym uzlom, ktorý sa často označuje ako „hlava“ a ktorý má za úlohu vždy smerovať na začiatok zoznamu. Hlava je dôležitá, pretože každý uzol v prepojenom zozname nemusí fyzicky nasledovať svojho nástupcu (to znamená, že predchodca a nástupca nemusia fyzicky susediť).

Ako každá dátová štruktúra, prepojený zoznam uľahčuje vytváranie, získavanie, vkladanie a ničenie prostredníctvom sady preddefinovaných funkcií, ktoré môže použiť každý vývojár.

Program Java, ktorý je navrhnutý na vytváranie a manipuláciu s prepojenými zoznamami, bude mať tri odlišné sekcie; trieda uzlov, trieda prepojeného zoznamu a ovládač. Aj keď sa tieto tri sekcie dajú kombinovať do jedného súboru, v informatike existuje princíp dizajnu známy ako „oddelenie obáv“, ktorý by mal vedieť každý vývojár.

Zásada oddelenia obáv vyžaduje, aby bola oddelená každá časť kódu, ktorá sa zaoberá konkrétnou obavou. Tento princíp vám pomôže vytvoriť čistejší (čitateľnejší) kód a je ideálny pre vytváranie dátových štruktúr.

Prvým krokom pri vytváraní prepojeného zoznamu v Jave je vytvorenie triedy uzlov. Trieda uzla by mala mať dva atribúty; jeden z atribútov bude predstavovať dátovú časť uzla, zatiaľ čo druhý atribút bude predstavovať prepojenú časť. Trieda uzlov by mala mať tiež konštruktor, getry a nastavovače.

Súvisiace: Naučte sa vytvárať triedy v Jave

Získačky a nastavovače umožnia iným triedam (napríklad triede prepojeného zoznamu) prístup k rôznym uzlom v rámci prepojeného zoznamu.

Príklad triedy uzlov

Nasleduje príklad triedy uzlov, aby ste získali predstavu o tom, čo máme na mysli:

verejná trieda Uzol {
súkromné ​​int Dáta;
súkromný uzol NextNode;
//constructor
public Node () {
Údaje = 0;
NextNode = null;
}
// getters and setters
public int getData () {
vrátiť údaje;
}
public void setData (int data) {
Dáta = dáta;
}
verejný uzol getNextNode () {
vrátiť NextNode;
}
public void setNextNode (Node nextNode) {
NextNode = nextNode;
}
}

V tomto prípade údajový atribút bude ukladať celočíselné hodnoty. Teraz, keď máte triedu uzlov, je čas prejsť na prepojený zoznam.

Nasleduje príklad prepojeného zoznamu v Jave.

verejná trieda LinkedList {
súkromná hlava uzla;
//constructor
public LinkedList () {
Hlava = nula;
}
}

Vyššie uvedený kód vytvorí prepojenú triedu zoznamu, ale bez rôznych operácií môže byť trieda považovaná za ekvivalent prázdneho shellu. Štruktúra údajov prepojeného zoznamu má niekoľko operácií, ktoré je možné použiť na jeho naplnenie:

• Vložte vpredu.
• Vložte do stredu.
• Vsadenie vzadu.

Súvisiace: Ako vytvoriť dátové štruktúry pomocou tried ES6 JavaScript

Súbor prepojených zoznamov metód vkladania je jedným z dôvodov, prečo sa vývojár môže rozhodnúť použiť tieto údaje štruktúra nad inou dátovou štruktúrou, ako sú zásobníky (ktorá umožňuje iba vkladanie a odstraňovanie zhora).

Použitie metódy Vložiť na prednú stranu

Metóda vloženia na začiatok, ako naznačuje názov, vkladá nové údaje (alebo nové uzly) na začiatok prepojeného zoznamu.

Vložte na prednú stranu príklad metódy

Nasleduje príklad, ako by ste nové údaje vložili na začiatok zoznamu.

 // metóda vložte uzol na prednú stranu
public void insertAtFront (int key) {
// vytvorte nový uzol pomocou triedy uzlov
Teplota uzla = nový Uzol ();
// skontrolujte, či bol dočasný uzol úspešne vytvorený
// priraďte k nim údaje, ktoré poskytol používateľ
if (Temp! = null) {
Temp.setData (kľúč);
Temp.setNextNode (null);
// skontrolujte, či je hlava prepojeného zoznamu prázdna
// priradenie uzla, ktorý bol práve vytvorený, k pozícii hlavy
if (Head == null) {
Hlava = teplota;
}
// ak je uzol už v pozícii hlavy
// pridajte do neho nový uzol a nastavte ho ako hlavu
inak {
Temp.setNextNode (Head);
Hlava = teplota;
}
}
}

The insertAtFront metóda vo vyššie uvedenom príklade umožňuje užívateľovi pridať nové uzly do daného prepojeného zoznamu.

Príklad použitia vložky na prednú stranu

Nasleduje príklad toho, ako by ste použili vložku vpredu.

vodič verejnej triedy {
// spustí program
public static void main (String [] args) {
// vytvorte nový prepojený zoznam s názvom Zoznam
LinkedList List = nový LinkedList ();
// pridajte každú hodnotu na začiatok prepojeného zoznamu ako nový uzol
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

The Vodič class (čo je názov, ktorý je často priradený spustiteľnej triede v Jave), používa triedu LinkedList na vytvorenie prepojeného zoznamu piatich párnych čísel. Pri pohľade na kód vyššie by malo byť ľahké vidieť, že číslo „2“ je v prepojenom zozname na prvom mieste. Ako to však môžete potvrdiť?

Použitie metódy Zobraziť všetky uzly

Metóda zobrazenia všetkých uzlov je základnou metódou prepojeného zoznamu. Bez neho vývojár neuvidí uzly v prepojenom zozname. Prechádza prepojeným zoznamom (začínajúc od hlavy) a tlačí údaje uložené v každom uzle, ktorý tvorí zoznam.

Zobraziť všetky uzly Príklad metódy

Nasleduje príklad použitia metódy zobraziť všetky poznámky v Jave.

// metóda zobrazenia všetkých uzlov
public void displayAllNodes () {
// vytvorte nový hovor uzla Temp a priraďte ho k vedúcemu prepojeného zoznamu
// ak má hlava hodnotu null, prepojený zoznam je prázdny
Teplota uzla = hlava;
if (Head == null) {
System.out.println ("Zoznam je prázdny.");
návrat;
}
System.out.println ("Zoznam:");
while (Temp! = null) {
// vytlačte údaje v každom uzle do konzoly (od hlavy)
System.out.print (Temp.getData () + "");
Temp = Temp.getNextNode ();
} 
}

Teraz, keď displayAllNodes metóda bola pridaná do súboru LinkedList triedu si môžete pozrieť prepojený zoznam pridaním jedného riadka kódu do triedy ovládačov.

Použitie príkladu metódy Zobraziť všetky uzly

Nižšie uvidíte, ako by ste použili metódu zobrazenia všetkých uzlov.

// vytlačte uzly v prepojenom zozname
List.displayAllNodes (); 

Vykonaním vyššie uvedeného riadku kódu sa v konzole vytvorí nasledujúci výstup:

Zoznam:

2 4 6 8 10

Použitie metódy Find Node

Existujú prípady, keď používateľ bude chcieť nájsť konkrétny uzol v prepojenom zozname.

Nebolo by napríklad praktické, aby banka, ktorá má milióny zákazníkov, vytlačila všetkých zákazníkov vo svojej databáze, keď potrebujú vidieť iba podrobnosti o konkrétnom zákazníkovi.

Preto namiesto použitia displayAllNodes metóda, efektívnejšou metódou je nájsť jeden uzol obsahujúci požadované údaje. To je dôvod, prečo je vyhľadávanie v metóde prepojeného zoznamu dôležité pre metódu jedného uzla.

Príklad metódy Find Node

Nasleduje príklad použitia metódy find node.

// hľadanie jedného uzla pomocou kľúča
public boolean findNode (int key) {
// vytvorte nový uzol a umiestnite ho na začiatok prepojeného zoznamu
Teplota uzla = hlava;
// zatiaľ čo aktuálny uzol nie je prázdny
// skontrolujte, či sa jeho údaje zhodujú s kľúčom poskytnutým používateľom
while (Temp! = null) {
if (Temp.getData () == key) {
System.out.println ("Uzol je v zozname"); 
návrat true;
}
// prechod na nasledujúci uzol
Temp = Temp.getNextNode ();
}
// ak sa kľúč nenašiel v prepojenom zozname
System.out.println ("Uzol nie je v zozname"); 
return false;
}

S displayAllNodes metóda, potvrdili ste, že LinkedList obsahuje 5 párnych čísel od 2 do 10. The findNode vyššie uvedený príklad môže potvrdiť, či je jedným z týchto párnych čísel číslica 4 jednoduchým zavolaním metódy v triede vodiča a zadaním čísla ako parametra.

Použitie príkladu metódy Find Node

Nasleduje príklad toho, ako by ste v praxi používali metódu find node.

// skontrolujte, či je uzol v prepojenom zozname
List.findNode (4);

Vyššie uvedený kód poskytne v konzole nasledujúci výstup:

Uzol je v zozname

Použitie metódy Odstrániť uzol

Na základe rovnakého bankového príkladu, ako je uvedený vyššie, môže zákazník v bankovej databáze chcieť zrušiť svoj účet. Tu bude metóda odstránenia uzla užitočná. Je to najkomplexnejšia metóda prepojeného zoznamu.

Metóda Odstrániť uzol vyhľadá daný uzol, vymaže tento uzol a prepojí predchádzajúci uzol s uzlom, ktorý nasleduje za uzlom, ktorý bol odstránený.

Príklad metódy odstránenia uzla

Nasleduje príklad metódy odstránenia uzla.

public void findAndDelete (int key) { 
Teplota uzla = hlava; 
Uzel prev = null; 
// skontrolujte, či hlavný uzol uchováva údaje 
// a zmaž to 
if (Temp! = null && Temp.getData () == key) { 
Head = Temp.getNextNode (); 
návrat; 
} 
// vyhľadajte ostatné uzly v zozname 
// a zmaž to 
while (Temp! = null) { 
if (Temp.getNextNode (). getData () == kľúč) { 
prev = Temp.getNextNode (). getNextNode (); 
Temp.setNextNode (predchádzajúci); 
návrat; 
} 
Temp = Temp.getNextNode (); 
} 
} 

Použitie príkladu metódy Odstrániť uzol

Nasleduje príklad použitia metódy odstránenia uzla v praxi.

// odstránenie uzla, ktorý uchováva údaje 4
List.findAndDelete (4);
// vytlačte všetky uzly v prepojenom zozname
List.displayAllNodes ();

Použitím dvoch riadkov kódu vyššie v už existujúcej triede ovládačov bude v konzole produkovaný nasledujúci výstup:

Zoznam:
2 6 8 10

Ak ste sa dostali na koniec tohto článku s návodom, naučíte sa:

• Ako vytvoriť triedu uzlov.
• Ako vytvoriť triedu prepojeného zoznamu.
• Ako naplniť triedu prepojených zoznamov preddefinovanými metódami.
• Ako vytvoriť triedu ovládačov a použiť rôzne metódy prepojeného zoznamu na dosiahnutie požadovaného výsledku.

Prepojený zoznam je len jednou z mnohých dátových štruktúr, ktoré môžete použiť na ukladanie, získavanie a odstraňovanie údajov. Keď už máte všetko, čo potrebujete, prečo neskúsiť tieto príklady na vlastnej koži v Jave?

Ako vytvárať a vykonávať operácie na poliach v Jave

Učíte sa Javu? Nechajte polia ľahko pracovať s vašimi údajmi.

Čítajte ďalej

O autorovi