Fix for linked lists closes #4080 and proves my...

Fix for linked lists closes #4080 and proves my desire not to ship
obviously broken code is even greater than my will to hold out for any
help. I threw in a free fix for this which I noticed while in there.

  scala> scala.collection.mutable.LinkedList[Int]().head

  res0: Int = 0

Also was reminded how useless tests can be:

  val ten = DoubleLinkedList(1 to 10: _*)
  ten.insert(DoubleLinkedList(11))
  // Post-insert position test
  require(ten.last == 11)

Fortunately a test confirming buggy behavior still serves a purpose by
breaking when you fix the bug which allowed it to pass, thus letting you
fix the broken test too. Life's (very) little compensations. Linked list
code should still be presumed broken. No review.

7 files changed, 38 insertions, 30 deletions

diff --git a/src/library/scala/collection/mutable/DoubleLinkedList.scala b/src/library/scala/collection/mutable/DoubleLinkedList.scala
index f2a732ffd1..4465ebef93 100644
--- a/src/library/scala/collection/mutable/DoubleLinkedList.scala
+++ b/src/library/scala/collection/mutable/DoubleLinkedList.scala
@@ -68,24 +68,22 @@ class DoubleLinkedList[A]() extends LinearSeq[A]
 object DoubleLinkedList extends SeqFactory[DoubleLinkedList] {
   /** $genericCanBuildFrom */
   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, DoubleLinkedList[A]] = new GenericCanBuildFrom[A]
+
   def newBuilder[A]: Builder[A, DoubleLinkedList[A]] =
     new Builder[A, DoubleLinkedList[A]] {
-      var current: DoubleLinkedList[A] = _
-      val emptyList = new DoubleLinkedList[A]()
-      if(null == current)
-        current = emptyList
+      def emptyList() = new DoubleLinkedList[A]()
+      var current = emptyList()
 
       def +=(elem: A): this.type = {
-        if (current.nonEmpty)
-          current.insert(new DoubleLinkedList(elem, emptyList))
+        if (current.isEmpty)
+          current = new DoubleLinkedList(elem, emptyList())
         else
-          current = new DoubleLinkedList(elem, emptyList)
+          current append new DoubleLinkedList(elem, emptyList())
+
         this
       }
 
-      def clear() {
-        current = emptyList
-      }
+      def clear(): Unit = current = emptyList()
       def result() = current
     }
 }
diff --git a/src/library/scala/collection/mutable/DoubleLinkedListLike.scala b/src/library/scala/collection/mutable/DoubleLinkedListLike.scala
index 18a0e164a2..7ad2f9558f 100644
--- a/src/library/scala/collection/mutable/DoubleLinkedListLike.scala
+++ b/src/library/scala/collection/mutable/DoubleLinkedListLike.scala
@@ -110,12 +110,9 @@ trait DoubleLinkedListLike[A, This <: Seq[A] with DoubleLinkedListLike[A, This]]
 
   private def outofbounds(n: Int) = throw new IndexOutOfBoundsException(n.toString)
 
-  override def drop(n: Int): This = super[SeqLike].drop(n)
-
-  override def tail = drop(1)
-
-  override def apply(n: Int): A   = atLocation(n)(_.elem)(outofbounds(n))
-  override def update(n: Int, x: A): Unit  = atLocation(n)(_.elem = x)(outofbounds(n))
-  override def get(n: Int): Option[A] = atLocation[Option[A]](n)(x => Some(x.elem))(None)
-
+  override def drop(n: Int): This         = super[SeqLike].drop(n)
+  override def tail                       = drop(1)
+  override def apply(n: Int): A           = atLocation(n)(_.elem)(outofbounds(n))
+  override def update(n: Int, x: A): Unit = atLocation(n)(_.elem = x)(outofbounds(n))
+  override def get(n: Int): Option[A]     = atLocation[Option[A]](n)(x => Some(x.elem))(None)
 }
diff --git a/src/library/scala/collection/mutable/LinkedList.scala b/src/library/scala/collection/mutable/LinkedList.scala
index beee4857b0..6c5bf9ae49 100644
--- a/src/library/scala/collection/mutable/LinkedList.scala
+++ b/src/library/scala/collection/mutable/LinkedList.scala
@@ -60,10 +60,9 @@ class LinkedList[A]() extends LinearSeq[A]
  *  @define coll linked list
  */
 object LinkedList extends SeqFactory[LinkedList] {
-
   override def empty[A]: LinkedList[A] = new LinkedList[A]
-
   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, LinkedList[A]] = new GenericCanBuildFrom[A]
