Arrays

Arrays 

Intro 

Array are the most fundamental data structure that can be used to store same type of data in a linear fashion. 

The data layout is not only linear in terms of traversal but contiguous in memory too. This being contiguous memory gives this data structure advantage since one can do pointer arithmetic to jump to any location on array in constant time. 

Usage 

• Store any type of data 
• Insert in O(1)
• Remove in O(1) 
• Access in O(1)

Pitfalls

• Cannot expand or decrease on fly. 

Note

• Since arrays are constant size, they are useful in situations where the size of data is already known at compile time.
• Values like alphabet size or constant range fit into this.

Array Implementation

• This simple implementation lets us create an array of any type T of constant size C.
• It provides access reference of T values so that we can read and update them as required.
• It also gives us option to print the whole array which is useful for demonstration purposes. 
• For every array each memory location is exactly size of type T and contiguous.
• It can be nested to form nested array structures. 
• Nested array structure should not be confused with a two dimensional arrays which can be created with int[4][5], this structure is very different in memory as compared to a nested array structure.
• The above point can be proved by printing the memory address of each element in nested structure
• Elements which belong to the same array are contiguous and size(T) distance.
• In the nested structure of nested_array the inner arrays i.e. the printed row memory address will be a constant of 4 bytes apart. since size(int) = 4; 
• The outer array in nested_array should have a each starting address of each row at a distance of sizeof(array<int,5>) distance apart i.e 24 bytes. However when I ran this it turns out that the outer array elements are 32 bytes distance apart and not 24 bytes. This is due to Memory Padding, read about it more here.
• In a two dimensional array only one malloc/new call is performed which gives a large chunk of memory = Sizeof(int) * 4 * 5 , the whole chunk is contiguous. 
• In a nested array structure there are multiple calls to malloc/new and therefore the total size of memory allocated remains the same but instead of one big chunk we get individual chunks of contiguous memory. 
• There was (prior to revision 11) a memory leak in the destructor call in nested structure, only the outer array is deleted not all elements inside the arrays.

 Next Steps

Now that we have a working array data structure, we shall move on in syllabus to solve the problems presented in the syllabus. If it is required to implement any algorithm then we shall first implement the algorithm and the follow on from there.