Methoden Entferne alle identische Knoten (Typ String) aus verkettete Liste

[Rah2k]

Hallo,
ich möchte gerne alle Knoten, die identisch mit einem übergebenen String sind, aus der Liste entfernen - inklusive Head-Knoten.
Ausschnitt aus meiner List-Klasse: Es geht um die deleteThis-Methode.

public class SinglyLinkedList {
   
    private Node start;
   
    public void add(String data) {
        Node element = new Node(data);
        if (start==null) {
            start = element;
        } else {
            Node temp = start;
            while(temp.next!=null) { //Bis zum letzten Element durchlaufen
                temp = temp.next;
            }
            temp.next =  element; //Das letzte Element = null, also hier einfügen
        }
    }

    public boolean isElementOf(String data) {
        Node temp = start;
        while (temp!=null) {
            if (temp.getStr().equals(data)) {
                return true;
            }
            temp = temp.getNext();
        }
        return false;
    }

    public int getListPosition(String data) {
        int count = 0;
        Node temp = start;
        while (temp!=null) {
            if (temp.getStr().equals(data)) {
                return count;
            }
            temp = temp.getNext();
            count++;
        }
        return count;
    }

    public void deleteThis(String data) {
        Node temp = start;
        if (isElementOf(data)) {
            Node previous = null;
            while (temp!=null) {
                if (getListPosition(data)==0) { //Wenn Head gelöscht werden soll
                    start = temp.next;
                    continue;
                }
               
                if (temp.getStr().equals(data)) {
                    previous.setNext(temp.getNext());
                }
                previous = temp;
                temp = temp.getNext();
            }
        } else {
            return;
        }
        return;
    }
}

main:

    public static void main(String[] args) {
       
        //test
        SinglyLinkedList liste2 = new SinglyLinkedList();
        liste2.add("TEST2");
        liste2.add("TEST2");
        liste2.add("TEST");
       
        liste2.deleteThis("TEST2");
        liste2.printListStr();
    }

Würde mich freuen wenn mit jemand weiterhelfen kann.

 

[httpdigest]

Leute, benutzt mehr Rekursion! 🙂

public void deleteThis(String data) {
  start = delete(start, data);
}
private Node delete(Node node, String data) {
  if (node == null)
    return null;
  Node n = delete(node.getNext(), data);
  if (node.getStr().equals(data))
    node = n;
  else
    node.setNext(n);
  return node;
}

 

[Xyz1]

Singly

ich denke, es müsste SingleLinkedList heißen.... 🙄

 

[Rah2k]

Leute, benutzt mehr Rekursion! 🙂

Danke dir! 🙂

ich denke, es müsste SingleLinkedList heißen.... 🙄

Also mir ist der Begriff SinglyLinkedList öfters in Tutorials begegnet. 🙂

 

[httpdigest]

Ich denke, grammatikalisch ist "Singly" auch richtig. Das singly ist ja das Adverb von single zu linked. "Wie ist es linked?" Singly. Das unterstützen auch diverse Online-Referenzen:
- https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list
- https://en.wikibooks.org/wiki/Data_Structures/Singly_Linked_Lists

EDIT:
Ist in etwa vergleichbar mit "QuicklyWrittenArticle". Da würde man ja auch nicht "QuickWrittenArticle" (bzw. "QuickAndWrittenArticle") sagen, da der Artikel ja nicht schnell und geschrieben ist, sondern schnell geschrieben.

 

[Xyz1]

Also mir ist der Begriff SinglyLinkedList öfters in Tutorials begegnet

Mir bei Tutorials auch das single

@httpdigest Danke 🙂

 

[Rah2k]

Leute, benutzt mehr Rekursion! 🙂

public void deleteThis(String data) {
  start = delete(start, data);
}
private Node delete(Node node, String data) {
  if (node == null)
    return null;
  Node n = delete(node.getNext(), data);
  if (node.getStr().equals(data))
    node = n;
  else
    node.setNext(n);
  return node;
}

Deine Lösung funktioniert wunderbar! So ganz verstehe ich allerdings den Ablauf nicht, habe nicht viel mit Rekursion bisher gemacht. Also:
- Aufruf delete()
- node ist != null
- Erneuter Aufruf delete(), mit nächsten Knoten
- Dann am Ende ist Null-Knoten erreicht
- Müsste dann nicht hier die Methode verlassen werden? (return null) Stattdessen wird die If-Anweisung ausgeführt. Das verstehe ich nicht ganz.

Danke vorab für kurze Erläuterung.

 

[httpdigest]

Ein return beendet immer nur diese eine Methodenausführung und nicht alle. Wenn eine Methodenausführung mit return zurückkehrt, dann geht es ja mit der Ausführung des Aufrufers weiter. Also nach dem delete()-Aufruf.
Der Trick bei dieser rekursiven Methode ist, dass die Aufgabe einer einzelnen delete()-Ausführung nur ist, zu ermitteln, ob dieser Knoten (node Parameter) oder ein nächster Knoten zurückgegeben und damit als Folgeknoten für eine vorherigen Ausführung verwendet werden soll. Wenn wir induktiv annehmen, dass das, was ein delete()-Aufruf zu jedem Zeitpunkt berechnet und zurückgibt, genau der nächste Knoten wäre, der eben nicht equals zum übergebenen data ist und dass alle Folgeknoten daran schon korrekt gefiltert sind, dann ist die Aufgabe der aktuellen Ausführung nur noch, zu gucken, ob denn der Knoten für diese Ausführung (der node Parameter) gefiltert werden soll, oder nicht.
Ich hoffe, das war etwas verständlich.

Ansonsten ist eine saubere iterative (mit Schleifen) Lösung auch nicht schwer.

 

[httpdigest]

Habe die rekursive Lösung mal zu einer iterativen Lösung umgewandelt.
Wenn du willst, kannst du hier ja noch ein bisschen "Fill in the gaps" spielen: 🙂

public void deleteThis(String data) {
  Node s = null, n = start;
  for (start = null; n != null; n = ____)
    if (!n.getStr().equals(data))
      s = deleteThis(____, ____);
}
private Node deleteThis(Node s, Node n) {
  if (s == null)
    start = ____;
  else
    s.setNext(____);
  return ____;
}