Data Structure

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

type array_name[length];
 
int a[5] = {10, -7, 3, 8, 42};

C++ Array

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

int arr[20] = {};

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

int arr[20];

The full story seems a little more complicated...

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 behavior.

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

SE212

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

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

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

Problems

• Maximum Subarray