Data Structures and Arrays

Solution

A data structure organizes a collection of related data so that certain operations on it are efficient. The three-part view: organization, operations, and trade-offs. Organization is how the data is laid out: an array stores its elements in a contiguous block of memory, in index order. Operations are what we are allowed to do with it: an array lets us read or write the element at any index. Trade-offs are what the organization makes fast and what it costs: an array gives fast access by index, but its size is fixed.

Solution

$100 + (3 \times 4) = 112$ . In general, the element at index i lives at start_address + (i × element_size). Access is one multiplication and one addition, then a direct jump to that address in RAM. There is no iterating through the elements. The cost is the same whether the array holds four elements or a million.

Solution

The size is fixed: once created, the array cannot change its size.
Insertion and deletion are costly: adding or removing an element in the middle forces shifting the elements after that position.
Memory can be wasted: slots we allocate but never use stay allocated.

Exercise

Write a static method resize that takes an int[] and a new size (assume newSize > 0) and returns a new array of that size holding the old array’s elements. It must work for both growing and shrinking; when it shrinks, copy only the elements that fit. State the cost of this operation.

public static int[] resize(int[] oldArray, int newSize) {
  // your code here
}

Solution

public static int[] resize(int[] oldArray, int newSize) {
  int[] newArray = new int[newSize];
  int elementsToCopy = Math.min(oldArray.length, newSize);
  for (int i = 0; i < elementsToCopy; i++) {
    newArray[i] = oldArray[i];
  }
  return newArray;
}

The cost is proportional to the number of elements copied: it allocates a new array and copies every element that fits.