List serialization which supports long lists, structural sharing and 2.9 serialization data. Added tests to check the structural sharing after deserialization. Simplified using closure. Split into 2 loops (lists, heads) to be breadth-first.

ListSer.scala

// package ...

import java.io._

object ListSer {

  sealed abstract class List[+A] extends Serializable {
    def isEmpty: Boolean
    def head: A
    def tail: List[A]

    def ::[B >: A] (x: B): List[B] = new ::(x, this)
  }

  final case class ::[B](private var hd: B, private var tl: List[B]) extends List[B] {
    override def head : B = hd
    override def tail : List[B] = tl
    override def isEmpty: Boolean = false

    private def writeObject(out: ObjectOutputStream) = ListSerializeCtrl(writeObject_2_10_1(out, _))

    private def writeObject_2_10_1(out: ObjectOutputStream, ctrl: ListSerializeCtrl) {
      out.writeObject(ListSerializeStart) // needed to differentiate with the legacy `::` serialization
      var current: List[B] = this
      ctrl.loop {
        current = current.tail
        out.writeObject(current)
      }
      val barrier = current
      current = this
      do {
        out.writeObject(current.head)
        current = current.tail
      } while (current ne barrier)
    }

    private def readObject(in: ObjectInputStream) = ListSerializeCtrl(readObject_2_10_1(in, _))

    private def readObject_2_10_1(in: ObjectInputStream, ctrl: ListSerializeCtrl) {
      val obj = in.readObject
      if (obj != ListSerializeStart)
        oldReadObject(in, obj)
      else {
        var current: List[B] = this
        ctrl.loop {
          val currentTail = in.readObject.asInstanceOf[List[B]]
          current.asInstanceOf[::[B]].tl = currentTail
          current = currentTail
        }
        val barrier = current
        current = this
        do {
          current.asInstanceOf[::[B]].hd = in.readObject.asInstanceOf[B]
          current = current.tail
        } while (current ne barrier)
      }
    }

    /* The oldReadObject method exists here for compatibility reasons.
    * :: objects used to be serialized by serializing all the elements to
    * the output stream directly, but this was broken (see SI-5374).
    */
    private def oldReadObject(in: ObjectInputStream, firstObject: AnyRef) {
      hd = firstObject.asInstanceOf[B]
      assert(hd != ListSerializeEnd)
      var current: ::[B] = this
      while (true) in.readObject match {
        case ListSerializeEnd =>
          current.tl = Nil
          return
        case a : Any =>
          val list : ::[B] = new ::(a.asInstanceOf[B], Nil)
          current.tl = list
          current = list
      }
    }

    private def oldWriteObject(out: ObjectOutputStream) {
      var xs: List[B] = this
      while (!xs.isEmpty) { out.writeObject(xs.head); xs = xs.tail }
      out.writeObject(ListSerializeEnd)
    }
  }

  case object Nil extends List[Nothing] {
    override def isEmpty = true
    override def head: Nothing =
      throw new NoSuchElementException("head of empty list")
    override def tail: List[Nothing] =
      throw new UnsupportedOperationException("tail of empty list")
    // Removal of equals method here might lead to an infinite recursion similar to IntMap.equals.
    override def equals(that: Any) = that match {
      case that1: collection.Seq[_] => that1.isEmpty
      case _ => false
    }
  }

  private case object ListSerializeStart

  @SerialVersionUID(0L - 8476791151975527571L)
  private case object ListSerializeEnd

  private object ListSerializeCtrl {
    private val tl = new ThreadLocal[ListSerializeCtrl]

    @inline def apply(fun: ListSerializeCtrl => Unit): Unit = tl.get match {
      case null =>
        val control = new ListSerializeCtrl
        tl.set(control)
        try fun(control)
        finally tl.set(null)
      case control =>
        if (control.inLoop)
          control.seen = true
        else
          fun(control)
    }
  }

  private final class ListSerializeCtrl {
    private var seen: Boolean = false
    private var inLoop: Boolean = false

