Почему добавление в список плохо?
=================================

я недавно начал изучать скала, а ямы встречаем`::` (cons) функция, которая добавляется в список.  
  
В книге "Программирование в Scala " в нем говорится, что функции добавления нет, потому что добавление в список имеет производительность o (n), тогда как предварительное добавление имеет производительность o (1)

Что-то не так в этом утверждении.

Isn»t производительность зависит от реализации? Isn»Можно ли просто реализовать список с прямыми и обратными ссылками и сохранить первый и последний элемент в контейнере?

Второй вопрос, который я предполагаю, что яя должен делать, когда у меня есть список, скажем, 1,2,3, и я хочу добавить 4 в конце? "

`x :: somelist` не мутирует`somelist`, но вместо этого создает новый список, который содержит х, а затем все элементы`somelist`, Это можно сделать за O (1) раз, потому что вам нужно только установить`somelist` как преемник`x` во вновь созданном, односвязном списке.

Если вместо этого использовались двусвязные списки,`x` также должен быть установлен в качестве предшественника`somelist`голова, которая изменила бы`somelist`, Так что, если мы хотим быть в состоянии сделать`::` в O (1) без изменения исходного списка мы можем использовать только односвязные списки.

Что касается второго вопроса: вы можете использовать`:::` объединить одноэлементный список в конец вашего списка. Это операция O (n).



 потому что требуется только две операции:

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

Вы никогда не программировали в Scala раньше, но вы можете попробовать[Буфер списка](https://www.scala-lang.org/docu/files/api/scala/collection/mutable/ListBuffer.html)



е много элементов в список в подпрограмме, или если вы создаете список, добавляя элементы, функциональная идиома состоит в том, чтобы создать список в обратном порядке, cons 'Принимая предметы нафронт из списка, затем полностью измените его в конце. Это дает вам производительность O (n) вместо O (n²)).



Стоит отметить, что здесь все изменилось.

Сегодня'S Scala, вы можете просто использовать`xs :+ x` добавить элемент в конце любой последовательной коллекции. (Существует также`x +: xs` готовиться. Мнемоника для многих из Scala 'S 2.8+ операций сбора является то, чтоседлоидет рядом сседлоразночтение.)

Это будет O (N) со связанной реализацией по умолчанию`List` или же`Seq`, но если вы используете`Vector` или же`IndexedSeq`Это будет эффективно постоянное время. в Scala`Vector` вероятно Скаласамая полезная спискообразная коллекцияв отличие от Java`Vector` что в основном бесполезно в наши дни.

Если вы работаете в Scala 2.8 или выше,[введение коллекций](https://docs.scala-lang.org/overviews/collections/introduction.html) это абсолют должен читать.



ным списком, так какЭто удобный неизменяемый тип коллекции. Когда ты сказал "список" на функциональном языке этообычно это то, что вы имеете в виду (односвязный список, обычно неизменный). Для такого типа append - это O (n), а cons - это O (1).