learning cpp: August 2011

Wednesday 31 August 2011

Delete middle node, 1st node or last node

The following is the logic for deleting the whichever node you want

template<class T>
T sll<T>::del(int i)
{
node<T> *p, *pres,*prev;
T x;
if(i<0||i>length())//i must be between 1 and length
{
return(-1);//ith node does not exist
}
else if(i==1)
{
p=first;//p points to first node
first=first->link;//move first to 2nd node so 1st node is logically deleted
x=p->data;//copy 1st node data to x
delete p;//delete 1st node
return(x);//return data of the deleted node
}
else//delete middle node or last node
{
pres=first;//present points to 1st node
for(int j=1;j<=i-1;j++)//searching for the ith node
{
prev=pres; //move prev ptr to pres ptr
pres=pres->link;//move pres ptr to next node
}
prev->link=pres->link;//change i-1 node link to i+1 th node
x=pres->data;
delete pres;
return(x);
}//end of else
}//end of del() function

/*
case 1: to delete ith node change i-1th node link to (i+1)th node
case 2: to delete 1st node, change first pointer to 2nd node:
steps:
1. p points to 1st node
2. move first to 2nd node, so 1st node is logically deleted
3. copy 1st node data to x, already p is pointing to 1st node so copy 1st node data to x
4. delete 1st node
5. return data of the deleted node

case 3: to delete last node, store NULL last but one node link field.
steps:
1. store NULL last but one node link filed
2. copy last node data to x
3. delete last node
4. return the data of the deleted node
case 4: if LL contains only one node, reinitialise first=NULL, after deletion of single node
*/

//deletion AT ITH NODE in the sll
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
template<class T>
class sll;
template<class T>
class node
{
private:
T data;
node<T>* link;
friend class sll<T>;
};
template <class T>
class sll
{
private:
node<T> * first;
public:
//Mem.Fun declarations
sll();
~sll();
int isempty();
void display();
int length();
void append(node<T> *k);
void create();
T del(int i);
};
//Member Functions defination
template<class T>
sll<T>::sll()
{
first=NULL;//first points to no where,it is an empty node
}
template<class T>
int sll<T>::isempty()
{
return(first==NULL);//return true when linked list is empty and false otherwise
}
template<class T>
void sll<T>::display()
{
node<T>* p;//p is pointer to a node
if(isempty())
cout<<"Linked List is empty\n";
else
{
cout<<"Linked list is as follows\n";
p=first;
while(p!=NULL)
{
cout<<p->data<<"\t"<<p->link<<"\n";
p=p->link;
}
}//end of else
}//end of display()
//finding lengh of nodes
template<class T>
int sll<T>::length()
{
node<T> *p=first;
int ctr=0;
while(p!=NULL)
{
ctr++;
p=p->link;
}
return(ctr);
}//end of length()

template<class T>
void sll<T>::append(node<T> *k)
{
node<T> *last;
k->link=NULL;
if(isempty())
first=k;
else
{
last=first;
while(last->link!=NULL)//keep moving last pointer until last node is reached
{
last=last->link;
}
last->link=k;//attach last node and new node k
}
}
template <class T>
void sll<T>::create()
{
T x;
node<T> *k;
first=NULL;
cout<<"enter values terminated by -1 or !\n";
cin>>x;
while(x!=-1&&x!='!')
{
k=new node<T>;
k->data=x;
append(k);
cin>>x;
}
}//end of create()
//deletion of the ith node which ever node you want
template<class T>
T sll<T>::del(int i)
{
node<T> *p, *pres,*prev;
T x;
if(i<0||i>length())//i must be between 1 and length
{
return(-1);//ith node does not exist
}
else if(i==1)
{
p=first;//p points to first node
first=first->link;//move first to 2nd node so 1st node is logically deleted
x=p->data;//copy 1st node data to x
delete p;//delete 1st node
return(x);//return data of the deleted node
}
else//delete middle node or last node
{
pres=first;//present points to 1st node
for(int j=1;j<=i-1;j++)//searching for the ith node
{
prev=pres; //move prev ptr to pres ptr
pres=pres->link;//move pres ptr to next node
}
prev->link=pres->link;//change i-1 node link to i+1 th node
x=pres->data;
delete pres;
return(x);
}//end of else
}//end of del() function

void main()
{
sll<int> a;//creating object a, d.c is called
int x,i;
clrscr();
a.create();

cout<<"enter which position you want to delete(ith node)\n";
cin>>i;
x=a.del(i);
if(x= =-1)
cout<<"Non existing node\n";
else
cout<<"deleted value is \t"<<x<<"\n";
cout<<"after deleting ith node \n";
a.display();

getch();
}

Singly Linked List Operations

Types of Linked list

Single Linked List

Dobule Linked List
Circular Linked List

Insertion element at middle of the SLL (or) Insertion element at ith node

