En introduktion till användning av länkade listor i Java

En datastruktur använder olika fördefinierade metoder för att lagra, hämta och ta bort data som kulminerar i skapandet av effektiva program. En länkad lista är en populär datastruktur, som består av en lista över noder som är anslutna (eller länkade).

Men hur skapar du en länkad lista i Java? Låt oss ta en titt.

Varje länkad lista börjar med en speciell nod som ofta kallas "huvudet", som har ansvaret att peka på listans början hela tiden. Huvudet är viktigt eftersom varje nod i en länkad lista inte behöver följa sin efterträdare fysiskt (vilket betyder att en föregångare och en efterträdare inte behöver vara fysiskt intill varandra).

Liksom varje datastruktur underlättar den länkade listan skapande, hämtning, infogning och förstörelse genom en uppsättning fördefinierade funktioner som kan användas av alla utvecklare.

Ett Java -program som är utformat för att skapa och manipulera länkade listor kommer att ha tre distinkta sektioner; nodklassen, den länkade listklassen och drivrutinen. Även om dessa tre sektioner kan kombineras i en fil, finns det en designprincip inom datavetenskap som kallas "separering av problem" som varje utvecklare bör känna till.

Principen om separering av oro dikterar att varje avsnitt i koden som tar upp ett specifikt problem bör separeras. Denna princip hjälper dig att skapa renare (mer läsbar) kod och är idealisk för att skapa datastrukturer.

Det första steget i att skapa en länkad lista i Java är att skapa en nodklass. En nodklass bör ha två attribut; ett av attributen representerar nodens datadel, medan det andra attributet representerar den länkade delen. En nodklass bör också ha en konstruktör, getters och setters.

Relaterad: Lär dig hur du skapar klasser i Java

Getters och setters kommer att tillåta andra klasser (t.ex. klassen för länkade listor) att komma åt de olika noder i den länkade listan.

Nodklass Exempel

Nedan följer ett exempel på en nodklass för att du ska få en uppfattning om vad vi menar:

offentlig klass Node {
privat int Data;
privat nod NextNode;
//constructor
offentlig nod () {
Data = 0;
NextNode = null;
}
// getters och setters
public int getData () {
returnera data;
}
public void setData (int data) {
Data = data;
}
public Node getNextNode () {
returnera NextNode;
}
public void setNextNode (Node nextNode) {
NextNode = nextNode;
}
}

I det här exemplet lagrar dataattributet heltalsvärden. Nu när du har nodklassen är det dags att gå vidare till den länkade listan.

Nedan är ett exempel på en länkad lista i Java.

public class LinkedList {
privat nodhuvud;
//constructor
public LinkedList () {
Huvud = null;
}
}

Koden ovan skapar en länkad listklass, men utan dess olika funktioner kan klassen ses som motsvarande ett tomt skal. Den länkade listans datastruktur har flera operationer som kan användas för att fylla i den:

• Insats framtill.
• Infoga i mitten.
• Insats på baksidan.

Relaterad: Hur man bygger datastrukturer med JavaScript ES6 -klasser

Den länkade listans samling av infogningsmetoder är en anledning till att en utvecklare kan välja att använda denna data struktur över en annan datastruktur, till exempel staplar (som bara tillåter infogning och radering uppifrån).

Använda skäret på den främre metoden

Insatsen längst fram, som namnet antyder, infogar ny data (eller nya noder) längst fram i den länkade listan.

Infoga vid det främre metodexemplet

Nedan följer ett exempel på hur du skulle infoga ny data längst fram i listan.

 // infoga nod vid frontmetoden
public void insertAtFront (int key) {
// skapa en ny nod med nodklassen
Nodtemp = ny nod ();
// kontrollera om Temp -noden skapades
// tilldela den data som användaren tillhandahållit
om (Temp! = null) {
Temp.setData (nyckel);
Temp.setNextNode (null);
// kontrollera om huvudet på den länkade listan är tomt
// tilldela noden som just skapades till huvudpositionen
if (Head == null) {
Huvud = Temp;
}
// om en nod redan är i huvudpositionen
// lägg till den nya noden och ställ den som huvud
annat {
Temp.setNextNode (huvud);
Huvud = Temp;
}
}
}

De insertAtFront metod i exemplet ovan tillåter en användare att lägga till nya noder till en given länkad lista.

Applicera insatsen i det främre exemplet

Nedan är ett exempel på hur du skulle applicera insats på framsidan.

