Почему добавление к списку в Scala имеет O (n) сложность по времени?

Я только что прочитал, что время выполнения операции добавления для List(: +) растет линейно с размером List.

Присоединение к a Listкажется довольно обычной операцией. Почему идиоматический способ сделать это состоит в том, чтобы предварительно добавить компоненты, а затем перевернуть список? Это также не может быть ошибкой проекта, поскольку реализация может быть изменена в любой момент.

С моей точки зрения, и добавление, и добавление должны быть O (1).

Есть ли законная причина для этого?

Я немного расширю свой комментарий. Структура List[T]данных от scala.collection.immutableоптимизирована для работы так, как работает неизменный список в более чисто функциональном языке программирования. У него очень быстрое время предварительной подготовки , и предполагается, что вы будете работать над головой почти весь свой доступ.

Неизменяемые списки получают очень быстрое время предопределения из-за того, что они моделируют свои связанные списки как серию «cons-ячеек». Ячейка определяет одно значение и указатель на следующую ячейку (классический стиль односвязного списка):

Cell [Value| -> Nil]

Когда вы переходите к списку, вы на самом деле просто делаете одну новую ячейку, а остальная часть существующего списка указывается на:

Cell [NewValue| -> [Cell[Value| -> Nil]]

Поскольку список неизменен, вы можете сделать это без фактического копирования . Нет опасности того, что старый список изменится и все значения в вашем новом списке станут недействительными. Однако вы теряете возможность иметь изменяемый указатель на конец вашего списка как компромисс.

Это очень хорошо подходит для рекурсивной работы со списками. Допустим, вы определили свою собственную версию filter:

def deleteIf[T](list : List[T])(f : T => Boolean): List[T] = list match {
  case Nil => Nil
  case (x::xs) => f(x) match {
    case true => deleteIf(xs)(f)
    case false => x :: deleteIf(xs)(f)
  }
}

Это рекурсивная функция, которая работает исключительно с заголовка списка и использует преимущества сопоставления с образцом через :: extractor. Это то, что вы часто видите в таких языках, как Haskell.

Если вы действительно хотите быстрое добавление, Scala предоставляет множество изменяемых и неизменных структур данных на выбор. На изменчивой стороне, вы можете посмотреть ListBuffer. Кроме того , Vectorиз scala.collection.immutableимеет быстрое время добавления.