Immutable容器的设计要点

Collection 分为 Mutable 和 Immutable ,  

Mutable 意味着可以并发、并行修改 集合，优点是可以在位编辑并且省空间，但是需要互斥与同步，并发编程并不容易，根据经验推荐几本书：
 ,  ,  
你将接接触到 java 本身各种解决并发安全编程的技术，包括 Phase/CyclicBarrier/CountdownLatch 及 UnSafe 锁原语等 ，也有 event-driven,  akka / STM 等各种解决方案。

Immutable 意味着无锁设计，访问效率最高，“有能力的解决并发问题，有智慧的绕过并发问题”，不变性  invariant 就是后者。
怎么设计一种Immutable list的RUD呢（不要问我C哪去了，）设计如下：
ADD x -    x = new Node ;  x ->next = Head ; Head= x.   场景如 foldLeft, foldRight 方向不同而已
UPDATE x -  首先 copy x  前面所有的结点， node = new Node;  Modify(node);  node->next = x->next ，然后返回新的头结点。
DELETE x -  首先  copy x  前面所有的结点，其中新copy的最后一个节点为y ,  则 y -> next = x->next, 然后返回新的头结点。

怎么设计一种Immutable tree的RUD呢（再要问我C哪去了，我就自杀）设计如下：
ADD x -     假设root为根结点，只需copy 根结点和x所有的父结点，操作类似list
UPDARE x -  假设root为根结点，只需copy 根结点和x所有的父结点，操作类似list
DELETE x - 假设root为根结点，只需copy 根结点和x所有的父结点，操作类似list

咋一看，虽然都是空间换时间，list 的UPDATE和 DELETE 最浪费空间，其实list是tree的退化，只一条分支而已。 如果用tree来实现list，可能更cost effective一些。那就需要在
tree node再加两个字段 pre 和 next，咋看都像数据结构的树的线索化。

Immutable tree比较tricky,其它可以优化的，只要节点的fan out 即  child足够多，那么要copy的父亲结点就足够少了，极致就是只有两层的树。除去root就是一层了。有点像并查集路径合并以及秩优化的最终查找树，whatever.

有人会问 Map 怎么办，大哥，底层不都是list和tree吗？ 君不见HashpMap 和 TreeMap, 还有HashSet和TreeSet.

要用 Immutable collection 请认准：
scala.collection, scala.collection.immutable
OR
java.util.collections  的 Collections.unmodifiableCollection(list/set/map)