# Array

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

- Stores multiple items of the same type together
- Based on tuples from Set Theory
- Makes it easy to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array
- The base value is index 0 and the difference between the two indexes is the offset

An Array is just a Pointer to the first element!!

### What you need to know

- Optimal for indexing; bad at searching, inserting, and deleting (except last element).

Types of Arrays

**Linear arrays**/ 1D arrays are declared with a fixed size (static size)- Dynamic Array have reserved space for additional elements.
- If a dynamic array is full, it copies its contents to a larger array.

**Multi-dimensional arrays**/ nested arrays allow for multiple dimensions (ex: 2D spacial representation via x, y coordinates)

#### Time Complexity of Arrays#card

- Indexing:
`O(1)`

- Search:
`O(n)`

- Insertion: n/a
- Deletion:
`O(n)`

- Optimized Search:
`O(log n)`

### Linear Array

#### Declaration

### Array Initialization

I probably learned this in CS138 but forgot most of it.

If you want to make sure that your arrays are zero initialized, do

Else, the values might be some garbage values if you just do

The full story seems a little more complicated...

Static Variable (file scope and function static) are initialized to zero.

Non-static variables (local variables) are indeterminate.

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

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:

Elements with missing values will be initialized to 0:

So this will initialize all elements to 0:

### SE212

This is an interesting perspective to think about arrays as Functions:

- An array $B$ is a function mapping indices to values. $Indices={i•i:nat∣0leqi<arraysize}$ $B:Indices→Value$

This function is a Total Function because it has a value for every index value (even if not initialized).