//Insertion element at middle of the SLL (or) Insertion element at ith node
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
template<class T>
class sll;
template<class T>
class node
{
private:
T data;
node<T>* link;
friend class sll<T>;
};
template <class T>
class sll
{
private:
node<T> * first;
public:
//Mem.Fun declarations
sll();
   int isempty();
void display();
int length();
   void append(node<T> *k);
void create();
void insert(int i, T x);
};
//Member Functions defination
template<class T>
sll<T>::sll()
{
first=NULL;//first points to no where,it is an empty node
}
template<class T>
int sll<T>::isempty()
{
return(first==NULL);//return true when linked list is empty and false otherwise
}
template<class T>
void sll<T>::display()
{
node<T>* p;//p is pointer to a node
if(isempty())
cout<<"Linked List is empty\n";
else
{
cout<<"Linked list is as follows\n";
p=first;
while(p!=NULL)
{
   cout<<p->data<<"\t"<<p->link<<"\n";
   p=p->link;
}
}//end of else
}//end of display()
template<class T>
void sll<T>::append(node<T> *k)
{
node<T> *last;
k->link=NULL;
if(isempty())
first=k;
else
{
last=first;
while(last->link!=NULL)//keep moving last pointer until last node is reached
{
   last=last->link;
}
last->link=k;//attach last node and new node k
}
}
template <class T>
void sll<T>::create()
{
T x;
node<T> *k;
first=NULL;
cout<<"enter values terminated by -1 or !\n";
cin>>x;
while(x!=-1&&x!='!')
{
k=new node<T>;
k->data=x;
append(k);
cin>>x;
}
}//end of create()
//inserting data at ith node
template<class T>
void sll<T>::insert(int i, T x)
{
   node<T> *p,*temp;
if(i<0||i>length())
{
    cout<<"Non-Existing Node\n";
   }
else
{
    p=new node<T>;
   //store data into the node
   p->data=x;
   if(i= =0) //insert at the begining or Linked list is empty
{
    p->link=NULL;
   first=p;
}
else //insert in the middle or at the end of the Linked List
{
temp=first;
//move the temp ptr to ith node (desired node)
   for(int j=1;j<=i-1;j++)
   temp=temp->link;
//insert new node p after temp node
p->link=temp->link;
temp->link=p;
} //inner else
}//outer else
}//end of insert()


void main()
{
sll<int> a;//creating object a, d.c is called
clrscr();
int i,x;
a.create();
cout<<"enter which position you want to insert(ith node value)\n";
cin>>i;
cout<<"enter data to be inserted\n";
cin>>x;
a.insert(i,x);
a.display();
  getch();
}
output:

Singly Linked List Operations

Types of Linked list

Single Linked List

Dobule Linked List
Circular Linked List

Monday 29 August 2011

Deletion of the last node

Deletion of the last node

1. Declare necessary variable
2. If list = NULL
print "Empty List"
Else
set p = list
if p->next = NULL
list = NULL
delete(p)
Else
while(p->next!=NULL)
temp = p
p = p->next
temp->next = NULL
delete(p)
3. For next deletion goto step 2

Deletion of the first node

Deletion of the first node

1. Declare the necessary variables
2. If list = NULL
print "Empty list"
Else
p = list
list = p -> next
3. Remove the node p i.e. delete(p)
4. For next deletion, goto step 2

Insertion new node at the end of the Linked List

Insertion new node at the end of the Linked List

Insertion new node at the end.

1. Declare neccessary variables.
2. Create an empty node and assign it to node pointer p.
3. Insert the data item to info field of newly created node,
i.e. p->info = data;
4. Assign NULL to the next field of newly created node
i.e. p->next = NULL;
5. If list == NULL;
then list = p;
Else
Find the last node of the current list say l.
then l->next = p;
6. For next insertion, goto step 2.

Insertion node at front single linked list

Algorithm for adding an element (data) to the front of the list list.

1. Declare and initialize necessary variables

2. Create an empty node and assign it to node pointer p.

3. Take input data and assign it to data field of new node

i.e. p->data = data;

4. Set next field. i.e. p->next = list;

5. Set list pointer to p i.e. list = p;

6. For next insertion operation, goto step 2

Singly Linked List Operations

1. Linked list

Single Linked List

Dobule Linked List
Circular Linked List

Sunday 28 August 2011

Counting no of nodes in the Singly Linked List (SLL)

function for counting the sll nodes is similar to display(), only difference is we are using counter variable to count the no of nodes in the loop.
This is the function for finding the no of nodes in the linked list
int length()
{
node<T> *p=first;
int ctr=0;
while(p!=NULL)
{
ctr++;
p=p->link;
}
return(ctr);
}//end of length()

//COUNT THE NUMBER OF NODES IN THE LINKED LIST (SLL)
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
template<class T>
class sll;
template<class T>
class node
{
private:
T data;
node<T>* link;
friend class sll<T>;
};
template <class T>
class sll
{
private:
node<T> * first;
public:
//Mem.Fun declarations
sll();

int isempty();

int length();
void append(node<T> *k);
void create();

};
//Member Functions defination
template<class T>
sll<T>::sll()
{
first=NULL;//first points to no where,it is an empty node
}
template<class T>
int sll<T>::isempty()
{
return(first==NULL);//return true when linked list is empty and false otherwise
}
//length() defination
template<class T>
int sll<T>::length()
{
node<T> *p=first;
int ctr=0;
while(p!=NULL)
{
ctr++;
p=p->link;
}
return(ctr);
}//end of length()

template<class T>
void sll<T>::append(node<T> *k)
{
node<T> *last;
k->link=NULL;
if(isempty())
first=k;
else
{
last=first;
while(last->link!=NULL)//keep moving last pointer until last node is reached
{
last=last->link;
}
last->link=k;//attach last node and new node k
}
}
template <class T>
void sll<T>::create()
{
T x;
node<T> *k;
first=NULL;
cout<<"enter values terminated by -1 or !\n";
cin>>x;
while(x!=-1&&x!='!')
{
k=new node<T>;
k->data=x;
append(k);
cin>>x;
}
}//end of create()

void main()
{
sll<int> a;//creating object a,and d.c is called
node<int> *p;
int x,i;
clrscr();
a.create();

getch();
}

Saturday 27 August 2011

Circular Linked List

Circular Linked List

Circular linked Lists is used to traverse the same list again. A circular list is very similar to the
linear list where in the circular list the pointer
of the last node points not NULL but the first node.

see the diagram