Skip to content

Array Lists and Dynamic Arrays

Introduction

The AList implementation provided by our textbook uses a fixed-sized array as the underlying data structure. This is fine if we happen to know in advance the number of elements we need to store, but that isn't always the case. A dynamic array-based implementation would be more convenient for the user.

Dynamic arrays double the size of the underlying array whenever the original array reaches capacity: First a new empty array is created. Then all elements are copied to the new array. Then the new array replaces the existing array.

Your goal for this assignment is to modify the OpenDSA AList class so that it takes advantage of dynamic arrays. You will also explore the performance characteristics of your modified data structure.

Starting Code

The AList class provided here has been lightly modified to conform to the CS 240 style guidelines.

Part 1: Required Modifications

Dynamically Increasing Array Size

You will update the OpenDSA AList class so that the append and insert methods resize the array when necessary. The following pseudocode is sufficient for the append operation:

Dynamic Append
if the current array is full:
    * Allocate a new array that is twice as large as the current array.
    * Copy all entries from the current array to the new array.
    * Replace the current array with the newly allocated array.
    * Place the new item at the appropriate index.

We could follow the same approach for insert:

Dynamic Insertion (Slow)
if the current array is full:
    * Allocate a new array that is twice as large as the current array.
    * Copy all entries from the current array to the new array.
    * Replace the current array with the newly allocated array.
    * Place the new item at the appropriate index in the new array, 
      after first shifting subsequent elements to the right.

This approach is simple, but inefficient. It unnecessarily moves elements after the insertion point twice: first to copy them into the new array, then to shift them over to make room for the inserted item. A better approach is to copy elements into the correct location during the initial copy:

Dynamic Insertion (Efficient)
if the current array is full:
    * Allocate a new array that is twice as large as the current array.
    * Copy all entries from the current array to their appropriate locations in the new array.
    * Replace the current array with the newly allocated array.
    * Place the new item at the appropriate index in the new array (no shifting necessary!)

For example, the following diagram illustrates the copy operations that would occur if we were to insert "Z" at index 2 in a length-four array:

Resize for Insertion

Note that Dynamic Insertion (Efficient) will work perfectly well for the append operation as well. If you implement it correctly, you should be able get away with a single increaseArray helper method.

Your modified append and insert methods must always return true,

Dynamically Decreasing Array Size

The resizing operation described above provides an efficient mechanism for ensuring that the AList always has adequate capacity. However without a corresponding mechanism for shrinking the array the AList might end up tying up a huge amount of unneeded memory. Imagine adding 1,000,000 items, then immediately removing them.

The obvious solution for this problem is to monitor the percentage of the array that is currently being used, and to resize the array if the value falls below some threshold.

Modify the remove method so that it shrinks the array by a factor of 2 whenever the number of used entries falls below 25%. As with insert, your remove method should avoid unnecessary shift operations when a resize occurs. For example, the following diagram illustrates a removal at index 1 that prompts an array resize:

Resize for Removal

Your resize operation should never decrease the array size below one.

Instrumentation for Analysis

In order to facilitate analysis of your updated class, add a public getAssignmentCount() method that will return the total number of array assignments performed within the AList since it was constructed. This will require to you find all assignment operations in your implementation and makes sure that each one is accounted for in the total. The following code snippet illustrates the expected behavior:

AList<String> numbers = new AList<>(4);
numbers.append("A");
numbers.append("B");
numbers.append("C");
numbers.append("D");
System.out.println(numbers.getAssignmentCount()); // Should print 4
numbers.moveToPos(2);
numbers.insert("Z"); // Results in a resize
System.out.println(numbers.getAssignmentCount()); // Should print 9

Part 2: Analysis

Use the following driver to generate a dataset illustrating the total and average array assignments across 10,000 append operations.

CountDriver.java
/**
 * Driver program to analyze both total and average array assignments during append
 * operations in the AList dynamic array implementation.
 *
 * @author CS 240 Instructors
 * @version V1.0, 9/7/2025
 */
public class CountDriver {

  /**
   * Main method that performs a specified number of append operations on an AList
   * and outputs both the total number of array assignments and the average
   * assignments per append after each append. <p>
   * The output format is CSV-compatible with three columns:
   * number of appends performed, total assignments performed, and average assignments per append.
   *
   * @param args Command line arguments - expects exactly one argument:
   *             the number of append operations to perform
   */
  public static void main(String[] args) {
    if (args.length != 1) {
      System.err.println("Usage: java CountDriver <number_of_appends>");
      System.exit(1);
    }

    int numAppends = Integer.parseInt(args[0]);

    AList<Integer> numbers = new AList<>();

    System.out.println("Num Appends, Total Assignments, Average Assignments per Append");
    for (int i = 1; i <= numAppends; i++) {
      numbers.append(i);
      int totalAssignments = numbers.getAssignmentCount();
      double average = (double) totalAssignments / i;
      System.out.println(i + ", " + totalAssignments + ", " + String.format("%.4f", average));
    }

  }

}

Use a spreadsheet application or online graphing tool to produce two line charts from this data. The first chart should plot the number of appends on the x-axis against the total number of array assignments on the y-axis. The second chart should plot the number of appends on the x-axis against the average number of array assignments on the y-axis. Make sure that both graphs have clearly labeled axes. Once you have produced these graphs, you will upload them through Gradescope along with answers to the associated analysis questions.

Submission and Grading

The project will be graded as follows:

Gradescope Functionality Tests for Part 170%
Gradescope Style Checks for Part 110%
Graphs and Analysis for Part 220%