En introduksjon til bruk av koblede lister i Java

En datastruktur bruker forskjellige forhåndsdefinerte metoder for å lagre, hente og slette data som kulminerer i opprettelsen av effektive programmer. En koblet liste er en populær datastruktur, som består av en liste over noder som er koblet (eller koblet).

Men hvordan lager du en lenket liste i Java? La oss ta en titt.

Hver koblede liste begynner med en spesiell node som ofte blir referert til som "hodet", som har ansvaret for å peke på starten av listen til enhver tid. Hodet er viktig fordi hver node i en koblet liste ikke trenger å følge sin etterfølger fysisk (noe som betyr at en forgjenger og en etterfølger ikke trenger å være fysisk tilstøtende).

Som enhver datastruktur letter den sammenkoblede listen opprettelse, gjenfinning, innsetting og ødeleggelse gjennom et sett med forhåndsdefinerte funksjoner som kan brukes av enhver utvikler.

Et Java -program som er designet for å lage og manipulere koblede lister, vil ha tre særegne seksjoner; nodeklassen, den sammenkoblede listeklassen og driveren. Selv om disse tre seksjonene kan kombineres i en fil, er det et designprinsipp innen informatikk kjent som "separasjon av bekymringer" som alle utviklere burde vite.

Prinsippet om separasjon av bekymringer tilsier at hver del av koden som tar for seg en bestemt bekymring, skal skilles. Dette prinsippet vil hjelpe deg med å lage renere (mer lesbar) kode og er ideelt for å lage datastrukturer.

Det første trinnet i å lage en koblet liste i Java er å opprette en nodeklasse. En nodeklasse bør ha to attributter; ett av attributtene vil representere datadelen av noden, mens det andre attributtet vil representere den koblede delen. En nodeklasse bør også ha en konstruktør, getters og settere.

I slekt: Lær hvordan du oppretter klasser i Java

Getterne og setterne vil tillate andre klasser (for eksempel den sammenkoblede listeklassen) å få tilgang til de forskjellige nodene i den koblede listen.

Nodeklasseeksempel

Nedenfor er et nodeklasseeksempel for at du skal få en ide om hva vi mener:

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

I dette eksemplet vil dataattributtet lagre heltallsverdier. Nå som du har nodeklassen, er det på tide å gå videre til den koblede listen.

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

offentlig klasse LinkedList {
private Node Head;
//constructor
offentlig LinkedList () {
Hode = null;
}
}

Koden ovenfor vil opprette en koblet listeklasse, men uten de forskjellige operasjonene kan klassen sees på som ekvivalent med et tomt skall. Datastrukturen i den koblede listen har flere operasjoner som kan brukes til å fylle den ut:

• Sett inn foran.
• Sett inn i midten.
• Sett inn på baksiden.

I slekt: Hvordan bygge datastrukturer med JavaScript ES6 -klasser

Den sammenkoblede listen med innsettingsmetoder er en grunn til at en utvikler kan velge å bruke disse dataene struktur over en annen datastruktur, for eksempel stabler (som bare tillater innsetting og sletting fra toppen).

Bruke innsatsen foran

Sett inn foran metoden, som navnet antyder, setter inn nye data (eller nye noder) på forsiden av den koblede listen.

Sett inn ved eksempelmetoden foran

Nedenfor er et eksempel på hvordan du vil sette inn nye data øverst på listen.

 // sett inn node foran metode
public void insertAtFront (int key) {
// opprett en ny node ved hjelp av nodeklassen
Node Temp = ny Node ();
// sjekk om Temp -noden ble opprettet
// tilordne dataene som ble levert av brukeren til den
hvis (Temp! = null) {
Temp.setData (nøkkel);
Temp.setNextNode (null);
// sjekk om hodet på den koblede listen er tomt
// tilordne noden som nettopp ble opprettet til hodeposisjonen
hvis (Head == null) {
Hode = Temp;
}
// hvis en node allerede er i hodeposisjonen
// legg til den nye noden og sett den som hodet
annet {
Temp.setNextNode (Head);
Hode = Temp;
}
}
}

De insertAtFront metoden i eksemplet ovenfor lar en bruker legge til nye noder i en gitt lenket liste.

Påføring av innsatsen på forsiden

Nedenfor er et eksempel på hvordan du vil bruke innsatsen foran.

