remove at index

[Hacer]

HALLO!!

In der Klasse List soll eine Methode removeAtIndex(int index) erstellen. Wird eine negative Zahl oder ein zu großer Index übergeben, soll die Liste unverändert bleiben. Da mein Code nicht richtig läuft, kann ich meine Methode nicht überprüfen. Deshalb wollte ich fragen, ob sich jemand meinen Code angucken und ein Feedback dazu geben kann.
Danke im Voraus

private void removeAtIndex(int index){
        if(index<0){
            return;
        }
        int currPos=0;
        Element pointer= firstElement;
        Element afterPointer =null;
        while(currPos< index && pointer!= null){
            pointer =pointer.getNext();
            currPos++;
            afterPointer= pointer.getNext();
            pointer.setNext(null);
        }
    }

 

[Meniskusschaden]

Da mein Code nicht richtig läuft, kann ich meine Methode nicht überprüfen.

Wie meinst du das? Falls er nicht kompiliert hast du doch Fehlermeldungen und falls er kompiliert kannst du mittels Debugger oder System.out.println Variablen kontrollieren.

Ich würde dir empfehlen, einen Schreibtischtest zu machen, also die Liste auf Papier aufzuzeichnen und dann dein Programm gedanklich schrittweise durchzugehen und die Zeiger entsprechend umzuhängen. Dann siehst du relativ schnell, wie deine Schleife die Liste kaputt macht.

 

[JStein52]

Vielleicht solltest du dir deinen Algorithmus noch mal laut umganssprachlich überlegen: was musst du tun wenn du das Element an der Position "index" löschen willst ? Es handelt sich ja wohl um eine einfach verkettete Liste bei der jeweils der "next"-Zeiger eines Elementes auf das nächste Element der Liste zeigt.
Welchen Zeiger musst du nun wie umsetzen ?

 

[Xyz1]

Da mein Code nicht richtig läuft, kann ich meine Methode nicht überprüfen.

Das hab ich für dich Übernommen:
http://www.java-forum.org/thema/quellcode-lesen.174599/#post-1101784

hat aber etwas gedauert, die Fehler an mehreren Stellen zu finden. Ich hab dir auch eine PN geschickt, in der ich erklären kann, falls noch nicht verstnaden.

 

[JStein52]

Das hab ich für dich Übernommen:

Wenn du jetzt noch erklären könntest was der Link mit dem vorliegenden Thread zu tun hat ?

 

[Xyz1]

Das Löschen ist so ähnlich (~) wie das Einfügen, auch hier muss "umverknüpft" werden.

Ist dir bewusst, dass es sich um eine einfach verkettete Liste (mit Refis) handelt? Hast du diese schon durchschaut?

Wikipedia ein extra Kapitel:
https://de.wikipedia.org/wiki/Liste_(Datenstruktur)#Einfach_verkettete_Liste

Mach den Schreibtischtest! Ein paar Blätter papier verschwenden, wird nicht schlimm sein.

 

[Xyz1]

Wenn du jetzt noch erklären könntest was der Link mit dem vorliegenden Thread zu tun hat ?

Es handelt sich um dieselbe/die gleiche List/Liste!!!!

Und die (ursprüngliche) hatte viele Fehler (compiliert e gar nicht), die ich behoben hab.

Worauf willst du hinau? Man kann removeAtIndex nicht einfach so ohne Kontext....

 

[JStein52]

Man kann removeAtIndex nicht einfach so ohne Kontext....

Doch kann man schon wenn man weiss dass es firstElement, getNext() und setNext() gibt

 

[Xyz1]

Doch kann man schon wenn man weiss dass es firstElement, getNext() und setNext() gibt

Der Compiler weiß es nicht, der Test weiß es auch nicht. Ein Mensch könnte es vielleicht außerhalb des Kontexts verstehen, aber es soll doch übersetzt werden, oder nich?

Wer weiß, ob getNext() nicht einfach die Liste mischt????

Also heute mal nicht beschimpfen. Schnapp dir ein Bier.

 

[JStein52]

Wer weiß, ob getNext() nicht einfach die Liste mischt????

Dann würde sie eher getMischt() heissen. Ausserdem schimpfe ich gar nicht. Und gibs zu, mehr als die genannten drei Informationen hast du auch nicht benutzt

 

[Hacer]

Hallo erstmal danke @JStein52, @DerWissende hatte zwar die anderen Klassen auch aber mein Quellcode warf dennoch ein Exception

 

[JStein52]

