Problems

Implement an array list from scratch.

import java.util.*;

class Tut04ArrayList {  

    private String[] privateArray; 
    private int numberOfElementsActuallyStoredInPrivateArray; // NOTE: Feel free to rename.

    public int size() {
        return numberOfElementsActuallyStoredInPrivateArray;
    };


    Tut04ArrayList() {
        // TODO: construct new array list with starting capacity of 1
    }

    String get(int index) {
        // TODO: get element at given index
        return null;
    }

    void add(String element) {
        // TODO: append element to the back of the list

    }

    void add(int index, String element) {
        // TODO: insert element so it has given index in the list
    } 

    void remove(int index) {
        // TODO: remove element at given index
    }


    // special function called automatically by System.out.println
    // NOTE: unlike the toString() function in Java's ArrayList<ElementType>,
    //       this function prints the empty slots (null's)
    //       so you can see what's happening under the hood
    public String toString() {
        return Arrays.toString(privateArray);
    }

    public static void main(String[] arguments) {
        Tut04ArrayList list = new Tut04ArrayList();
        System.out.println(list); // [null]
        list.add("Hello");
        System.out.println(list); // [Hello]
        list.add("World");
        System.out.println(list); // [Hello, World]
        list.add(1, "Cruel");
        System.out.println(list); // [Hello, Cruel, World, null]
        list.remove(0);
        System.out.println(list.size()); // 2
        System.out.println(list); // [Cruel, World, null, null]
                                  // NOTE: [Cruel, World, World, null] also okay if size() was 2
    }
} 

Use your array list.

Give your array list a new function called void repeatElements(int numRepeats); If list currently contains elements ["Blango", "Sproot", "Sparket"], calling list.repeatElements(3) should cause it to contain ["Blango", "Blango", "Blango", "Sproot", "Sproot", "Sproot", "Sparket", "Sparket", "Sparket"].

Try to solve this problem using only get(...), size(...) and add(...) from the previous part.

Solutions

import java.util.*;

class Tut04ArrayList {  
    private String[] privateArray; 
    private int numberOfElementsActuallyStoredInPrivateArray; // NOTE: Feel free to rename.

    public int size() {
        return numberOfElementsActuallyStoredInPrivateArray;
    };


    Tut04ArrayList() {
        privateArray = new String[1];

        // NOTE: This line is technically optional because objects are automatically zero-initialized in Java.
        numberOfElementsActuallyStoredInPrivateArray = 0;
    }

    String get(int index) {
        return privateArray[index];
    }

    void add(String element) {
        add(numberOfElementsActuallyStoredInPrivateArray, element);
    }

    void add(int index, String element) {
        if (numberOfElementsActuallyStoredInPrivateArray == privateArray.length) {
            String[] newPrivateArray = new String[2 * privateArray.length];
            for (int i = 0; i < privateArray.length; ++i) {
                newPrivateArray[i] = privateArray[i];
            }
            privateArray = newPrivateArray;
        }
        for (int i = numberOfElementsActuallyStoredInPrivateArray - 1; i >= index; --i) {
            privateArray[i + 1] = privateArray[i];
        }
        privateArray[index] = element;
        numberOfElementsActuallyStoredInPrivateArray++;
    } 

    void remove(int index) {
        for (int i = index; i < numberOfElementsActuallyStoredInPrivateArray - 1; ++i) {
            privateArray[i] = privateArray[i + 1];
        }
        --numberOfElementsActuallyStoredInPrivateArray;

        // NOTE: This line is optional; sets the newly-empty slot to null
        privateArray[numberOfElementsActuallyStoredInPrivateArray] = null;
    }

    void repeatElements(int numRepeats) {
        // NOTE: This is NOT a good algorithm for solving this problem (though it does work correctly).
        // We will discuss in class :)
        // FORNOW: Think about what it actually does under the 
        int numBefore = size();
        for (int i = 0; i < numBefore; ++i) {
            for (int repetition = 0; repetition < (numRepeats - 1); ++repetition) {
                int index = i * numRepeats;
                add(index, get(index));
            }
        }
    }

    // special function called automatically by System.out.println
    // prints the empty slots (null's) so you can see what's actually happening
    public String toString() {
        return Arrays.toString(privateArray);
    }

    public static void main(String[] arguments) {
        {
            Tut04ArrayList list = new Tut04ArrayList();
            System.out.println(list); // [null]
            list.add("Hello");
            System.out.println(list); // [Hello]
            list.add("World");
            System.out.println(list); // [Hello, World]
            list.add(1, "Cruel");
            System.out.println(list); // [Hello, Cruel, World, null]
            list.remove(0);
            System.out.println(list.size()); // 2
            System.out.println(list); // [Cruel, World, null, null]
                                      // NOTE: [Cruel, World, World, null] also okay if size() was 2
        }
        {
            Tut04 list = new Tut04();
            list.add("Blango");
            list.add("Sproot");
            list.add("Sparket");
            System.out.println(list);
            list.repeatElements(3);
            System.out.println(list);
        }
    }
}