public class -förare {
// kör programmet
public static void main (String [] args) {
// skapa en ny länkad lista som heter List
LinkedList List = ny LinkedList ();
// lägg till varje värde längst fram i den länkade listan som en ny nod
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

De Förare class (vilket är namnet som ofta tilldelas den körbara klassen i Java) använder klassen LinkedList för att skapa en länkad lista med fem jämna nummer. Om man tittar på koden ovan ska det vara lätt att se att siffran "2" ligger i huvudpositionen i den länkade listan. Men hur kan du bekräfta detta?

Använda metoden Visa alla noder

Visa alla noder -metoden är en viktig länkad listmetod. Utan det kommer en utvecklare inte att kunna se noder i en länkad lista. Den går genom den länkade listan (från huvudet) och skriver ut data som lagras i varje nod som utgör listan.

Visa alla noder Metodexempel

Nedan är ett exempel på hur du använder metoden Visa alla anteckningar i Java.

// visa alla noder metod
public void displayAllNodes () {
// skapa ett nytt nodanrop Temp och tilldela det till chefen för den länkade listan
// om huvudet har ett nollvärde är den länkade listan tom
Nod Temp = Huvud;
if (Head == null) {
System.out.println ("Listan är tom.");
lämna tillbaka;
}
System.out.println ("Listan:");
medan (Temp! = null) {
// skriv ut data i varje nod till konsolen (från huvudet)
System.out.print (Temp.getData () + "");
Temp = Temp.getNextNode ();
} 
}

Nu när displayAllNodes metoden har lagts till i Länkad lista klass kan du visa den länkade listan genom att lägga till en enda kodrad i förarklassen.

Använda exempel på metod för Visa alla noder

Nedan ser du hur du använder metoden för att visa alla noder.

// skriv ut noderna i en länkad lista
List.displayAllNodes (); 

Genom att köra raden ovan kommer följande utdata i konsolen:

Listan:

2 4 6 8 10

Använd metoden Find Node

Det kommer att finnas tillfällen när en användare vill hitta en specifik nod i en länkad lista.

Till exempel skulle det inte vara praktiskt för en bank som har miljontals kunder att skriva ut alla kunders i sin databas när de bara behöver se detaljerna för en specifik kund.

Därför istället för att använda displayAllNodes metod, är en mer effektiv metod att hitta den enda noden som innehåller nödvändig data. Det är därför sökandet efter en enda nodmetod är viktigt i den länkade listdatastrukturen.

Hitta exempel på nodmetod

Nedan är ett exempel på hur du använder metoden Söknod.

// sök efter en enda nod med en nyckel
public boolean findNode (int key) {
// skapa en ny nod och placera den i spetsen för den länkade listan
Nod Temp = Huvud;
// medan den aktuella noden inte är tom
// kontrollera om dess data matchar nyckeln från användaren
medan (Temp! = null) {
if (Temp.getData () == key) {
System.out.println ("Noden finns i listan"); 
återvända sant;
}
// flytta till nästa nod
Temp = Temp.getNextNode ();
}
// om nyckeln inte hittades i den länkade listan
System.out.println ("Noden finns inte i listan"); 
return falsk;
}

Med displayAllNodes metod bekräftade du att Länkad lista innehåller 5 jämna tal från 2 till 10. De findNode exemplet ovan kan bekräfta om ett av dessa jämna nummer är siffran 4 genom att helt enkelt anropa metoden i förarklassen och ange numret som en parameter.

Använda exempel på Find Node Method

Nedan följer ett exempel på hur du skulle använda metoden för att hitta nod i praktiken.

// kontrollera om en nod finns i den länkade listan
List.findNode (4);

Koden ovan ger följande utdata i konsolen:

Noden finns i listan

Använd metoden Ta bort en nod

Med samma bankexempel ovan kan en kund i bankens databas vilja stänga sitt konto. Det är här metoden för att ta bort en nod kommer att vara användbar. Det är den mest komplexa länkade listmetoden.

Metoden Ta bort en nod söker efter en given nod, tar bort den noden och länkar den föregående noden till den som följer noden som har tagits bort.

Ta bort ett exempel på en nodmetod

Nedan följer ett exempel på metoden delete a node.

public void findAndDelete (int key) { 
Nod Temp = Huvud; 
Nod prev = null; 
// kontrollera om huvudnoden innehåller data 
// och ta bort den 
if (Temp! = null && Temp.getData () == key) { 
Head = Temp.getNextNode (); 
lämna tillbaka; 
} 
// söka i de andra noder i listan 
// och ta bort den 
medan (Temp! = null) { 
if (Temp.getNextNode (). getData () == key) { 
prev = Temp.getNextNode (). getNextNode (); 
Temp.setNextNode (föregående); 
lämna tillbaka; 
} 
Temp = Temp.getNextNode (); 
} 
} 

Använda exemplet Ta bort en nodmetod

Nedan följer ett exempel på hur du använder delete a node -metoden i praktiken.

// ta bort noden som innehåller data 4
List.findAndDelete (4);
// skriv ut alla noder i den länkade listan
List.displayAllNodes ();

Om du använder de två kodraderna ovan i den befintliga förarklassen kommer följande utdata att visas i konsolen:

Listan:
2 6 8 10

Om du tog dig till slutet av den här självstudieartikeln har du lärt dig:

• Hur man skapar en nodklass.
• Hur man skapar en länkad listklass.
• Hur man fyller i en länkad listklass med sina fördefinierade metoder.
• Hur man skapar en förarklass och använder de olika länkade listmetoderna för att uppnå önskat resultat.

En länkad lista är bara en av många datastrukturer som du kan använda för att lagra, hämta och ta bort data. Eftersom du har allt du behöver för att komma igång, varför inte prova dessa exempel själv i Java?

Hur man skapar och utför operationer på matriser i Java

Lär dig Java? Låt matriser hantera dina data med lätthet.

Läs Nästa

Om författaren