Linked List

 
#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;
}
 
// 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

 // 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;
 }