(Implementation of intList class using linked list)

A container class is a data type that is capable of holding a collection of items. In C++, container classes can be implemented as a class, along with member functions to add, remove, and examine items. This lab introduces concept of a List.

A intList of elements of type integer is a finite sequence of elements of integer together with the following operations:

Construct the list, leaving it empty.

Determine whether the list is empty or not.

Determine whether the list is full or not.

Find the size of the list.

Clear the list to make it empty.

Insert an entry at a specified position of the list.

Remove an entry from a specified position in the list.

Retrieve the entry from a specified position in the list.

Append

insertToFront

Merge two lists

Intersection of two lists

Declaration of intList class:

class intList{

private:

Node *next;

int sz; //To keep track of how many items are in the list

public:

intList(); //The intList has been created and is initialized to be empty.

void clear();// All intList entries have been removed; the List is empty.

bool isEmpty() const; // The function returns true or false according to whether the List is empty or not.

bool isFull() const; //The function returns true or false according to whether the List is full or not.

int size() const; //The function returns the number of entries in the List.

bool retrieve(int position, int &x) const;

bool remove(int position, int &x);

bool remove(int val); //removes the node containing val as its data.

bool insert(int position, const int &x);

void print()const;

void insertLast(int val);

void insertFirst(int val);

int indexOf(int val)const;

intList interSection(const intList &)const;

intList union(const intList &)const;

};

A list is considered as having no fixed length: it can grow and shrink as additions or deletions are made anywhere on the list.

When an insertion is done the new value does not replace an existing value. When a new value is inserted at position i, the previous values all remain unchanged on the list but those which appeared at position i or later will now have new positions on the list.

Similarly, a deletion removes a value from the list but does not leave a gap: the remaining values assume new positions.

Operations that access entries of a list.

To find an entry in a list, we use an integer that gives its position within the list.

We shall number the positions in a list so that the first entry in the list has position 0, the second position 1, and so on. First, if we insert an entry at a particular position, then the position numbers of all later entries increase by 1. If we remove an entry, then the positions of all following entries decrease by 1.

bool insert(int position, int item);

If the List is not full and 0<= position <=n, where n is the number of entries in the List, the function succeeds: Any entry formerly at position and all later entries have their position numbers increased by 1, and x is inserted at position in the List. Returns: TRUE if insertion was successful or FALSE if the insertion failed.

Note that insert allows position ==n, since it is allowed to insert an entry after the last entry of the list.

bool remove(int position, int &x);

If 0<= position < n, where n is the number of entries in the List, the function succeeds: The entry at position is removed from the List, and all later entries have their position numbers decreased by 1. The parameter x records a copy of the entry formerly at position.

Returns: TRUE if deletion was successful or FALSE if the deletion failed.

bool retrieve(int position, int &x) const;

If 0_<=position < n, where n is the number of entries in the List, the function succeeds: The entry at position is copied to x; all List entries remain unchanged.

Returns: TRUE if retrieve was successful or FALSE if the search failed.

Given the methods for lists described above, implement the intList class, and make sure that following main function executes correctly.

void main()

{

intList myList; // Instantiate a list object

cout << "Simple List Demonstration ";

cout << "(List implemented as an Array";

cout << "Create a list and add a few tasks to the list";

myList.insert(0,12);//list is {12}

myList.insert(0, 4);//{4,12}

myList.insert(0, 7);//{7,4,12}

myList.insert(2, 34);//list becomes {7,4,34,12}

myList.insert(myList.size(), 85);//list becomes {7,4,34,12,85}

// Show what is in the list

myList.print()

// Test the list length function

cout << " List now contains " << myList.size() << "items. ";

// Test delete function

cout << "Testing delete of last item in list. ";

int val;

if (myList.remove(myList.size() - 1, val) == true)

cout << "delete operation was successfull:" << val << endl;

myList.print();

// Test delete function

cout << "Testing delete of first item in list. ";

if (myList.remove(0, val) == true)

cout << "delete operation was successfull:" << val << endl;

myList.print();

// Test delete function with a known failure argument

cout << "Testing failure in delete function. ";

if (myList.remove(10,val)==true)

cout <<" This was not expected. should not have been able to delete. ";

else

cout << "Unable to locate item to delete. ";

// Test retrieve ( failure)

cout << "Testing function. item at position 22 ";

if (myList.retrieve(22, val) == true)

cout << "retrieve result: val = " << val << " ";

else

cout << " result: Unable to locate item in list ";

// Test retrieve ( success)

cout << "Testing function. item at first position ";

if (myList.retrieve(0,val)==true)

cout << "retrieve result: val = " << val << " ";

else

cout << " result: Unable to locate item in list ";

}