Implement Single Linked List in C++

Introduction:

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Working Principle:

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Example:

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Code:

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include<iostream>
#include<stdlib.h>
using namespace std;

void create_list(int);
void addatbeg(int);
void addafter(int,int);
void addatend(int);
void del(int);
void display();
void count();
void rev();
void search(int);

struct node
{
	int info;
	struct node *link;
}*start;

int main()
{
	cout<<endl<<endl<<"   Website: Daily Just 4 U    \t\t ##### Singly Linked List #####    \t\t Muhammad Usman (Comsats Wah) "<<endl<<endl;
	int choice,n,m,position,i;
	start=NULL; 
	cout<<endl;
	while(1)
	{
		cout<<"***** Main Menu *****"<<endl<<endl;
		cout<<" 1. Create List"<<endl;
		cout<<" 2. Add at beginning"<<endl;
		cout<<" 3. Add at middle / after position"<<endl;
		cout<<" 4. Add at end"<<endl;
		cout<<" 5. Delete"<<endl;
		cout<<" 6. Display"<<endl;
		cout<<" 7. Count"<<endl;
		cout<<" 8. Reverse"<<endl;
		cout<<" 9. Search"<<endl;
		cout<<" 10. Quit"<<endl;

		cout<<" Enter ur choice = ";
		cin>>choice;
		cout<<endl;
		switch(choice)
		{
			case 1:
				cout<<" How many nodes you want "<<endl<<" ";
				cin>>n;
				for(i=0;i<n;i++)
				{
					cout<<" Enter the element "<<endl<<" ";
					cin>>m;
					create_list(m);
				}
				cout<<endl;
				break;
			case 2:
				cout<<" Enter the element "<<endl<<" ";
				cin>>m;
				addatbeg(m);
				cout<<endl;
				break;
			case 3:
				cout<<" Enter the element "<<endl<<" ";
				cin>>m;
				cout<<" Enter the position after which this element is inserted "<<endl<<" ";
				cin>>position;
				addafter(m,position);
				cout<<endl;
				break;
			case 4:
				cout<<" Enter the element "<<endl<<" ";
				cin>>m;
				addatend(m);
				cout<<endl;
				break;	
			case 5:
				if(start==NULL)
				{
					cout<<" List is empty !!! "<<endl;
					continue;
				}
				cout<<" Enter the element value for deletion "<<endl<<" ";
				cin>>m;
				del(m);
				cout<<endl;
				break;
			case 6:
				display();
				cout<<endl;
				break;
			case 7:
				count();
				cout<<endl;
				break;
			case 8:
				rev();
				cout<<endl;
				break;
			case 9:
				cout<<" Enter the element to be searched "<<endl<<" ";
				cin>>m;
				search(m);
				cout<<endl;
				break;
			case 10:
				exit(1);
			default:
				cout<<" Wrong choice "<<endl;
		}
	}
	return 0;
}

void create_list(int data)
{
	struct node *q,*tmp;
	tmp=new(struct node);
	tmp->info=data;
	tmp->link=NULL;

	if(start==NULL) /*if list is empty*/
	{
		start=tmp;	/*element inserted at start or first*/
	}  
	else   /*if list not empty*/ 	
	{
		q=start;
		while(q->link!=NULL) // transversing to reach at end element
		{
			q=q->link;
		}	
		q->link=tmp;  /*element inserted at end*/
	}
}

void addatbeg(int data)
{
	struct node *tmp;
	tmp=new(struct node);
	tmp->info=data;
	tmp->link=start;
	start=tmp;
}

void addafter(int data,int pos)
{
	struct node *tmp,*q;
	tmp=new(struct node);
	
	int i;
	q=start;
	for(i=1;i<=pos;i++)
	{
		q=q->link;
		if(q==NULL)
		{
			cout<<" There are less than "<<pos<<" elements "<<endl;
			return;
		}
	}
	tmp=new(struct node);
	tmp->link=q->link;
	tmp->info=data;
	q->link=tmp;
}

void addatend(int data)
{
	struct node *tmp, *q;
	tmp=new(struct node);
	tmp->info=data;
	tmp->link=start;
	
	if(start==NULL) /*if list is empty*/
	{
		start=tmp;	/*element inserted at start or first*/
	}  
	else   /*if list not empty*/
	{
		q=start;
	    while(q->link!=NULL) // transversing to reach at end element
		{
			q=q->link;
		}	
		q->link=tmp;  /*element inserted at end*/
	}
	
}

void del(int data)
{
	struct node *tmp,*q;
	tmp=new(struct node);
	if(start->info==data)
	{
		tmp=start;
		start=start->link;	/*first element deleted*/
		delete(tmp);
		return;
	}
	q=start;
	while(q->link->link!=NULL)
	{
		if(q->link->info==data)	       /*element deleted in between*/
		{
			tmp=q->link;
			q->link=tmp->link;
			free(tmp);
			return;
		}
		q=q->link;
	}
	if(q->link->info==data)		/*last element deleted*/
	{
		tmp=q->link;
		free(tmp);
		q->link=NULL;
		return;
	}
	cout<<" Element "<<data<<" not found "<<endl;
}

void display()
{
	struct node *q;
	if(start==NULL)
	{
		cout<<" List is empty !!! "<<endl;
		return;
	}
	q=start;
	cout<<" List is: "<<endl<<" ";
	while(q!=NULL)
	{
		cout<<q->info<<"   ";
		q=q->link;
	}
	cout<<endl;
}

void count()
{
	struct node *q=start;
	int cnt=0;
	while(q!=NULL)
	{
		q=q->link;
		cnt++;
	}
	cout<<" Number of nodes / elements = "<<cnt<<endl;
}

void rev()
{
	struct node *p1,*p2,*p3;
	if(start->link==NULL)  	/*if only one element*/
	{
		return;
	}
	/*if multiple elements*/
	p1=start;
	p2=p1->link;
	p3=p2->link;
	p1->link=NULL;
	p2->link=p1;
	while(p3!=NULL)
	{
		p1=p2;
		p2=p3;
		p3=p3->link;
		p2->link=p1;
	}
	start=p2;
}

void search(int data)
{
	struct node *ptr=start;
	int pos=1;
	while(ptr!=NULL)
	{
		if(ptr->info==data)
		{
			cout<<" Node "<<data<<" found at position "<<pos<<endl;
			return;
		}
		ptr=ptr->link;
		pos++;
	}
	if(ptr==NULL)
	{
		cout<<" Node "<<data<<" not found at position "<<pos<<endl;
	}	
}

Output:

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------