Einfach verknüpfte Liste in Java

68192
safaiyeh

Ich habe meine eigene Implementierung einer Singly Linked List erstellt. Kann ich irgendetwas verbessern, was die Effizienz angeht? Welche anderen Methoden würden Sie mir empfehlen, um sie zu implementieren? Mein Ziel ist es, nur die Komponenten der grundlegenden Datenstrukturen zu verstehen.

LinkedList:

public class StratchLinkedList {

private Node head;
private int size;

public StratchLinkedList() {
    head = null;
    size = 0;
}

public void add(Object data) {

    Node temp = new Node(data);
    Node curr = head;

    if (head == null) {
        head = temp;
    } else {
        while (curr.getNext() != null) {
            curr = curr.getNext();
        }

        curr.setNext(temp);
    }
}

public void add(Object data, int index) {

    Node temp = new Node(data);
    Node curr = head;

    if (index == 0){
        temp.setNext(head);
        this.head = temp;
    } else{
        for(int i = 1; i < index; i++){
            curr = curr.getNext();
        }
        temp.setNext(curr.getNext());
        curr.setNext(temp);
    }

    this.size++;
}

public void replace(Object data, int index) {
    Node curr = head;
    for (int i = 0; i < 0; i++){
        curr = curr.getNext();
    }

    curr.setData(data);
}

public Object get(int index) {

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

    return curr.getData();
}

public void remove(int index) {

    Node curr = head;

    if (index == 0) {
        head = head.getNext();
    } else {
        for (int i = 1; i < index; i++){
            curr = curr.getNext();
        }

        curr.setNext(curr.getNext().getNext());
    }

    this.size--;
}

public int size() {
    return this.size;
}

public String toString() {
    String list = "";
    list += "[" + this.head.getData() + "]";

    Node curr = head.getNext();
    while (curr != null){
        list += "[" + curr.getData() + "]";
        curr = curr.getNext();
    }

    return list;

}

}

Knoten:

public class Node {

Node next;
Object data;

public Node(Object data) {
    this(data, null);
}

public Node(Object data, Node next) {
    this.next = next;
    this.data = data;
}

public Object getData() {
    return this.data;
}

public void setData(Object data) {
    this.data = data;
}

public Node getNext() {
    return this.next;
}

public void setNext(Node nextNode) {
    this.next = nextNode;
}

}

BEARBEITEN: Code in Arbeit.

public class StratchLinkedList<T> {

private Node head;
private Node tail;
private int size;

public StratchLinkedList() {
    head = null;
    tail = null;
    size = 0;
}

public void insert(T data, int index) {

    if (index > size) {
        throw new IllegalArgumentException("The index [" + index
                + "] is greater than the currentent size [" + size + "].");
    } else {

        Node temp = new Node(data);
        Node current = getNode(index);

        if (index == 0) {
            temp.setNext(head);
            head = temp;
            tail = head;
        } else {
            temp.setNext(current.getNext());
            current.setNext(temp);
        }

        if ( index == size - 1 ) {
            tail.setNext(temp);
            tail = temp;
        }

    }

    size++;
}

public void append(T data) {
    insert(data, size);
}

public void replace(T data, int index) {
    getNode(index).setData(data);
}

public void remove(int index) {

    if (index == 0) {
        head = head.getNext();
    } else {
        getNode(index).setNext(getNode(index).getNext().getNext());
    }

    this.size--;
}

private Node getNode(int index) {

    if ( index > size ) {
        throw new IllegalArgumentException("The index [" + index + "] is greater than the current size [" + size + "].");
    }
    Node current = head;
    for (int i = 1; i < index; i++) {
        current = current.getNext();
    }

    return current;
}

public T get(int index) {
    return getNode(index).getData();
}

public int size() {
    return this.size;
}

public String toString() {
    StringBuilder builder = new StringBuilder();

    Node current = head;
    while( current != null ) {
        builder.append("[" + current.getData() + "]");
        current = current.getNext();
    }

    return builder.toString();

}



private class Node {

