Lab 8: Dynamic Array with List

The DynamicArrayWithList Program

This week you will create a DynamicArrayWithList program. For your implementation you will need to keep track of not only pHead and pTail, but also pEnd, which will be the current logical end of the list the current size of the list. The "bucket size" for allocating new list nodes each time the list grows should be 3. You must also implement the ability to store a number at any "array" index position (which was extra for lab 4), where the underlying linked list grows to accommodate whatever index value is provided.

Running the program looks like what is shown below (index values and display of entire array added 10/9):

In the above example the list is initialized to have three nodes when the program starts. Notice how we can overwrite an existing array element (move 3 for an value 7 to be stored at index position 0). At move 5 the three existing nodes are all now full, so adding value 2 at index 3 means we have to allocate a new chunk of three more new nodes, where value 2 takes up the first of them.

Reading & "Reading Outline"

There is no external reading this week. Instead of an essay, this week you will draw a D-C-B-A diagram for your DynamicArrayWithList program, take a picture of it with a phone / camera / webcam, and upload the image. The image is what you will place on your shared slide as your starting point for your partner work in lab next week.

Confused on what exactly constitutes a test case? See this example (from Fall 2021 CS 141) on test cases used to design code for inserting in-order into a linked list.

Hints: Make sure your test cases handle:

1. The beginning of the program where there is a sentinel Node and 3 other Nodes

2. Replacing a value into a Node that has already been allocated

3. Overwriting an existing value in an existing Node, and

4. Adding a value to a location that is currently past the end of the array.

Submit your D-C-B-A diagram using this UNIQUE LAB 8 Reading Outline Submission Form, which is NOT the same one we've used other weeks.

Lab Activity

With your partner start with Lab 8 starter code in Replit that already has the Node declaration, has a function to display the list, and has a function to return a pointer to the nth Node on the list (assuming it is within the list size). You will need to implement the function addValueAt(...)

Run the provided test cases, which are basically the same as the sample input shown above.

Besides the usual listing of your partner names and your catchy title, and the importance, on your slides describe:

1. A summary of what you did / did not get working, referring to which test cases you passed

2. What you learned / discovered along the way as you wrote and debugged your code. In this section you should have specific brief snippets of code showing where the problems were and how you corrected them. Do not post entire functions, only the 1-2 lines illustrating each problem and how you solved it.