Úvod do používání propojených seznamů v Javě

Datová struktura používá k ukládání, načítání a odstraňování dat různé předdefinované metody, které vyvrcholí vytvořením efektivních programů. Propojený seznam je populární datová struktura, která se skládá ze seznamu uzlů, které jsou propojeny (nebo propojeny).

Jak ale vytvoříte propojený seznam v Javě? Podívejme se na to.

Každý propojený seznam začíná zvláštním uzlem, který je často označován jako „hlava“ a který má za úkol neustále ukazovat na začátek seznamu. Hlava je důležitá, protože každý uzel v propojeném seznamu nemusí fyzicky následovat svého nástupce (to znamená, že předchůdce a nástupce nemusí fyzicky sousedit).

Jako každá datová struktura, propojený seznam usnadňuje vytváření, načítání, vkládání a ničení prostřednictvím sady předdefinovaných funkcí, které může použít každý vývojář.

Program Java, který je určen k vytváření a manipulaci s propojenými seznamy, bude mít tři charakteristické sekce; třída uzlu, třída propojeného seznamu a ovladač. Ačkoli tyto tři části lze kombinovat do jednoho souboru, v informatice existuje princip designu známý jako „oddělení starostí“, který by měl znát každý vývojář.

Zásada oddělení obav vyžaduje, aby byla oddělena každá část kódu, která řeší konkrétní problém. Tento princip vám pomůže vytvořit čistší (čitelnější) kód a je ideální pro vytváření datových struktur.

Prvním krokem při vytváření propojeného seznamu v Javě je vytvoření třídy uzlů. Třída uzlu by měla mít dva atributy; jeden z atributů bude představovat datovou část uzlu, zatímco druhý atribut bude představovat propojenou část. Třída uzlu by měla mít také konstruktor, getry a nastavovače.

Příbuzný: Naučte se vytvářet třídy v Javě

Získavače a nastavovače umožní ostatním třídám (například třídě propojených seznamů) přístup k různým uzlům v propojeném seznamu.

Příklad třídy uzlu

Níže uvádíme příklad třídy uzlů, abyste získali představu o tom, co máme na mysli:

veřejná třída Node {
soukromé int Data;
soukromý uzel NextNode;
//constructor
public Node () {
Data = 0;
NextNode = null;
}
// getters and setters
public int getData () {
vrátit data;
}
public void setData (int data) {
Data = data;
}
veřejný uzel getNextNode () {
vrátit NextNode;
}
public void setNextNode (Node nextNode) {
NextNode = nextNode;
}
}

V tomto případě bude datový atribut ukládat celočíselné hodnoty. Nyní, když máte třídu uzlů, je čas přejít na propojený seznam.

Níže je uveden příklad propojeného seznamu v Javě.

veřejná třída LinkedList {
soukromá hlava uzlu;
//constructor
public LinkedList () {
Hlava = null;
}
}

Výše uvedený kód vytvoří propojenou třídu seznamu, ale bez různých operací lze tuto třídu považovat za ekvivalent prázdného shellu. Datová struktura propojeného seznamu má několik operací, které lze použít k naplnění:

• Vložte vpředu.
• Vložte do středu.
• Vsadit vzadu.

Příbuzný: Jak vytvářet datové struktury pomocí tříd JavaScript ES6

Kolekce propojených seznamů metod vkládání je jedním z důvodů, proč se vývojář může rozhodnout použít tato data struktura nad jinou datovou strukturou, jako jsou komíny (která umožňuje pouze vkládání a mazání shora).

Použití metody Vložit na přední stranu

Metoda insert at the front, jak název napovídá, vloží nová data (nebo nové uzly) na začátek propojeného seznamu.

Vložit na přední metodě příklad

Níže je uveden příklad toho, jak byste na začátek seznamu vložili nová data.

 // vložte uzel na přední metodu
public void insertAtFront (int klíč) {
// vytvořte nový uzel pomocí třídy uzlů
Node Temp = new Node ();
// zkontrolujte, zda byl úspěšně vytvořen dočasný uzel
// přiřadit k nim data, která poskytl uživatel
if (Temp! = null) {
Temp.setData (klíč);
Temp.setNextNode (null);
// zkontrolujte, zda je hlava propojeného seznamu prázdná
// přiřaďte právě vytvořený uzel k pozici hlavy
if (Head == null) {
Hlava = teplota;
}
// pokud je uzel již na pozici hlavy
// přidejte do něj nový uzel a nastavte jej jako hlavu
jinak {
Temp.setNextNode (Head);
Hlava = teplota;
}
}
}

The insertAtFront metoda ve výše uvedeném příkladu umožňuje uživateli přidat do daného propojeného seznamu nové uzly.

Příklad použití vložky na přední straně

Níže je příklad toho, jak byste použili vložku vpředu.

