En introduktion til brug af sammenkædede lister i Java

En datastruktur bruger forskellige foruddefinerede metoder til at gemme, hente og slette data, der kulminerer i oprettelsen af ​​effektive programmer. En sammenkædet liste er en populær datastruktur, som består af en liste over noder, der er forbundet (eller sammenkædet).

Men hvordan opretter du en linket liste i Java? Lad os se.

Hver sammenkædede liste begynder med en særlig knude, der ofte omtales som "hovedet", som har ansvaret for altid at pege på starten af ​​listen. Hovedet er vigtigt, fordi hver knude på en sammenkædet liste ikke behøver at følge sin efterfølger fysisk (hvilket betyder, at en forgænger og en efterfølger ikke behøver at være fysisk tilstødende).

Som enhver datastruktur letter den sammenkædede liste oprettelse, hentning, indsættelse og destruktion gennem et sæt foruddefinerede funktioner, der kan bruges af enhver udvikler.

Et Java -program, der er designet til at oprette og manipulere sammenkædede lister, vil have tre særskilte sektioner; nodeklassen, den sammenkædede listeklasse og driveren. Selvom disse tre sektioner kan kombineres i en fil, er der et designprincip inden for datalogi kendt som "adskillelse af bekymringer", som enhver udvikler bør kende.

Princippet om adskillelse af bekymringer dikterer, at hvert afsnit i koden, der adresserer et specifikt problem, skal adskilles. Dette princip hjælper dig med at oprette renere (mere læsbar) kode og er ideel til oprettelse af datastrukturer.

Det første trin i oprettelsen af ​​en sammenkædet liste i Java er at oprette en nodeklasse. En nodeklasse skal have to attributter; en af ​​attributterne repræsenterer nodens datadel, mens den anden attribut repræsenterer den linkede del. En nodeklasse bør også have en konstruktør, getters og settere.

Relaterede: Lær, hvordan du opretter klasser i Java

Getters og settere giver andre klasser (f.eks. Den linkede listeklasse) adgang til de forskellige noder inden for den linkede liste.

Node klasse eksempel

Nedenfor er et nodeklasseeksempel, så du kan få en idé om, hvad vi mener:

offentlig klasse Node {
private int Data;
privat Node NextNode;
//constructor
offentlig knude () {
Data = 0;
NextNode = null;
}
// getters og setters
public int getData () {
returnere data;
}
public void setData (int data) {
Data = data;
}
offentlig knude getNextNode () {
returner NextNode;
}
public void setNextNode (Node nextNode) {
NextNode = nextNode;
}
}

I dette eksempel gemmer dataattributten hele talværdier. Nu hvor du har nodeklassen, er det tid til at gå videre til den linkede liste.

Nedenfor er et eksempel på en linket liste i Java.

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

Koden ovenfor vil oprette en linket listeklasse, men uden dens forskellige operationer kan klassen ses som ækvivalent til en tom skal. Datastrukturen på den linkede liste har flere operationer, der kan bruges til at udfylde den:

• Indsæt foran.
• Indsæt i midten.
• Indsæt bagpå.

Relaterede: Sådan opbygges datastrukturer med JavaScript ES6 -klasser

Den sammenkædede lister samling af indsættelsesmetoder er en grund til, at en udvikler kan vælge at bruge disse data struktur over en anden datastruktur såsom stakke (som kun tillader indsættelse og sletning fra toppen).

Brug af indsatsen foran

Indsatsen på forsiden metode, som navnet antyder, indsætter nye data (eller nye noder) på forsiden af ​​den linkede liste.

Indsæt ved Front Method Eksempel

Nedenfor er et eksempel på, hvordan du vil indsætte nye data forrest på din liste.

 // indsæt knude foran
public void insertAtFront (int key) {
// opret en ny knude ved hjælp af nodeklassen
Node Temp = ny Node ();
// kontrollere, om Temp -noden blev oprettet
// tildele de data, der blev leveret af brugeren, til den
hvis (Temp! = null) {
Temp.setData (nøgle);
Temp.setNextNode (null);
// kontrollere, om hovedet på den linkede liste er tomt
// tildel noden, der lige blev oprettet, til hovedpositionen
hvis (Head == null) {
Hoved = Temp;
}
// hvis en knude allerede er i hovedpositionen
// tilføj den nye knude til den og indstil den som hoved
andet {
Temp.setNextNode (Head);
Hoved = Temp;
}
}
}

Det insertAtFront metode i eksemplet ovenfor giver en bruger mulighed for at tilføje nye noder til en given linket liste.

Anvendelse af indsatsen på forsiden Eksempel

Nedenfor er et eksempel på, hvordan du vil anvende indsats foran.

