CSC161 Homework 1: Lists

Contents

Overview

We've made an interface for the List ADT and started to implement a Vector class. For this homework, you are going to finish implementing it and then then demonstrate it. We have already done some of this in class. Try to understand the code involved in the implementation from the ADT page—ask me or a classmate questions if you cannot work through something! Don't forget the destructor.

Requirements

• finish implementing Vector
• in main, create a list of ints
• in main, demonstrate that each of the methods works
• make sure to follow the style guidelines

Extra credit

Extra credit will max out at 5 points.

EC-1 (3 points)

Make it templated.

EC-3 (3 points)

Make Vector a little smarter...Right now, every time we add to a Vector, the entire array gets copied to a new segment of memory with one new spot. Change it so that the Vector implementation makes the Vector bigger than necessary (hint: using a data member called capacity), and only move it to new memory if listSize reaches capacity. One rule of thumb is to double capacity every time the array fills its alloted size. For long lists, this could cause some issues, since potentially twice as much memory needs to be claimed—if that amount of contiguous memory doesn't exist, then your program won't be able to allocate it!

EC-4 (5 points)

Add an apply method to the List ADT that takes a function pointer, and implement this function in Vector. The function pointer should point to a function that takes an element of the array and returns nothing. The apply method should invoke this function once on each item in the list.

Submissions

Everything should be uploaded to Canvas by the deadline posted.