CODEWITHSUNDEEP
scalapointersdata-structuresscala-collections
Mik378
Mik378

Reputation: 22171

LinkedList vs MutableList in scala

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)?

Upvotes: 0

Views: 1815

Answers (1)

0__
0__

Reputation: 67280

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.

Upvotes: 2

Related Questions