Arrays

• Definition: Contiguous area of memory consisting of equal-size elements indexed by contiguous sequence of integers
• Description:
  • Arrays - Coursera (video)
  • Dynamic Arrays - Coursera (video)
  • Jagged Arrays - Youtube (video)
  • Linear and Multi-Dim Arrays - UC Berkeley CS61B (video) (Start watching from 15m 32s)
• Implement a vector (mutable array with automatic resizing):
  • Practice coding using arrays and pointers, and pointer math to jump to an index instead of using indexing.
  • New raw data array with allocated memory
    • can allocate int array under the hood, just not use its features
    • start with 16, or if starting number is greater, use power of 2 - 16, 32, 64, 128
  • size() - number of items
  • capacity() - number of items it can hold
  • is_empty()
  • at(index) - returns item at given index, blows up if index out of bounds
  • push(item)
  • insert(index, item) - inserts item at index, shifts that index's value and trailing elements to the right
  • prepend(item) - can use insert above at index 0
  • pop() - remove from end, return value
  • delete(index) - delete item at index, shifting all trailing elements left
  • remove(item) - looks for value and removes index holding it (even if in multiple places)
  • find(item) - looks for value and returns first index with that value, -1 if not found
  • resize(new_capacity) // private function
    • when you reach capacity, resize to double the size
    • when popping an item, if size is 1/4 of capacity, resize to half
• Implement:
  • isPrime(int n) - Youtube (video) to understand cofactor relationships
  • Sieve of Eratosthenes - Youtube (video) to understand use of 1-D Arrays
  • Pascal's Triangle - UC Berkeley CS61B (video) (Start watching from 38m 30s) to learn Jagged Arrays
• Time
  • O(1) to add/remove at end (amortized for allocations for more space), index, or update
  • O(n) to insert/remove elsewhere
  • O(1) to access any element
• Space
  • contiguous in memory, so proximity helps performance
  • space needed = (array capacity, which is >= n) * size of item, but even if 2n, still O(n)
• Indexing
  • One Dimensional Array:
    element_addr = array_start_addr + element_size x (i - first_index)
  • Multi Dimensional Array:
    array_start_addr + element_size x [(row - first_row_index) x total_num_cols + (column - first_col_index)]
    where total_num_cols = max_col_index - min_col_index + 1
• Ordering
  • Row Major: last index changes most rapidly e.g (1,1) --> (1,2) --> (1,3)
  • Column Major: first index changes most rapidly e.g (1,1) --> (2,1) --> (3,1)