從鏈接列表中刪除一個節點

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

我想實現與鏈表的堆棧。在彈出功能我遍歷，直到最後一個節點，並使其爲空。當我打印清單。它保持不變。將根分配給temp並遍歷它會導致任何問題？從鏈接列表中刪除一個節點

來源

2016-10-14 Lokesh Cherukuri

你應該是最後一個前旁邊元素的空設置字段。不是元素 – Damian0o

但我把那個元素本身作爲null。不會那樣釋放內存嗎？ –

你不應該對空閒內存感興趣，因爲GC會處理這個問題。你應該從列表中刪除對該元素的引用 – Damian0o

您可以通過簡化您的實施來避免這一切。這只是一個堆棧，所以它是LIFO。所有你需要做的是使最後一個元素push -ed root。當pop -ing返回data,root並將root設置爲下一行。

你這樣做的方式將O(1)的典型複雜度增加到和pop操作的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; 
    } 
}

來源

2016-10-14 07:50:51 ChiefTwoPencils

正如@ChiefTwoPencils在其他答覆中提到，必須要實現這個的首選方式。但是，要糾正彈出操作的邏輯，您應該跟蹤第二個最後一項，一旦得到該數據，就可以返回下一個節點的數據值，並將下一個鏈接設置爲空。

這裏是您的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; 
     } 
    }

希望它能幫助。

來源

2016-10-14 08:02:40 Sanjeev

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

}

來源

2016-10-14 08:53:17 tapan

從鏈接列表中刪除一個節點

回答

相關問題