Lab 4: Implementing Dynamic Arrays

--- tags: labs, spr22 --- # Lab 4: Implementing Dynamic Arrays :::info The lab schedule for this week has been disrupted by the long weekend. As a result, you can either attend an in-person lab or work on your own time for this week. There are three options for lab: - spend time finishing up your HW2 work - implement array-resizing as we did in class for yourself - (advanced) implement the "wrap-around" array indices as we showed at the end of Friday's class (where the start and end references can be anywhere in the array). Note that the TAs will offer only limited help with this, as they focused their preparation time on the first two options. For exams, we expect you to understand the idea of how array resizing works. You will never be tested on the wrap-around arrays (that option is just for those who would find it fun to try). ::: ## Learning Goals * understand how dynamic arrays work under the hood by implementing one * understand amortization and its relation to runtime analysis ## Setup If you are implementing the basic array-resizing, start from this code bundle. If you are implementing the wrap-around arrays, start from this code bundle. :::warning **TODO:** add a GitHub link ::: ## Dynamic Arrays (For Both Options) [Dynamic arrays go on and on and onnn yeahhh!](https://youtu.be/Vysgv7qVYTo?t=68) As you've learned in class, a dynamic array is a data structure that behaves like a list in that it can grow and shrink in size, but also retains the performance of an array for access, insertion, and deletion. **Task:** Before you implement any methods, edit `DynamicArrayTest.java` to include interaction tests for `get`, `addLast`, `removeLast`, `size`. As a reminder, such tests call one of these functions, then use another (one or more) of these functions to help check the result. ## Option 2: Problems for Basic Array Resizing Your code bundle starts from the basic `DynamicArray` (aka `ArrList`) class from Wednesday's lecture. You will re-develop the code from Friday's lecture. Yes, you can see the resulting code. The goal here is for you to try to develop it yourself, using the posted code to help you check your work. **Task:** Set up a test in which you try to add more elements than the array has capacity. Note what response you get from Java. **Task:** Modify `addLast` to grow the size of the array if it is out of space. Be sure to run your interaction tests to make sure they work. **Task:** Write an `addFirst` method on the `DynamicArray`. **Task:** What sorts of situations do you think you should test regarding `addFirst`? Think about what the special cases might be. Think about what might go wrong. **Task:** If you still have time, intentionally break either your `addFirst` or `addLast` (a good way to do this is to put the new element in the wrong spot, or to remove the code that updates the `end` reference). Now, think about how to use a combination of tests and the debugger to locate the problem (the point here is to practice with debugging, not to fix the code). ## Option 3: Instructions for Wrap-Around Arrays Your task is to make `addFirst` (which we haven't yet written) as efficient as `addLast` by introducting a `start` field ------------------ ## Program Overview In the `sol` package you will find two files: `DynamicArray.java` and `DynamicArrayTest.java`. `DynamicArray` is a class that implements the list interface, `IList`, provided in the `src` package. Your job is to create a dynamic array of `String`s by implementing the required methods in `DynamicArray`, using an array backing rather than the linked list structure you have dealt with previously. Then you will write tests for these methods in `DynamicArrayTest`. You will also analyze the runtime both theoretically and empirically of the operations you implemented. ## Dynamic Array [Dynamic arrays go on and on and onnn yeahhh!](https://youtu.be/Vysgv7qVYTo?t=68) As you've learned in class, a dynamic array is a data structure that behaves like a list in that it can grow and shrink in size, but also retains the performance of an array for access, insertion, and deletion. **Task:** Write tests for `get`, `addLast`, `removeLast`, `size`. Try to brainstorm some edge cases with your partner! **Task:** In the `DynamicArray` constructor, initialize the fields `contents`, `capacity`, and `currentSize` to their appropriate states based on the constructor parameters. **Task:** Implement `get` and `size`. `get` should throw an an `IndexOutOfBoundsException` if the index provided is out of bounds. Size should return the number of elements currently in the array. **Task:** Implement `addLast`. In this method, you will need to grow the underlying array by a factor of two once it fills up and copy the contents of the old array into the new one. For example, if your array has a capacity of 4 and you try and add a 5th element the array should expand to capacity 8. It will retain the original four elements plus the one you just added for a total of 5 elements and 3 remaining empty spots. :::success **Checkpoint:** call a Lab TA over to show your addLast method and make sure its working!! ::: **Task:** Implement `removeLast`. Do not yet implement shrinking. Now that your array has basic functionality and can grow, you should now implement shrinking. * The array should halve its capacity when the array is a quarter full. For example, if your array has a capacity of 17, it should shrink to capacity 8 when there are only 4 elements left (i.e. right after the 5th element is removed). * Finally, if your array has a capacity of 3 or below, it should not shrink anymore. That being said, it CAN shrink to a size below 3, but cannot shrink after that. Example: In the following array with capacity 8 ``[5 4 3 _ _ _ _ _]`` if we were to `removeLast`, the resulting array would be``[5 4 _ _]`` with capacity 4. **Task:** Augment `removeLast` to handle shrinking. **Task:** Analyze the runtime of your `addLast` by counting the number of operations. Is it linear? Constant? **Task:** Run the `testAddLastRuntime` test a couple of times in `DynamicArrayTest`, increasing the number of iterations to add more elements to the list, and see how the length of the list affects the runtime of `addLast`. When running the test with JUnit you can see the actual amount of time that it takes. :::success **Checkpoint:** call a Lab TA over to show your removeLast method and discuss your runtime analysis. Great job finishing up! ::: ______________________________ *Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CSCI0200 document by filling out the [anonymous feedback form](https://docs.google.com/forms/d/e/1FAIpQLSdFzM6mpDD_1tj-vS0SMYAohPAtBZ-oZZH0-TbMKv-_Bw5HeA/viewform?usp=sf_link).*