En datastruktur använder olika fördefinierade metoder för att lagra, hämta och radera data vilket kulminerar i skapandet av effektiva program. En länkad lista är en populär datastruktur, som består av en lista med noder som är anslutna (eller länkade).
Men hur skapar man en länkad lista i Java? Låt oss ta en titt.
Hur fungerar en länkad lista?
Varje länkad lista börjar med en speciell nod som ofta kallas “huvudet”, som alltid har ansvaret att peka på listans början. Huvudet är viktigt eftersom varje nod i en länkad lista inte behöver följa sin efterföljare fysiskt (vilket innebär att en föregångare och en efterföljare inte behöver vara fysiskt intill varandra).
Liksom alla datastrukturer 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.
Skapa en länkad lista i Java
Ett Java-program som är designat 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 “separation of concerns” som varje utvecklare borde känna till.
Separationsprincipen kräver att varje avsnitt i koden som tar upp ett specifikt problem ska 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 för att skapa en länkad lista i Java är att skapa en nodklass. En nodklass ska ha två attribut; ett av attributen kommer att representera datadelen av noden, medan det andra attributet kommer att representera den länkade delen. En nodklass bör också ha en konstruktor, getters och sättare.
Getters och seters kommer att tillåta andra klasser (såsom den länkade listklassen) att komma åt de olika noderna i den länkade listan.
Exempel på nodklass
Nedan är ett nodklassexempel så att du kan få en uppfattning om vad vi menar:
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 det här exemplet kommer dataattributet att lagra heltalsvärden. Nu när du har nodklassen är det dags att gå vidare till den länkade listan.
Exempel på länkad lista
Nedan är ett exempel på en länkad lista i Java.
public class LinkedList {
private Node Head;
//constructor
public LinkedList() {
Head = null;
}
}
Koden ovan kommer att skapa en länkad listklass, men utan dess olika operationer kan klassen ses som motsvarigheten till ett tomt skal. Den länkade listdatastrukturen har flera operationer som kan användas för att fylla i den:
Sätts in framtill. Sätt in i mitten. Insats baktill.
Den länkade listsamlingen av infogningsmetoder är en anledning till att en utvecklare kan välja att använda denna datastruktur framför en annan datastruktur som t.ex. stackar (som endast tillåter infogning och radering från toppen).
Använda metoden Insert at the Front
Insert at the front-metoden, som namnet antyder, infogar ny data (eller nya noder) längst fram i den länkade listan.
Infoga vid framsidan Metodexempel
Nedan är ett exempel på hur du skulle infoga ny data längst fram i din lista.
//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 exemplet ovan tillåter en användare att lägga till nya noder till en given länkad lista.
Applicering av insatsen vid frontexemplet
Nedan är ett exempel på hur du skulle applicera inlägg framtill.
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 Förare klass (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 borde det vara lätt att se att siffran “2” är i huvudpositionen i den länkade listan. Men hur kan du bekräfta detta?
Använda metoden Visa alla noder
Metoden visa alla noder är en viktig länkad listmetod. Utan det kommer en utvecklare inte att kunna se noderna i en länkad lista. Den går genom den länkade listan (med början från huvudet) och skriver ut data som lagras i varje nod som bildar listan.
Visa alla noder Metodexempel
Nedan är ett exempel på hur man använder metoden visa alla anteckningar 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 när visa alla noder metod har lagts till Länkad lista klass kan du se den länkade listan genom att lägga till en enda kodrad till förarklassen.
Använda metoden Visa alla noder
Nedan ser du hur du skulle använda metoden visa alla noder.
//print the nodes in a linked list
List.displayAllNodes();
Att köra kodraden ovan kommer att producera följande utdata i konsolen:
Listan:
2 4 6 8 10
Använda metoden Hitta nod
Det kommer att finnas tillfällen då en användare vill hitta en specifik nod i en länkad lista.
Det skulle till exempel 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 om en specifik kund.
Därför, istället för att använda visa alla noder metod, är en effektivare metod att hitta den enda nod som innehåller de erforderliga data. Det är därför sökningen efter en enskild nodmetod är viktig i den länkade listdatastrukturen.
Hitta nodmetodexempel
Nedan är ett exempel på hur man använder hitta nodmetoden.
//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 visa alla noder metoden bekräftade du att Länkad lista innehåller 5 jämna nummer från 2 till 10. Den 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å metoden Hitta nod
Nedan är ett exempel på hur du skulle använda hitta nodmetoden i praktiken.
//check if a node is in the linked list
List.findNode(4);
Koden ovan kommer att producera följande utdata i konsolen:
The node is in the list
Använda metoden Ta bort en nod
Med samma bankexempel från ovan kan en kund i bankens databas vilja stänga sitt konto. Det är här metoden 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 efter noden som har tagits bort.
Ta bort ett exempel på en nodmetod
Nedan är ett exempel på metoden ta bort en nod.
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();
}
}
Använda exempel på metoden Ta bort en nod
Nedan är ett exempel på hur metoden ta bort en nod används i praktiken.
//delete the node that holds the data 4
List.findAndDelete(4);
//print all nodes in the linked list
List.displayAllNodes();
Genom att använda de två kodraderna ovan i den redan existerande drivrutinsklassen kommer följande utdata att skapas i konsolen:
The List:
2 6 8 10
Nu kan du skapa länkade listor i Java
Om du kom 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 dess 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 radera data. Eftersom du har allt du behöver för att komma igång, varför inte prova dessa exempel själv i Java?
Om författaren
Kadeisha Kean (39 artiklar publicerade)
Kadeisha Kean är en full-stack mjukvaruutvecklare och teknisk/teknikskribent. Hon har den distinkta förmågan att förenkla några av de mest komplexa tekniska koncepten; producera material som lätt kan förstås av alla nybörjare. Hon brinner för att skriva, utveckla intressant programvara och att resa runt i världen (genom dokumentärer).
Mer från Kadeisha Kean
Prenumerera på vårt nyhetsbrev
Gå med i vårt nyhetsbrev för tekniska tips, recensioner, free e-böcker och exklusiva erbjudanden!
Klicka här för att prenumerera
