CS 2420-20 Homework 6

Due: Tuesday, February 7th, 2012 9:10am

Start with circular.c (parts 1 and 2) and linkedlist.c (part 3) from array.zip.

Part 1 – Shrinking an Array

Suppose that you create an array container, add 1000 items to it, remove 999 items, and then spend the next three days adding and removing one number at a time. The array size will stay at 1024, so the array is wasting a lot of space—in principle, at least.

Adjust remove_from_front and remove_from_end so that they shrink the array when the count becomes less than 1/4 the size of the array, but never shrink the array to a size less than 1.

(Why shrink at 1/4 capacity instead of, say, 1/2 capacity?)

Part 2 – Inserting into the Middle

Add an add_to_middle function that takes an array container and an integer and adds the integer in the middle of all existing items. If the array container has an odd number of items, add the new item before the current middle item.

What is the complexity of inserting N items, one at a time to the middle of the array?

Part 3 – Challenge: Inserting into the Middle of a Linked List

In linkedlist.c, add an add_to_middle function that takes a list container and an integer and adds the integer in the middle of all existing items in constant time.

You can arrange for each insertion to take constant time by having a container keep track of the middle of its list (as well as the start and end). Be sure to adjust the “middle” pointer when adding or removing at the start or end of the list, too. The list container’s count (and whether the count is even or odd) helps in properly maintaining the “middle” pointer. Carefully consider (and test!) the case of a list having zero or one elements.