scala雾中风景(19): MutableList与mutable.LinkedList的问题

群里看到的问题:

scala> import scala.collection._

scala> val l = mutable.MutableList(1,2)
l: scala.collection.mutable.MutableList[Int] = MutableList(1, 2)

scala> val t = l.tail
t: scala.collection.mutable.MutableList[Int] = MutableList(2)

scala>  l += 3
res0: l.type = MutableList(1, 2, 3)

scala> t.length
res1: Int = 1

这里显示 t 的长度没有问题,但显示t的值的时候,却不是预期的:

scala> t
res2: scala.collection.mutable.MutableList[Int] = MutableList(2, 3)

怎么把l列表后来增加的3也给包含进去了。这要看这个MutableListtail方法的实现是怎么回事了。

scala.collection.mutable.MutableList里为了实现scala.collection.GenTraversableLike特质里的head, tail等方法,是通过链表scala.collection.mutable.LinkedList来存储数据。它的tail方法实现如下:

override def tail: MutableList[A] = {
    val tl = new MutableList[A]
    tailImpl(tl)
    tl
}

// this method must be private for binary compatibility
private final def tailImpl(tl: MutableList[A]) {
    require(nonEmpty, "tail of empty list")
    tl.first0 = first0.tail
    tl.len = len - 1
    tl.last0 = if (tl.len == 0) tl.first0 else last0
}

这里面要看看 tl.first0 = first0.tail 的实现是什么,在LinkedListLike里:

override def tail: This = {
    require(nonEmpty, "tail of empty list")
    next
}

它直接返回当前链表的下一个节点引用。所以当原链表末尾附加新的值时,这个 tl 链表也是可以引用到的,因为它们是复用的。

不过因为对这个tl的len设置过了,所以迭代的时候,并不会越界。并且toString方法也不会多展示不属于它的数据的:

scala> t.toString
res14: String = MutableList(2)

scala> t.foreach(print)
2

但在repl的展示上,就没有做的很严谨了,它没有调用这个对象的toString来展示它的值,而是自己把这个节点及链表后续节点的值都展示了:

scala> t
res15: scala.collection.mutable.MutableList[Int] = MutableList(2, 3)

这应该算是repl展示层面的不严谨吧。不过MutableList的实现也不太严谨,这个t虽然length是1,但后边节点如果有值的话也是可以索引到的:

scala> t(0)
res17: Int = 2

scala> t(1)
res18: Int = 3

scala> l += 4
res19: l.type = MutableList(1, 2, 3, 4)

scala> t(2)
res20: Int = 4

这也算是一个陷阱吧,mutable的集合在使用的时候要清楚它的场景和限制。

scala雾中风景(19): MutableList与mutable.LinkedList的问题》上有2个想法

  1. Pingback引用通告: scala雾中风景(20): MutableList迭代器的bug | 在路上

  2. scala 2.11.0中 linkedlist已经被弃用,请问使用什么代替linkedlist呢?

发表评论

电子邮件地址不会被公开。 必填项已用*标注