    Node next;
    T data;

    public Node(T data) {
        this(data, null);
    }

    public Node(T data, Node next) {
        this.next = next;
        this.data = data;
    }

    public T getData() {
        return this.data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node getNext() {
        return this.next;
    }

    public void setNext(Node nextNode) {
        this.next = nextNode;
    }

}

}
Antworten
22

7 Antworten auf die Frage

18
Brythan

Wiederholen Sie sich nicht (TROCKEN)

public void add(Object data) {

    Node temp = new Node(data);
    Node curr = head;

    if (head == null) {
        head = temp;
    } else {
        while (curr.getNext() != null) {
            curr = curr.getNext();
        }

        curr.setNext(temp);
    }
}

Sie haben ein sizeFeld, deshalb sollten Sie es in dieser Funktion aktualisieren.

Eigentlich können Sie diese Funktion jedoch einfacher schreiben:

public void add(Object data) {
    add(data, size);
}

Das reduziert Ihren duplizierten Code und vereinfacht die Wartung. Es beseitigt auch den Fehler, bei dem Sie die Größe nicht aktualisiert haben. Dies ist einer der Hauptgründe, warum doppelter Code schlecht ist: Es ist leicht, inkonsistente Ergebnisse zu erhalten.

Vertrauen Sie Ihrer Eingabe nicht

public void add(Object data, int index) {

    Node temp = new Node(data);
    Node curr = head;

    if (index == 0){
        temp.setNext(head);
        this.head = temp;
    } else{
        for(int i = 1; i < index; i++){
            curr = curr.getNext();
        }
        temp.setNext(curr.getNext());
        curr.setNext(temp);
    }

    this.size++;
}

Was passiert wenn index > size? Sie werfen ein a, NullPointerExceptionwenn Sie versuchen, den nullZeiger am Ende der Liste dereferenzieren . Das ist eher wenig informativ. Es gibt verschiedene Alternativen. Sie könnten die Liste mit leeren Knoten auffüllen, wenn dies der Fall ist, aber dies wäre ebenso wenig informativ, wenn dies unbeabsichtigt war. Sie könnten eine informativere Ausnahme auslösen:

    if ( index > size ) {
        throw new IllegalArgumentException("The index [" + index + "] is greater than the current size [" + size + "].");
    }

Oder Sie könnten lautlos so tun, als wären indexsie gleich sizeund machen weiter:

    if ( index > size ) {
        index = size;
    }

Wenn das Hinzufügen am Ende der Liste üblich ist, haben Sie eine andere Alternative:

