faecher:informatik:oberstufe:adt:verkettete_liste:liste_java:insert

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:adt:verkettete_liste:liste_java:insert [20.10.2021 17:16] – [Einfügen eines neuen Elements] sbelfaecher:informatik:oberstufe:adt:verkettete_liste:liste_java:insert [23.11.2023 16:01] (aktuell) – Marco Kuemmel
Zeile 1: Zeile 1:
-====== Länge der Liste bestimmen/Neues Element Einfügen  ======+====== Einfügen eines neuen Elements ======
  
-===== Listenlänge =====+Das Einfügen eines neuen Knotens ist im folgenden Objektdiagramm dargestellt. Man muss beim Ändern der Objektreferenzen (''nextNode'') darauf achten, dass die Reihenfolge stimmt und man die Referenz auf den ursprünglichen Nachfolger des Knotens, hinter dem der neue Knoten eingefügt wird nicht verliert. ((Hier: Aufpassen, dass man ''node2'' nicht "verliert", sonst ist die Liste an dieser Stelle unterbrochen und alle Nachfolger werden von der Garbage Collection entsorgt...))
  
 +{{ :faecher:informatik:oberstufe:adt:verkettete_liste:liste_java:insert.drawio.png?700 |}}
  
-Die Länge der Liste kann man bestimmen, indem man sich vom ersten Element zum letzten bewegt und dabei mit einem Zähler die verarbeiteten Elemente mit zählt. 
- 
-----  
 {{:aufgabe.png?nolink  |}} {{:aufgabe.png?nolink  |}}
 === (A1) === === (A1) ===
 +Schreibe als Merksatz stichwortartig nieder, was beim Einfügen eines neuen Knotens an Stelle des n-ten vorhandenen Knotens alles passieren muss. Gibt es Fälle, die gesondert behandelt werden müssen?
  
-  * Implementiere die Methode ''length'' +---- 
-  * Teste deine Methode mit unterschiedlich langen Listen. welchen Fall solltest du unbedingt testen? +
- +
-++++ Lösungsvorschlag | +
-<code java> +
-    /** +
-     * Gibt die Anzahl der Elemente der Liste zurück +
-     *  +
-     * @return   Anzahl der Listenelemente +
-     */ +
-    public int length() { +
-        int numElements = 0; +
-         +
-        Node<T> n = first; +
-         +
-        if ( n == null) { +
-            return numElements; +
-        } +
-         +
-        numElements++; +
-         +
-        while ( n.getNext() != null ) { +
-            n = n.getNext(); +
-            numElements++; +
-        } +
-         +
-        return numElements; +
-    } +
-</code> +
-++++ +
- +
-===== Einfügen eines neuen Elements ===== +
- +
-Das Einfügen eines neuen Knotens ist im folgenden Objektdiagramm dargestellt. Man muss beim ändern der Objektreferenzen (''nextNode'') darauf achten, dass die Reihenfolge stimmt und man die Referenz auf den ursprünglichen Nachfolger des Knotens, hinter dem der neue Knoten eingefügt wird nicht verliert. ((Hier: Aufpassen, dass man ''node2'' nicht "verliert", sonst ist die Liste an dieser Stelle unterbrochen und alle Nachfolger werden von der Garbage Collection entsorgt...)) +
- +
-{{ :faecher:informatik:oberstufe:adt:verkettete_liste:liste_java:insert.drawio.png?700 |}} +
 {{:aufgabe.png?nolink  |}} {{:aufgabe.png?nolink  |}}
 === (A2) === === (A2) ===
-Schreibe als Merksatz stichwortartig nieder, was beim Einfügen eines neuen Knotens nach dem n-ten vorhandenen Knoten alles passieren muss. Gibt es Fälle, die gesondert behandelt werden müssen? 
  
-----  +Implementiere die Methode ''insertAt(index: int, val: T)'', sodass man damit ein neues Element nach dem n-ten  Listenelement einfügen kann. 
-{{:aufgabe.png?nolink  |}} +
-=== (A3) ===+
  
-Implementiere die Methode ''insertAt'', so dass man damit ein neues Element nach dem n-ten  Listenelement einfügen kann.  +Teste deine Methode, indem du Elemente in eine Liste einfügst und mit dem Objektinspektor überprüfst, dass das neue Element an der richtigen Stelle eingefügt wurde - und dass die nachfolgenden Knoten noch erreichbar sind. Welche Testfälle sind besonders interessant? 
-Teste deine Methode, indem du Elemente in eine Liste einfügst und mit dem Objektinspektor überprüfst, dass das neue Element an der richtigen Stelle eingefügt wurde - und dass die Nachfolgenden Knoten noch erreichbar sind.+ 
 +//Tipp: Nutze die bereits implementierte Methode ''getNode(index: int): Node''//
  
 ++++ Lösungsvorschlag | ++++ Lösungsvorschlag |
-Kann sicher weiter optimiert werden.+
 <code java> <code java>
     /**     /**
Zeile 71: Zeile 32:
         Node<T> new_node = new Node(val, null);         Node<T> new_node = new Node(val, null);
                  
-        // Wenn der Index groesser als die Laenge ist  
-        // passiert nix 
-        if (this.length() < index) { 
-            return; 
-        } 
-        // Wenn der Index gleich ist, die die Listenlaenge 
-        // muss das neue Element angehängt werden 
-        if (this.length() == index) { 
-            this.append(val); 
-            return; 
-        } 
         // Wenn der Index Null ist, muss das Element als erster neuer         // Wenn der Index Null ist, muss das Element als erster neuer
         // Knoten eingefuegt werden         // Knoten eingefuegt werden
Zeile 87: Zeile 37:
             new_node.setNext(first);             new_node.setNext(first);
             first = new_node;             first = new_node;
-            return; +        } else { 
-        } +            Node<T> n = this.getNode(index-1); 
-        // In allen anderen Faellen muss das n-te Element  +            new_node.setNext(n.getNext()); 
-        // aufgesucht werden und der neue Knoten dort eingefügt werden. +            n.setNext(new_node); 
-        Node<T> n = first; +        }        
-        for (int i=1; i<index; i++) { +
-            n = n.getNext(); +
-        } +
-         +
-        new_node.setNext(n.getNext()); +
-        n.setNext(new_node);+
                  
     }     }
 +    
 </code> </code>
 +++++
 +
 +----
 +
 +<btn>[[..:liste_java:lengthvalue|<<< Zurück zur Länge und Wert auslesen >>> ]]</btn> **oder** <btn>[[..:liste_java:remove|Weiter zum Löschen >>> ]]</btn>
  • faecher/informatik/oberstufe/adt/verkettete_liste/liste_java/insert.1634750160.txt.gz
  • Zuletzt geändert: 20.10.2021 17:16
  • von sbel