Summary: The full service wide-body form of a linked list class

LinkedList<T>

This one needs a good bit of caution from a perfomance perspective. Actually this is a great example of the kind of tension that you see in a set of libraries like the BCL that is trying to serve a wide-range of customers. We'd like to have ease of use features like being able to get from a list node back to the list because customers request these things. We also like to be able to do internal sanity checks because they are common pitfalls and addressing them goes a long way to helping developer productivity. So sometimes we make choices that are far from the most performant because perf isn't deemed to be the high order bit on developer productivity.

Consider the linked list node:

		    public sealed class [LinkedListNode<T>]
		    {
		        public [LinkedListNode(T] value);
		        public [LinkedList<T>] List { get; }
		        public [LinkedListNode<T>] Next { get; }
		        public [LinkedListNode<T>] Previous { get; }
		        public T Value { get; set; }
		    }
	

OK just from that description we can see that the list is doubly linked and each node has a parent pointer to the head of the list. So what's the minimum cost of a node?

Well let's say T is Object we have to have
-obj header
-method table pointer
-parent pointer
-next pointer
-previous pointer
-the Object (also pointer)

total size 24 bytes. Eep!

Now if instead we just threaded a singly linked through the actual class we intend to make a list out of the marginal cost would be only 4 bytes per node. But of course we'd have to be able to modify the class...

So does that mean this list implementation is bad? Hardly, but if you were going to have millions of nodes I'd probably use something else.

See also: Other classes with comments System.Collections.Generic