Ja, mir war schon klar dass in den Klassen noch Fehler waren. Ich wusste nur auf Anhieb nicht was er mit dem link zur removeAtIndex(index) beitragen wollte. Denn die ist ja schön übersichtlich zu schreiben auch wenn man den restlichen Code noch nicht hat/kennt. Könnte so ja glatt Teil einer Java-Klausur sein. Natürlich braucht man den Rest dann zum Testen und Debuggen.

 

[Hacer]

Ich habe jetzt eine neue Lösung zu removeAtIndex:

    private void removeAtIndex(int index){
        if(index<0){
            return;
        }
        else if(index==0&& firstElement!=null){
            Element pointer= firstElement;
            firstElement = pointer.getNext();
        }else{
            Element pointer =firstElement;
            int currPos=0;
            while(pointer!=null&& currPos!= index){
                pointer=pointer.getNext();
                currPos++;
            }if(pointer!=null){
                pointer.setNext(pointer.getNext().getNext());
            }
        }
    }

 

[Xyz1]

Damit sollte es funktionieren, aber nich getestet.

 

[Hacer]

@DerWissende yeaaah danke

 

[JStein52]

Damit sollte es funktionieren, aber nich getestet.

Funktioniert es wirklich ?? Wenn ich das richtig sehe zeigt bei dir jetzt pointer nach der while-Schleife auf das Element an der Position die gelöscht werden soll oder ? Und dort veränderst du den next. Du musst aber bei dem Element davor den next ändern !

 

[Meniskusschaden]

Ich habe es nicht getestet, aber müsste da nicht eine NullPointer-Exception fliegen, wenn man das letzte Listenelement entfernen möchte?

 

[Hacer]

@JStein52 pointer zeigt nach der while-Schleife auf den index-1ten Stelle.

 

[Meniskusschaden]

@JStein52 pointer zeigt nach der while-Schleife auf den index-1ten Stelle.

Bist du davon nur überzeugt oder hast du es auch getestet? Ich habe es zwar auch nicht getestet, teile aber die Einschätzung von @JStein52.

Meines Erachtens gibt es noch mindestens drei Fehler: den von @JStein52 beschriebenen, den von mir beschriebenen und vermutlich ist es auch nicht korrekt, dass du firstElement nicht auf null setzt, wenn du das letzte verbliebene Element entfernst und somit eine leere Liste erhältst.

 

[Hacer]

@Meniskusschaden also es wird kein NullPointerException geworfen

 

[InfectedBytes]

@Meniskusschaden also es wird kein NullPointerException geworfen

Nur weil keine NPE fliegt, heißt es noch lange nicht das alles Fehlerfrei funktioniert...

edit:
Versuch mal das letzte Element zu löschen, wenn ich mich gerade nicht verguckt habe, wirst du dann definitiv eine NPE bekommen

 

[Hacer]

@InfectedBytes das habe ich auch gar nicht behauptet

 

[Hacer]

Ich habe es jetzt nochmal versucht, auf eine andere Lösung komme ich leider nicht. Weiß auch gar nicht ob das so geht

    private void removeAtIndex(int index){
        if(index<0){
            return;
        }
        else if(index==0&& firstElement!=null){
            Element pointer= firstElement;
            firstElement = pointer.getNext();
            pointer=null;
        }else{
            Element pointer =firstElement;
            int currPos=0;
            while(pointer!=null&& currPos!= index){
                pointer=pointer.getNext();
                currPos++;
            }if(pointer!=null){
                Element indexteStelle= pointer.getNext();
                pointer.setNext(indexteStelle.getNext());
                indexteStelle = null;
            }
        }
    }

 

[InfectedBytes]

pointer=null kannst du machen, bringt aber nichts, da pointer eh nur eine lokale Variable ist.

Es ist immer noch das Problem vorhanden, welches von @JStein52 angesprochen wurde. Du sollst das Element an Position i löschen. Du suchst aber das Element an Stelle i und löscht dann das nachfolgende Element.

 

[Meniskusschaden]

und vermutlich ist es auch nicht korrekt, dass du firstElement nicht auf null setzt, wenn du das letzte verbliebene Element entfernst und somit eine leere Liste erhältst.

Ich glaube, bei diesem vermeintlichen Fehler habe ich mich geirrt, denn durch
firstElement = pointer.getNext();setzt du beim Entfernen des letzten Elementes firstElement ja doch auf null, weil pointer.getNext();in dem Fall ja auch null enthält.
Einfacher wäre aber firstElement = firstElement.getNext();, weil pointer an der Stelle dann überflüssig wäre.

 

[Xyz1]

"Immer" möglichst komplette Beispiele posten. Ich hab es einfach mal "verbessert":

