Complete Program Source code : Implementation of Double Linked List
As I had told earlier that towards the end you shall see the complete program implementing the double linked list,here it is
#include <cstdlib>
#include <iostream>
#include<fstream>
#include<conio.h>
#include<process.h>
#include <stdlib.h>
using namespace std;
typedef struct node
{
int data; // stores the node data
node *next,*prev;// 2 ptrs(ptr vars),will have mem add,holding node type
}NODE;
// GLOBAL VARS
NODE *first,*last;// Global ptrs,will have mem add,holding
// node type
long nodecount=0;//global var to keep count of nodes created
// FUNCTION PROTOTYPES
void addathead(NODE*);
void addattail(NODE*);
void deletenode(NODE*);
void addafter(NODE*,NODE*);
void addbefore(NODE*,NODE*);
NODE* search(int);
void deleteall();
void display();
int inputdata();
NODE* create();//create a blank node
NODE* create(int);//create a populated node,with the int passed
void deletelast();
void save();
void loadlist();//create a list as per the data in a file
int main(int argc, char *argv[])
{
first=last=NULL;// initing ptrs to NULL
while(1) // infinite loop
{
system("cls");
char choice;
cout<<"\n\n\t\t\tDOUBLE LINK LIST MENU";
cout<< "\n\t\t\t=====================";
cout<< "\n\t\t\t1. Add a Record at Head";
cout<< "\n\t\t\t2. Add a Record at Tail";
cout<< "\n\t\t\t3. Add a Record by Search after a Node";
cout<< "\n\t\t\t4 Add a Record by Search before a Node";
cout<< "\n\t\t\t5. Get Record Count";
cout<< "\n\t\t\t6. Delete Selected Record";
cout<< "\n\t\t\t7. Display Records";
cout<< "\n\t\t\t8. Delete All records";
cout<< "\n\t\t\t9. Delete Last record";
cout<< "\n\t\t\ts. Save list to file";
cout<< "\n\t\t\tr. Load a list";
cout<< "\n\t\tPress Q to quit anytime";
cout<< "\n\t\tPlease Enter Choice (1 - 9)";choice=getche();
switch(choice)
{
case '1':NODE *temp;
int num;
num=inputdata();
temp=create(num);
addathead(temp);temp=NULL;break;
case '2':
num=inputdata();
temp=create(num);
addattail(temp);temp=NULL;break;
case '3':NODE *newnode,*addnodeafter;
num=inputdata();
newnode=create(num);
cout<<"\n\n\t\tEnter data after which to add node :";cin>>num;
addnodeafter=search(num);
addafter(addnodeafter,newnode);
newnode=addnodeafter=NULL;
break;
case '4':
NODE *addnodebefore;
num=inputdata();
newnode=create(num);
cout<<"\n\n\t\tEnter data before which to add node :";cin>>num;
addnodebefore=search(num);
addbefore(addnodebefore,newnode);
newnode=addnodebefore=NULL;
break;
case '5':cout<<"\n\n\t\tTotal "<<nodecount<<" Records,Press a key to continue ...";
getch();break;
case '6':cout<<"\n\n\t\tEnter data for which to delete node :";cin>>num;
temp=search(num);
deletenode(temp);temp=NULL;break;
case '7':display();break;
case '8':deleteall();break;
case '9':deletelast();break;
case 's':save();break;
case 'r':loadlist();break;
case 'q':deleteall();exit(0);break;
case 'Q':deleteall();exit(0);break;
default : {cout<<"\n\n\t\tInvalid Choice ! Press a key to continue ...";
getch();}
}
}
system("PAUSE");
return EXIT_SUCCESS;
}
//************************************************************************
NODE* create(int num) // function returns a pointer(add) of NODE type(add of new node)
// null if node not created
//function is passed the value with which node to be populated
{
NODE *temp;
temp=new NODE;
if(temp) // Mem allocated sucessfully,ie temp not NULL
{
temp->data=num;
temp->next=NULL;//new node doesnt pt anywhere yet,till anothernode created
temp->prev=NULL;
return temp;
}
else
{
cout<<"\n\n\t\tOut of memory ! Press a key to continue ...";getch();
return NULL;
}
}
NODE* create() // function returns a pointer(add) of NODE type(add of new node)
// null if node not created,node data made=0
{
NODE *temp;
temp=new NODE;
if(temp) // Mem allocated sucessfully,ie temp not NULL
{
temp->data=0; //no data passed ,by default init to zero
temp->next=NULL;//new node doesnt pt anywhere yet,till anothernode created
temp->prev=NULL;
return temp;
}
else
{
cout<<"\n\n\t\tOut of memory ! Press a key to continue ... ";getch();
return NULL;
}
}
int inputdata() //Function inputs data from user and returns that data
{
int num;
cout<<"\n\n\n\t\tEnter the integer data to add to list : ";cin>>num;
return num;
}
void addathead(NODE *temp)// this function is passed pointer(an add of type NODE)
//and it links that node at the beg of list
{
if(temp)//add passed is not NULLL
{
if(first==NULL)//node being linked is the first node in the list
{
first=last=temp;
}
else
{
temp->next=first;
first->prev=temp;
first=temp;
}
nodecount++;
cout<<"\n\n\t\tAdded data to list. Press a key to continue ...";getch();
}else
{
cout<<"\n\n\t\tOut of Memory error. Node could not be added ! Press a key to continue ...";getch();
}
}
void addattail(NODE *temp)// this function is passed pointer(an add of type NODE)
//and it links that node at the end of list
{
if(temp)//add passed is not NULLL
{
if(first==NULL)//node being linked is the first node
{
first=last=temp;
}
else
{
temp->prev=last;
last->next=temp;
last=temp;
}
nodecount++;
cout<<"\n\n\t\tAdded data to list. Press a key to continue ...";getch();
}
else
{
cout<<"\n\n\t\tOut of Memory error. Node could not be added ! Press a key to continue ...";getch();
}
}
NODE* search(int searchdata)//returns pointer to (add of )node with givendata
//returns NULL for no match/no node exists
{
NODE *temp=first;
if(temp) //if first node exists
{
while(temp)// runs untill temp becomes NULL
{
if (temp->data==searchdata)
{
return temp; // return the add of node where match found
}
else
{
temp=temp->next;// go to next node
}
}
cout<<"\n\n\t\t Data not Found ! Press a key to continue ... to continue...";getch();
return temp ; // will return NULL at the end of last node
}
else
{
cout<<"\n\n\t\tNo Node Exists ! Press a key to continue ...";getch();
return NULL;
}
}
void addafter(NODE *nodetoaddafter,NODE *newnod)
//function is passed a ptr to a NODE(add of),the node after which to add
//node(nodetoaddafter),and the add of the node to be
//added(newnod)
{
if(nodetoaddafter)// NULL is not passed as the node to add after
{
NODE *temp;
temp=nodetoaddafter;
if(nodetoaddafter!=last)//node after which to add is not the last node
{
newnod->prev=nodetoaddafter;
newnod->next=nodetoaddafter->next;
temp->next=newnod;
}
else
{
newnod->prev=nodetoaddafter;
newnod->next=nodetoaddafter->next;
temp->next=newnod;
last=newnod;
}
nodecount++;
cout<<"\n\n\t\tAdded data to list. Press a key to continue ...";getch();
}
else
{
cout<<"\n\n\t\tOut of Memory error. Node could not be added ! Press a key to continue ...";getch();
}
}
void addbefore(NODE *nodetoaddbefore,NODE* newnode)
{
//fn is passed a ptr to a NODE(add of) //,the node before which to add
//node(nodetoaddbefore),and the add of the node to be
//added(newnode)
if(nodetoaddbefore)// NULL is not passed as the node to add before
{
NODE *temp=nodetoaddbefore;
if(nodetoaddbefore!=first)//node before which to add is not the first node
{
temp->prev->next=newnode;
newnode->next=temp;
newnode->prev=temp->prev;
temp->prev=newnode;
}
else
{
temp->prev->next=newnode;
newnode->next=temp;
newnode->prev=temp->prev;
temp->prev=newnode;
first=newnode;
}
nodecount++;
cout<<"\n\n\t\tAdded data to list. Press a key to continue ...";getch();
}
else
{
cout<<"\n\n\t\tOut of Memory error. Node could not be added ! Press a key to continue ...";getch();
}
}
void deletenode(NODE *nodetobedeleted)
//the add of node to be deleted is passed
{
if(nodetobedeleted)//add passed is not NULL
{
if(nodetobedeleted==first && nodetobedeleted==last)//only node
{
delete nodetobedeleted;
first=last=NULL;
}
else if(nodetobedeleted==first)
{
NODE *temp=first;
first=first->next;
delete temp;
first->prev=NULL;
}
else if(nodetobedeleted==last)
{
NODE *temp=last;
last=last->prev;//last changes
last->next=NULL;
delete temp;temp=NULL;
}
else // none of above,node in between
{
nodetobedeleted->prev->next=nodetobedeleted->next;
nodetobedeleted->next->prev=nodetobedeleted->prev;
delete nodetobedeleted;nodetobedeleted=NULL;
}
nodecount--;
cout<<"\n\n\t\tDeleted ! Press a key to continue ...";getch();
}
else
{
cout<<"\n\t\tcould not delete,Press a key to continue ... !";getch();
}
}
void display() //displays all the nodes in the list
{
NODE *temp;
temp=first;
cout<<"\n\n\n";
while(temp)
{
cout<<endl<<"\t\t\t"<<temp->data;
temp=temp->next;
}
cout<<"\n\n\t\t "<<nodecount<<" records displayed ,Press a key to continue .....";getch();
}
void deleteall()//deletes all the nodes in the list,sets global ptrs to
// to NULL
{
int count=nodecount;
cout<<"\n\n\t\t"<<count<<" existing records will be deleted ! (y/n) " ;char choice=getch();
if((choice=='Y'|| choice=='y'))
{
NODE *temp;
temp=first;
while(temp)
{
first=first->next;
delete temp;nodecount--;
temp=first;
}
first=last=NULL;
nodecount=0;
cout<<"\n\n\t\t"<<count<<" records deleted. Press a key to continue ..." ;getch();
}
}
void deletelast() // deletes the last node
{
NODE *t=last;
deletenode(t);
}
void save() // This saves the list in memory to a file joshi,bin in the
//current directory of the executable.it is to be noted that
//at the end of file NULL or 0 is stored,by default
//this had created a bug while trying to read the file
// see loadlist()
{
fstream listfile;
listfile.open("list.dls",ios::out) ;
NODE *temp;
temp=first;
while(temp!=NULL)
{
listfile.write((char*)temp,sizeof(int));
temp=temp->next;
}
listfile.close();
cout<<"\n\n\n\t\tLink list has been saved in file list.dls in current folder.";
cout<<"\n\n\t\tPress a key to continue ... ";getch();
}
void loadlist()
{
if(!(first==NULL)) //list not empty in memory
{
deleteall();//delete existing list in memory
}
fstream listfile;
listfile.open("list.dls",ios::in) ;
listfile.seekg(0);//set file ptr at the beg of file
while(!listfile.eof())
{
NODE *temp=create();//create a blank node
if(temp) //memory allocation successful
{
listfile.read((char*)temp,sizeof(temp->data));// read the start data to temp
// now,if the file was empty it still has null at the end
// so 0 is read
if (temp->data==NULL)// if file is empty or we are at end;
{
cout<<"\n\n\t\tFile is empty OR End of File reached ...";
cout<<"\n\n\t\t Press a key to continue ... !";getch();
delete temp;// no need to load a list now
}
else
{
//valid data read
cout<<"\n\n\t\tdata read from file :"<<temp->data;
addattail(temp); //addattail caters to the node being added to an empty list
}
}
else
{
cout<<"\nUnable to load list,Out of memory ! Press a key to continue ...";getch();
}
}
listfile.close();
}
That is all.
If you liked this article please do leave a reply and share it with friends.
Thanks.