+
   def newBuilder[A]: Builder[A, LinkedList[A]] =
     (new MutableList) mapResult ((l: MutableList[A]) => l.toLinkedList)
 }
diff --git a/src/library/scala/collection/mutable/LinkedListLike.scala b/src/library/scala/collection/mutable/LinkedListLike.scala
index b24cda946e..a3fd786c2a 100644
--- a/src/library/scala/collection/mutable/LinkedListLike.scala
+++ b/src/library/scala/collection/mutable/LinkedListLike.scala
@@ -60,12 +60,14 @@ trait LinkedListLike[A, This <: Seq[A] with LinkedListLike[A, This]] extends Seq
   var next: This = _
 
   override def isEmpty = next eq this
-
   override def length: Int = length0(repr, 0)
 
-  @tailrec private def length0(elem: This, acc: Int): Int = if (elem.isEmpty) acc else length0(elem.next, acc + 1)
+  @tailrec private def length0(elem: This, acc: Int): Int =
+    if (elem.isEmpty) acc else length0(elem.next, acc + 1)
 
-  override def head: A    = elem
+  override def head: A =
+    if (isEmpty) throw new NoSuchElementException
+    else elem
 
   override def tail: This = {
     require(nonEmpty, "tail of empty list")
@@ -92,7 +94,8 @@ trait LinkedListLike[A, This <: Seq[A] with LinkedListLike[A, This]] extends Seq
   def insert(that: This): Unit = {
     require(nonEmpty, "insert into empty list")
     if (that.nonEmpty) {
-      next = next.append(that)
+      that append next
+      next = that
     }
   }
 
@@ -100,7 +103,7 @@ trait LinkedListLike[A, This <: Seq[A] with LinkedListLike[A, This]] extends Seq
     var i = 0
     var these: This = repr
     while (i < n && !these.isEmpty) {
-      these = these.next.asInstanceOf[This] // !!! concrete overrides abstract problem
+      these = these.next
       i += 1
     }
     these
@@ -108,7 +111,7 @@ trait LinkedListLike[A, This <: Seq[A] with LinkedListLike[A, This]] extends Seq
 
   private def atLocation[T](n: Int)(f: This => T) = {
     val loc = drop(n)
-    if (!loc.isEmpty) f(loc)
+    if (loc.nonEmpty) f(loc)
     else throw new IndexOutOfBoundsException(n.toString)
   }
 
diff --git a/test/files/run/bug4080.check b/test/files/run/bug4080.check
new file mode 100644
index 0000000000..66ce31bb43
--- /dev/null
+++ b/test/files/run/bug4080.check
@@ -0,0 +1 @@
+LinkedList(1, 0, 2, 3)
diff --git a/test/files/run/bug4080.scala b/test/files/run/bug4080.scala
new file mode 100644
index 0000000000..92740ed776
--- /dev/null
+++ b/test/files/run/bug4080.scala
@@ -0,0 +1,12 @@
+import scala.collection.mutable.LinkedList
+
+object Test {
+  def main(args: Array[String]) {
+    val ll = LinkedList(1, 2, 3)
+    ll.insert(LinkedList(0))
+    println(ll)
+    val ll2 = LinkedList[Int]()
+    try println(ll2.head)
+    catch { case _ => () }
+  }
+}
diff --git a/test/files/run/t3361.scala b/test/files/run/t3361.scala
index 17af89a67c..892e36dbd9 100644
--- a/test/files/run/t3361.scala
+++ b/test/files/run/t3361.scala
@@ -39,10 +39,8 @@ object Test extends App {
 
   def insert_1 {
     val ten = DoubleLinkedList(1 to 10: _*)
-    ten.insert(DoubleLinkedList(11)) match {
-      case _: Unit => require(true)
-      case _ => require(false)
-    }
+    ten.append(DoubleLinkedList(11))
+
     // Post-insert size test
     require(11 == ten.size)
     // Post-insert data test