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 forbundet).

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

Hvordan fungerer en linket liste?

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.

Oprettelse af en linket liste i Java

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 datadelen af noden, mens den anden attribut repræsenterer den sammenkædede 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:

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

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

Eksempel på tilknyttet liste

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

public class LinkedList {  
 private Node Head;  
 //constructor  
 public LinkedList() {  
 Head = 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 denne datastruktur frem for en anden datastruktur, f.eks. Stakke (hvilket 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.

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

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

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?

mac desktop tændes ikke

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.

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

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 ser du, hvordan du vil bruge metoden til visning af alle noder.

//print the nodes in a linked list  
 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 datastrukturen på den sammenkædede liste.

Find Node Method Eksempel

Nedenfor er et eksempel på at bruge metoden 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;  
 }

Med displayAllNodes metode, bekræftede du, at LinkedList indeholder 5 lige tal fra 2 til 10. The 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.

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

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

The node is in the list

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

Brug Eksempel på metode til sletning af en knude

Nedenfor er et eksempel på at bruge metoden delete a node i praksis.

hvordan man opretter en Windows -batchfil

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

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

The List:  
2 6 8 10

Nu kan du oprette sammenkædede lister i Java

Hvis du nåede til slutningen af denne tutorialartikel, 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 behøver for at komme i gang, hvorfor ikke prøve disse eksempler selv i Java?

Del Del Tweet E -mail 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 Relaterede emner

Programmering
Java
Programmering
Kodningstip

Om forfatteren Kadeisha Kean(21 artikler udgivet)

Kadeisha Kean er en softwareudvikler i fuld stak og teknisk/teknologisk forfatter. Hun har den særlige evne til at forenkle nogle af de mest komplekse teknologiske begreber; producerer materiale, der let kan forstås af enhver nybegynder i teknologi. Hun brænder for at skrive, udvikle interessant software og rejse rundt i verden (gennem dokumentarer).

Mere fra Kadeisha Kean

Abonner på vores nyhedsbrev

Tilmeld dig vores nyhedsbrev for at få tekniske tips, anmeldelser, gratis e -bøger og eksklusive tilbud!

Klik her for at abonnere