Löschen Sie mehrere Knoten aus der verknüpften Liste Java

Question

Ich versuche, mehrere Knoten zu löschen, die ein Kriterium aus einer verknüpften Liste erfüllt. Das Programm ist ein bisschen komplex, also werde ich den Kern davon bestimmen. Die Knoten in meiner verknüpften Liste hat die folgenden Eigenschaften (einen Namen mit einer Nummer zugeordnet):

Name Number 
Dog  1 
Cat  1 
Rat  2 
Donkey 3 
Fish 1 

Ich möchte die Knoten mit der Nummer 1. Meine Löschfunktion löschen können:

public void Delete(Int N) { 

     Node current = Head; 
     Node previous = Head; 


     while (current.getNum() != N) { 

      if (current.getNextNode() == null) { 

       System.out.print("Not found"); 

      } else { 

       previous = current; 

       current = current.getNextNode(); 

      } 

     } 

     if (current == Head) { 

      Head = Head.getNextNode(); 

     } else { 

      Node A = current.getNextNode(); 
      previous.setNextNode(A); 

     } 

    } 

Dies funktioniert, aber es entfernt nur das erste Vorkommen. Ich weiß, dass es an der fehlenden oder geeigneten Schleifenstruktur liegen könnte, aber ich arbeite seit Stunden daran und bin auf dem Weg verwirrt. Ich habe versucht, eine Trace-Tabelle manuell zu machen, aber das funktioniert auch nicht.

Wie kann die Funktion bearbeitet werden, so dass sie die gesamten verknüpften Listen durchläuft und die Knoten entfernt, die den Kriterien entsprechen?

Answer 1

Ihre Schleife while (current.getNum() != N) nach dem ersten Auftreten eines Knotens enden wird, dass die Zahl N. hat Wenn Sie durch die gesamte Liste hinwollen dann sollte die Schleife aussehen wie

while (current != null) { 
    //do something with the list 
    current = current.getNextNode(); 
} 

Speziell für diesen Fall möchten Sie einen Knoten entfernen.

Node prev = null; 
while (current != null) { 
    Node next = current.getNextNode() 
    if(current.getNum() == N){ 
     //condition to remove current node has been found. 
     if(prev == null){ 
      Head = next; 
     } else { 
      prev.setNextNode(next); 
     } 
    } else { 
     //only advance prev if we haven't deleted something 
     prev = current; 
    } 
    current = current.getNextNode(); 
} 

Answer 2

Dies sollte die passenden Node Instanzen aus der verknüpften Liste entfernen:

public void delete(int n) { 

    int count = 0; 

    Node prev = null, next; 
    for (Node current = head; current != null; current = next) { 
     next = current.getNextNode(); 
     if (current.getNum() == n) { 
      count++; 
      if (prev != null) { 
       prev.setNextNode(next); 
      } else { 
       head = next; 
      } 
     } else { 
      prev = current; 
     } 
    } 

    System.out.print(count > 0 ? ("Number deleted: " + count) : "Not found"); 
} 

Answer 3

Wenn Sie einen Knoten in der LinkedList löschen möchten, können Sie eine der folgenden Möglichkeiten

1. eine neue verknüpfte Liste nur mit den Knoten, in denen Nummer nicht zu N ist gleich
2. oder ändern Sie die vorhandene.

Ich habe die erste Möglichkeit, die Schaffung einer neuen verknüpften Liste mit Element, in dem Nummer entspricht nicht zu N.

class Node { 

    public String name; 
    public int number; 
    public Node next; 
} 

public class LinkedListTest { 

    public static void main(String[] args) { 

     LinkedListTest obj = new LinkedListTest(); 
     Node head = obj.createLinkList(); 
     Node startPointer = head; 
     while (startPointer != null) { 

      System.out.println(startPointer.name + " " + startPointer.number); 
      startPointer = startPointer.next; 
     } 
     System.out.println("***********"); 
     Node newNodeHead = obj.deleteNode(1, head); 
     startPointer = newNodeHead; 
     while (startPointer != null) { 

      System.out.println(startPointer.name + " " + startPointer.number); 
      startPointer = startPointer.next; 
     } 

    } 

    public Node deleteNode(int n, Node head) { 

     Node current = head; 
     Node newNodestartPointer = null; 
     Node newNodeCurrent = null; 
     while (current != null) { 

      if (!(current.number == n)) { 

       if (newNodestartPointer == null) { 
        newNodestartPointer = new Node(); 
        newNodestartPointer.name = current.name; 
        newNodestartPointer.number = current.number; 
        newNodestartPointer.next = null; 
        newNodeCurrent = newNodestartPointer; 
       } else { 

        Node newNode = new Node(); 
        newNode.name = current.name; 
        newNode.number = current.number; 
        newNodeCurrent.next = newNode; 
        newNodeCurrent = newNode; 
       } 
      } 
      current = current.next; 
     } 

     return newNodestartPointer; 
    } 

    public Node createLinkList() { 

     Node head = null; 

     Node newNode = new Node(); 
     newNode.name = "Dog"; 
     newNode.number = 1; 
     newNode.next = null; 

     head = newNode; 

     newNode = new Node(); 
     newNode.name = "Cat"; 
     newNode.number = 1; 
     newNode.next = null; 
     head.next = newNode; 
     Node prevNode = newNode; 

     newNode = new Node(); 
     newNode.name = "Rat"; 
     newNode.number = 2; 
     newNode.next = null; 
     prevNode.next = newNode; 
     prevNode = newNode; 

     newNode = new Node(); 
     newNode.name = "Donkey"; 
     newNode.number = 3; 
     newNode.next = null; 
     prevNode.next = newNode; 

     return head; 
    } 
} 

verwendet