Какова временная сложность метода `last` для List в scala?

Question

Что такое временная сложность метода last для List в scala?

scala> var list = List(1,2,3,4,5)
list: List[Int] = List(1, 2, 3, 4, 5)

scala> list.last
res0: Int = 5

Проходит ли scala итерацию по всему списку, чтобы получить последний элемент (O (n)), или в списке есть указатель на последний элемент (O (1))?

Answer 1

Если вам нужен постоянный доступ к последнему элементу, рассмотрите возможность использования IndexedSeq. last сложность всегда O (1)

Answer 2

Глядя на источник, это O (n)

  override /*TraversableLike*/
  def last: A = {
    if (isEmpty) throw new NoSuchElementException
    var these = this
    var nx = these.tail
    while (!nx.isEmpty) {
      these = nx
      nx = nx.tail
    }
    these.head
  }