Care to review my immutable singly linked list?

Question

public sealed class SinglyLinkedList<T> : IEnumerable<T>
{
 readonly static SinglyLinkedList<T> _empty = new SinglyLinkedList<T>();
 readonly bool _isEmpty;
 readonly T _head;
 readonly SinglyLinkedList<T> _tail;
 private SinglyLinkedList()
 {
 _isEmpty = true;
 }
 private SinglyLinkedList(T head)
 {
 _isEmpty = false;
 _head = head;
 }
 private SinglyLinkedList(T head, SinglyLinkedList<T> tail)
 {
 _isEmpty = false;
 _head = head;
 _tail = tail;
 }
 public static SinglyLinkedList<T> Empty
 {
 get { return _empty; }
 }
 public int Count
 {
 get 
 {
 var list = this;
 var count = 0;
 while (!list._isEmpty)
 {
 count++;
 list = list._tail;
 }
 return count; 
 }
 }
 public bool IsEmpty
 {
 get { return _isEmpty; }
 }
 public T Head
 {
 get
 {
 if (_isEmpty)
 throw new InvalidOperationException("The list is empty.");
 return _head;
 }
 }
 public SinglyLinkedList<T> Tail
 {
 get
 {
 if (_tail == null)
 throw new InvalidOperationException("This list has no tail.");
 return _tail;
 }
 }
 public static SinglyLinkedList<T> FromEnumerable(IEnumerable<T> e)
 {
 if (e == null)
 throw new ArgumentNullException("e");
 return FromArrayInternal(e.ToArray());
 }
 public static SinglyLinkedList<T> FromArray(params T[] a)
 {
 if (a == null)
 throw new ArgumentNullException("a");
 return FromArrayInternal(a);
 }
 public SinglyLinkedList<T> Append(T value)
 {
 var array = new T[Count + 1]; 
 var list = this;
 var index = 0;
 while (!list._isEmpty)
 {
 array[index++] = list._head;
 list = list._tail;
 }
 array[index] = value;
 return FromArrayInternal(array);
 }
 public SinglyLinkedList<T> Prepend(T value)
 {
 return new SinglyLinkedList<T>(value, this);
 } 
 public SinglyLinkedList<T> Insert(int index, T value)
 {
 if (index < 0)
 throw new ArgumentOutOfRangeException("index", "Cannot be less than zero.");
 var count = Count;
 if (index >= count)
 throw new ArgumentOutOfRangeException("index", "Cannot be greater than count.");
 var array = new T[Count + 1]; 
 var list = this;
 var arrayIndex = 0;
 while (!list._isEmpty)
 {
 if (arrayIndex == index)
 {
 array[arrayIndex++] = value;
 }
 array[arrayIndex++] = list._head;
 list = list._tail;
 }
 return FromArrayInternal(array);
 }
 public IEnumerator<T> GetEnumerator()
 {
 var list = this;
 while (!list._isEmpty)
 {
 yield return list._head;
 list = list._tail;
 }
 }
 public override string ToString()
 {
 if (_isEmpty)
 return "[]";
 return string.Format("[{0}...]", _head);
 }
 IEnumerator IEnumerable.GetEnumerator()
 {
 return GetEnumerator();
 }
 static SinglyLinkedList<T> FromArrayInternal(T[] a)
 {
 var result = Empty;
 for (var i = a.Length - 1; i >= 0; i--)
 {
 result = result.Prepend(a[i]);
 }
 return result;
 }
}

• George Mauer: Just want to point out that Microsoft has put out an immutable collections library

Answer 1

1. The constructor with one argument is never used and doesn't make much sense (list with a head but no tail?).
2. You shouldn't use Count in your own methods unless absolutely necessary, because it's O(n). Or you should cache the result in a field.
3. Because you use Count so often, your Insert() walks through the whole list three times! The second time it's because of completely unnecessary Count. You should completely rewrite it, Insert() can be done in O(index), which can be much better than your O(n).

Answer 2

You might consider separating out the functionality between the controller/iterator and the item. For example, try using something like what is below (or an alteration of it). In any linked list scenario, the item itself is the controller of before/after pointers. Since you are wanting a single linked list, you would probably be best served with having an item class. Now that you have that, you can simply implement a controller which represents the whole list and the more user friendly functionality.

Single linked item example:

public class SingleLinkedItem<T>
{
 public SingleLinkedItem(SingleLinkedList<T> list, SingleLinkedItem<T> itemBefore, T item)
 {
 if (ItemBefore.List != list)
 throw new Exception("Item being added must be from the same list.");
 List = list;
 ItemBefore = itemBefore;
 Item = item;
 }
 public readonly SingleLinkedList<T> List;
 public SingleLinkedItem<T> ItemBefore { get; set; }
 public readonly T Item;
}

Controller example:

public sealed class SingleLinkedList<T>
{
 public SingleLinkedItem<T> First { get; private set; }
 public SingleLinkedItem<T> Last { get; private set; }
 public long Length { get; private set; }
 public void Add(T item)
 {
 var linkedItem = new SingleLinkedItem<T>(this, Last, item);
 Last = linkedItem;
 Length++;
 if (First == null)
 First = Last;
 }
}

These examples focus on a fast append style, which also means that searching or iterating over it will always be in reverse order. If you need a fast-forward search and can sacrifice a slower append, just reverse the linked direction.