    @inline def loop(body: => Unit) {
      try
        do {
          seen = false
          inLoop = true
          body
        } while (seen)
      finally inLoop = false
    }
  }

  def test1() {
    var r: List[Int] = Nil
    var i = 0
    while (i < 1000000) {
      r = i :: r
      i += 1
    }
    //val largeList = r
    val largeList = r :: r

    val oos = new ObjectOutputStream(new FileOutputStream("C:\\misc\\largeList.ser"))
    oos.writeObject(largeList)
    oos.flush()
    oos.close()

    val ois = new ObjectInputStream(new FileInputStream("C:\\misc\\largeList.ser"))
    val read = ois.readObject().asInstanceOf[List[_]]
    println(read.isEmpty)
  }

  def test2() {
    val l1: List[String] = "1" :: Nil
    val l2: List[String] = "2" :: "3" :: l1
    val p = (l1, l2)
    val pr = (l2, l1)
    val a = Array(l2, p)
    val l3: List[AnyRef] = p :: l2 :: l1 :: p :: a :: Nil

    def verifyL1L2(l1: List[String], l2: List[String]) { assert(l1 eq l2.tail.tail) }

    def verifyP(p: (List[String], List[String])) { verifyL1L2(p._1, p._2) }

    def verifyPr(p: (List[String], List[String])) { verifyL1L2(p._2, p._1) }

    def verifyL3(list: List[AnyRef]) {
      val p = list.head.asInstanceOf[(List[String], List[String])]
      val l1 = p._1
      val l2 = p._2
      val a = list.tail.tail.tail.tail.head.asInstanceOf[Array[AnyRef]]
      verifyP(p)
      assert(p eq list.tail.tail.tail.head)
      assert(l2 eq list.tail.head)
      assert(l1 eq list.tail.tail.head)
      assert(a(0) eq l2)
      assert(a(1) eq p)
    }

    verifyP(p)
    val pc = deepCopy(p)
    verifyP(pc)

    verifyPr(pr)
    val prc = deepCopy(pr)
    verifyPr(prc)

    verifyL3(l3)
    val l3c = deepCopy(l3)
    verifyL3(l3c)

    println()
  }

  case class Foo(tail: List[Foo])

  def test3() {
    def create(len: Int): List[Foo] = if (len == 0) Nil else {
      val tail = create(len - 1)
      Foo(tail) :: tail
    }

    def check(list: List[Foo]) {
      if (list.isInstanceOf[::[Foo]]) {
        val lf = list.asInstanceOf[::[Foo]]
        assert(lf.head.tail eq lf.tail)
        check(lf.tail)
      }
    }

    val xs = List.fill(32)(7)
    val dxs = deepCopy(xs)
    // assert(xs == dxs)

    val ys = create(3002)
    check(ys)
    val dys = deepCopy(ys)
    check(dys.asInstanceOf[List[Foo]])
    println()
    // assert(ys == dys)
  }

  def deepCopy[T](obj : T): T = {
    val baos = new ByteArrayOutputStream()
    val oos = new ObjectOutputStream(baos)
    oos.writeObject(obj)
    oos.flush()
    val data = baos.toByteArray
    println("size:" + data.length)
    val bais = new ByteArrayInputStream(data)
    val ois = new ObjectInputStream(bais)
    ois.readObject().asInstanceOf[T]
  }

  def test4() {
    var r: List[Int] = Nil
    var i = 0
    while (i < 500) { //500
      r = i :: r
      i += 1
    }
    //val largeList = r
    val largeList = r :: r

    var total = 0L
    i = 0
    while (i < 20) {
      val start = System.currentTimeMillis()
      var j = 0
      while (j < 2000) { // 200
        val r2 = deepCopy(r)
        j += 1
      }
      val end = System.currentTimeMillis()
      val dur = end - start
      if (i >= 10)
        total += dur
      println(end - start)
      i += 1
    }
    val avg = (total * 1.0) / 10
    println(avg)
  }

  def main(args: Array[String]) {
    test3()
  }
}