        if ( null == tail ) {
            tail = head;
        }
    } else if ( index >= size ) {
        tail.setNext(temp);
        tail = temp;

Dadurch wird eine neue tailVariable hinzugefügt, die auf das Ende der Liste zeigt. Beachten Sie, dass Sie zusätzliche Änderungen vornehmen müssen, um die tailVariable zu verwalten, wenn Sie auf diese Weise vorgehen. Wenn Sie a nicht beibehalten tail, sollten Sie in Betracht ziehen, die Standardeinstellung vor der Liste hinzuzufügen . In einer verknüpften Liste ist das einfach, während das Hinzufügen am Ende schwierig ist, wenn die Liste einzeln verknüpft ist.

Sie müssen nicht this.mit Feldnamen verwendet werden, es sei denn, Sie haben einen Namenskonflikt (z. B. einen Funktionsparameter). Du kannst es also einfach sagen

    size++;

TROCKEN Teil II

Die Funktionen replaceund get, und removesollten auch auf die Situation achten, in der indexsich die Liste außerhalb der Liste befindet. Für replaceund getmöchten Sie vielleicht eine findFunktion definieren, die Sie gerne verwenden würden

    Node current = find(index);

und als etwas definieren

private Node find(int index) {
    if ( index >= size ) {
        throw new IllegalArgumentException("The index [" + index + "] is greater than the current size [" + size + "].");
    }

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

Beachten Sie, dass ich schreibe, currentanstatt es als abzukürzen curr. Der Bruchteil der Sekunde, den er beim Lesen speichert, wiegt mehr als den Sekundenbruchteil auf, den die Eingabe benötigt. Nicht unbedingt heute, aber in sechs Monaten müssen Sie einen Moment daran denken, was currbedeutet. Und natürlich hat jeder, der es liest, es sofort herausgefunden. Nützlicher Code wird mehr gelesen als geschrieben, daher ist es sinnvoll, für den üblichen Fall zu optimieren.

StringBuilder

public String toString() {
    String list = "";
    list += "[" + this.head.getData() + "]";

    Node curr = head.getNext();
    while (curr != null){
        list += "[" + curr.getData() + "]";
        curr = curr.getNext();
    }

    return list;
}

StringVerwenden Sie StringBuilderanstelle von a die Verwendung von a . StringBuilderist zum Anhängen bestimmt. Regelmäßige StringWerte sind nicht. Die Verwendung +=auf einem Stringerstellt implizit Stringjedes Mal ein Neues . Wenn Sie Glück haben, schreibt der Compiler StringBuilderstattdessen Ihre Version um .

public String toString() {
    StringBuilder builder = new StringBuilder();

    Node current = head;
    while ( current != null ) {
        builder.append("[" + current.getData() + "]");
        current = current.getNext();
    }

    return builder.toString();
}

Beachten Sie, dass dieser Code auch den Fall einer leeren Liste behandelt, was der ursprüngliche Code nicht tat (er würde einen auslösen, NullPointerExceptionwenn er mit einer leeren Liste aufgerufen wird, da er versuchen würde, die Null zu entreissen head).

+1 für 'public void add (Objektdaten) {add (Daten, Größe); } `... elegant und effektiv Aneesh K vor 4 Jahren 1
9
Corbin

Willkommen bei CodeReview! Ich bin kein großer Java-Experte, aber hoffentlich kann ich einen Blick darauf werfen.

Es sieht ziemlich gut aus, aber ich habe ein paar Anmerkungen.


Zu Lernzwecken ist Object in Ordnung, aber in einer echten Implementierung möchten Sie Generika verwenden. Da die Generika rundherum ziemlich einfach sind, könnte dies eine gute Einführung in das Codieren mit Generika sein.


for (int i = 0; i < 0; i++){
    curr = curr.getNext();
}

Ich gehe davon aus, dass dies ein Tippfehler ist. Dies könnte auch eine gute Einführung in das Testen von Einheiten sein, wenn Sie dies noch nicht gemacht haben.


Sie scheinen die Operation "get the node at index x" an vielen verschiedenen Stellen auszuführen. Es sollte in eine Methode gezogen werden.


Knoten ist ein Implementierungsdetail der Liste. Es sollte keine publicKlasse sein, die die Verbraucher sehen können.


Anstatt die Liste jedes Mal zu durchlaufen, wenn Sie ein Element anfügen, sollten Sie eine Endreferenz speichern, damit sie eine konstante Zeit anstatt linear sein kann.


Ich würde in Betracht ziehen, langsame Operationen von der Liste wegzulassen. Wenn Menschen eine bestimmte Datenstruktur verwenden, gehen sie in der Regel davon aus, dass alle Methoden relativ effizient sind.


Um eine verknüpfte Liste direkt in einer Hochsprache zu erstellen, benötigen Sie einen Iterator. So können Sie alle möglichen Dinge erledigen, die wie eine konstante Zeit sehr schön sind, add(Iterator location, Object data)ohne die Daten freizulegen Node(Sie können dies ohne Iterator tun, indem Sie einfach eine getHead()Methode haben und dann die Knoten direkt durchlaufen: /). Dadurch wird auch travseral der Liste etwas sauberer. Wenn Sie die Liste implementieren sollten Iterable, können Sie es als Bonus für for-each-Schleifen verwenden.


Klasseninhalte werden normalerweise unter der Klassendeklaration eingerückt:

public class SomeClass {
    public SomeClass() {}
}

Das hängt natürlich vom persönlichen Stil ab, aber ich habe noch nie gesehen, dass die Implementierung der Klassen mit der Deklaration fluchtet.

Dies ist eine noch kleinere Sache, aber die Benutzer neigen dazu, die thisEigenschaften beim Zugriff auf Eigenschaften wegzulassen, sofern dies nicht erforderlich ist.


public void replace(Object data, int index)

Ich würde erwarten, dass eine Ersetzungsmethode den alten Wert zurückgibt, der in der Liste gespeichert wurde.


Sie sollten sicherstellen, dass sich die Indexwerte im Bereich der Liste befinden. Ein IllegalArgumentExceptionist ein bisschen sinnvoller als ein NullPointerException. (Obwohl es durchaus möglich wäre, nur die NPE passieren zu lassen ...)

Hinweis: Iteratoren machen es etwas schwieriger, einen ungültigen Index bereitzustellen.


Sie sollten StringBuilderin verwenden toString. Normalerweise spielt es keine Rolle, aber für einen Container, der möglicherweise ziemlich groß ist, kann dies einen bedeutenden Leistungsunterschied darstellen.


Sie könnten einen Sentinel-Knoten verwenden. Damit können Sie einige der Spezialfälle rund um den Kopfknoten vereinfachen (wie ich es vor dem Auftreten von Brython versucht habe), und die Argumentation bezüglich der Liste wird etwas einfacher. Leider verschwendet es leider auch ein kleines bisschen Platz, kostet eine Zuweisung und lässt eine leere Liste tatsächlich etwas Unübertroffenes beim Bau tun, aber meh ... In allen Situationen, außer in den am stärksten eingeschränkten Situationen, neigen die Nachteile nicht dazu.

+1, um langsame Operationen zu vermeiden. Machen Sie entweder `add (Object)`, fügen Sie einen Modus am Kopf ein oder halten Sie einen Zeiger auf den letzten Knoten, sodass das Anhängen an das Ende schnell ist. 200_success vor 4 Jahren 1
6
Evan Bechtol

Hier ist ein Fehler :: Ihre Schleifenlogik ist falsch!

 public void replace(Object data, int index) {
    Node curr = head;
    for (int i = 0; i < 0; i++){
        curr = curr.getNext();
    }

    curr.setData(data);
}

Zum Spass:

  • Implementieren Sie eine Methode, die 2 wie Knoten zusammenführen kann
  • Methode zum Einfügen eines Knotens am Kopf der Liste
  • Finde den kleinsten / größten Wert
  • Suche nach einem bestimmten Wert
4
Philipp

Um Ihre Klasse in einem echten Projekt besser nutzbar zu machen, können Sie sie in eine generische Klasse umwandeln . Auf diese Weise können Benutzer Ihrer Klasse einen erstellen StratchLinkedList<String>, StratchLinkedList<Integer>oder StratchLinkedList<SomeClassOfMyOwn>wo alle Methoden den angegebenen Typ annehmen und zurückgeben Object. Dies verhindert unnötige Typumwandlungen und verbessert die Typensicherheit bei der Interaktion mit Ihrer Klasse.

Eine weitere Verbesserung, die Sie in Betracht ziehen könnten, ist die Implementierung einiger Schnittstellen wie Iterableoder sogar Collection. Dadurch könnten viele Algorithmen der Standardbibliothek nahtlos mit Ihrer Klasse interagieren.

2
whydoubt

Ich weiß, dass der Thread über ein Jahr alt ist, aber für die Nachwelt ...

Die Antwort von Brythan ist ausgezeichnet, aber mit dem StringBuilder-Abschnitt besteht noch Verbesserungsbedarf.

builder.append("[" + current.getData() + "]");

Wie in der Schleife gefunden, wird es wahrscheinlich vom Java-Compiler in Folgendes umgewandelt:

builder.append(new StringBuilder().append("[").append(current.getData()).append("]").toString());

Wir können jedoch direkt an builderdie Erstellung eines neuen StringBuilder-Objekts und den Aufruf von toString () pro Iteration anhängen und diese vermeiden:

builder.append("[").append(current.getData()).append("]");
Ich habe Ihre Antwort bestätigt, seit ich denke, dass das Anfügen mehrerer Elemente sauberer ist, aber haben Sie ein klares Beispiel dafür, wie der Compiler den Code in das umwandelt, was er zu tun glaubt, oder ist es nur eine Vermutung, die auf Ihrem Wissen basiert? (Ich hätte die gleiche Vermutung, aber ich würde gerne einen Beweis sehen) Marc-Andre vor 3 Jahren 0
Der Bytecode, der durch den ursprünglichen Code "compile" generiert wird, kann tatsächlich die verschachtelten `StringBuilder'-Aufrufe enthalten, so dass diese Antwort richtig ist. Was heutzutage mit dem Bytecode geschieht, wenn mehrere Optimierungsstufen usw. durchlaufen werden, ist viel weniger vorhersehbar. Unabhängig davon enthält diese Antwort einen guten Rat. rolfl vor 3 Jahren 0
1
Haakon Løtveit

Ich gehe davon aus, dass Sie dies tun, um mehr über Java zu lernen, und nicht als eigentliches Projekt als Angestellter.

Für den Anfang haben andere Leute Ihnen über die Größe der Fehler berichtet. Ich werde hier ein Ketzer sein und sagen, dass, da Sie dies zum Lernen tun, es bei jedem Aufruf unter Verwendung von Rekursion berechnet wird.

Dies wird eine anständige erste Rekursionsmethode sein, und da es für das Lernen ist, wer sich um Geschwindigkeit kümmert, solange es nicht schrecklich ist.

Zweitens haben Sie zwei Methoden namens add. Hinzufügen fügt nur am Ende der Liste hinzu, oder? Was zu tun ist, ist zu berechnen, welcher Index das wäre (natürlich durch Aufrufen von size ()) und dann add (Object, int) sagen, wo er hinzugefügt werden soll.

add(Object item) {
  int index = size() - 1; // assumes zero-indexing
  add(item, index);
}

Dies ist allen klar, was passiert. Wir alle wissen, dass das letzte Element eines Arrays das ist array.length - 1, daher ist dies für niemanden eine Überraschung.

Nachdem Sie das getan haben, hatte Philipp den hervorragenden Vorschlag, es generisch zu machen und Schnittstellen zu implementieren. Ich würde dazu noch etwas hinzufügen und das Erlernen von Anmerkungen, wie die Annonation @NonNull, vorschlagen . Diese Informationen können sehr schön sein, auch wenn Sie sie nicht selbst verwenden.

Bei StringBuilder ist es gut zu sehen, wie es funktioniert, nicht nur, weil es schneller ist, sondern vor allem, denn wenn Sie nur lernen, ist es wahrscheinlich das erste Treffen mit dem Builder-Muster, das Sie lernen werden Ich liebe die Sekunde, in der Sie eine Klasse mit 14 String-Argumenten im Konstruktor sehen. (Dieser Kodex wurde in R'Lyeh unter die See gebracht.) An diesem Punkt wissen Sie, was zu tun ist, und haben ein besseres Verständnis.

Eine Sache, die mich wirklich traurig macht, ist, dass Sie keinen Javadocs hinzugefügt haben. Javadocs sind eines der besten Dinge in Bezug auf Java und veranlassten konkurrierende Plattformen, ihr Spiel zu verbessern, wenn es um Dokumentation ging. Sie sollten wirklich lernen, wie man sie schreibt. Oracle hat eine Anleitung

Alles andere wurde schon n-mal gesagt, also werde ich es nicht noch einmal sagen.

1
scherj5

Nur ein sehr kleiner Fehler, denke ich, könnte es in Ihrer removeFunktion sein. Wird nicht Aufruf .getNext().getNextauf das letzte Element geben Sie ein, NullPointerExceptionwo Sie anrufen, .getNext()auf Null?