Objektorientierte Programmierung OOP

public class LinkedList {    private ListNode head;

    public LinkedList() {        this.head = null;    }    public void add(int value) {        ListNode newNode = new ListNode(value, this.head);        this.head = newNode;    }}

Wir können  eine verkettete Liste durch das sukzessive Einfügen von Knoten am Anfang der Liste aufbauen. Die Methode add()

1. erzeugt einen neuen Listenknoten,

2. trägt den Wert des Eintrags ein,

3. lässt das next-Attribut dieses Knotens auf den Kopf der Liste zeigen und

4. setzt den Kopf der Liste auf den neu erzeugten Listenknoten.

LinkedList liste = new LinkedList(); // 1

liste.add(47);                       // 2    

liste.add(11);                       // 3

public int size() {

         ListNode current = this.head;

         int count = 0;

         while (current != null) {

             count++;

             current = current.getNext();

         }

     return count;

}

Die Methode size() zeigt eine typisches Muster, um über eine verkettete Liste zu iterieren. Solange nicht das Ende der Liste erreicht ist (current != null), wird eine Aktion auf den betrachteten Knoten (current) angewendet, und anschließend der nächste Knoten (current.getNext()) aufgesucht.

Wird die Methode size() auf unsere oben erstellte zweielementige Liste angewendet, so verweist die lokale Variablecurrent zunächst auf den Listenkopf (der das Element 11 enthält) und hangelt sich im ersten Durchlauf der while-Schleife zum zweiten Listenknoten (der das Element 47 enthält) vor. Dessen null-Referenz übernimmt sie im zweiten Durchlauf derwhile-Schleife, worauf diese beendet wird.

 public int size() {        int count = 0;        for (ListNode current = this.head; current != null;             current = current.getNext()) {            count++;        }        return count;    }

public boolean contains(int value) {        ListNode current = this.head;        while (current != null) {            if (current.getEntry() == value) {                return true;            }            current = current.getNext();        }        return false;    }

