class LinkedList

{

private:

Node * head; // address of the first node

public:

LinkedList();

void append(int);

void display();

~LinkedList();

void insert(int);

};

LinkedList::LinkedList()

{

// empty list

head = NULL;

}

void LinkedList::append(int data)

{

Node *tempNode = head;

Node *newNode = new Node;

newNode->data = data;

newNode->next = NULL;

if (!head) // empty list, head == NULL

{

head = newNode;

}

else

{

while (tempNode->next != NULL)

{

tempNode = tempNode->next;

}

tempNode->next = newNode;

}

}

void LinkedList::display()

{

Node *tempNode = head;

while (tempNode != NULL)

{

cout << tempNode->data << endl;

tempNode = tempNode->next; // move to the next node

}

}

LinkedList::~LinkedList()

{

Node *tempNode = head;

Node *preNode = head;

while (tempNode != NULL)

{

preNode = tempNode;

tempNode = tempNode->next; // move to the next node

delete preNode;

}

}

void LinkedList::insert(int data)

{

Node *newNode = new Node;

newNode->data = data;

Node *tempNode = head;

Node *preNode = head;

if (head == NULL)

{

head = newNode;

newNode->next = NULL;

}

else if (data < head->data)

{

newNode->next = head;

head = newNode;

}

else

{

while (tempNode != NULL && tempNode->data <= data)

{

preNode = tempNode;

tempNode = tempNode->next; // move to the next node

}

preNode->next = newNode;

newNode->next = tempNode;

}

}

Using C++, modify the linked list class to include the following member functions:

1. A member function named search that returns the position of a specific value in the linked list. The first node in the list is at position 0, the second node is at position 1, and so on. If x is not found on the list, the search should return -1.

2. A member function for inserting a new item at a specified position. A position of 0 means that the value will become the first item on the list, a position of 1 means that the value will become the second item on the list, and so on. A position equal to or greater than the length of the list means that the value is placed at the end of the list.

Test the new member functions using an appropriate driver program.