0

Below, both descriptions of these data structures: (from Programming in scala book)

Linked lists

Linked lists are mutable sequences that consist of nodes that are linked with next pointers. In most languages null would be picked as the empty linked list. That does not work for Scala collections, because even empty sequences must support all sequence methods. LinkedList.empty.isEmpty, in par- ticular, should return true and not throw a NullPointerException. Empty linked lists are encoded instead in a special way: Their next field points back to the node itself. Like their immutable cousins, linked lists are best operated on sequen- tially. In addition, linked lists make it easy to insert an element or linked list into another linked list.

Mutable lists

A MutableList consists of a single linked list together with a pointer that refers to the terminal empty node of that list. This makes list append a con- stant time operation because it avoids having to traverse the list in search for its terminal node. MutableList is currently the standard implementation of mutable.LinearSeq in Scala.

Main difference is the addition of the last element's pointer in MutableList type.

Question is: What might be the usage preferring LinkedList rather than MutableList? Isn't MutableList strictly (despite the new pointer) equivalent and even more practical with a tiny addition of used memory (the last element's pointer)?

Improve this question
2
  • 1
    You have a nice comparision of mutable lists here: stackoverflow.com/questions/11049213/… Commented Jan 4, 2013 at 15:09
  • I will not fill okay by returning a mutable list from a function, or by receiving a mutable list in a function - that's it Commented Jan 4, 2013 at 22:19

1 Answer 1

Reset to default
2

Since MutableList wraps a LinkedList, most operations involve an extra indirection step. Note that wrapping means, it contains an internal variable to a LinkedList (indeed two, because of the efficient last element lookup). So the linked list is a required building block to realise the mutable list.

If you do not need prepend or look up of the last element, you could thus just go for the LinkedList. Scala offers you a large choice of data structures, so the best is first to make a checklist of all the operations that you require (and their preferred efficiency), then choose the best fit.

Generally, I recommend you to use immutable structures, they are often as efficient as the mutable ones and don't produce problems with concurrency.

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

1 Comment

Thanks, I would add that LinkedList is quite similar to Node element presents in java.util.LinkedList type (in Java). MutableList wrapping LinkedList(in order to be able to locate last element), is thus similar to java.util.LinkedList. Therefore, both code designs (building mutable linked lists) are a matter of taste.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.