Wie man eine Verkettete Liste Datenstruktur in Java erstellt

Eine Datenstruktur zu erstellen, die effektiv eine Sammlung von Elementen verwaltet, kann in der Programmierung eine Herausforderung darstellen. Eine der am häufigsten verwendeten Strukturen ist die Verkettete Liste. In diesem Blogbeitrag führen wir Sie durch den Prozess der Erstellung einer Verketteten Liste in Java, selbst wenn es bereits eine integrierte Klasse in der Java-Standardbibliothek gibt.

Das Problem verstehen

Wenn Sie an Datenstrukturen denken, denken Sie vielleicht an Arrays, aber manchmal sind diese unzureichend. Hier kommen verkettete Listen ins Spiel. Eine Verkettete Liste ermöglicht es Ihnen, Elemente effizient einzufügen und zu löschen, ohne ein Array neu zu dimensionieren. Sie besteht aus einer Sequenz von Knoten, wobei jeder Knoten Daten und eine Referenz auf den nächsten Knoten enthält.

Die integrierte Option

Java bietet eine integrierte LinkedList-Klasse im Paket java.util, die praktisch und in vielen Situationen geeignet ist. Allerdings kann das Erstellen einer eigenen Implementierung Ihr Verständnis vertiefen und Ihnen mehr Kontrolle über das Verhalten der Datenstruktur geben.

Erstellen Sie Ihre eigene Verkettete Liste

Im Folgenden werden wir untersuchen, wie wir eine einfache Verkettete Liste von Grund auf neu erstellen können. In diesem Tutorial konzentrieren wir uns auf eine einfach verkettete Liste, die das Einfügen und Löschen von Knoten vom Anfang aus ermöglicht.

Schritt 1: Definieren Sie die Link-Klasse

Zunächst müssen wir eine Link-Klasse erstellen, um jedes Element in der Liste darzustellen. So sieht es im Code aus:

class Link {
    public int data1;
    public double data2;
    public Link nextLink;

    // Link-Konstruktor
    public Link(int d1, double d2) {
        data1 = d1;
        data2 = d2;
    }

    // Link-Daten ausgeben
    public void printLink() {
        System.out.print("{" + data1 + ", " + data2 + "} ");
    }
}

Schritt 2: Definieren Sie die LinkList-Klasse

Als Nächstes benötigen wir eine Klasse für die gesamte Liste:

class LinkList {
    private Link first;

    // LinkList-Konstruktor
    public LinkList() {
        first = null;
    }

    // Gibt true zurück, wenn die Liste leer ist
    public boolean isEmpty() {
        return first == null;
    }

    // Fügt einen neuen Link am Anfang der Liste ein
    public void insert(int d1, double d2) {
        Link link = new Link(d1, d2);
        link.nextLink = first;
        first = link;
    }

    // Löscht den Link am Anfang der Liste
    public Link delete() {
        Link temp = first;
        if (first == null) {
            return null; // oder Ausnahme werfen
        }
        first = first.nextLink;
        return temp;
    }

    // Gibt alle Links in der Liste aus
    public void printList() {
        Link currentLink = first;
        System.out.print("Liste: ");
        while (currentLink != null) {
            currentLink.printLink();
            currentLink = currentLink.nextLink;
        }
        System.out.println("");
    }
}

Schritt 3: Testen Sie die LinkList

Schließlich implementieren wir eine Hauptmethode, um unsere Verkettete Liste zu testen:

class LinkListTest {
    public static void main(String[] args) {
        LinkList list = new LinkList();

        // Fügen Sie einige Elemente ein
        list.insert(1, 1.01);
        list.insert(2, 2.02);
        list.insert(3, 3.03);
        list.insert(4, 4.04);
        list.insert(5, 5.05);

        // Geben Sie die Liste aus
        list.printList();

        // Elemente löschen
        while (!list.isEmpty()) {
            Link deletedLink = list.delete();
            System.out.print("gelöscht: ");
            deletedLink.printLink();
            System.out.println("");
        }
        list.printList();
    }
}

Fazit

In diesem Blogpost haben wir untersucht, wie man eine benutzerdefinierte Verkettete Liste in Java erstellt, die über grundlegende Methoden zum Einfügen, Löschen und Ausgeben von Knoten verfügt. Während die native LinkedList-Klasse in Javas Standardbibliothek für viele Anwendungen ausreichen mag, kann die Implementierung Ihrer eigenen eine lohnende Erfahrung sein, die Ihre Programmierfähigkeiten verbessert.

Weitere Verbesserungen

Nachdem Sie diese grundlegende Implementierung beherrscht haben, ziehen Sie in Betracht, Folgendes hinzuzufügen:

• Doppelt verkettete Liste: Jeder Knoten sollte Referenzen auf sowohl den nächsten als auch den vorherigen Knoten haben.
• Einfügen/Löschen in der Mitte/Am Ende: Methoden zum Hinzufügen oder Entfernen von Knoten aus verschiedenen Positionen.
• Get- und Sortiermethoden: Funktionen zum Abrufen bestimmter Elemente oder zum Sortieren der verketteten Liste.

Sich mit diesen Verbesserungen vertraut zu machen, kann Ihre Fähigkeiten auf die nächste Stufe heben. Viel Spaß beim Programmieren!