En introduksjon til bruk av koblede lister i Java

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 koblet liste i Java? La oss ta en titt.



Hvordan fungerer en lenket liste?

Hver koblede liste begynner med en spesiell node som ofte blir referert til som 'hodet', som har ansvaret for å peke til begynnelsen av listen til enhver tid. Hodet er viktig fordi hver node i en lenket 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 alle datastrukturer letter den sammenkoblede listen opprettelse, gjenfinning, innsetting og ødeleggelse gjennom et sett med forhåndsdefinerte funksjoner som kan brukes av enhver utvikler.

Opprette en lenket liste i Java

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:


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 eksemplet vil dataattributtet lagre heltallsverdier. Nå som du har nodeklassen, er det på tide å gå videre til den koblede listen.

Eksempel på lenket liste

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

public class LinkedList {
private Node Head;
//constructor
public LinkedList() {
Head = 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 denne datastrukturen fremfor 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.

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

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.

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

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?

disken min er på 100 hele tiden

Bruke metoden Vis alle noder

Metoden for visning av alle noder er en viktig metode for koblet liste. 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.

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

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.

//print the nodes in a linked list
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 nodemetode er viktig i datastrukturen i den koblede listen.

Finn eksempel på node metode

Nedenfor er et eksempel på bruk av finnemetoden.

//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, bekreftet du at LinkedList inneholder 5 partall fra 2 til 10. The 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.

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

Koden ovenfor gir følgende utgang i konsollen:

The node is in the list

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

Bruk eksempelet Slett en node

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

hvordan du bruker Adobe Media Encoder
//delete the node that holds the data 4
List.findAndDelete(4);
//print all nodes in the linked list
List.displayAllNodes();

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

The List:
2 6 8 10

Nå kan du opprette koblede lister i Java

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

  • Hvordan lage en nodeklasse.
  • Slik oppretter du en koblet listeklasse.
  • Hvordan fylle ut en lenket listeklasse med sine forhåndsdefinerte metoder.
  • Hvordan lage en førerklasse 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?

Dele Dele kvitring E -post Hvordan lage og utføre operasjoner på matriser i Java

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

Les neste Relaterte temaer
  • Programmering
  • Java
  • Programmering
  • Kodetips
Om forfatteren Kadeisha Kean(21 artikler publisert)

Kadeisha Kean er en fullstabel programvareutvikler og teknisk/teknologisk forfatter. Hun har den særegne evnen til å forenkle noen av de mest komplekse teknologiske konseptene; produsere materiale som lett kan forstås av enhver nybegynner i teknologi. Hun brenner for å skrive, utvikle interessant programvare og reise verden rundt (gjennom dokumentarer).

Mer fra Kadeisha Kean

Abonner på vårt nyhetsbrev

Bli med i vårt nyhetsbrev for tekniske tips, anmeldelser, gratis ebøker og eksklusive tilbud!

Klikk her for å abonnere