Array

An array is a collection of items stored at contiguous memory locations.

• Usually starts at index 0
• Stores multiple items of same type together An array is a Pointer to the first element. $\to$ think back to C++

Types of Arrays

• Linear Array
• Dynamic Array
• Multi-dimensional arrays (2D arrays)

Time Complexity of Arrays

• Indexing: $O(1)$
• Search: $O(n)$
• Insertion: n/a
• Deletion: $O(n)$
• Optimized Search: $O(log(n))$

Array Initialization

Zero initialized array:

int arr[20]={};

Else, the values might contain some garbage values:

int arr[20];

Full story seems a little more complex... Static Variable (file scope and function static) are initialized to zero...

int x; // zero
int y = 0; // also zero
 
void foo() {
    static int x; // also zero
}

Non-static variables (local variables) are indeterminate.

Reading them prior to assigning a value results in undefined behaviour.

void foo() {
    int x;
    printf("%d", x); // the compiler is free to crash here
}

In the case of arrays of pointers, something similar happens. I ran into this while doing this LeetCode Trie question. Question: what is the difference between using Trie* next[26] = {} and Trie* next[26]?

Answer: The main difference between Trie* next[26] = {} and Trie* next[26] is in the initialization of the array.

• Trie* next[26] = {} initializes the next array to all NULL pointer
• Trie* next[26] declares an array of 26 pointers to Trie objects, but it does not initialize them to any particular value. This means that the pointers could contain garbage values, or could point to any location in memory

Initialize to a given value

Unless that value is 0 (in which case you can omit some part of the initializer and the corresponding elements will be initialized to 0), there’s no easy way.

Don’t overlook the obvious solution, though:

int myArray[10] = { 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 };

Elements with missing values will be initialized to 0:

int myArray[10] = { 1, 2 }; // initialize to 1,2,0,0,0...

So this will initialize all elements to 0:

int myArray[10] = { 0 }; // all elements 0