using namespace std;
#include<iostream>

class IntList{
	private:
		struct ListNode{
			int value;
			ListNode *next;
		};
		ListNode *head;
	public:
		IntList(){
			head = NULL;
		}
		void appendNode(int);	
		void displayNode();
		void searchNode(int);
		void insertNode(int);
		void deleteNode(int);
};

void IntList::insertNode(int num){
	ListNode *newNode, *nodePtr, *prevNode = NULL;
	
	newNode = new ListNode;
	newNode->value = num;
	newNode->next = NULL;
	
	if(head == NULL){
		head = newNode;
	} else if(head->value > newNode->value) {
		newNode->next = head;
		head = newNode;		
	}else {
		nodePtr = head;
		while(nodePtr->value < num && nodePtr != NULL){
			prevNode = nodePtr;
			nodePtr=nodePtr->next;			
		}
		
		newNode->next = nodePtr;
		prevNode->next = newNode;
		
	}
	
}

void IntList::deleteNode(int num){
	ListNode *newNode, *nodePtr, *prevNode = NULL;
	
	if(head == NULL){
		cout<<"List is empty"<<endl;
	} else if(head->value == num) {
		nodePtr = head;
		head = head->next;
		delete nodePtr;			
	}else {
		nodePtr = head;
		while(nodePtr->value != num && nodePtr != NULL){
			prevNode = nodePtr;
			nodePtr=nodePtr->next;			
		}		
		prevNode->next = nodePtr->next;
		delete nodePtr;
		
	}	
}

void IntList::appendNode(int num){
	
	ListNode *newNode, *nodePtr;
	
	newNode = new ListNode;
	newNode->value = num;
	newNode->next = NULL;
	
	if(head == NULL){
		head = newNode;
	}else{
		nodePtr = head;
		while(nodePtr->next != NULL){
			nodePtr = nodePtr->next;
		}
		nodePtr->next = newNode;
	}
}

void IntList::displayNode(){
	ListNode *nodePtr;
	int count = 0;
	int sum = 0;
	
	if(head == NULL){
		cout<<"No node exists"<<endl;
	}else {
		nodePtr = head;
	
		while(nodePtr != NULL){
			cout<<nodePtr->value<<endl;
			sum = sum + nodePtr->value;
			nodePtr= nodePtr->next;
			count++;
			
		}
		cout<<"No. of nodes: "<<count<<endl;	
		cout<<"Sum of nodes: "<<sum<<endl;	
	}	
}
void IntList::searchNode(int num){
	ListNode *nodePtr;
	bool found = false;
	
	if(head == NULL){
		cout<<"No node exists"<<endl;
	}else{
		nodePtr = head;
	
		while(nodePtr != NULL && !found){
			if(nodePtr->value == num){
				found = true;
			}
			nodePtr= nodePtr->next;			
		}
		
		if(found){
			cout<<"Node Found"<<endl;
		}else{
			cout<<"Node NOT Found"<<endl;
		}
	}	
}


int main(){
	IntList list1;
	
	cout<<"***DISPLAYING***"<<endl;
	list1.displayNode();
		
	cout<<"***APPENDING NODE 4,9,12***"<<endl;
	list1.appendNode(4);
	list1.appendNode(9);
	list1.appendNode(12);

	
	cout<<"***DISPLAYING***"<<endl;
	list1.displayNode();

	cout<<"***INSERT NODE 10***"<<endl;
	list1.insertNode(10);
	
	cout<<"***DISPLAYING***"<<endl;
	list1.displayNode();
	
	cout<<"***delete NODE 9***"<<endl;
	list1.deleteNode(9);
	
	cout<<"***DISPLAYING***"<<endl;
	list1.displayNode();
	
	cout<<"***SEARCHING***"<<endl;
	list1.searchNode(12);
	
}