Lära Implementering av LinkedList i Java | Grundläggande Datastrukturer i Java

Det är dags att utmana dig själv med några riktigt komplexa uppgifter.

Vi kommer att implementera vår förenklade datastruktur—specifikt SinglyLinkedList.

Vi börjar med att implementera klassen Node, som kommer att lagra ett värde och en referens till nästa Node.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Implementeringen av klassen Node i SinglyLinkedList visades redan i föregående kapitel, så vi kommer inte att uppehålla oss vid den länge.

Nästa steg är att skapa klassen SinglyLinkedList, där vi definierar all logik för vår datastruktur:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }
}

Vi skapade fältet Node head, som kommer att lagra det första elementet i vår datastruktur.

I en vanlig LinkedList finns det också en head och tail som lagrar det första och sista elementet i datastrukturen. Eftersom datastrukturen ska vara tom vid initiering sätter vi detta fält till null i konstruktorn.

Vår datastruktur behöver stödja alla CRUD-operationer.

Skapa

Låt oss gå steg för steg och skriva en metod för att lägga till ett element i slutet av listan, vilket representerar Create-operationen:

SinglyLinkedList.java


              12345678910111213141516171819202122
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        current.next = newNode;
    }
}

Ovan kan du se implementeringen av metoden för att lägga till ett element i slutet av listan. Låt oss gå igenom hur denna metod fungerar:

Ett objekt av klassen Node, newNode, skapas och initieras via konstruktorn, där data från parametrarna i metoden append() skickas in;
Därefter kontrolleras om listan är tom, och om så är fallet ersätts det första elementet i listan (head) med newNode genom ompekning;
Sedan läggs en return-sats till för att avsluta metoden;
Om listan inte är tom skapas ett nytt objekt, current, som representerar Node head i detta sammanhang;
Med hjälp av en while-loop itereras genom hela listan tills current.next är null, det vill säga tills det fastställs att nästa element i listan är tomt;
När det sista icke-noll-elementet i listan hittas, sätts dess länk till newNode, vilket lägger till elementet i listan.

Med andra ord var målet med append-metoden att sätta länken för det sista elementet till det nya elementet. På detta sätt läggs ett nytt element till i listan.

Läs

Låt oss gå vidare; nu behöver vi implementera läsoperationen.

SinglyLinkedList.java


              12345678
            
public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

Läsoperationen är ganska enkel. Vi behöver iterera genom varje element i listan och skriva ut dem på skärmen. I vårt fall använder vi även platshållaren current, som vi initierar med Node head;
Därefter anger vi villkoret för while-loopen till current != null och skriver ut fältet data på skärmen;
För att iterera genom listan använder vi referensen genom att tilldela om current, vilket ser ut som current = current.next;;
Vi gör detta tills Node current blir tom. Därefter lämnar vi loopen och går vidare till nästa rad.

Fundera förresten på hur man kan ersätta denna while-loop med en do-while-loop. Är det möjligt alls?

Uppdatera

Nu går vi vidare till uppdateringsmetoden, som är mer intressant i sin implementation:

SinglyLinkedList.java


              12345678910111213
            
public void update(int index, int newData) {
    if (index < 0 || index >= size()) {
        System.out.println("Invalid index");
        return;
    }

    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }

    current.data = newData;
}

Först kontrollerar vi om detta index finns i vår lista med ett if-uttryck. Om inte, skriver vi ut meddelandet "Invalid index" och avslutar metoden. Detta görs för att undvika fel;
Om indexet är inom listans gränser fortsätter vi med den välbekanta algoritmen. Först skapar vi ett objekt av klassen Node kallat current, som vi initierar som head;
Istället för att använda en while-loop använder vi en for-loop, vilket är mer lämpligt här eftersom vi vet exakt antal iterationer vi behöver. Antalet iterationer är lika med värdet på parametern index;
Vår loop ser ut så här:
for (int i = 0; i < index; i++). I denna loop hittar vi det önskade elementet med den välbekanta operationen: current = current.next;
När vi har hittat det önskade elementet tilldelar vi dess attribut data ett nytt värde genom att utföra operationen
current.data = newData. Vi hämtar newData från parametrarna till denna metod.

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 1. Kapitel 6

