Lära Implementering av LinkedList i Java

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.

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å igenom stegen 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:

Vi skapar ett objekt av klassen Node, newNode, och initierar det via konstruktorn, där vi skickar in data från parametrarna till append()-metoden;
Därefter kontrollerar vi om listan är tom, och om så är fallet ersätter vi det första elementet i listan (head) med newNode genom ompekning;
Sedan lägger vi till en return-sats för att avsluta metoden;
Om listan inte är tom skapar vi i denna metod ett nytt objekt, current, som representerar Node head i detta sammanhang;
Med hjälp av en while-loop itererar vi genom hela listan tills current.next är null, vilket innebär att vi har hittat nästa tomma element i listan;
När vi hittar det sista icke-noll-elementet i listan sätter vi dess länk till newNode, och på så sätt lägger vi till elementet i vår lista.

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ägger vi till ett nytt element 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. Det krävs att iterera genom varje element i listan och skriva ut dem på skärmen. I vårt fall används ä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änds referensen genom att omassignera current, vilket ser ut som current = current.next;;
Detta upprepas tills Node current blir tom. Därefter avslutas loopen och vi 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 kontrolleras om detta index finns i vår lista med ett if-uttryck. Om inte, skrivs meddelandet "Invalid index" ut och metoden avslutas. Detta görs för att undvika fel;
Om indexet ligger inom listans gränser fortsätter vi med den välbekanta algoritmen. Först skapas ett objekt av klassen Node kallat current, som initialiseras som head;
Istället för att använda en while-loop används en for-loop, vilket är mer lämpligt här eftersom vi vet exakt antal iterationer som behövs. 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 hittas det önskade elementet med den välbekanta operationen: current = current.next;
När det önskade elementet har hittats tilldelas dess attribut data ett nytt värde genom operationen
current.data = newData. Värdet newData tas från parametrarna till denna metod.

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 1. Kapitel 7

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

Avsnitt 1. Kapitel 7