[20 points] To emphasize that the linked list is not the only way to implement the List ADT, implement an ArrayList class with the same functions as the LinkedList class above. However, this time you must use an array to store the Items, instead of a linked list.

To use an array for storage, you must dynamically allocate the array, because the maximum size is not known when the list is created. Start with an array size of 3. If more than three Items are added, you must allocate a new, larger array and copy the existing Items into that array. (Just increase the size by 3, or whatever.) We're using a small incremental size so that it will be easy to demonstrate this functionality in the main function.

Your LinkedList class must include the following:

• [1 pts] Public default constructor that creates an empty list.

• [2 pts] Public copy constructor that creates a copy of the list.

• [2 pts] Public destructor that deletes all the nodes of the list.

• [3 pts each] Public methods:

  • int length() -- returns the number items in the list (int)

  • void append(const Item&) -- adds a copy of the Item to the end of the list (no return value)

  • bool remove(Item&) -- removes the first item of the list and stores it into the reference passed in; returns true if item is removed, false if list was empty

  • bool empty() -- returns true if list is empty, false if not

  • bool insert(const Item&, int) -- adds a copy of the Item to the list at the specified position; returns true if successfully added, false if list was too small (e.g., insert at position 5, but the list only has 2 items)

Some implementation hints:

• Devise a way to keep track of how many valid Items are in the array. In other words, if the array size is 3, but there are only two Items in the list, how can you tell? (There is no "special" key/value to denote an empty Item.)

• The size grows whenever too many Items are added, but does the size of the array ever shrink? Should it?

• The head of the list does not need to be stored at index 0, and the tail does not need to be stored at index length-1. When you remove the head, you don't HAVE to move the array elements around. (But you can, if you want to.)

• Try to make your code efficient. Think about when you should or should not move array elements around, or when you should or should not increase the size of the array. Your grade won't depend on efficiency, but it's good to be thinking about these issues.

ArrayList.cpp: