Несомненно, для хорошего понимания неизменяемых структур стоит ознакомиться с функциональными языками программирования. В данном случае Clojure будет лучшим выбором (в сравнении со Scala) - там идея персистентных неизменяемых структур данных проходит сквозь весь дизайн языка.
Если совсем кратко по вопросу, то неизменяемые структуры данных лучше за счет
гарантий относительно того, что они не могут измениться. Поясняю. Т.к. в современных языках программирования принято передавать аргументы в функцию по ссылке, то нет возможности утверждать, что метод не изменил коллекцию или любой другую структуру. Особенно это актуально для стороннего кода.
Также такая гарантия неизменяемости заставляет более тщательно проектировать алгоритмы и API конкуретных сред, вместо поспешного изменения состояния какой либо разделяемой структуры из разных потоков выполения (разделяемое изменяемое состояние это вообще зло при написании конкурентного кода).
Если же совсем абстрактно, то неизменяемые структуры данных изменяют дизайн программы с (разделяемые изменяемые данные + код изменяющий эти данные) на (неизменяемые данные в контекстах + чистые функции).
К минусам возможно отнести дополнительную нагрузку на сборщик мусора, т.к. для одного измененного поля в структуре создается дополнительная копия данной структуры (конечно без дублирования структур по сслыкам, т.к. содержимое этих структур не может измениться). Это не совсем минус, но дизайн. Ну и для создания неизменяемых структур данных с удобным API на императивных языках программирования нужно писать чуть больше кода (в актуальных функциональных языках подавляющее большинство структур иммутабельны).
Почитать можно тут
tonsky.me/talks/2015-codefest 
