Menu
I always thought that the benefit of linked lists was that you could add or remove items (especially not from the end) without having to copy lots of elements thanks to the beauty of pointers.
However, Scala's List is immutable (at least by default). What is the benefit of having an immutable linked list (because there are definite downsides, e.g. not O(1) element access.)
Thanks!
789
In Scala, the list represents a linked list. In a Scala list, each element need not be of the same data type. The implementation of Scala lists uses a mutable state internally during the construction phase. In Scala, the list is defined under the scala.
Linked lists are preferable over arrays when:you don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big. you don't need random access to any elements. you want to be able to insert items in the middle of the list (such as a priority queue)
Linked lists are often used because of their efficient insertion and deletion. They can be used to implement stacks, queues, and other abstract data types.
Linked list is linear data structure where elements are not sorted and there memory locations are not in sequence.So liked list has Struct called Node which hold data and reference to the next element. Linked list.
I think the main reason is that one of the most powerful uses of linked lists is head/tail splitting. There are lots of recursive algorithms that look like this one:
def listlen[A](xs: List[A], already: Int = 0): Int = xs match {
case Nil => already
case x :: rest => listlen(rest, already+1)
}
Of course, lists already know how to get their length; this is just an example. The point is that you pull off the head, and then do something else with the tail--lots of useful things work this way.
Since lists are immutable, we can do something else--we can take as much time as we want to evaluating the rest of our list! We don't have to finish in one go; we're sure it will never change. This would not be the case if the list were mutable--either we need to lock the list, preventing anyone else from seeing it, or we need to make a defensive copy of the whole thing just in case someone might swap it.
Now, if you really want a mutable list, there's mutable.LinkedList that has the nice insertion properties that you're talking about. But that doesn't give you the elegant recursion with peace of mind that the immutable lists give you.
(Note that you could do some of this with an immutable array-backed structure, but the possible benefit of a collection with each element wrapped is that you don't need to save or copy the whole array just because you need a few elements from the end; if the early elements in the list aren't pointed to any more, they can be garbage collected.)
137
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
