Use case for LinkedList

Question

This post only discusses scala.collection.mutable.LinkedList. Other implementations are not the topic of this thread.

My question is: what is the use case of this class? I find it has the problems of both mutable and immutable type of structures while yielding the benefits of none. I say that because:

• the API looks to me as if it were an immutable API (filter, map, drop, take etc all return a new LinkedList instead of doing in-place modifications)
• all the benefits of immutable linked list are, at least I guess, not present, ie maximum sharing between structures, since those are still mutable (through var elem and var next.

So basicly we have a linear access time, linear append time, linear space etc and nothing to show for it in space complexity or in ability to reason about code (except maybe the O(1) prepend but it's still the case with immutable lists).

Do I fail to see an important benefit of this type of structure? I'm looking for objective measures and/or use-cases appliable to this class.

Answer 1

I'd say the reason is complexity - the linked list class allows you to hold a reference to a node in the middle of the list, and use insert or update at that node, instead of going through the head of the list.

[] --> [] --> ... --> [] --> ... --> [] --|
^                     ^
head                  myReference

In an application where I know exactly where a change in some sequence will happen (myReference above), it costs much less to modify that location than copying everything up to that location as would be the case with immutable.List (i.e. I just insert a new node after myReference).

                             myNewNode
                             v
[] --> [] --> ... --> [] --> [] ---> ... --> [] --|
^                     ^
head                  myReference

An example of such an application - an L-system where you expand parts of a string. It's much cheaper to insert new nodes in-place, than it is to copy the entire string each time it needs to be expanded.

Another reason is completeness - since DoubleLinkedList and LinkedListLike share a lot of common infrastructure, providing an extra LinkedList class came as a low cost to the standard library size.