Archives for

Linked List

Implementation of Singly linked list in C plus plus

The simplest kind of linked list is a singly-linked list , which has one link per node. This link points to the next node in the list, or to a null value or empty list if it is the final node.A singly linked list’s node is divided into two parts. The first part holds or points to information about the node, and second part holds the address of next node. A singly linked list travels one way.

A singly-linked list containing two values: the value of the current node and a link to the next node

A singly-linked list containing two values: the value of the current node and a link to the next node

/*

A simple implementation of linked list in C plus plus (CPP/C++)

*/  
/*
Program downloaded from www.GeeksPlanet.net
For any help, post comment here

http://geeksplanet.net/2008/11/data-structures/implementation-of-singly-linked-list-using-c-plus-plus/

Compiler used: g++
*/
#include<iostream>
using namespace std;
struct node{
	int data;
	node *next;
	};
/*
This function adds a node at the end of the   
list and returns pointer to the added node,   
This takes pointer to the first node and 
pointer to the last node as argument. By 
giving the last node as argument we are saving 
some computer labour as it need not travel 
from the start to the end to find the last node 
*/
node * addnode(node*,node*);
/*
This function just takes the first node as 
the argument and traverses the entire list 
displaying the data in each node.
*/
void shownodes(node*);
/*
This function takes the first node as argument
and traverses the list until it finds the last
node and deletes it and returns pointer to the 
new last node.
*/
node * delete_node(node*);
/*
*f and *l are the global variables keeping track
of first and last nodes.
*/
node *f,*l;

main()
{
	int i,ch;
	f=l=NULL;
	cout<<"\t 1 to add a node"<<endl;
	cout<<"\t 2 to see the nodes"<<endl;
	cout<<"\t 3 to delete a node"<<endl;
	cout<<"\t 0 to exit"<<endl;
	while(1)
	{
		cout<<"Enter your choice:";
		cin>>ch;
		switch(ch)
		{
		case 1:
		{        
			if(f==NULL)
			l=f=addnode(f,l); //Since first node is the last node
			else
			l=addnode(f,l);	  //Last node is the new node added	
			break;
		}
		case 2:
			shownodes(f);break;
		case 3:
			l=delete_node(f);break; // Last node has been changed to the last but one.
		case 0:
			break;
		default:
			cout<<"Please enter a proper choice"<<endl;break;
		}
		if(ch==0)
		break;
	}
}
node * addnode(node *f,node *l)
{
	node *n;
	n=new node; 
	//Allocating memory for the new node
	cout<<"Enter data:";
	cin>>n->data;
        //This is going to be the last node, so its next point to NULL
	n->next=NULL;
	//If there is no first node, then the new node is the first and last node.
	if(f==NULL)
	{f=l=n;return f;}
	else
	{
		// Pointing the last node to the new node
		l->next=n; 
		//Setting the new node as the last node
		l=n;return l;
	}
	
	
}
void shownodes(node *f)
{
	cout<<"showing data"<<endl;
	node *guest=f;
	while(guest!=NULL)
	{
		cout<<"\t"<<guest->data<<endl;
		guest=guest->next;
	}
}
node * delete_node(node *f)
{
	node *guest,*lb;
	guest=lb=f;	
	while(guest->next!=NULL)
	{	
		lb=guest;
		guest=guest->next;	
	}
	lb->next=NULL;
	cout<<"node deleted"<<endl;
	return lb;
}	

Download the prgoram linked-list.cpp