CODEWITHSUNDEEP
scalalinked-list
NullPointer0x00
NullPointer0x00

Reputation: 1858

Scala linked list stackoverflow

Using scala I have added about 100000 nodes to a linked list. When I use the function length, for example mylist.length. I get a 'java.lang.StackOverflowError' error, is my list to big to process? The list is only string objects.

Upvotes: 5

Views: 1244

Answers (4)

Kevin Wright
Kevin Wright

Reputation: 49705

Can you confirm that you truly need to use the length method? It sounds like you might not be using the correct collection type for your use-case (hard to tell without any extra information). Lists are optimised to be mapped over using folds or a tail-recursive function.

Despite saying that, this is absolutely an oversight that can easily be fixed in the standard library with a tail-recursive function. Hopefully we can get it in time for 2.9.0.

Upvotes: 0

huynhjl
huynhjl

Reputation: 41646

It appears the library implementation is not tail-recursive override def length: Int = if (isEmpty) 0 else next.length + 1. It seems like this is something that could be discussed on the mailing list to check if an enhancement ticket should be opened.

You can compute the length like this:

def length[T](l:LinkedList[T], acc:Int=0): Int =
  if (l.isEmpty) acc else length(l.tail, acc + 1)

Upvotes: 11

jimmyb
jimmyb

Reputation: 4387

In Scala, computing the length of a List is an order n operation, therefore you should try to avoid it. You might consider switching to an Array, as that is a constant time operation.

Upvotes: 1

Jon McAuliffe
Jon McAuliffe

Reputation: 3157

You could try increasing the stack/heap size available to the JVM. 

scala JAVA_OPTS="-Xmx512M -Xms16M -Xss16M" MyClass.scala

Where

-Xss<size>  maximum native stack size for any thread
-Xms<size>  set initial Java heap size
-Xmx<size>  set maximum Java heap size

This question has some more information.

See also this This Scala document.

Upvotes: 0

Related Questions