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.

---

---

Cum funcționează o listă conectată?

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.

Crearea unei liste conectate în Java

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 setatorii 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 {
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;
}
}

Î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ă.

Exemplu de listă legată

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

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


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 față.
• Introduceți în mijloc.
• Introduceți în spate.

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

Colecția de liste legate de metode de inserare este un motiv pentru care un dezvoltator ar putea alege să utilizeze această structură de date 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.

//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 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 despre modul în care ați aplica inserarea în partea din față.

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

magazin Google Play pe Kindle Fire

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.

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

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 folosi metoda de afișare a tuturor nodurilor.

//print the nodes in a linked list
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 , 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.

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

Cu displayAllNodes , ați confirmat că LinkedList conține 5 numere pare de la 2 la 10. 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 metoda de găsire a nodului în practică.

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


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

The node is in the 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(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();
}
}

Folosind Exemplul de metodă Ștergeți un nod

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

cum să știți dacă telefonul Android este spart

//delete the node that holds the data 4
List.findAndDelete(4);
//print all nodes in the linked list
List.displayAllNodes();

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

The List:
2 6 8 10

Acum puteți crea liste conectate în Java

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 de listă legată pentru a obține rezultatul dorit.

O listă legată este doar una dintre multele 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?

Acțiune Acțiune Tweet E-mail 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 Subiecte asemănătoare

• Programare
• Java
• Programare
• Sfaturi de codare

Despre autor Kadeisha Kean(21 articole publicate)

Kadeisha Kean este un dezvoltator de software complet și scriitor tehnic / tehnologic. Are capacitatea distinctă de a simplifica unele dintre cele mai complexe concepte tehnologice; producând materiale care pot fi ușor de înțeles de către orice novice în tehnologie. Este pasionată de scriere, dezvoltarea de software-uri interesante și călătoria prin lume (prin documentare).

Mai multe de la Kadeisha Kean

Aboneaza-te la newsletter-ul nostru

Alăturați-vă newsletter-ului pentru sfaturi tehnice, recenzii, cărți electronice gratuite și oferte exclusive!

Faceți clic aici pentru a vă abona