Scala linked list stackoverflow

Question

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.

Answer 1

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)

Answer 2

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.