Die binäre Suche setzt zunächst eine Ordnung unter den zu durchsuchenden Elementen voraus. Selbst auf einer sortierten Liste lässt sie sich jedoch nicht effizient implementieren, da Listen auf sequenziellem Zugriff beruhen. Die binäre Suche auf linearen Datenstrukturen erfordert wahlfreien Zugriff.

 public int sum() {        ListNode current = this.head;        int sum = 0;        while (current != null) {            sum += current.getEntry();            current = current.getNext();        }        return sum;    }

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

    private int size(ListNode node) {    // 1        if (node == null) {              // 2            return 0;                    // 3        }                                // 4        return size(node.getNext()) + 1; // 5    }

Beachten Sie das Zusammenspiel der öffentlichen und der privaten size()-Methoden. Die öffentliche Methode ruft mit dem Listenkopf die private Methode auf, die rekursiv die eigentliche Arbeit erledigt. Dieses Muster ist uns im Zusammenhang mit rekursiven Methoden bereits bekannt und wird uns auch bei rekursiven Datenstrukturen oft begegnen.

public int sum() {

        return sum(this.head);    }    private int sum(ListNode node) {        if (node == null) {            return 0;        }        return node.getEntry() + sum(node.getNext());    }

public void printList() {        printList(this.head);    }    private void printList(ListNode node) {        if (node == null) {            return;        }        node.print();        System.out.print(" ");        printList(node.getNext());    }

public void printReverseList() {        printReverseList(this.head);    }    private void printReverseList(ListNode node) {        if (node == null) {            return;        }         printReverseList(node.getNext());        node.print();        System.out.print(" ");    }

1. Wir müssen den Knoten, der entfernt werden soll, in der verketteten Liste finden, und

2. Wir müssen dafür sorgen, dass die dem gesuchten Knoten benachbarten Knoten wieder so miteinander verkettet sind, dass ihre ursprüngliche Reihenfolge erhalten bleibt.

Erneut haben wir eine öffentliche Methode und einen nicht-öffentlichen rekursiven Algorithmus definiert. Beachten Sie, dass hier zwei Basisfälle vorliegen:

1.Ein Basisfall tritt auf, wenn kein passender Knoten in der Liste gefunden wurde oder wenn die Liste leer ist (Zeile 2 ).

2. Der zweite Basisfall liegt vor, wenn der Eintrag eines Knotens in der Liste mit dem gesuchten Wert, der als zweiter Parameter (value) beim Aufruf der Methode übergeben wurde, übereinstimmt (Zeile 5).

Falls keiner dieser Basisfälle auftritt, wird die Methode remove() rekursiv auf den Rest der Liste angewendet (Zeile 8). Das Ergebnis jedes rekursiven Aufrufs ist entweder die ursprüngliche Restliste oder die um den gesuchten Knoten verringerte Restliste. Wir müssen aber auf jeden Fall das Ergebnis mit dem Knoten, der auf die ursprüngliche Restliste verwies, über dasnext-Attribut verknüpfen (Zeile 8), um bei der Rückabwicklung der rekursiven Aufrufe die sich aus den Basisfällen ergebende Restliste mit dem unveränderten Vorspann der Ursprungsliste Knoten für Knoten wieder zu verknüpfen.

public void remove(int value) {        this.head = remove(this.head, value);    }    private ListNode remove(ListNode node, int value) { // 1        if (node == null) {                             // 2            return  null;                               // 3        }                                               // 4        if (node.getEntry() == value) {                 // 5            return node.getNext();                      // 6        }                                               // 7        node.setNext(remove(node.getNext(), value));    // 8        return node;                                    // 9    } 

Antwort 1 beantwortet die erste Frage richtig. Da keine neue Liste konstruiert wird, liefert die private, rekursive remove()-Methode gemäß Zeile 7 als Ergebnis den Wert des ersten Aufrufs, das head-Attribut, zurück.

Die Antwort auf Frage 2 ist die gleiche wie auf Frage 1.

  public boolean contains(int value) {        return contains(this.head, value);    }    private boolean contains(ListNode node, int value) {        if (node == null) {            return false;        }        if (node.getEntry() == value) {            return true;        }        return contains(node.getNext(), value);    }

Hier gibt es zwei Basisfälle: der erste ist das Ende der Liste bzw. eine leere Liste, der zweite ist der Fall, dass ein passendes Element gefunden wird. Falls der gesuchte Eintrag gefunden wird, endet das Verfahren nach endlich vielen Schritten. Falls der gesuchte Eintrag nicht gefunden wird, erreichen wir nach endlich vielen Schritten über die next-Attribute das Ende der Liste, das durch den null-Verweis gekennzeichnet ist, und das Verfahren konvergiert durch den ersten Basisfall.

public void add(int index, int value) {        if (index < 0 || index > size()) {            throw new IndexOutOfBoundsException("index muss im "                 + "Bereich von 0 bis " + size() + " liegen.");        }        this.head = add(this.head, index, value);    }    private ListNode add(ListNode node,                          int steps, int value) {             // 1        if (steps == 0) {                                    // 2            return new ListNode(value, node);                // 3        }                                                    // 4        node.setNext(add(node.getNext(), steps - 1, value)); // 5        return node;                                         // 6    }

Die private rekursive add()-Methode bewältigt mehrere Aufgaben:

• Zunächst muss sie sich rekursiv an die Einfügestelle heranzählen (steps - 1 in Zeile 5).

• Ist die Einfügestelle erreicht (Zeile 2), muss ein neuer Knoten mit dem erwünschten Eintrag und einer Referenz auf den Nachfolgerknoten erzeugt werden (Zeile 3). Dies ist der Basisfall.

• Das Ergebnis jedes rekursiven Aufrufs ist eine Teilliste, die mit dem Knoten, der auf die ursprüngliche Teilliste verwies, durch setNext() verknüpft wird (Zeile 5), Hier erfolgt auch die Verkettung des Vorgängerknotens mit dem neuen Knoten.

Die öffentlichen add()-Methode hat vor dem Aufruf der privaten add()-Methode noch die wichtige Aufgabe, zu prüfen, ob die im Parameter index übergebene Einfügestelle zulässig ist.

Verkettete Listen können viele weitere Methoden haben. So könnte man z. B. den Eintrag an einer bestimmten Position abrufen, die Liste leeren, eine Teilliste erzeugen wollen und vieles mehr.

    public int get (int index) {        if (index <0 | | index> = size ()) {            throw new IndexOutOfBoundsException (                                "Ungültiger Index");        }        ListNode current = this.head;        for (int i = 0; i <index; i + +) {            Strom = current.getNext ();        }        zurück current.getEntry ();    }

Rekursiv:

    public int get (int index) {        if (index <0 | | index> = size ()) {            throw new IndexOutOfBoundsException (                                "Ungültiger Index");        }        zurück zu bekommen (this.head, index) getEntry ().    }

    Private ListNode bekommen (ListNode Knoten int Stufen) {        if (Schritte == 0) {            zurück Knoten;        }         zurück zu bekommen (node.getNext (), nur wenige Schritte - 1);    }

 public void clear() {        this.head = null;    }

öffentlichen LinkedList Unterliste (int fromIndex, int toIndex) {        if (fromIndex <0 | | toIndex> size ()                           | | FromIndex> toIndex) {            throw new IndexOutOfBoundsException (                                "Ungültiger Index");        }        LinkedList list = new LinkedList ();        list.head = Unterliste (this.head, fromIndex,                                        toIndex - fromIndex);        zurück zur Liste;    }        Private ListNode Unterliste (ListNode Knoten int Schritte, int size) {        if (size == 0) {            return null;        }        if (Schritte == 0) {            ListNode subListNode = new ListNode (node.getEntry ());            subListNode.setNext (Unterliste (node.getNext (), 0,                                                       size - 1));            zurück subListNode;        }        zurück Unterliste (node.getNext (), nur wenige Schritte - 1, size);    }

public LinkedList mergeSort() {        int length = this.size();        if (length <= 1) {            return this;        }        LinkedList leftSorted                = this.subList(0, length / 2).mergeSort();        LinkedList rightSorted                 = this.subList(length / 2, length).mergeSort();        leftSorted.mergeWith(rightSorted);        return leftSorted;    }    private void mergeWith(LinkedList otherList) {        if (otherList.isEmpty()) {            return;        }        if (this.isEmpty()) {            this.head = otherList.head;            return;        }        if (otherList.head.getEntry() <= this.head.getEntry()) {            int first = otherList.removeFirst();            this.mergeWith(otherList);            this.add(first);            return;        }         int first = this.removeFirst();        otherList.mergeWith(this);        otherList.add(first);        this.head = otherList.head;    }    private int removeFirst() {        if (this.head == null) {            throw new IndexOutOfBoundsException("leere Liste");        }        int first = this.head.getEntry();        this.head = this.head.getNext();        return first;    }

Vergleichen Sie die Implementierung mit der Beschreibung des Sortier-Algorithmus „Merge-Sort“ in Kapitel 34.

public class SortedList {    private ListNode head;    public SortedList() {        this.head = null;    }    public void add(int value) {        this.head = add(this.head, value);    }    private ListNode add(ListNode node, int value) {        if (node == null) {            return new ListNode(value, node);        }        if (node.getEntry() > value) {            return new ListNode(value, node);        }         node.setNext(add(node.getNext(), value));        return node;    }}

Die Methode add() fügt jeden neuen Eintrag an der richtigen Stelle in die sortierte Liste ein.

Rekursives Einfügen eines Elements

Rekursives Einfügen eines Elements

printList(), printReverseList(), size(), sum() (alle Varianten), get(), clear(), subList(). Methoden, die als Parameter Indexpositionen erwarten (get(), subList()), werden allerdings für sortierten Listen selten verwendet.

Wir hatten in der Klasse LinkedList im vorherigen Abschnitt die Methode add() überladen. Die zweite add()-Methode dient dazu, einen Knoten mit einem neuen Eintrag an einer gewählten Stelle index in eine Liste einzufügen. Für eine sortierte Liste wäre eine solche Funktionalität fatal.

Es wäre sehr schlechter Programmierstil, die Methode entgegen ihrer Zweckbestimmung mit einer unschädlichen Funktionalität zu überschreiben wie etwa

    public void add(int index, int value) {        this.add(value); // Tun Sie so etwas nie!    }

Eher wäre zu überlegen, die für beide Klassen nützlichen Methodendefinitionen in eine gemeinsame (ggf. abstrakte) Oberklasse zu verlagern und diese einmal mit LinkedList und einmal mit SortedList zu spezialisieren.

public void remove(int value) {        this.head = remove(this.head, value);    }    private ListNode remove(ListNode node, int value) { //  1        if (node == null) {                             //  2            return  null;                               //  3        }                                               //  4        if (node.getEntry() > value) {                  //  5            return node;                                //  6        }                                               //  7        if (node.getEntry() == value) {                 //  8            return node.getNext();                      //  9        }                                               // 10         node.setNext(remove(node.getNext(), value));    // 11        return node;                                    // 12    }

Die Effizienz ergibt sich aus dem zweiten Basisfall (Zeile 5). Sobald bei der rekursiven Ausführung ein Eintrag angetroffen wird, der größer als value ist, steht fest, dass ein Eintrag mit dem Wert value auch in der restlichen Liste nicht mehr gefunden wird.

Es bestehen keine weiteren Unterschiede.

public boolean contains (int value) {        Rückgabe enthält (this.head, value);    }    private boolean contains (ListNode Knoten, int value) {        if (Knoten == null) {            return false;        }        if (node.getEntry ()> value) {                 return false;            }            if (node.getEntry () == value) {            return true;        }        Rückgabe enthält (node.getNext (), value);    }

Für einige Abstraktionen ist eine einfach verkettete Liste nicht das optimale Modell. Wenn z. B. eine Warteschlange mit Hilfe einer verketteten Liste implementiert werden soll, die das Einfügen am Ende und das Entfernen am Anfang der Schlange unterstützt, können diese Methoden effizienter implementiert werden, wenn die Elemente der Liste in beide Richtungen, also vorwärts und rückwärts, verkettet sind.

public class DoublyLinkedListNode {    private String entry;    private DoublyLinkedListNode next;    private DoublyLinkedListNode prev;}

Eine Warteschlangen stellt typischerweise zwei Methoden enqueue() zum Hinzufügen eines Eintrags und dequeue() zum Entfernen eines eines Eintrags bereit. Sie arbeitet nach dem First In First Out-Prinzip, so dass mit dequeue() immer der Eintrag aus der Warteschlange zurückgegeben wird, der der sich am längsten in der Warteschlage befindet.

public class DoublyLinkedListNode {    private String-Eintrag;    Private DoublyLinkedListNode next;    Private DoublyLinkedListNode prev;    öffentlichen DoublyLinkedListNode (String value,                                 DoublyLinkedListNode prevNode) {        this.entry = Wert;        this.prev = prevNode;        this.next = null;    }        öffentlichen DoublyLinkedListNode getNext () {        return next;    }        public void SetNext (DoublyLinkedListNode nextNode) {        this.next = nextNode;    }