Удалить узел из связанного списка

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

Я пытаюсь реализовать Stack with Linkedlist. В поп-функции я прохожу до последнего узла и делаю его нулевым. Когда я распечатаю список. он остается неизменным. Применяет ли root к temp и обходит с ним проблему?

Answer 1

Вы можете избежать этого все вместе, упростив вашу реализацию. Это всего лишь стек, так что это LIFO. Все, что вам нужно сделать, это сделать последний элемент push -ed root. Когда pop-вернуть data в root и установить root на следующую строку.

Способ, которым вы это делаете, увеличивает типичную сложность O(1) до O(N) для push и pop операций.

Что-то вроде:

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, которые должны быть предпочтительным способом реализации этого. Однако, чтобы исправить вашу логику поп-операции, вы должны отслеживать второй последний элемент, и как только вы получите, что вы можете вернуть значение данных следующего узла и установить следующую ссылку в значение null.

Здесь изменяется логиком из кода метода поп

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

}