Dynamic Arrays

Outline

Static Array Limitations

• Array capacity is fixed
• Allocating too much memory is wasteful
• Allocating too little memory makes array too limited

Dynamic Arrays

Whats the solution?

• Dynamic arrays allow array sto be resized
• Memory allocated only on as needed basis / just-in-time
• Allocation is checked whenever an insert, append or delete operations occurs

Dynamic Array Resizing Algorithm

1. Check if array is at capacity
2. If at capacity
   • Allocate a new array with additional space
   • Copy elements form existing to new array
   • set a reference to the new array

Strategies for proportional size allocation

• Additional space is allocated as amortized
  • Expensive operations (allocating, copying) are performed in advance
• Compromise between space and copying
• Proportional size allocation
  • Allocate new array with double the capacity of the array
  • Example
    • Allocate array with capacity of 5 i.e
    • Append value "A" to array i.e
      • Check if count is greater than capacity i.e
      • False, so set
  • Example
    • Array with state i.e
    • Append value "F" to Array i.e
    • Check if count is greater than capacity i.e
    • True, so allocate new array with double the capacity i.e
    • Copy contents of array to new array i.e
    • Reference the new array and append "F" to the array i.e
    • Increment count i.e

Array shrinking

If deleting occurs more frequently, array can be shrunk

• When count is 1/4 of the array capacity
  1. Allocate pace to 1/2 of current capacity
  2. Copy existing items to new array
  3. Refer to the new array

Operations Complexity

Array operations complexity

Topics

• Big O notation
• Arrays
• Linear Search