Why could I be getting a java stackoverflow error using linked lists?

Question

I am attempting to add multiple polynomials which are entered in sparse input/output format. Basically to represent 1 + 5x + 2x^2 the input would be

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

If I wished to add 3x^2 the input would be

2,3; 
;

The power is always ordered from smallest to largest and 0 constants are not printed. I have not used recursive functions and my algorithm is working for "small" (20 milliseconds) and "medium" (50 milliseconds) input sizes. However when I test for "large" input sizes, I just get a stack overflow error! Below is my code,

Thanks in advance!

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

}

Do you get a stack trace? If so, post some of it here. If not, how far does it get before failing? Have you debugged into it? Note that your code would be easier to follow if you used normal Java naming conventions - it's worth getting into the habit of that. — Jon Skeet
– Jon Skeet, Commented Mar 28, 2015 at 7:54
(The most obvious point of recursion here is toString, by the way... that may be the problem. Consider using an iterative approach instead, ideally using a StringBuilder...) — Jon Skeet
– Jon Skeet, Commented Mar 28, 2015 at 7:55
Can you provide an example of an input for which this fails? — Dawood ibn Kareem
– Dawood ibn Kareem, Commented Mar 28, 2015 at 8:29
The reason for most any stack overflow error is that you are using recursion without a termination condition, or the termination condition never occurs. — user207421
– user207421, Commented Mar 28, 2015 at 8:59
@EJP Probably not the case here. I'd have to go along with Jon's diagnosis that the toString method is probably the culprit, and it probably is just the sheer number of terms that is causing the problem. Using iteration rather than recursion in toString, as Jon suggested, will almost certainly fix this. — Dawood ibn Kareem
– Dawood ibn Kareem, Commented Mar 28, 2015 at 9:15

Stefan Haustein · Accepted Answer · 2015-03-29 14:05:23Z

1

Your toString implementation in node is recursive, that can lead to a stack overflow for longer lists (the stack size is usually much more limited than the heap size).

One way to address this would be to move toString to list, then implementing it in an iterative way:

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. Why not use a TreeMap<Integer, Integer> for this (or just an array if it's not too sparse)? This should make insertions much faster (O(log n) instead of (O(n)) while still maintaining the order.

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

edited Mar 29, 2015 at 14:05

answered Mar 28, 2015 at 9:46

Stefan Haustein

18.9k3 gold badges40 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Dawood ibn Kareem Over a year ago

The question is "why could I be getting a stack overflow error". I'm not sure that you've answered it.

Xh Lin Over a year ago

We haven't learn about trees yet...been in this class for less than a month

Collectives™ on Stack Overflow

Why could I be getting a java stackoverflow error using linked lists?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related