Menu
Coming from a Java background, I'm wondering why List in Scala doesn't have a size field like its Java equivalent LinkedList. After all, with a size field you'll be able to determine the size of the list in constant-time, so why was the size field dropped?
(This question refers to the new collection classes in Scala 2.8 and later. Also, I'm referring to the immutable List, not the mutable one.)
704
Following are the point of difference between lists and array in Scala: Lists are immutable whereas arrays are mutable in Scala. Lists represents a linked list whereas arrays are flat.
Specific to Scala, a list is a collection which contains immutable data, which means that once the list is created, then it can not be altered. In Scala, the list represents a linked list. In a Scala list, each element need not be of the same data type.
A set is a collection which only contains unique items which are not repeatable and a list is a collection which contains immutable data. In scala, ListSet class implements immutable sets using a list-based data structure.
Scala Lists are quite similar to arrays which means, all the elements of a list have the same type but there are two important differences. First, lists are immutable, which means elements of a list cannot be changed by assignment. Second, lists represent a linked list whereas arrays are flat.
One cannot say the size field was dropped, as such list without the size have existed for 50 years since LISP where they are ubiquitous and they are very common in ML and Haskell too, both influential in scala.
The basic reason is that list is a recursive structure. A non empty List is Cons(head: A, tail: List[A]) — except that Cons is in fact called :: to allow a convenient infix notation. You can access the tail (the list without its head element) and that is a list too. And this is done just about all the time. So having the count in the list would not mean adding just one integer, but as many integers as there are elements. This is feasible, but certainly not free.
If you compare with java's LinkedList, LinkedList has a recursive implementation (based on Node, which is more or less like Cons, but with links in both direction). But a LinkedList is not a Node, it owns them (and keep their count). So while it has a recursive implementation, you cannot treat it recursively. It you wanted the tail of a LinkedList as a LinkedList, you would have to either remove the head and have your list changed or else copy all the tail elements to a new LinkedList. So scala's List and java's LinkedList are very different structures.
150
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