public class driver {
// udfører programmet
public static void main (String [] args) {
// opret en ny sammenkædet liste kaldet Liste
LinkedList List = ny LinkedList ();
// tilføj hver værdi foran på den linkede liste som en ny knude
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

Det Chauffør class (som er det navn, der ofte tildeles den eksekverbare klasse i Java), bruger LinkedList -klassen til at oprette en sammenkædet liste med fem lige numre. Når man ser på koden ovenfor, skal det være let at se, at tallet "2" er i hovedpositionen på den linkede liste. Men hvordan kan du bekræfte dette?

Brug af metoden Vis alle noder

Metoden Vis alle noder er en vigtig metode til sammenkædede lister. Uden det vil en udvikler ikke kunne se knudepunkterne i en sammenkædet liste. Den bevæger sig gennem den sammenkædede liste (starter fra hovedet) og udskriver de data, der er gemt i hver knude, der danner listen.

Vis alle noder Metodeeksempel

Nedenfor er et eksempel på brug af visningen alle noter -metoden i Java.

// vis alle noder metode
public void displayAllNodes () {
// opret et nyt nodeopkald Temp og tildel det til lederen af ​​den linkede liste
// hvis hovedet har en nullværdi, så er den linkede liste tom
Node Temp = Hoved;
hvis (Head == null) {
System.out.println ("Listen er tom.");
Vend tilbage;
}
System.out.println ("Listen:");
mens (Temp! = null) {
// udskriv dataene i hver knude til konsollen (startende fra hovedet)
System.out.print (Temp.getData () + "");
Temp = Temp.getNextNode ();
} 
}

Nu hvor displayAllNodes metode er blevet føjet til LinkedList klasse kan du se den sammenkædede liste ved at tilføje en enkelt kodelinje til førerklassen.

Brug af metodeeksemplet Vis alle noder

Nedenfor kan du se, hvordan du ville bruge metoden til visning af alle noder.

// udskriv noderne i en sammenkædet liste
List.displayAllNodes (); 

Udførelse af kodelinjen ovenfor vil producere følgende output i konsollen:

Listen:

2 4 6 8 10

Brug af Find Node -metoden

Der vil være tilfælde, hvor en bruger vil finde en bestemt knude i en linket liste.

For eksempel ville det ikke være praktisk for en bank, der har millioner af kunder, at udskrive alle kunders i deres database, når de kun skal se detaljerne for en bestemt kunde.

Derfor, i stedet for at bruge displayAllNodes metode, er en mere effektiv metode at finde den enkelt knude, der indeholder de nødvendige data. Det er derfor, at søgningen efter en enkelt node -metode er vigtig i den sammenkædede liste datastruktur.

Find eksempel på node metode

Nedenfor er et eksempel på at bruge metoden Find node.

// søg efter en enkelt node ved hjælp af en nøgle
offentlig boolsk findNode (int -nøgle) {
// opret en ny knude og placer den i spidsen for den linkede liste
Node Temp = Hoved;
// mens den aktuelle knude ikke er tom
// kontrollere, om dens data matcher nøglen fra brugeren
mens (Temp! = null) {
hvis (Temp.getData () == nøgle) {
System.out.println ("Noden er på listen"); 
vende tilbage sandt;
}
// gå til den næste knude
Temp = Temp.getNextNode ();
}
// hvis nøglen ikke blev fundet på den linkede liste
System.out.println ("Knuden er ikke på listen"); 
return falsk;
}

Med displayAllNodes metode, bekræftede du, at LinkedList indeholder 5 lige tal fra 2 til 10. Det findNode eksemplet ovenfor kan bekræfte, om et af disse lige tal er tallet 4 ved blot at kalde metoden i førerklassen og angive nummeret som en parameter.

Brug af Find Node Method Eksempel

Nedenfor er et eksempel på, hvordan du ville bruge metoden Find node i praksis.

// kontrollere, om en knude er på den linkede liste
List.findNode (4);

Ovenstående kode vil producere følgende output i konsollen:

Knuden er på listen

Brug af metoden Slet en knude

Ved at bruge det samme bankeksempel ovenfra kan en kunde i bankens database ønske at lukke sin konto. Det er her metoden til sletning af en knude vil være nyttig. Det er den mest komplekse linkede metode.

Metoden Slet en knude søger efter en given knude, sletter denne knude og forbinder den forrige knude med den, der følger den knude, der er blevet slettet.

Slet et node metodeeksempel

Nedenfor er et eksempel på metoden til sletning af en knude.

public void findAndDelete (int key) { 
Node Temp = Hoved; 
Node prev = null; 
// kontrollere, om hovednoden gemmer dataene 
// og slet det 
hvis (Temp! = null && Temp.getData () == nøgle) { 
Head = Temp.getNextNode (); 
Vend tilbage; 
} 
// søg i de andre noder på listen 
// og slet det 
mens (Temp! = null) { 
hvis (Temp.getNextNode (). getData () == nøgle) { 
prev = Temp.getNextNode (). getNextNode (); 
Temp.setNextNode (forrige); 
Vend tilbage; 
} 
Temp = Temp.getNextNode (); 
} 
} 

Brug af eksempelet Slet en knude metode

Nedenfor er et eksempel på, hvordan du bruger metoden delete a node i praksis.

// slet den knude, der gemmer dataene 4
List.findAndDelete (4);
// udskriv alle noder i den linkede liste
List.displayAllNodes ();

Brug af de to kodelinjer ovenfor i den eksisterende driverklasse vil producere følgende output i konsollen:

Listen:
2 6 8 10

Hvis du nåede til slutningen af ​​denne selvstudie -artikel, har du lært:

• Sådan opretter du en node -klasse.
• Sådan opretter du en linket listeklasse.
• Sådan udfyldes en linket listeklasse med sine foruddefinerede metoder.
• Sådan opretter du en førerklasse og bruger de forskellige linkede listemetoder til at opnå det ønskede resultat.

En sammenkædet liste er blot en af ​​mange datastrukturer, som du kan bruge til at gemme, hente og slette data. Da du har alt, hvad du har brug for for at komme i gang, hvorfor ikke prøve disse eksempler selv i Java?

Sådan oprettes og udføres operationer på arrays i Java

Lærer du Java? Lad arrays let håndtere dine data.

Læs Næste

Om forfatteren