offentlig klasse sjåfør {
// utfører programmet
public static void main (String [] args) {
// opprett en ny koblet liste kalt List
LinkedList List = ny LinkedList ();
// legg til hver verdi på forsiden av den koblede listen som en ny node
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

De Sjåfør class (som er navnet som ofte er tilordnet den kjørbare klassen i Java), bruker LinkedList -klassen til å lage en koblet liste med fem partall. Når du ser på koden ovenfor, bør det være lett å se at tallet "2" er i topposisjonen i den koblede listen. Men hvordan kan du bekrefte dette?

Bruke metoden Vis alle noder

Metoden for visning av alle noder er en viktig koblet liste -metode. Uten det vil en utvikler ikke kunne se nodene i en koblet liste. Den går gjennom den koblede listen (starter fra hodet) og skriver ut dataene som er lagret i hver node som danner listen.

Vis alle noder Metodeeksempel

Nedenfor er et eksempel på hvordan du bruker display all notes -metoden i Java.

// vise alle noder -metoden
public void displayAllNodes () {
// opprett et nytt nodeanrop Temp og tilordne det til hodet på den koblede listen
// hvis hodet har en nullverdi, er den koblede listen tom
Node Temp = Hode;
hvis (Head == null) {
System.out.println ("Listen er tom.");
komme tilbake;
}
System.out.println ("Listen:");
mens (Temp! = null) {
// skriv ut dataene i hver node til konsollen (starter fra hodet)
System.out.print (Temp.getData () + "");
Temp = Temp.getNextNode ();
} 
}

Nå som displayAllNodes metoden er lagt til LinkedList klasse kan du se den koblede listen ved å legge til en enkelt linje med kode i førerklassen.

Bruke metodeeksempelet Vis alle noder

Nedenfor ser du hvordan du bruker metoden for visning av alle noder.

// Skriv ut nodene i en koblet liste
List.displayAllNodes (); 

Utførelse av kodelinjen ovenfor gir følgende utgang i konsollen:

Listen:

2 4 6 8 10

Bruke Find Node -metoden

Det vil være tilfeller når en bruker vil finne en bestemt node i en koblet liste.

For eksempel ville det ikke være praktisk for en bank som har millioner av kunder å skrive ut alle kundene i databasen når de bare trenger å se detaljene til en bestemt kunde.

Derfor, i stedet for å bruke displayAllNodes metode, er en mer effektiv metode å finne enkeltnoden som inneholder nødvendige data. Dette er grunnen til at søket etter en enkelt node -metode er viktig i datastrukturen i den koblede listen.

Finn eksempel på node metode

Nedenfor er et eksempel på bruk av finnemetoden.

// søk etter en enkelt node ved hjelp av en nøkkel
offentlig boolsk findNode (int key) {
// opprett en ny node og plasser den i spissen for den koblede listen
Node Temp = Hode;
// mens den nåværende noden ikke er tom
// sjekk om dataene samsvarer med nøkkelen fra brukeren
mens (Temp! = null) {
hvis (Temp.getData () == nøkkel) {
System.out.println ("Noden er i listen"); 
returner sant;
}
// gå til neste node
Temp = Temp.getNextNode ();
}
// hvis nøkkelen ikke ble funnet i den koblede listen
System.out.println ("Noden er ikke på listen"); 
return falsk;
}

Med displayAllNodes metode, bekreftet du at LinkedList inneholder 5 partall fra 2 til 10. De finnNode eksemplet ovenfor kan bekrefte om et av disse partallene er tallet 4 ved ganske enkelt å kalle metoden i førerklassen og angi tallet som en parameter.

Bruk eksempelet Find Node Method

Nedenfor er et eksempel på hvordan du vil bruke finnemetoden i praksis.

// sjekk om en node er i den koblede listen
List.findNode (4);

Koden ovenfor gir følgende utgang i konsollen:

Noden er på listen

Bruke metoden Slett en node

Ved å bruke det samme bankeksemplet ovenfra, kan en kunde i bankens database ønske å lukke kontoen sin. Det er her slette -en -noden -metoden vil være nyttig. Det er den mest komplekse koblede listemetoden.

Metoden Slett en node søker etter en gitt node, sletter den noden og kobler den forrige noden til den som følger noden som er slettet.

Slett et Node Method -eksempel

Nedenfor er et eksempel på slett en node -metode.

public void findAndDelete (int key) { 
Node Temp = Hode; 
Node prev = null; 
// sjekk om hodetoden holder dataene 
// og slett den 
if (Temp! = null && Temp.getData () == nøkkel) { 
Head = Temp.getNextNode (); 
komme tilbake; 
} 
// søk i de andre nodene i listen 
// og slett den 
mens (Temp! = null) { 
if (Temp.getNextNode (). getData () == nøkkel) { 
prev = Temp.getNextNode (). getNextNode (); 
Temp.setNextNode (forrige); 
komme tilbake; 
} 
Temp = Temp.getNextNode (); 
} 
} 

Bruk eksempelet Slett en node

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

// slette noden som inneholder dataene 4
List.findAndDelete (4);
// Skriv ut alle noder i den koblede listen
List.displayAllNodes ();

Ved å bruke de to kodelinjene ovenfor i den eksisterende driverklassen vil du få følgende utdata i konsollen:

Listen:
2 6 8 10

Hvis du kom til slutten av denne opplæringsartikkelen, har du lært:

• Hvordan lage en nodeklasse.
• Hvordan lage en sammenkoblet liste.
• Hvordan fylle ut en lenket listeklasse med sine forhåndsdefinerte metoder.
• Hvordan lage en sjåførklasse og bruke de forskjellige listede metodene for å oppnå ønsket resultat.

En koblet liste er bare en av mange datastrukturer som du kan bruke til å lagre, hente og slette data. Siden du har alt du trenger for å komme i gang, hvorfor ikke prøve disse eksemplene selv i Java?

Hvordan lage og utføre operasjoner på matriser i Java

Lærer du Java? La matriser håndtere dataene dine enkelt.

Les neste

Om forfatteren