public class List {

    private Element firstElement;

    public void add(int index, Payload p) {
        Element element = new Element(p);
        if (index == 0) {
            element.setNext(firstElement);
            firstElement = element;
        } else if (index > 0) {
            Element prev = getElementAt(index - 1);
            if (prev != null) {
                element.setNext(prev.getNext());
                prev.setNext(element);
            }
        }
    }

    private Element getElementAt(int index) {
        if (index >= 0) {
            Element node = firstElement;
            Element element = firstElement;
            for (int currPos = 0; currPos < index && element != null; currPos++) {
                element = element.getNext();
            }
            return element;
        } else {
            return null;
        }
    }

    private void removeAtIndex(int index) {
        if (index < 0) {
            return;
        }
        if (index == 0) {
            if (firstElement == null) {
                return;
            }
            firstElement = firstElement.getNext();
        } else {
            Element pointer = firstElement;
            while (index-- > 1) {
                pointer = pointer.getNext();
                if (pointer == null) {
                    return;
                }
            }
            if (pointer.getNext() == null) {
                return;
            }
            pointer.setNext(pointer.getNext().getNext());
        }
    }

    private void printAll() {
        int i = 0;
        Element e;
        while ((e = getElementAt(i)) != null) {
            System.out.println(i + ": " + e.p.s);
            i++;
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        List liste = new List();

        liste.add(0, new Payload("a"));
        liste.printAll();

        liste.add(0, new Payload("b"));
        liste.printAll();

        liste.add(2, new Payload("d"));
        liste.printAll();

        liste.add(0, new Payload("c"));
        liste.printAll();

        liste.add(1, new Payload("e"));
        liste.printAll();

        liste.removeAtIndex(5);
        liste.printAll();

        liste.removeAtIndex(4);
        liste.printAll();

        liste.removeAtIndex(0);
        liste.printAll();

        liste.removeAtIndex(1);
        liste.printAll();
    }
}

class Element {

    Element next;
    Payload p;

    public Element(Payload p) {
        this.p = p;
    }

    public Element(Element next) {
        this.next = next;
    }

    public Element getNext() {
        return next;
    }

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

class Payload {

    String s;

    public Payload(String s) {
        this.s = s;
    }
}

Spoiler: Ausgabe:

0: a

0: b
1: a

0: b
1: a
2: d

0: c
1: b
2: a
3: d

0: c
1: e
2: b
3: a
4: d

0: c
1: e
2: b
3: a
4: d

0: c
1: e
2: b
3: a

0: e
1: b
2: a

0: e
1: a

Damit sollte aber alles geklärt sein, sonst fühl ich mich verarscht.

Edit: Doch nicht, wenn man e > 0 aus einer LEEREN Liste entfernen möchte, tritt noch eine NPE auf.

Aber ich glaube daran, du kannst das jetzt auch ohne unsere Hilfe.

 

[Hacer]

Ich wollte mit firstElement= pointer.getNext(); das erste Element durch das nächste ersetzen. Also so war es zu mindest gemeint

 

[Hacer]

@DerWissende hallo ich habe mir gestern mal deine Lösung angeguckt und versucht es nachzuvollziehen, doch ich verstehe nicht, was du nach der while-Schleife machst.

 

[JStein52]

if (pointer.getNext() == null) {
return;
}
pointer.setNext(pointer.getNext().getNext());

Er schläft noch.
Aber du hast es soweit verstanden dass bei ihm nach der Schleife pointer auf das Element vor dem zu löschenden zeigt ? Mit der ersten Abfrage prüft er ob es dahinter überhaupt noch Elemente gibt falls jemand das 6.te von 5 Elementen löschen will.
Und anschliessend setzt er einfach den next-Zeiger auf das übernächste Element.

 

[Xyz1]

@DerWissende hallo ich habe mir gestern mal deine Lösung angeguckt und versucht es nachzuvollziehen, doch ich verstehe nicht, was du nach der while-Schleife machst.

Deshalb musst du den Schreibtischtest machen. Ich kann doch nicht vorkauen und dann in dein Gehirn einpflanzen.

 

[Hacer]

@JStein52 erstmal vielen Dank jetzt verstehe ich was damit gemeint ist. und @DerWissende ich mache die Aufgaben eigentlich fast nur mit Stift und Papier und nur um meine Ergebnisse zu überprüfen, arbeite ich mit Eclipse.... aber vielen Dank!

 

[Hacer]

Ich bin nur halt nicht die beste in Programmierung, von alleine komme ich nie auf solche Lösungen