Immutable Collection Strategy

From: Wavemaker (jabberdabber_at_BiteMeHotmail.com)
Date: 12/21/04 

Date: Tue, 21 Dec 2004 11:10:42 -0600

I've been thinking about creating an immutable collection class in
C#. This class would store immutable objects.

With an immutable collection, any time a change is made, instead of
the collection itself being modified, a new collection is created
and returned. This is the way the string class behaves in Java and
C#. When you perform an operation on a string object, a new string
object is created.

The problem is that copying an entire collection each time it is
modified isn't necessarily efficient. Ideally, when a new collection
is created from an existing one, as much of the old collection is
reused in creating the new one. This would save on resources.

This has led me to consider which data structure would be best for
this situation (putting aside other performance considerations for
the moment). What I'm looking for is a data structure that would let
me reuse as much of it as possible with each operation.

A singular linked list would work ok in some situations. For
example, if you have ten links and delete the first one. The
remaining nine links could be reused for the new collection without
being altered. But in other situations, say the last link is
deleted, nearly the entire collection would have to be copied. A
binary tree might be better.

Any thoughts? Thanks.