Some parts are written exercises. They also need to be turned in.

Given the following declarations:

class NodeType {

public:

NodeType( int = 0 ); // constructor with default value for

// info field

int info; // data

NodeType * nextPtr; // pointer to next node in the list

};

// Constructor

NodeType::NodeType( int data )

{

info = data;

nextPtr = 0;

}

//Assume the following are declared in the main

NodeType * head;

NodeType * currentPtr;

int value;

1.Draw pictures showing what happens when the following commands are done, one after the other. There should be 6 pictures.

head = NULL;

value = 5;

currentPtr = new NodeType;

currentPtr->info = value;

currentPtr->nextPtr = head;

head = currentPtr;

Change the above code so that the value is read in from the keyboard.

2.Make the last 4 lines of the problem above into the body of a function that takes a value and the pointer head that points to a linked list ( list may be empty, meaning head may initially be NULL ), and inserts a new node at the front, containing the value. Name the function insert. The pointer currentPtr should be a local variable. Value and the pointer head would be arguments to the function. What kind of parameters should each of them be: value parameter or reference parameter and why? Save the function; we will test it out later.

3.Write a C++ statement that prints out the data in the first node in Picture A using currentPtr. Write the statement that makes the change from picture A to picture B that does not use head. What happens if you repeat the two statements again? Use the two statements to write a function that prints out all the values stored in a linked list pointed to by the pointer head. The pointer head should be the only argument for the function printList, and currentPtr should be a local variable inside the function. Is head passed by reference or by value?

A B

4. Use functions from 2 and 3, and write an interactive program that starts with an empty list (head is NULL ) has choices of Add, Print, and Quit. For Add, the integer the user types in will be added to the front of the linked list by calling your insert function; for Print, all the values in the linked list from the front to the end will be printed out using your printList function. The program will keep repeating until the user chooses to quit.

Test your two functions by running your program.

5.Write a function deleteFirst that will delete the first node in a linked list pointed to by the parameter head. Should head be a value parameter or reference parameter?

6.Write a boolean function called find that will be given a pointer to a linked list and a value. If the value is in the linked list, it should return true; if not, it should return false.

7.Starting from picture C, draw the pictures that show step by step what is needed to get to picture D. We are assuming the part of the linked list shown is somewhere in the middle of a long linked list.

C D

Using your pictures, write the code to delete a node from the middle of the linked list starting from picture C. Now insert before it the code that will move currentPtr and previousPtr through the list until it finds a particular value if it exists (look at the find function from above). The previousPtr should start out as NULL and always be one node behind the currentPtr. Use your code to make a boolean function findAndDelete that is given a pointer to a linked list and a value, and if the value is in the linked list, it is deleted and the function returns true. If it is not in the list, the function returns false.

8. Expand your menu to test your three new functions. When choosing to test the find or findAndDelete functions, the user will be first asked to enter the value to find or to find and delete. Depending on whether the functions returned true or false, the main program should write an appropriate message to the user.

9. Finally write a function called deleteList that will delete all nodes in the linked list and return the parameter head set to nullptr. You can add it to the menu for testing, but also put it at the end of the program to release all dynamic memory you used.

5 8 NIL 8 NIL head currentPtr head currentPtr