リンクリストからノードを削除する

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(); 
    } 
} 

LinkedListでスタックを実装しようとしています。ポップ関数では、最後のノードまで移動してnullにしています。私はリストを印刷します。それは変わらないままです。 tempにルートを割り当て、それをトラバースしても何の問題もありませんか？

Answer 1

実装を単純化することで、これらをすべて回避することができます。それは単なるスタックなので、LIFOです。あなたがする必要があるのは、最後の要素をpush-rootにするだけです。 pop -ingの場合は、dataをrootに返し、rootを次の行に設定します。

pushとpop操作では、通常の複雑さがO(1)からO(N)に増加します。

ような何か：

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

これを実現するための好ましい方法でなければならない@ChiefTwoPencils、によって他の回答で述べたように。しかし、pop操作のロジックを修正するには、最後の2番目の項目を追跡して、次のノードのデータ値を返して次のリンクをnullに設定することができます。ここで

はpopメソッド

 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; 
     } 
    } 

のコードからロジックを変更され、それがお役に立てば幸いです。

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; 
    } 

}