Scala DoubleLinkedList replacement

Question

DoubleLinkedList is deprecated since Scala 2.11.0 (http://www.scala-lang.org/api/current/index.html#scala.collection.mutable.DoubleLinkedList$). Why is this? There doesn't seem to be a clear replacement for it. Is there any plans for a successor?

The relevant Git commit message - not very informative: https://github.com/scala/scala/commit/3cc99d7b4aa43b1b06cc837a55665896993235fc — David Soroko, Dec 24 '14 at 14:33

score 0 · Answer 1 · edited May 23 '17 at 12:01

0

"Idiosyncratic and dangerous" API, as it is described in the commit message and deprecation, sums it up.

The general direction has been to reduce the size of the standard library, and of collections in particular, so it's likely that a replacement would arrive (if ever) only as part of a re-imagined and re-engineered replacement collections library. (There are efforts underway.)

The last comments on this issue are of the order, "How is this even supposed to work?" It's surprisingly difficult to reconcile many of the standard API of the 2.8 collections with mutability, which is one reason the experiment to unify mutable and immutable collections behind common interfaces has lived up to its hype.

edited May 23 '17 at 12:01

Community

1
1

answered Dec 25 '14 at 07:40

som-snytt

39,429
2
47
129

David Blaine sucks in comparison with scala's MutableList :) – dk14 Dec 25 '14 at 12:49
You are not answering any of the questions. Your oppinion regarding computing curricula and data structures may be relevant in discussion foruns or mailing lists, but not relevant for clarifiying any of the questions here. – Richard Gomes Jan 11 '16 at 12:50
@RichardGomes Probably the question, "Why is this?" is too broad, especially on a holiday. This waggish answer was just a placeholder until Rex Kerr answered it. The real answer is the phrase, "breaking encapsulation", which corresponds to the phrase in the commit, "idiosyncratic and dangerous". I'll edit to reduce the wag factor. – som-snytt Jan 11 '16 at 18:36
@RichardGomes Apologies, this answer also waxes waggish at the end. – som-snytt Jan 11 '16 at 18:47

score 0 · Answer 2 · answered Jul 25 '18 at 03:41

Answering what is a replacement for DoubleLinkedList, alas, as of 2.12.6, there is no non-deprecated collection type that offers constant time addition/removal from both ends. Vector comes close, but there's no way to remove elements from it, only replace (using update). I had a similar requirement, and ended up using java.util.LinkedList. And yes, this is one use case where Java offers a feature not present in Scala.

Sample code:

import scala.collection.JavaConverters._
val xs = new java.util.LinkedList[T]().asScala
// remove from beginning, O(1)
xs.remove(0)
// remove from end, O(1)
xs.remove(xs.size - 1)
// append, O(1)
xs += e
// prepend, O(1)
e +=: xs

Scala DoubleLinkedList replacement

2 Answers2

Linked