In class, you have seen how stacks of integers can be implemented using either arrays or linked lists. The same is true of sequences of integers. In assignment #5, you implemented a sequence of integers using arrays. This time around, you are to do the same thing using linked lists.

From the point of view of somebody using your class, the change in the implementation should be entirely invisible. Your assignment #6 solution should be completely “plug compatible” with your assignment #5 solution. Exactly the same test program and sample executable can be used.

Now that you know all about merging, both “intersect” and “unionWith” are to be done properly. If you aren’t sure how to efficiently implement the intersection operation, see the posted solution to assignment #5. It is suggested (but not required) that you use a linked list with a tail pointer and that you have a private member method (“addAtEnd”) that adds a new value to the end of a sequence. This method can, of course, only be used when we are sure that a new value belongs at the end of a sequence. This is, however, always the case in “intersect” and “unionWith”.

You may also find it useful to have “copyFrom” and “deleteList” private member methods. “copyFrom” should leave an object containing a copy of the linked list in another object, and “deleteList” should delete an object’s linked list. In the model solution, “deleteList” is used three times, once in the destructor and twice elsewhere. You will find that “copyFrom” and “deleteList” can be pretty well lifted from the chapter 11 notes.

Be sure to give some thought to what kind of variable “walkPosition” should be. Remember that the purpose of this variable is to keep track of how far a walk has progressed, and that we want to be able to go directly to the position of interest.

Submit files “IntSequence.h” and “IntSequence.cpp”. Your solution must use linked lists. As mentioned above a singly-linked list with tail pointer is recommended, but the type of linked list is your choice.

Updated: Tuesday, February 10th, 2009.