řidič veřejné třídy {
// spustí program
public static void main (String [] args) {
// vytvořte nový propojený seznam s názvem Seznam
Seznam LinkedList = nový LinkedList ();
// přidejte každou hodnotu na začátek propojeného seznamu jako nový uzel
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

The Řidič class (což je název, který je často přiřazen spustitelné třídě v Javě), využívá třídu LinkedList k vytvoření propojeného seznamu pěti sudých čísel. Při pohledu na výše uvedený kód by mělo být snadné zjistit, že číslo „2“ je v propojeném seznamu na pozici hlavy. Ale jak to můžete potvrdit?

Použití metody Zobrazit všechny uzly

Metoda zobrazení všech uzlů je základní metodou propojeného seznamu. Bez toho vývojář neuvidí uzly v propojeném seznamu. Prochází propojeným seznamem (počínaje od hlavy) a tiskne data uložená v každém uzlu, který tvoří seznam.

Zobrazit všechny uzly Příklad metody

Níže je uveden příklad použití metody zobrazení všech poznámek v Javě.

// metoda zobrazení všech uzlů
public void displayAllNodes () {
// vytvořte nový Temp volání volání a přiřaďte jej hlavičce propojeného seznamu
// pokud má hlava hodnotu null, pak je propojený seznam prázdný
Teplota uzlu = hlava;
if (Head == null) {
System.out.println ("Seznam je prázdný.");
vrátit se;
}
System.out.println ("Seznam:");
while (Temp! = null) {
// vytiskněte data v každém uzlu do konzoly (od hlavy)
System.out.print (Temp.getData () + "");
Temp = Temp.getNextNode ();
} 
}

Nyní, když displayAllNodes metoda byla přidána do souboru Spojový seznam třídu můžete zobrazit propojený seznam přidáním jednoho řádku kódu do třídy ovladačů.

Použití příkladu metody Zobrazit všechny uzly

Níže uvidíte, jak byste použili metodu zobrazení všech uzlů.

// vytiskněte uzly v propojeném seznamu
List.displayAllNodes (); 

Spuštění výše uvedeného řádku kódu vytvoří v konzole následující výstup:

Seznam:

2 4 6 8 10

Pomocí metody Najít uzel

Existují případy, kdy uživatel bude chtít najít konkrétní uzel v propojeném seznamu.

Například by nebylo praktické, aby banka, která má miliony zákazníků, vytiskla ve své databázi všechny zákazníky, když potřebují vidět pouze podrobnosti o konkrétním zákazníkovi.

Proto místo použití displayAllNodes metoda, efektivnější metodou je najít jediný uzel obsahující požadovaná data. To je důvod, proč je v datové struktuře propojeného seznamu důležité hledání metody s jedním uzlem.

Příklad metody Find Node

Níže je uveden příklad použití metody find node.

// vyhledejte jeden uzel pomocí klíče
public boolean findNode (int key) {
// vytvořte nový uzel a umístěte jej na začátek propojeného seznamu
Teplota uzlu = hlava;
// zatímco aktuální uzel není prázdný
// zkontrolujte, zda se jeho data shodují s klíčem poskytnutým uživatelem
while (Temp! = null) {
if (Temp.getData () == klíč) {
System.out.println ("Uzel je v seznamu"); 
return true;
}
// přechod na další uzel
Temp = Temp.getNextNode ();
}
// pokud klíč nebyl nalezen v propojeném seznamu
System.out.println ("Uzel není v seznamu"); 
return false;
}

S displayAllNodes metodou, potvrdili jste, že Spojový seznam obsahuje 5 sudých čísel od 2 do 10. The findNode výše uvedený příklad může potvrdit, zda je jedním z těchto sudých čísel číslice 4 pouhým zavoláním metody ve třídě ovladače a zadáním čísla jako parametru.

Použití příkladu metody Find Node

Níže je uveden příklad toho, jak byste v praxi používali metodu find node.

// zkontrolujte, zda je uzel v propojeném seznamu
List.findNode (4);

Výše uvedený kód vytvoří v konzole následující výstup:

Uzel je v seznamu

Použití metody Odstranit uzel

Při použití stejného příkladu banky výše může zákazník v databázi banky chtít uzavřít svůj účet. Zde bude metoda odstranění uzlu užitečná. Je to nejsložitější metoda propojeného seznamu.

Metoda Odstranit uzel vyhledá daný uzel, odstraní tento uzel a propojí předchozí uzel s uzlem, který následuje za uzlem, který byl odstraněn.

Odstranit příklad metody uzlu

Níže je uveden příklad metody odstranění uzlu.

public void findAndDelete (int klíč) { 
Teplota uzlu = hlava; 
Uzel prev = null; 
// zkontrolujte, zda hlavní uzel uchovává data 
// a smažte to 
if (Temp! = null && Temp.getData () == key) { 
Head = Temp.getNextNode (); 
vrátit se; 
} 
// prohledejte ostatní uzly v seznamu 
// a smažte to 
while (Temp! = null) { 
if (Temp.getNextNode (). getData () == klíč) { 
prev = Temp.getNextNode (). getNextNode (); 
Temp.setNextNode (předchozí); 
vrátit se; 
} 
Temp = Temp.getNextNode (); 
} 
} 

Použití příkladu metody Odstranit uzel

Níže je uveden příklad použití metody odstranění uzlu v praxi.

// odstranění uzlu, který uchovává data 4
List.findAndDelete (4);
// tisk všech uzlů v propojeném seznamu
List.displayAllNodes ();

Použití dvou řádků kódu výše v již existující třídě Driver vytvoří v konzole následující výstup:

Seznam:
2 6 8 10

Pokud jste se dostali na konec tohoto článku s návodem, dozvěděli jste se:

• Jak vytvořit třídu uzlů.
• Jak vytvořit propojenou třídu seznamu.
• Jak naplnit třídu propojeného seznamu jejími předdefinovanými metodami.
• Jak vytvořit třídu ovladače a použít různé metody propojeného seznamu k dosažení požadovaného výsledku.

Propojený seznam je jen jednou z mnoha datových struktur, které můžete použít k ukládání, načítání a mazání dat. Když už máte vše, co potřebujete, proč nezkusit tyto příklady sami v Javě?

Jak vytvářet a provádět operace na polích v Javě

Učit se Javu? Nechejte pole snadno zpracovávat vaše data.

Číst dále

O autorovi