Почему я могу получить ошибку java stackoverflow с помощью связанных списков?

Question

Я пытаюсь добавить несколько многочленов, которые вводятся в разреженном формате ввода/вывода. В основном для представления 1 + 5x + 2x^2 вход будет

0,1:1,5:2,2; 
; 

Если я хотел бы добавить 3x^2 вход будет

2,3; 
; 

Сила всегда упорядоченный от наименьшего к наибольшему и 0 константы не печатаются. Я не использовал рекурсивные функции, и мой алгоритм работает для «малых» (20 миллисекунд) и «средних» (50 миллисекунд) входных размеров. Однако, когда я тестирую «большие» размеры ввода, я просто получаю ошибку переполнения стека! Ниже мой код,

Заранее спасибо!

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.StringTokenizer; 

class list { 

    //contains the reference to the first node in the list 
    private node firstNode; 
    //construct an empty list called linkedList 
    public list(String linkedList) { 

     firstNode = null; 

    } 

    public list() { 
     this("linkedlist"); 
    } 

    public String toString(){ 
     return firstNode +""; 
    } 

    //where i is the power 
    public node find (int power, int coeff) { 

     node nodePos = null; 
     node n = firstNode; 

     while (n!= null) { 
      if (n.pow == power) { 
       nodePos = n; 
       break; 
      } else if (n.next == null) { 
       nodePos = n; 
       break; 
      } else if ((n.pow < power) & (n.next.pow > power)){ 
       nodePos = n; 
       break; 
      } else if (n.pow > power) { 
       nodePos = firstNode; 
       break; 
      } else { 
       n = n.next; 
      } 
     } 
     return nodePos; 
    } 


    public void insert (int p, int c) { 

     node position = null; 

     //if list is empty, add node as the first element 
     if (isEmpty()) { 
      firstNode = new node(p, c, null); 
     } else { 
      position = find(p, c); 
      //do addition 
      if (position.pow == p) { 
       position.coeff = position.coeff + c; 
      } else if (position.pow > p) { 
       //insert before 
       firstNode = new node (p, c, position); 
      } else { 
       //insert after 
       position.next = new node(p, c, position.next); 
      } 
     } 
    } 


    private boolean isEmpty() { 
     return firstNode == null; 
    } 

} 

class node { 

    int pow; 
    int coeff; 
    node next; 

    public node() { 
     pow = 0; 
     coeff = 0; 
     next = null; 
    } 

    public node (int pow, int coeff) { 
     this.pow = pow; 
     this.coeff = coeff; 
     next = null; 
    } 

    public node (int pow, int coeff, node next) { 
     this.pow = pow; 
     this.coeff = coeff; 
     this.next = next; 
    } 

    public String toString(){ 
     if (next == null){ 
      if (coeff == 0) { 
       return ""; 
      } 
      return pow+","+coeff+";"; 
     } else if (coeff == 0){ 
      return next + ""; 
     } 
     else { 
      return pow+","+coeff+";"+next; 
     } 
    } 
} 

public class Adderv2 { 

    public static void main(String[]args) throws IOException{ 

     //LinkedList<Integer> list = new LinkedList<Integer>(); 

     InputStreamReader reader = new InputStreamReader(System.in); 
     BufferedReader br = new BufferedReader(reader); 
     String line = br.readLine(); 

     list linkedList = new list(); 

     while (!line.equals(";")) { 

      //Split string by ';' 
      StringTokenizer st = new StringTokenizer(line, ";"); 
      while (st.hasMoreElements()) { 

       //split string up by ','s 
       StringTokenizer st2 = new StringTokenizer(st.nextToken(), ","); 
       while(st2.hasMoreElements()) { 

        //convert tokens to integer 
        int i1 = Integer.parseInt(st2.nextToken()); 
        int i2 = Integer.parseInt(st2.nextToken()); 

        //insert the integers into the list 
        linkedList.insert (i1, i2); 
       } 
      } 

      //read next line 
      line = br.readLine(); 
     } 
     System.out.println(linkedList); 
     System.out.println(";"); 
    } 

} 

Answer 1

Ваш toString реализация в node является рекурсивным, что может привести к переполнению стека для длинных списков (размер стека обычно гораздо более ограниченным, чем размер кучи).

Одним из способов решения этой проблемы было бы перейти к toStringlist, затем ее реализации в итерационном образом:

public String toString(){ 
    StringBuilder sb = new StringBuilder(); 
    node current = firstNode; 
    while (current != null) { 
    sb.append(pow + "," + coeff + ";"); 
    current = current.next(); 
    } 
    return sb.toString(); 
} 

P.S. Почему бы не использовать TreeMap<Integer, Integer> для этого (или просто массив, если он не слишком разрежен)? Это должно сделать вставки гораздо быстрее (O (журнал N) вместо (O (п)), сохраняя при этом порядок.

public class Poly { 
    TreeMap<Integer,Integer> map = new TreeMap<Integer, Integer>(); 

    public void insert(int pow, int coeff) { 
    Integer old = map.get(pow); 
    int value = old == null ? 0 : old.intValue(); 
    map.put(pow, old + coeff); 
    } 

    public void toString() { 
    StringBuilder sb = new StringBuilder(); 
    for (Map.Entry<Integer,Integer> e: map.entrySet()) { 
     sb.append(e.key() + "," + e.value() + ";"); 
    } 
    return sb.toString(); 
    }