Simple List Class

Having implemented our linked List functions, we are now ready to design and implement a simple Linked List class:

List Class:

template <class ITEM_TYPE>
class List
{
public:
    List();

    ~List();
    List(const List<ITEM_TYPE> &copyThis);
    List& operator =(const List& RHS);

    node<ITEM_TYPE>* insert_head(ITEM_TYPE i);           //inset i at the head of list

    node<ITEM_TYPE>* insert_after(ITEM_TYPE i,           //insert i after iMarker
                                 node<ITEM_TYPE>* iMarker);

    node<ITEM_TYPE>* insert_before(ITEM_TYPE i,          //insert i before iMarker
                                  node<ITEM_TYPE>* iMarker);

    node<ITEM_TYPE>* insert_sorted(ITEM_TYPE i);         //insert i. Assume sorted list



    ITEM_TYPE Delete(node<ITEM_TYPE>* iMarker);         //delete node pointed to by iMarker


    void Print() const;                                 //print the list

    node<ITEM_TYPE>* search(const ITEM_TYPE &key);      //return pointer to node containing
                                                        //  key. NULL if not there

    node<ITEM_TYPE>* prev(node<ITEM_TYPE>* iMarker);    //get the previous node to iMarker


    ITEM_TYPE& operator[](int index);                   //return the item at index

    node<ITEM_TYPE>* begin() const;                     //return the head of the list

    node<ITEM_TYPE>* end() const;                       
                                                        
    bool empty() const { return head == nullptr; }      
    
    int size() const{ return _size; }
    template <class U>
    friend ostream& operator <<(ostream& outs,          //insertion operator for list
                                const List<U>& l);
private:
    node<ITEM_TYPE>* head;
    int _size;
};

Testing:

An Interactive Test Application

You will create an interactive application that will create a list with five random numbers, show it, and present the following menu to the user:

{6}->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd 

The user will be able to add a random number after the current position (marked by braces), insert a number before or after the current position, delete the node at the current position, search for an item that may be in the list, or navigate the current position to the next or previous node, or to go to the home position, or the end of the list.

Note: The cursor position is maintained in the test function and NOT in the List class. The posiiton of the cursor is shown by a pair of braces '{ }' and it will be adjusted appropriately as operations are executed. Deleting a node will cause the cursor position to be set to the beginning of the list. (Why is that?)

Note: Can you see the problem with this class? How vulnerable is this class to outside intrusion? How serious is this problem?

Sample Run:

Look for 

/*
 * [C]omments like this: (these are added after the program was run)
 */

for explanations on activities in the sample run:

=======================================
/*
 * Initial list and menu. Cursor is at the head:
 */
{6}->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd n

/*
 * [N]ext: once you get to the end of the list, the cursor will stay there.
 * 		It will not fall off
 */
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->{54}->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd n

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->[54]->{6}->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd n

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->[54]->[6]->{35}->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd n

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->[54]->[6]->[35]->{17}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd n

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->[54]->[6]->[35]->{17}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd n

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->[54]->[6]->[35]->{17}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd n]n

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->[54]->[6]->[35]->{17}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd 
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
??
[6]->[54]->[6]->[35]->{17}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd 
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->[54]->[6]->[35]->{17}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd n

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->[54]->[6]->[35]->{17}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd p

/*
 * [P]revious: once you get to the begining of the list, 
 * 		the cursor will stay there.
 *      It will not fall off
 */
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->[54]->[6]->{35}->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd p

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->[54]->{6}->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd p

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->{54}->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd p

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
{6}->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd p

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
{6}->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd p

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
{6}->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd p

/*
 * [R]andom: inserts a random item after the current position.
 */
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
{6}->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd r

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->{90}->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd r

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->[90]->{80}->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd r

/*
 * [A]fter: inserts an item after the current position
 */

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->[90]->[80]->{71}->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd a

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
: 77
[6]->[90]->[80]->[71]->{77}->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd n

/*
 * [B]efore: inserts an item before the current position
 */
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[6]->[90]->[80]->[71]->[77]->{54}->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd b

/*
 * [D]elete: deletes the item at the current position and resets position of cursor
 *		NOTE: deleting on an empty list does not cause a crash.
 */
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
: 55
[6]->[90]->[80]->[71]->[77]->{55}->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
{6}->[90]->[80]->[71]->[77]->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
{90}->[80]->[71]->[77]->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
{80}->[71]->[77]->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
{71}->[77]->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
{77}->[54]->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
{54}->[6]->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
{6}->[35]->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
{35}->[17]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
{17}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

/*
 * [D]elete: on an empty list does not cause a crash
 */
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

/*
 * [R]andom: on an empty list will add a random number at the head of the list
 */
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd r

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
{99}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

/*
 * [A]fter: on an empty list will add a number at the head of the list
 */
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd a

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
: 44
{44}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd d

/*
 * [B]efore: on an empty list will add a number at the head of the list
 */
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd b

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
: 33
{33}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd r  

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[33]->{99}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd r

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[33]->[99]->{13}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd r

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[33]->[99]->[13]->{16}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd r

/*
 * [H]ome and [E]nd take the current position to the begining 
 *		and the end of the list
 */
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[33]->[99]->[13]->[16]->{40}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd h

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
{33}->[99]->[13]->[16]->[40]->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd e

/*
 * e[x]it: will exit the proogram
 */
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[33]->[99]->[13]->[16]->{40}->|||
[R]andom [A]fter  [B]efore [D]elete  [P] Previous  [N] Next  [H]ome  [E]nd x

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
---------- END ----------------

Please Note: 

The above test did not have the search function in the menu. So, here it is: 

/*
 * [S]earch will move the cursor to the position of the key if it is found. No change 
 *         in cursor position if key is not found in the list.
 */
[R]andom [A]fter  [B]efore [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd s 99

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
: [33]->{99}->[13]->[16]->[40]->|||
[R]andom [A]fter  [B]efore [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd s16

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
: [33]->[99]->[13]->{16}->[40]->|||
[R]andom [A]fter  [B]efore [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd s33

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
: {33}->[99]->[13]->[16]->[40]->|||
[R]andom [A]fter  [B]efore [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd s-42

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
: {33}->[99]->[13]->[16]->[40]->|||
[R]andom [A]fter [B]efore [D]elete [S]earch [P] Previous [N] Next [H]ome [E]nd