LinkedList memory consumption compared to a list when working with large arrays

Question

Can someone tell me if the linked list of structures can increase the size of the equivalent list (given that the list uses a doubling strategy to increase the size of the internal array).

So, a structure is given that says 40 bytes (I know about 16 bytes and the structure, but I'm working with some old code here, and this will not be a simple option, changing the structure for the class). consists in the fact that each time the internal array of the list is changed, the memory must be allocated for the new array (new_array_size * 40). Thus, with a very large array, you end up with an outofmemoryexception, since there is no contiguous space large enough to create this new array. I know that a linked list requires more space for each element (node), since it needs to hold back and forth pointers for the elements in the list, but my question is whether this means that to add an additional element you only need continuous memory slot (40 + the_space_needed_for_the_pointers). In other words, the linked list will not suffer from the need to allocate a huge new section of continuous memory for expansion.

Answer 1

Yes, that's for sure. LinkedList does not use an array for storage, it is really a chain of links. You will not get garbage in a bunch of large objects if you need to store a large number of elements, unlike List, and avoid problems with fragmentation of the address space that ends your program early.

Beware that it is not a replacement for List; indexing is O (n) instead of O (1). A big difference if you do not always repeat the list sequentially. When you need to make such piercing options, it's time to start looking at the 64-bit operating system.

Answer 2

Since the linked list only refers to the forward and backward links, you are not tied to continuous memory allocation. Reply @Hans has excellent points; however, I do not agree that 64-bit OS is the only option for high-performance indexing.

Are you limited to these two options?

If you have a large number of structures for reference, can you consider a binary tree? The surface of using a tree is that indexing is part of a linked list - O (log n). The disadvantage is the extra work of maintaining a balanced tree. Balancing is mandatory - without balance, you will receive the equivalent of a linked list.

Check out this MSDN article (6 parts) starting in Part 3 with binary trees. There are several varieties of base BST.