Table of Contents

Static Array

A static array is like a box that you can store things in, or take things out of. It can only fit a certain number of things, before getting full. You can’t make the box bigger or smaller.

A static array is a data structure with a fixed size, where objects or data types can be stored.

Static Array

• Memory
  • The array takes up a contiguous block of memory (continuous, no holes)
  • Each element of the array points to an address in memory
  • You can have empty slots in an array, reserved in memory but not pointing to anything.
• Indexing
  • Each index points to an element of the array.
  • Most programming languages start at 0.
    • Math and Functional languages start at 1 (MATLAB, Fortran, …).
• Usage
  • Dynamic programming: Used to cache the solutions of subproblems for quick re-access, in problems like Knapsack.
• Operations
  • Access an element: Get the value at a specific index of the array.
  • Search for an element: Run through the array searching for a specific value, until you find it.

Dynamic Array

Imagine a resizable box. You can put as many things as you want into it, and it’ll become as big as it needs to, to hold it all. If you take stuff out, it will shrink too. That’s a dynamic array.

A dynamic array is an array with dynamic size. In addition to indexing an item or searching for a specific item, you can also add or remove items to the array, and its size will adjust accordingly. If you add an extra item, the array size will expand to hold the item and more (there will be empty slots).

Dynamic Array

• Operations: Dynamic arrays have the same operations as arrays, as well as additional ones.
  • Insertion: Add an item to the array.
  • Append: Add an item to the very end of an array
  • Remove: Remove an item from the array and create a new array to hold it all.

Implementation

• Dynamic arrays work by checking if an array is full before an insertion. If it’s already full:
  • A new array is created, usually of double size. This would require O(2N) iteration.
  • All the elements are copied over to the new array. This is O(N).
  • The new element is inserted to the new array. This is O(1)
• In Java, the ArrayList collection provides the functionality of a dynamic array.
  • It doubles in size when necessary.