LinkedList memory consumption versus List when working with large arrays

Question

Hi,

Can anyone tell me if a linkedlist of structures will be allowed to grow larger than the equivalent List (given that a list uses a doubling strategy for increasing the size of it's internal array).

So given a struct that is say 40 bytes (I know about the 16 bytes and structure thing, but I am working with some legacy code here and it wouldn't be an easy option changing the struct to a class) my understanding is that each time the list's internal array is resized, the memory needs to be allocated for the new array (new_array_size * 40). So with a very large array, you eventually get an outofmemoryexception as there is no contiguous space large enough to create this new array. I know a linkedlist requires more space for each element (node) as it needs to hold forward and reverse pointers to the items in the list, but my question is does this mean that to add an extra element you only need a contiguous memory slot of (40 + the_space_needed_for_the_pointers). In other words the linkedlist will not suffer from having to allocate a huge new section of contiguous memory to expand.

Answer 1

Yes, that's accurate. LinkedList doesn't use an array for storage, it really is a chain of references. You'll get no garbage in the Large Object Heap when you need to store a large number of elements, unlike List, and avoid trouble with address space fragmentation conking your program out early.

Beware that it is not a substitute for List, indexing is O(n) instead of O(1). Big difference, unless you always iterate the list sequentially. When you need to make shrill choices like these, it is high time to start considering a 64-bit operating system.

Answer 2

Since a linked list is only referencing a forward and backward reference, you are not bound to contiguous memory allocation. @Hans' answer has excellent points; however, I do not agree that a 64-bit OS is the only option to have high-performance indexing.

Are you limited to those 2 choices?

If you are going to have a large number of structures to reference, can you consider a binary tree? Upside to using a tree is that indexing is a fraction of the linked list - O(log n). The downside is the extra work to keep a tree balanced. Balancing is imperative - without balance, you will end up with the equivalent of a linked list.

Check out this MSDN article (6 parts) starting at part 3 with binary trees. There are several varieties of the basic BST.