Ú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.

---

---

Ako funguje prepojený zoznam?

Každý prepojený zoznam začína špeciálnym uzlom, ktorý sa často označuje ako „hlava“ a za ktorý je potrebné 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.

Vytvorenie prepojeného zoznamu v Jave

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:


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 tomto prípade údajový atribút bude ukladať celočíselné hodnoty. Teraz, keď máte triedu uzlov, je čas prejsť na prepojený zoznam.

Príklad prepojeného zoznamu

Nasleduje príklad prepojeného zoznamu v Jave.

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


Vyššie uvedený kód vytvorí prepojenú triedu zoznamov, avšak 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ť túto dátovú štruktúru v inej štruktúre údajov, ako sú napríklad zásobníky (ktorá umožňuje vkladanie a odstraňovanie iba 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.

//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 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.

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 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ť?

Raspberry Pi spustenie programu pri štarte

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.

//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();
}
}

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.

//print the nodes in a linked list
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 Hľadať uzol

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

Napríklad by nebolo 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.

//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;
}

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.

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


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

The node is in the list

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) {
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();
}
}

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

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

ako nahrať HD video na facebook z počítača

//delete the node that holds the data 4
List.findAndDelete(4);
//print all nodes in the linked list
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:

The List:
2 6 8 10

Teraz môžete vytvárať prepojené zoznamy v Jave

Ak ste sa dostali na koniec tohto tutoriálu, 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?

zdieľam zdieľam Tweet E -mail 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 Súvisiace témy

• Programovanie
• Java
• Programovanie
• Tipy na kódovanie

O autorovi Kadeisha Kean(21 publikovaných článkov)

Kadeisha Kean je softvérový vývojár a technický/technologický spisovateľ. Má výraznú schopnosť zjednodušiť niektoré z najzložitejších technologických konceptov; produkovať materiál, ktorému každý technologický nováčik ľahko porozumie. Je nadšená písaním, vývojom zaujímavého softvéru a cestovaním po svete (prostredníctvom dokumentov).

Viac od Kadeisha Keana

prihlásiť sa ku odberu noviniek

Pripojte sa k nášmu bulletinu a získajte technické tipy, recenzie, bezplatné elektronické knihy a exkluzívne ponuky!

Kliknutím sem sa prihlásite na odber