Introducere în utilizarea listelor conectate în Java

O structură de date utilizează diferite metode predefinite pentru a stoca, prelua și șterge date, care culminează cu crearea de programe eficiente. O listă legată este o structură de date populară, care constă dintr-o listă de noduri care sunt conectate (sau legate).

Dar cum creați o listă legată în Java? Hai să aruncăm o privire.

Fiecare listă legată începe cu un nod special care este adesea denumit „cap”, care are responsabilitatea de a indica permanent începutul listei. Capul este important deoarece fiecare nod dintr-o listă legată nu trebuie să-și urmeze succesorul fizic (ceea ce înseamnă că un predecesor și un succesor nu trebuie să fie adiacenți fizic).

Ca orice structură de date, lista legată facilitează crearea, recuperarea, inserarea și distrugerea printr-un set de funcții predefinite care pot fi utilizate de orice dezvoltator.

Un program Java conceput pentru a crea și manipula liste legate va avea trei secțiuni distincte; clasa nodului, clasa listei legate și driverul. Deși aceste trei secțiuni se pot combina într-un singur fișier, există un principiu de proiectare în informatică cunoscut sub numele de „separarea preocupărilor” pe care fiecare dezvoltator ar trebui să îl cunoască.

Principiul separării preocupărilor dictează separarea fiecărei secțiuni a codului care abordează o problemă specifică. Acest principiu vă va ajuta să creați cod mai curat (mai lizibil) și este ideal pentru crearea structurilor de date.

Primul pas în crearea unei liste legate în Java este crearea unei clase de noduri. O clasă de nod ar trebui să aibă două atribute; unul dintre atribute va reprezenta porțiunea de date a nodului, în timp ce celălalt atribut va reprezenta porțiunea legată. O clasă de noduri ar trebui să aibă, de asemenea, un constructor, getters și setere.

Legate de: Aflați cum să creați cursuri în Java

Getters și seterii vor permite altor clase (cum ar fi clasa listei conectate) să acceseze diferitele noduri din lista conectată.

Exemplu de clasă nod

Mai jos este un exemplu de clasă de nod pentru a vă face o idee despre ce vrem să spunem:

public class Node {
date private private;
private Node NextNode;
//constructor
nod public () {
Date = 0;
NextNode = nul;
}
// getters și seters
public int getData () {
returnează date;
}
public void setData (date int) {
Date = date;
}
nod public getNextNode () {
returnează NextNode;
}
public void setNextNode (Node nextNode) {
NextNode = NextNode;
}
}

În acest exemplu, atributul de date va stoca valori întregi. Acum că aveți clasa de noduri, este timpul să treceți la lista legată.

Mai jos este un exemplu de listă legată în Java.

clasă publică LinkedList {
Cap de nod privat;
//constructor
public LinkedList () {
Cap = nul;
}
}

Codul de mai sus va crea o clasă de listă legată, cu toate acestea, fără diferitele sale operații, clasa poate fi văzută ca echivalentul unui shell gol. Structura de date a listei legate are mai multe operații care pot fi utilizate pentru a o completa:

• Introduceți în partea din față.
• Introduceți în mijloc.
• Introduceți în spate.

Legate de: Cum să construiți structuri de date cu clasele JavaScript ES6

Colectarea listelor legate de metode de inserare este unul dintre motivele pentru care un dezvoltator ar putea alege să utilizeze aceste date structură peste o altă structură de date, cum ar fi stive (care permite doar inserarea și ștergerea din partea de sus).

Folosind metoda Insert at the Front

Inserarea din metoda frontală, așa cum sugerează și numele, introduce date noi (sau noduri noi) în partea din față a listei conectate.

Introduceți în Exemplul de metodă frontală

Mai jos este un exemplu despre modul în care ați insera date noi în partea din față a listei.

 // introduceți nodul în metoda frontală
public void insertAtFront (cheie int) {
// creați un nou nod folosind clasa de noduri
Node Temp = Nod nou ();
// verificați dacă nodul Temp a fost creat cu succes
// atribuiți-i datele furnizate de utilizator
if (Temp! = nul) {
Temp.setData (cheie);
Temp.setNextNode (nul);
// verificați dacă capul listei legate este gol
// atribuiți nodul care tocmai a fost creat poziției capului
if (Head == nul) {
Cap = Temp;
}
// dacă un nod se află deja în poziția capului
// adăugați noul nod la acesta și setați-l ca cap
altceva {
Temp.setNextNode (Head);
Cap = Temp;
}
}
}

The insertAtFront metoda din exemplul de mai sus permite utilizatorului să adauge noi noduri la o anumită listă legată.

Aplicarea insertului în exemplul frontal

Mai jos este un exemplu al modului în care ați aplica inserarea în partea din față.