Fråga AI

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

Suggested prompts:

Can you show me the code for the append method?

How would you implement the read operation in code?

Can you explain how the update method works with an example?

Svep för att visa menyn

Det är dags att utmana dig själv med några riktigt komplexa uppgifter.

Vi kommer att implementera vår förenklade datastruktur—specifikt SinglyLinkedList.

Vi börjar med att implementera klassen Node, som kommer att lagra ett värde och en referens till nästa Node.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Implementeringen av klassen Node i SinglyLinkedList visades redan i föregående kapitel, så vi kommer inte att uppehålla oss vid den länge.

Nästa steg är att skapa klassen SinglyLinkedList, där vi definierar all logik för vår datastruktur:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }
}

Vi skapade fältet Node head, som kommer att lagra det första elementet i vår datastruktur.

Vår datastruktur behöver stödja alla CRUD-operationer.

Skapa

Låt oss gå steg för steg och skriva en metod för att lägga till ett element i slutet av listan, vilket representerar Create-operationen:

SinglyLinkedList.java


              12345678910111213141516171819202122
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        current.next = newNode;
    }
}

Ovan kan du se implementeringen av metoden för att lägga till ett element i slutet av listan. Låt oss gå igenom hur denna metod fungerar:

Ett objekt av klassen Node, newNode, skapas och initieras via konstruktorn, där data från parametrarna i metoden append() skickas in;
Därefter kontrolleras om listan är tom, och om så är fallet ersätts det första elementet i listan (head) med newNode genom ompekning;
Sedan läggs en return-sats till för att avsluta metoden;
Om listan inte är tom skapas ett nytt objekt, current, som representerar Node head i detta sammanhang;
Med hjälp av en while-loop itereras genom hela listan tills current.next är null, det vill säga tills det fastställs att nästa element i listan är tomt;
När det sista icke-noll-elementet i listan hittas, sätts dess länk till newNode, vilket lägger till elementet i listan.

Med andra ord var målet med append-metoden att sätta länken för det sista elementet till det nya elementet. På detta sätt läggs ett nytt element till i listan.

Läs

Låt oss gå vidare; nu behöver vi implementera läsoperationen.

SinglyLinkedList.java


              12345678
            
public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

Läsoperationen är ganska enkel. Vi behöver iterera genom varje element i listan och skriva ut dem på skärmen. I vårt fall använder vi även platshållaren current, som vi initierar med Node head;
Därefter anger vi villkoret för while-loopen till current != null och skriver ut fältet data på skärmen;
För att iterera genom listan använder vi referensen genom att tilldela om current, vilket ser ut som current = current.next;;
Vi gör detta tills Node current blir tom. Därefter lämnar vi loopen och går vidare till nästa rad.

Fundera förresten på hur man kan ersätta denna while-loop med en do-while-loop. Är det möjligt alls?

Uppdatera

Nu går vi vidare till uppdateringsmetoden, som är mer intressant i sin implementation:

SinglyLinkedList.java


              12345678910111213
            
public void update(int index, int newData) {
    if (index < 0 || index >= size()) {
        System.out.println("Invalid index");
        return;
    }

    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }

    current.data = newData;
}

Först kontrollerar vi om detta index finns i vår lista med ett if-uttryck. Om inte, skriver vi ut meddelandet "Invalid index" och avslutar metoden. Detta görs för att undvika fel;
Om indexet är inom listans gränser fortsätter vi med den välbekanta algoritmen. Först skapar vi ett objekt av klassen Node kallat current, som vi initierar som head;
Istället för att använda en while-loop använder vi en for-loop, vilket är mer lämpligt här eftersom vi vet exakt antal iterationer vi behöver. Antalet iterationer är lika med värdet på parametern index;
Vår loop ser ut så här:
for (int i = 0; i < index; i++). I denna loop hittar vi det önskade elementet med den välbekanta operationen: current = current.next;
När vi har hittat det önskade elementet tilldelar vi dess attribut data ett nytt värde genom att utföra operationen
current.data = newData. Vi hämtar newData från parametrarna till denna metod.

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 1. Kapitel 6