/////////////////////////////////////////////.cpp file

#include <iostream>
#include "ModLinkedList.h"
using namespace std;

//Prototype
void search(int);
int number;

int main()
{
	LinkedList<int> list;

	// Build the list
	cout << "Enter a number to be searched: ";
	cin >> number;
	cout << "Now searching for the number\n";
	list.displayNode(number);
	list.appendNode(1);
	list.appendNode(2);
	list.appendNode(3);
	list.appendNode(4);
	list.appendNode(5);
	list.appendNode(6);
	

	cout << "Now displaying the number.\n";
	list.displayNode(number);
	list.displayList();
	return 0;
}

////////////////////////////////////////////////////////.h file ////////////////

// A class template for holding a linked list.
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>		// For cout and NULL
using namespace std;

template <class T>
class LinkedList
{
private:
	// Declare a structure for the list
	struct ListNode
	{
		T value;
		struct ListNode *next;
	}; 

	ListNode *head;	// List head pointer

public:
	LinkedList()	// Constructor
		{ head = NULL; }
	~LinkedList(); // Destructor
	void appendNode(T);
	void insertNode(T);
	void deleteNode(T);
	void displayList();
	void displayNode(T);
};


//**************************************************
// appendNode appends a node containing the value  *
// pased into newValue, to the end of the list.    *
//**************************************************

template <class T>
void LinkedList<T>::appendNode(T newValue)
{
	ListNode *newNode, *nodePtr;

	// Allocate a new node & store newValue
	newNode = new ListNode;
	newNode->value = newValue;
	newNode->next = NULL;

	// If there are no nodes in the list
	// make newNode the first node
	if (!head)
		head = newNode;
	else	// Otherwise, insert newNode at end
	{
		// Initialize nodePtr to head of list
		nodePtr = head;

		// Find the last node in the list
		while (nodePtr->next)
			nodePtr = nodePtr->next;

		// Insert newNode as the last node
		nodePtr->next = newNode;
	}
}

//**************************************************
// displayList shows the value                     *
// stored in each node of the linked list          *
// pointed to by head.                             *
//**************************************************

template <class T>
void LinkedList<T>::displayList()
{
	ListNode *nodePtr;

	nodePtr = head;
	while (nodePtr)
	{
		cout << nodePtr->value << endl;
		nodePtr = nodePtr->next;
	}
}

//**************************************************
// The insertNode function inserts a node with     *
// newValue copied to its value member.            *
//**************************************************

template <class T>
void LinkedList<T>::insertNode(T newValue)
{
	ListNode *newNode, *nodePtr, *previousNode = NULL;

	// Allocate a new node & store newValue
	newNode = new ListNode;
	newNode->value = newValue;
	
	// If there are no nodes in the list
	// make newNode the first node
	if (!head)
	{
		head = newNode;
		newNode->next = NULL;
	}
	else	// Otherwise, insert newNode
	{
		// Initialize nodePtr to head of list and previousNode to NULL.
		nodePtr = head;
		previousNode = NULL;

		// Skip all nodes whose value member is less
		// than newValue.
		while (nodePtr != NULL && nodePtr->value < newValue)
		{	
			previousNode = nodePtr;
			nodePtr = nodePtr->next;
		}

		// If the new node is to be the 1st in the list,
		// insert it before all other nodes.
		if (previousNode == NULL)
		{
			head = newNode;
			newNode->next = nodePtr;
		}
		else	// Otherwise, insert it after the prev. node.
		{
			previousNode->next = newNode;
			newNode->next = nodePtr;
		}
	}
}

//*****************************************************
// The deleteNode function searches for a node        *
// with searchValue as its value. The node, if found, *
// is deleted from the list and from memory.          *
//*****************************************************

template <class T>
void LinkedList<T>::deleteNode(T searchValue)
{
	ListNode *nodePtr, *previousNode;

	// If the list is empty, do nothing.
	if (!head)
		return;
	
	// Determine if the first node is the one.
	if (head->value == searchValue)
	{
		nodePtr = head->next;
		delete head;
		head = nodePtr;
	}
	else
	{
		// Initialize nodePtr to head of list
		nodePtr = head;

		// Skip all nodes whose value member is 
		// not equal to searchValue.
		while (nodePtr != NULL && nodePtr->value != searchValue)
		{	
			previousNode = nodePtr;
			nodePtr = nodePtr->next;
		}

		// If nodePtr is not at the end of the list, 
		// link the previous node to the node after
		// nodePtr, then delete nodePtr.
		if (nodePtr)
		{
			previousNode->next = nodePtr->next;
			delete nodePtr;
		}
	}
}

//**************************************************
// Destructor                                      *
// This function deletes every node in the list.   *
//**************************************************

template <class T>
LinkedList<T>::~LinkedList()
{
	ListNode *nodePtr, *nextNode;

	nodePtr = head;
	while (nodePtr != NULL)
	{
		nextNode = nodePtr->next;
		delete nodePtr;
		nodePtr = nextNode;
	}
}

/////////////////////////////////////////////
template <class T>
void LinkedList<T>::displayNode(T searchValue)
{
	ListNode *nodePtr, *previousNode;

	// If the list is empty, do nothing.
	if (!head)
		return;
	
	// Determine if the first node is the one.
	if (head->value == searchValue)
	{
		nodePtr = head->next;
		//delete head;
		head = nodePtr;
	}
	else
	{
		// Initialize nodePtr to head of list
		nodePtr = head;

		// Skip all nodes whose value member is 
		// not equal to searchValue.
		while (nodePtr != NULL && nodePtr->value != searchValue)
		{	
			previousNode = nodePtr;
			nodePtr = nodePtr->next;
		}

		// If nodePtr is not at the end of the list, 
		// link the previous node to the node after
		// nodePtr, then delete nodePtr.
		if (nodePtr)
		{
			previousNode->next = nodePtr->next;
			delete nodePtr;
		}
	}
}

/////////////////////////////////////////////

#endif

//C++ Code