#include<iostream.h>

class node{
public:
int data;
node* next;
node(int x){
data=x;
next=NULL;};

void display(){
cout<<data<<"  ";
};
};

class linked_list{
private:
node* first;
public:
linked_list(){
first=NULL;};

void insert_last(int d){
node* newnode=new node(d);
node* current=first ;
if(first==NULL)
first=newnode;
else{
while(current->next!=NULL)
current=current->next;
current->next=newnode;
}};

void insert_first(int z){
node* newnode= new node(z);
if(first==NULL)
first=newnode;
else{
newnode->next=first;
first=newnode;}
};

void display(){
node* current=first;
while(current!=NULL){
current->display();
current=current->next;}
};

void insert_mid(int d){
node* newnode=new node(d);
node* current=first;
node* temp;
while(current->next->data<d)
current=current->next;

temp=current->next;
current->next=newnode;
newnode->next=temp;
};

int l_delete(int x){
node* current=first;
if(first==NULL){
cout<<"List is empty"<<endl;
return -1;}
if(first->data==x)
first=first->next;
else{
while((current->next->data!=x)&&(current->next!=NULL))
current=current->next;}
if(current->next==NULL)
cout<<"error"<<endl;
else{
current->next=current->next->next;
delete current;}
return x;};
};



main(){
linked_list list;
int no, g, h, d, e;
char c, a0, a1, a2, a3;
do{
cout<<"Please choose the number of the option"<<endl<<endl;
cout<<"\t\t______________________ MENU _____________________"<<endl;
cout<<"\t\t1. Add new node to the end of the list"<<endl;
cout<<"\t\t2. Add new node to the beginning of the list"<<endl;
cout<<"\t\t3. Add new node in the middle of the list"<<endl;
cout<<"\t\t4. Delete a node from the list"<<endl;
cout<<"\t\t5. Display the list"<<endl;
cout<<"\t\t_________________________________________________"<<endl;
cin>>no;
switch(no){
case 1: do{
cout<<"Please enter the element you want to insert to the node:"<<endl;
cin>>g;
list.insert_last(g);
cout<<"Do you want to add more to the end of the list? y/n"<<endl;
cin>>a0;}
while(a0=='y');
break;
case 2: do{
cout<<"Please enter the element you want to insert to the node:"<<endl;
cin>>h;
list.insert_first(h);
cout<<"Do you want to add more to the beginning of the list? y/n"<<endl;
cin>>a1;}
while(a1=='y');
break;
case 3: do{
cout<<"Please enter the element you want to insert to the node:"<<endl;
cin>>d;
list.insert_mid(d);
cout<<"Do you want to add more to the mid of the list? y/n"<<endl;
cin>>a2;}
while(a2=='y');
break;
case 4: do{
cout<<"Please enter the value of the element you want to delete:"<<endl;
cin>>e;
list.l_delete(e);
cout<<"Do you want to delete more from the list? y/n"<<endl;
cin>>a3;}
while(a3=='y');
break;
case 5: list.display();
cout<<endl;
break;
default:
cout<<"Error in number"<<endl;
break;}
cout<<"Do you want to continue? y/n"<<endl;
cin>>c;}
while(c=='y');
}

#include <iostream>
#include <fstream>
using namespace std;
 
class List
{
	private:
		struct ListN
		{
			char item;
			ListN* next;
		};
		ListN* head;
		ListN* tail;
		int size;
 
	public:
		List();
		~List();
		void insert (char );
		void remove (int );
		void deleteAll ();
		void retrieve ();
		void countIte();
		void countRec();
		void display();
		void sort();
		void save();
};
 
 
List :: List()
{
	head = tail = NULL;
	size = 0;
}
 
List :: ~List()
{
	deleteAll ();
}
 
void List :: sort()
{
	ListN* curPtr;
	curPtr = head;
	char buffer;
	int i;
	int j;
 
	for (i=1; i<size; i++)
	{
		for(j=size-1, curPtr = head; j>=i; j--, curPtr = curPtr -> next)
		{
			if (curPtr->item > curPtr->next->item)
			{
				buffer = curPtr -> item;
				curPtr->item = curPtr->next->item;
				curPtr->next->item = buffer;
			}
		}
	}
 
	//alternate method for sorting
	/*if (size >= 2)
	{
		for (curPtr = head; curPtr->next != NULL; curPtr = curPtr -> next)
		{
			cout << "sorting " << curPtr-> item << endl;
			if (curPtr->item > curPtr->next->item)
			{
				buffer = curPtr -> item;
				curPtr->item = curPtr->next->item;
				curPtr->next->item = buffer;
			}
		}
	}*/
}
 