șofer de clasă publică {
// execută programul
public static void main (String [] args) {
// creați o nouă listă legată numită Listă
LinkedList List = new LinkedList ();
// adăugați fiecare valoare în partea din față a listei legate ca un nod nou
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

The Conducător auto class (care este numele atribuit deseori clasei executabile în Java), utilizează clasa LinkedList pentru a crea o listă legată de cinci numere pare. Privind codul de mai sus, ar trebui să fie ușor să vedeți că numărul "2" se află în poziția de cap în lista legată. Dar cum puteți confirma acest lucru?

Folosind metoda Afișare toate nodurile

Metoda afișării tuturor nodurilor este o metodă esențială a listei legate. Fără aceasta, un dezvoltator nu va putea vedea nodurile dintr-o listă legată. Se deplasează prin lista legată (începând de la cap) imprimând datele stocate în fiecare nod care formează lista.

Afișați toate nodurile Exemplu de metodă

Mai jos este un exemplu de utilizare a metodei de afișare a tuturor notelor în Java.

// afișează metoda tuturor nodurilor
public void displayAllNodes () {
// creați un nou nod de apel Temp și atribuiți-l capului listei legate
// dacă capul are o valoare nulă, atunci lista legată este goală
Nod Temp = Head;
if (Head == nul) {
System.out.println ("Lista este goală.");
întoarcere;
}
System.out.println ("Lista:");
while (Temp! = nul) {
// imprimați datele din fiecare nod pe consolă (începând de la cap)
System.out.print (Temp.getData () + "");
Temp = Temp.getNextNode ();
} 
}

Acum că displayAllNodes metoda a fost adăugată la LinkedList clasă puteți vizualiza lista legată adăugând o singură linie de cod la clasa șoferului.

Utilizarea Exemplului de metodă Afișare toate nodurile

Mai jos, veți vedea cum ați utiliza metoda de afișare a tuturor nodurilor.

// tipăriți nodurile dintr-o listă legată
List.displayAllNodes (); 

Executarea liniei de cod de mai sus va produce următoarea ieșire în consolă:

Lista:

2 4 6 8 10

Folosind metoda Find Node

Vor exista cazuri când un utilizator va dori să găsească un anumit nod într-o listă legată.

De exemplu, nu ar fi practic ca o bancă care are milioane de clienți să tipărească toți clienții în baza lor de date atunci când trebuie să vadă doar detaliile unui anumit client.

Prin urmare, în loc să utilizați displayAllNodes metoda, o metodă mai eficientă este de a găsi singurul nod care conține datele necesare. Acesta este motivul pentru care căutarea unei metode cu un singur nod este importantă în structura de date a listei legate.

Găsiți un exemplu de metodă nod

Mai jos este un exemplu de utilizare a metodei de găsire a nodului.

// căutați un singur nod folosind o cheie
public boolean findNode (cheie int) {
// creați un nod nou și plasați-l în capul listei conectate
Nod Temp = Head;
// în timp ce nodul curent nu este gol
// verificați dacă datele sale se potrivesc cu cheia furnizată de utilizator
while (Temp! = nul) {
if (cheia Temp.getData () ==) {
System.out.println ("Nodul este în listă"); 
întoarce-te adevărat;
}
// treceți la următorul nod
Temp = Temp.getNextNode ();
}
// dacă cheia nu a fost găsită în lista legată
System.out.println ("Nodul nu este în listă"); 
returnează fals;
}

Cu displayAllNodes, ați confirmat că LinkedList conține 5 numere pare de la 2 la 10. The findNode exemplul de mai sus poate confirma dacă unul dintre acele numere pare este numărul 4 prin simpla apelare a metodei din clasa driverului și furnizarea numărului ca parametru.

Folosind Exemplul de metodă Găsire nod

Mai jos este un exemplu despre modul în care ați folosi în practică metoda de găsire a nodului.

// verificați dacă un nod este în lista legată
List.findNode (4);

Codul de mai sus va produce următoarea ieșire în consolă:

Nodul se află în listă

Folosind metoda Șterge un nod

Folosind același exemplu bancar de mai sus, un client din baza de date a băncii ar putea dori să își închidă contul. Aici va fi utilă metoda de ștergere a unui nod. Este cea mai complexă metodă de listă legată.

Metoda Șterge un nod caută un nod dat, șterge acel nod și leagă nodul anterior de cel care urmează nodului șters.

Ștergeți un exemplu de metodă nod

Mai jos este un exemplu de metodă de ștergere a unui nod.

public void findAndDelete (cheie int) { 
Nod Temp = Head; 
Nod prev = nul; 
// verificați dacă nodul principal deține datele 
// și ștergeți-l 
if (Temp! = null && Temp.getData () == cheie) { 
Head = Temp.getNextNode (); 
întoarcere; 
} 
// căutați în celelalte noduri din listă 
// și ștergeți-l 
while (Temp! = nul) { 
if (Temp.getNextNode (). getData () == cheie) { 
prev = Temp.getNextNode (). getNextNode (); 
Temp.setNextNode (prev); 
întoarcere; 
} 
Temp = Temp.getNextNode (); 
} 
} 

Folosind Exemplul de metodă Delete a Node

Mai jos este un exemplu de utilizare a metodei de ștergere a unui nod în practică.

// ștergeți nodul care deține datele 4
List.findAndDelete (4);
// tipăriți toate nodurile din lista legată
List.displayAllNodes ();

Utilizarea celor două linii de cod de mai sus în clasa de driver preexistentă va produce următoarea ieșire în consolă:

Lista:
2 6 8 10

Dacă ați ajuns la sfârșitul acestui articol tutorial, veți fi învățat:

• Cum se creează o clasă de noduri.
• Cum se creează o clasă de listă legată.
• Cum să populezi o clasă de listă legată cu metodele sale predefinite.
• Cum să creați o clasă de drivere și să utilizați diferitele metode legate de listă pentru a obține rezultatul dorit.

O listă legată este doar una dintre numeroasele structuri de date pe care le puteți utiliza pentru a stoca, prelua și șterge date. Deoarece aveți tot ce aveți nevoie pentru a începe, de ce să nu încercați aceste exemple în Java?

Cum să creați și să efectuați operațiuni pe tablouri în Java

Învățați Java? Permiteți matricelor să vă gestioneze datele cu ușurință.

Citiți în continuare

Despre autor