C# Traps and Traps – part 2

Theory vs practice.

One of the first conclusions from learning about memory, data structures and collections was that we should always choose the collection according to our usage. The next step was to learn about all the collections so we could make an informed decision while writing our code.

An array is a collection that takes uninterrupted space in memory – and thanks to that, if we know where the first element of an array is in the memory, we can compute where the n-th element is – we just have to add n multiplied by the size of the element to the first element address and as a result, we know the address of the n-th element. The problem with an array is that when we need to expand the array (add new elements) we have to find a new place in the memory that will fit the array (including new elements), copy the memory to the new address, change the pointer to the memory and then free the old memory. The details differ between implementations but it is generally a lot of work.

Linked list, on the other hand, is great if we don’t need to have fast access to the n-th element, but we would like to add a lot of elements to the collection. A linked list does not take uninterrupted memory block, but instead, every element of the collection has knowledge of where the next (and sometimes previous) element is. This way, knowing the first element, you can get the address to next one, from there the next one and so on. When you need to access an n-th element of the Linked List it is difficult, because we need to visit n elements to finally find n-th. But it is super easy to add new elements to this collection, the only thing we need to do is to modify the previous element of the collection so that it points to the new element and makes the new element point to next element of the array. No need to copy memory, we just change pointers. Neat.

Continue reading “C# Traps and Traps – part 2”