1 files changed, 26 insertions, 5 deletions
diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala
index 1eedf93269..e1bcc0711c 100644
--- a/src/library/scala/collection/immutable/ListMap.scala
+++ b/src/library/scala/collection/immutable/ListMap.scala
@@ -13,13 +13,16 @@ package collection
 package immutable
 
 import generic._
-import scala.annotation.{tailrec, bridge}
+import scala.annotation.tailrec
 
 /** $factoryInfo
  *  @since 1
  *  @see [[http://docs.scala-lang.org/overviews/collections/concrete-immutable-collection-classes.html#list_maps "Scala's Collection Library overview"]]
  *  section on `List Maps` for more information.
  *
+ *  Note that `ListMap` is built in reverse order to canonical traversal order (traversal order is oldest first).
+ *  Thus, `head` and `tail` are O(n).  To rapidly partition a `ListMap` into elements, use `last` and `init` instead.  These are O(1).
+ *
  *  @define Coll immutable.ListMap
  *  @define coll immutable list map
  */
@@ -29,7 +32,13 @@ object ListMap extends ImmutableMapFactory[ListMap] {
     new MapCanBuildFrom[A, B]
   def empty[A, B]: ListMap[A, B] = EmptyListMap.asInstanceOf[ListMap[A, B]]
 
-  private object EmptyListMap extends ListMap[Any, Nothing] { }
+  @SerialVersionUID(-8256686706655863282L)
+  private object EmptyListMap extends ListMap[Any, Nothing] {
+    override def apply(key: Any) = throw new NoSuchElementException("key not found: " + key)
+    override def contains(key: Any) = false
+    override def last: (Any, Nothing) = throw new NoSuchElementException("Empty ListMap")
+    override def init: ListMap[Any, Nothing] = throw new NoSuchElementException("Empty ListMap")
+  }
 }
 
 /** This class implements immutable maps using a list-based data structure, which preserves insertion order.
@@ -49,8 +58,7 @@ object ListMap extends ImmutableMapFactory[ListMap] {
  *  @define willNotTerminateInf
  */
 @SerialVersionUID(301002838095710379L)
-@deprecatedInheritance("The semantics of immutable collections makes inheriting from ListMap error-prone.", "2.11.0")
-class ListMap[A, +B]
+sealed class ListMap[A, +B]
 extends AbstractMap[A, B]
    with Map[A, B]
    with MapLike[A, B, ListMap[A, B]]
@@ -159,7 +167,6 @@ extends AbstractMap[A, B]
      */
     override def apply(k: A): B1 = apply0(this, k)
 
-
     @tailrec private def apply0(cur: ListMap[A, B1], k: A): B1 =
       if (cur.isEmpty) throw new NoSuchElementException("key not found: "+k)
       else if (k == cur.key) cur.value
@@ -177,6 +184,15 @@ extends AbstractMap[A, B]
       if (k == cur.key) Some(cur.value)
       else if (cur.next.nonEmpty) get0(cur.next, k) else None
 
+
+    override def contains(key: A): Boolean = contains0(this, key)
+
+    @tailrec private def contains0(cur: ListMap[A, B1], k: A): Boolean =
+      if (k == cur.key) true
+      else if (cur.next.nonEmpty) contains0(cur.next, k)
+      else false
+
+
     /** This method allows one to create a new map with an additional mapping
      *  from `key` to `value`. If the map contains already a mapping for `key`,
      *  it will be overridden by this function.
@@ -186,6 +202,7 @@ extends AbstractMap[A, B]
       new m.Node[B2](k, v)
     }
 
+
     /** Creates a new mapping without the given `key`.
      *  If the map does not contain a mapping for the given key, the
      *  method returns the same map.
@@ -203,5 +220,9 @@ extends AbstractMap[A, B]
         remove0(k, cur.next, cur::acc)
 
     override protected def next: ListMap[A, B1] = ListMap.this
+
+    override def last: (A, B1) = (key, value)
+
+    override def init: ListMap[A, B1] = next
   }
 }