Java-Code für verknüpfte Liste

69294
Quelle (EN)
Adam Johns

Ich habe die Implementierung einer verketteten Liste von Grund auf geübt. Kann jemand helfen, meinen Code zu überprüfen?

class Node {
    Node next;
    int num;

    public Node(int val) {
        num = val;
        next = null;
    }
}

public class LinkedList {

    Node head;

    public LinkedList(int val) {
        head = new Node(val);
    }

    public void append(int val) {
        Node tmpNode = head;
        while (tmpNode.next != null) {
            tmpNode = tmpNode.next;
        }
        tmpNode.next = new Node(val);
    }

    public void insert(int val) {
        Node currentNode = head;
        Node nextNode = head.next;

        if (currentNode.num > val) {
            Node tmpNode = head;
            head = new Node(val);
            head.next = tmpNode;
            return;
        }

        if (nextNode != null && nextNode.num > val) {
            currentNode.next = new Node(val);
            currentNode.next.next = nextNode;
            return;
        }

        while (nextNode != null && nextNode.num < val) {
            currentNode = nextNode;
            nextNode = nextNode.next;
        }

        currentNode.next = new Node(val);
        currentNode.next.next = nextNode;
    }

    public void delete(int val) {
        Node prevNode = null;
        Node currNode = head;

        if (head.num == val) {
            head = head.next;
            return;
        }

        while (currNode != null && currNode.num != val) {
            prevNode = currNode;
            currNode = currNode.next;
        }

        if (currNode == null) {
            System.out.println("A node with that value does not exist.");
        }
        else {
            prevNode.next = currNode.next;
        }

    }

    public void print() {
        Node tmpNode = head;
        while (tmpNode != null) {
            System.out.print(tmpNode.num + " -> ");
            tmpNode = tmpNode.next;
        }
        System.out.print("null");
    }

    public static void main(String[] args) {
        LinkedList myList = new LinkedList(5);
        myList.append(7);
        myList.append(16);
        myList.insert(9);
        myList.insert(4);
        myList.insert(6);
        myList.insert(17);
        myList.delete(16);
        myList.delete(5);
        myList.delete(4);
        myList.delete(17);
        myList.delete(34);
        myList.print();
    }
}
Antworten
11
Ich habe gerade erkannt, dass meine Append-Funktion am Anfang auch nicht überprüft, ob head null ist. Meine aktuelle Funktion würde eine NPE auslösen, wenn sie null wäre. Adam Johns vor 6 Jahren 1

3 Antworten auf die Frage

6
toto2

  1. Ihre Implementierung lässt keine leere Liste zu.

    1. Es ist ein bisschen seltsam, nur den Konstruktor zu haben, der einen Knotenwert annimmt.

  2. Sie sollten die ListSchnittstelle wahrscheinlich implementieren .

  3. Sie sollten sich mit Generika befassen, anstatt Ihre Liste fest zu codieren, um nur ints zu erhalten.

  4. Es sieht so aus insert(), als würden Sie versuchen, eine geordnete verknüpfte Liste zu erstellen . Tut es append()aber nicht. (Wenn Sie wirklich eine geordnete verknüpfte Liste definieren möchten, können Sie immer noch Generics verwenden, aber Sie müssen Typen verwenden, die untergeordnet sind Comparable).

  5. In insert()und delete()du hast einige ifBedingungen, gefolgt von einer whileSchleife. Ich vermute, dass sie in einer einzigen whileSchleife zusammengefügt werden können. Ich war faul und habe es noch nicht versucht, es könnte also nicht wahr sein.

4
Anirban Nag 'tintinmj'

Was @ toto2 gesagt hat plus

  • Ich würde die printMethode ändern . Überschreibung toStringMethode.

  • Fügen Sie keine System.out.printlnAPI-Klasse ein. Sie werden Ihre LinkedListKlasse zukünftig in GUI oder Web-App wiederverwenden . Dann beeinträchtigen unerwünschte SOPs Ihren Code.

4
guitar_freak

Genau wie gesagt:

  • Mischen insert()mit append()? Macht das Sinn? Wähle ein
  • Sie akzeptieren keine leere Liste.

Hier ist ein turbo-schnelles Beispiel mit dem append()Akzeptieren einer leeren Liste:

class Node {
    Node next;
    int num;
    public Node(int val) {
        num = val;
        next = null;
    }
}

class LinkedList {

    private Node head = null;

    public void append(int val) {
        Node lastNode = getLastNode();
        if (lastNode == null) {
            head = new Node(val);
        } else {
            lastNode.next = new Node(val);
        }
    }

    public void delete(int val) {
        if(head == null){
            return;
        }

        Node prevNode = null;
        Node currNode = head;
        while (currNode != null && currNode.num != val) {
            prevNode = currNode;
            currNode = currNode.next;
        }
        if(prevNode == null){
            head = head.next;
            return;
        }
        if (currNode == null) {
            System.out.println("A node with that value does not exist.");
            return;
        }
        prevNode.next = currNode.next;
    }

    public void print() {
        System.out.println("");
        if(head == null){
            System.out.print("EMPTY");
            return;
        }
        Node tmpNode = head;
        while (tmpNode != null) {
            System.out.print(tmpNode.num + " -> ");
            tmpNode = tmpNode.next;
        }
    }

    private Node getLastNode() {
        if (head == null) {
            return null;
        }
        Node tmpNode = head;
        while (tmpNode.next != null) {
            tmpNode = tmpNode.next;
        }
        return tmpNode;
    }

    public static void main(String[] args) {
        LinkedList myList = new LinkedList();
        myList.print();
        myList.append(35);
        myList.append(33);
        myList.print();
        myList.delete(33);
        myList.delete(35);
        myList.delete(35);
        myList.print();
    }
}

Dies ist nur ein Beispiel, also möchten Sie das absolute Minimum implementieren, aber Generics, Comparable System.out.printsind natürlich immer noch aktuelle Themen.

Verwandte Probleme