ZTutorial‐04 - james-bern/CS136 GitHub Wiki

⚠⚠⚠ TODO Rely less on Cow

,--------.               ,---.                                 ,--.   ,--.        ,--.   
'--.  .--',---.,--. ,--./  O  \ ,--.--.,--.--. ,--,--.,--. ,--.|  |   `--' ,---.,-'  '-. 
   |  |  | .-. |\  '  /|  .-.  ||  .--'|  .--'' ,-.  | \  '  / |  |   ,--.(  .-''-.  .-' 
   |  |  ' '-' ' \   ' |  | |  ||  |   |  |   \ '-'  |  \   '  |  '--.|  |.-'  `) |  |   
   `--'   `---'.-'  /  `--' `--'`--'   `--'    `--`--'.-'  /   `-----'`--'`----'  `--'   
               `---'                                  `---'

Writeup

Motivation

In programming, sometimes we want to store a bunch of things, but we don’t know how many things we’ll need to store ahead if time. Or, perhaps the number of things we need to store changes over time.

We need a (variable-size) list.

An array list is a fabulous, general-purpose way of implementing a list.

Let's implement our own array list in Java. 🙂👍

Brainstorm the Data Structure

First, we need to answer the question: “How will users interact with our data structure?” Said another way: “What public-facing methods and variables should our data structure have?”

This is a tough question!

We can answer it by writing usage code, code that uses the data structure we are going to write. Note: We write usage code before we start implementing a data structure, i.e., before we “code it up.”

I recommend writing this particular bit of usage code on a piece of paper or in a Sticky Notes app. This will make it easier for your to throw away. 🙂👍 As you write the usage code, remember to follow your heart. As Casey Muratori says, "[Imagine] how the [data structure] would work if it had no constraints on it whatsoever. If it was 'magical', as it were."

  • What methods do you wish you could call?
  • What do you wish those methods were named?
  • What arguments do you wish those methods took?
  • What order do you wish those arguments were in?

For reference, here is my brainstorming usage code:

CowArrayList arrayList = new CowArrayList();
arrayList.add("Hello");
arrayList.add("World");
arrayList.insert(1, "Cruel");
arrayList.add(arrayList.get(0)); // NOTE: in C++, i might prefer arrayList[0]
System.out.println(arrayList); // [ Hello, Cruel, World, Hello, ]
arrayList.removeElementAt(2);
System.out.println(arrayList); // [ Hello, Cruel, Hello, ]

My brainstorming code gives me the following todo list:

  • CowArrayList() { ... }
    • this constructor gets called automatically when we create a new instance of CowArrayList
  • public String toString() { ... }
    • the toString() method gets called automatically when we System.out.println an instance of CowArrayList
  • void add(String element) { ... }
  • void insert(int index, String element) { ... }
  • void removeElementAt(int index) { ... }

Implement the Data Structure

One thing at a time!

  1. Start with a class that is empty except for a public static void main(String[] args) { }.
  2. Decide what method you will implement and test next, but do NOT start coding it up yet.
  3. Add some code to the data structure’s main() that uses the method (this is called usage code). Consider including:
    • Print statements (System.out.println(...), Cow.printArray(...), etc.).
    • Comments saying what each print statement will print if your implementation of the method is correct.
  4. Actually code up the method. This code is called the implementaion.
  5. Build and run the data structure’s main(), and carefully make sure that:
    • The method works correctly.
    • You didn’t mess up any other methods while implementing it.
    • Note: You may not be able to test everything yet; just do the best you can and then return to step 1.

Walkthrough

After each step, I build and run my data structure’s main(). The compiler is (usually) your friend!

  • If I just wrote usage code -- the compiler will tell me what to implement next 🙂👍
  • If I just wrote implementation -- the compiler will tell me where my typos are 🙂👍

Go compiler go!

class CowArrayList { ... }

+ class CowArrayList {
+     public static void main(String[] args) {
+     }
+ }

CowArrayList() { ... }

class CowArrayList {
    public static void main(String[] args) {
+       CowArrayList arrayList = new CowArrayList();
+       System.out.println(arrayList.length); // 0
+       Cow.printArray(arrayList.internalArray); // [ null, null, null, null, ]
    }
}
class CowArrayList {
+   int length;
+   String[] internalArray;
+   CowArrayList() {
+       this.length = 0;
+       this.internalArray = new String[4];
+   }

    public static void main(String[] args) {
        CowArrayList arrayList = new CowArrayList();
        System.out.println(arrayList.length); // 0
        Cow.printArray(arrayList.internalArray); // [ null, null, null, null, ]
    }
}

public String toString() { ... }

String get(int index) { ... }

void add(String element) { ... }

void insert(int index, String element) { ... }

void removeElementAt(int index) { ... }

class CowArrayList {

    int length; // number of elements stored in array list
    String[] internalArray; // length of this internal array is array list's capacity

    CowArrayList() {
        this.length = 0;
        this.internalArray = new String[4];
    }

    public String toString() {
        String result = "< ";
        for (int i = 0; i < length; ++i) {
            result += this.get(i) + ", ";
        }
        result += ">";
        return result;
    }


    void add(String element) {
        if (this.length == this.internalArray.length) { // internal array is full
            String[] newInternalArray = new String[2 * this.internalArray.length];
            for (int i = 0; i < this.length; ++i) {
                newInternalArray[i] = this.internalArray[i];
            }
            this.internalArray = newInternalArray;
        }
        this.internalArray[this.length++] = element;
    }

    public static void main(String[] args) {
        CowArrayList arrayList = new CowArrayList();
        System.out.println(arrayList.length);    // 0    Cow.printArray(arrayList.internalArray); // [ null, null, null, null, ]

        // [ Bulbasaur, null, null, null, ]
        // [ Bulbasaur, Ivysaur, null, null, ]
        // [ Bulbasaur, Ivysaur, Venusaur, null, ]
        // [ Bulbasaur, Ivysaur, Venusaur, Charmander, ]
        // [ Bulbasaur, Ivysaur, Venusaur, Charmander, Charmeleon, null, null, null, ]
        // ...
        // [ Bulbasaur, ..., Blastoise, null, ..., null, ]
        for (int i = 0; i < 9; ++i) {
            arrayList.add(Cow.pokemon[i]);
            Cow.printArray(arrayList.internalArray);
        }

        System.out.println(arrayList.length);    // 9
    }

}

Part 2: CowArrayList<ElementType> 

* Make `CowArrayList` **generic**, _i.e.,_ able to store any type. E.g., we can instantiate a `CowArrayList<String>` for storing `String`'s, a `CowArrayList<Vector2>` for storing `Vector2`'s, and so on.

class CowArrayList<ElementType> {
    int length; // number of elements stored in array list
    ElementType[] internalArray; // capacity is length of this internal array

    @SuppressWarnings("unchecked")
    CowArrayList() {
        this.length = 0;
        // NOTE: Java doesn't allow new ElementType[this.capacity], so
        //       we use a workaround (make array of Object's and cast)
        this.array = (ElementType[]) new Object[this.capacity];
    }

    ...

    void add(ElementType element) { ... }

    ...
}

Home   Docs   Glow   HelpHours   LectureRecordings

⚠️ **GitHub.com Fallback** ⚠️