Löschen eines Knotens aus einer verknüpften Liste

Question

class StackNode{ 
    int data; 
    StackNode next; 

    public StackNode(int data, StackNode next){ 
     this.data = data; 
     this.next = next; 
    } 
} 

public class StackWithLinkedList { 

    StackNode root = null; 

    public void push(int data){ 
     if(root == null) 
      root = new StackNode(data, null); 
     else { 
      StackNode temp = root; 
      while(temp.next != null) 
       temp = temp.next; 

      temp.next = new StackNode(data, null); 
     } 
    } 

    public int pop() throws Exception{ 
     if(root == null) 
      throw new Exception("No Elements in Stack"); 
     else { 
      StackNode temp = root; 
      while(temp.next != null) 
       temp = temp.next; 
      int data = temp.data; 
      temp = null; 
      return data; 
     } 
    } 


    public void print(){ 
     StackNode temp = root; 
     while(temp!= null){ 
      System.out.print(temp.data +" "); 
      temp = temp.next; 
     } 
     System.out.print("\n"); 
    } 

    public static void main(String[] args) { 
     StackWithLinkedList stack = new StackWithLinkedList(); 
     for(int i = 1; i<=15; i++){ 
      Random randomGen = new Random(); 
      stack.push(randomGen.nextInt(i)); 
     } 
     stack.print(); 
     System.out.print("\n"); 
     try { 
      System.out.println("Deleted: "+stack.pop()); 
      System.out.println("Deleted: "+stack.pop()); 
     } catch (Exception e) { 
      e.printStackTrace(); 
     } 
     stack.print(); 
    } 
} 

Ich versuche, Stack mit Linkedlist zu implementieren. In der pop-Funktion traversiere ich bis zum letzten Knoten und mache ihn null. Wenn ich die Liste drucke. es bleibt unverändert. Verursacht das Zuweisen von root zu temp und das Traversieren damit irgendein Problem?

Answer 1

Sie können dies alles vermeiden, indem Sie Ihre Implementierung vereinfachen. Es ist nur ein Stack, also ist es LIFO. Alles, was Sie tun müssen, ist das letzte Element push -ed die root. Geben Sie pop -ing die data in root zurück und setzen Sie root auf die nächste Zeile.

Die Art, wie Sie es tun, erhöht die typische Komplexität von O(1) zu O(N) für die push und pop Operationen.

Etwas wie:

public void push(int data) { 
    root = new StackNode(data, root); 
} 

public int pop() throws Exception { 
    if (root == null) 
     throw new Exception("No Elements in Stack"); 
    else { 
     int data = root.data; 
     root = root.next; 
     return data; 
    } 
} 

Answer 2

Wie @ChiefTwoPencils in anderer Antwort erwähnt, das muss der bevorzugte Weg, dies umzusetzen. Um jedoch Ihre Logik der Pop-Operation zu korrigieren, sollten Sie den vorletzten Punkt verfolgen und sobald Sie das erhalten haben, können Sie den Datenwert des nächsten Knotens zurückgeben und den nächsten Link auf Null setzen.

Hier wird

Logik aus dem Code der Pop-Methode geändert

 public int pop() throws Exception{ 
     if(root == null) 
      throw new Exception("No Elements in Stack"); 
     else { 
      int data = -1; 
      if(root.next==null) { 
       data = root.data; 
       root = null; 
       return data; 
      } 

      StackNode temp = root; 
      while(temp.next.next != null) 
       temp = temp.next; 
      data = temp.next.data; 
      temp.next = null; 
      return data; 
     } 
    } 

Hoffe, es hilft.

Answer 3

public int pop() throws Exception{ 
    if(root == null) 
     throw new Exception("No Elements in Stack"); 
    else { 
     StackNode temp = root; 
     StackNode prev; 
     while(temp.next != null){ 
      prev = temp; 
      temp = temp.next; 
     } 
     int data = temp.data; 
     prev.next = null; 
     return data; 
    } 

}