void List :: insert(char item)
{
	ListN* newPtr;
	ListN* curPtr;
	newPtr = new ListN;
	curPtr = head;
 
	newPtr -> next = NULL;
	newPtr -> item = item;
 
	if (size == 0)
	{
		head = newPtr;
		newPtr -> next = NULL;
	}
 
	else
	{
		curPtr = tail;
		curPtr->next = newPtr;
	}
 
	tail = newPtr;
	size++;
}
 
void List :: retrieve()
{
	ifstream read;
	char temp1;
	char check;
 
	read.open("Q2.txt");
	read >> temp1;
 
	insert(temp1);
	check = temp1;
 
	for (;;)
	{
		read >> temp1;
 
		if (temp1 == check)
			break;
		check = temp1;
		insert(temp1);
	}
	sort();
}
 
void List :: display()
{
	int i;
	ListN* curPtr;
	curPtr = head;
 
	sort();
	if (size == 0)
		cout << "No item in the List!!" << endl;
 
	else
	{
		cout << "\tThe list of record is :\t";
		for (i=1; i<=size; i++)
		{
			cout << curPtr -> item << " ";
			curPtr = curPtr -> next;
		}
	}
 
 
}
 
void List :: save()
{
	int i;
	ListN* curPtr;
	ofstream save;
 
	save.open("Q2.txt");
 
	curPtr = head;
	for( i=0; i<size; i++ )
	{
		save << curPtr -> item << endl;
		curPtr = curPtr -> next;
	}
}
 
void List :: remove(int index)
{
	int i;
	ListN* previous;
	ListN* curPtr;
	curPtr = head;
 
	if (index <= size && index >0)
	{
		if(index == 1)
		{
			head = head -> next;
			delete curPtr;
			curPtr->next = NULL;
		}
 
		for(i=1; i<index-1; i++)
			curPtr = curPtr -> next;
 
		previous = curPtr;
 
		curPtr = curPtr -> next;
 
		previous -> next = curPtr -> next;
 
		curPtr = NULL;
		size--;
	}
 
	else if (index<0 || index>size)
		cout << "The record number is out of range!!" << endl;
 
	previous = NULL;
 
}
 
void List :: deleteAll ()
{
	cout << size << endl;
	int i;
 
	for (i=size; i>0 ; i--)
	{
		if (i == 1)
		{
			head = NULL;
			size--;
		}
		else
		remove(i);
	}
}
 
void List :: countIte()
{
	int count;
	int i;
	ListN* curPtr;
 
	count = 0;
 
	for (i=0, curPtr = head; i<size; i++, curPtr = curPtr->next)
		count++;
 
	cout << "The total records is :\t\t" << count << endl;
}
 
void List :: countRec()
{
	ListN* curPtr;
	int count;
 
	count = 0;
 
	for(curPtr = head; curPtr != NULL; curPtr = curPtr->next, count++);
	{
	}
 
	cout << "The total records is :\t\t" << count << endl;
}
 
int main()
{
	List a;
	int choice;
	int index;
	char val;
 
	do
	{
		cout << "1	Insert a new item into the linked list." << endl;
		cout <<	"2	Remove an item from the linked list." << endl;
		cout <<	"3	Remove all items from the linked list." << endl;
		cout <<	"4	Get the item from a text file and added to the sorted linked list." << endl;
		cout <<	"5	Count the number of item iteratively." << endl;
		cout <<	"6	Count the number of item recursively." << endl;
		cout <<	"7	List the content of the linked list." << endl;
		cout << "8\tQuit." << endl << endl;
		cout << "\tYour Choice :\t";
		cin >> choice;
 
		cout << "\n\n\n" << endl;
 
		switch(choice)
		{
			case 1:
				cout << "Enter a value for insert :\t";
				cin >> val;
				a.insert(val);
				cout << "\n\n" << endl;
				break;
			case 2:
				cout << "Enter the index of record for deletion :\t";
				cin >> index;
				a.remove(index);
				cout << "\n\n" << endl;
				break;
			case 3:
				a.deleteAll();
				cout << "\n\n" << endl;
				break;
			case 4:
				a.retrieve();
				cout << "\n\n" << endl;
				break;
			case 5:
				a.countIte();
				cout << "\n\n" << endl;
				break;
			case 6:
				a.countRec();
				cout << "\n\n" << endl;
				break;
			case 7:
				a.display();
				cout << "\n\n" << endl;
				break;
 
			case 8:
				break;
		}
	}while(choice != 8);
 
	return 0;
}