In this project you will create a new and somewhat different integer List ADT, this time in C++. You will use this List to perform shuffling operations, and determine how many shuffles are necessary to bring a List back into its original order. Begin by carefully reviewing Queue and Stack examples posted on the webpage in Examples/C++. These examples have, which have been updated recently, establish conventions for building ADTs in the C++ language. The header file List.h has also been posted at Examples/pa7, along with a test client, some output files and a Makefile for this project.

                                       

The Perfect Shuffle

                                       

A perfect shuffle is one in which a deck of cards is split evenly, then merged into a new deck by alternately inserting cards from each half into the new deck. For instance, if our deck contains 7 cards, labeled 0-6, we would perform the following steps.

                                                                                                                                                       

Deck:
Split:
Prepare to Merge:

                                       

Merge:

                                                                                                       

0123456

                                       

012 | 3456

                                       

3456 012

                                       

3041526

                                                                                                                                                       

Performing the same perfect shuffle operation on the new list, we get: 1 3 5 0 2 4 6. Repeating the shuffle once again gives the original order: 0 1 2 3 4 5 6. We would say that the order of this method or re-arrangement is 3, since applying it to any deck 3 times returns the deck to its original order.

                                       

We will represent a deck of