dll.cpp

Implementation of a Doubly linked list.

#include<iostream.h>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
//using namespace std;
class node
{
    private:
    char *data;
    node *prev,*next;
    public:
    void append(node **,char*),addatbeg(node **,char *),display(node *),delatpos(node **,int),delatbeg(node **),delatend(node **),reverse(node **);
};
void node::append(node **h,char *ptr)
    {
	node *temp=(node *)malloc(sizeof(node)),*r=*h;
        if(temp==NULL)
            {
                cout<<"\nHeap Full!!"<<endl;
                exit(1);
            }
        else strcpy(temp->data,ptr);
        if(*h==NULL)//insert at beg
            {
                temp->prev=NULL;
		temp->next=NULL;
                *h=temp;
            }
        else
            {
                for(;r->next!=NULL;r=r->next);//r points to last node
                r->next=temp;
                temp->prev=r;
                temp->next=NULL;
            }
        cout<<"\nData appended!!"<<endl;
    }
void node::addatbeg(node **h,char *ptr)
    {
        node *temp=(node *)malloc(sizeof(node));
        if(temp==NULL)
            {
            cout<<"\nHeap Full!!"<<endl;
            exit(1);
            }
	else strcpy(temp->data,ptr);
        if(*h!=NULL)
        {
            (*h)->prev=temp;
            temp->next=*h;
            temp->prev=NULL;
            *h=temp;
        }
        else
        {
            temp->prev=NULL;
            temp->next=NULL;
            *h=temp;
        }
    cout<<"Data added at beginning!!"<<endl;
    }
void node::delatbeg(node **h)
{
    node*temp=*h;
    if(temp==NULL)
	cout<<"\nQueue Empty!!"<<endl;
    else
        {
            if(temp->next==NULL)
                {//temp is the only node
                    cout<<"\nFirst node deleted :"<<temp->data<<endl;
                    free(temp);
                    *h=NULL;
                }
            else
            {
                cout<<"\nFirst node deleted :"<<temp->data<<endl;
                temp->next->prev=NULL;
                *h=temp->next;
                free(temp);
            }
        }
}
void node::delatend(node **h)
    {
	node *temp=*h;
        if(temp==NULL)
                cout<<"\nQueue Empty!!"<<endl;
	else
	    {
		if(temp->next==NULL)//temp is the only node
		{
		    cout<<"\nLast node deleted :"<<temp->data<<endl;
		    free(temp);
		    *h=NULL;
		}
		else
		{
		    for(;temp->next!=NULL;temp=temp->next);//temp points to last node
		    temp->prev->next=NULL;
		    cout<<"\nLast node deleted :"<<temp->data<<endl;
		    free(temp);
		}
	    }
    }
void node::delatpos(node **h,int pos)
    {
	node *temp=*h;int i;
	    if(temp==NULL)
		cout<<"Queue Empty!!--No such Position!"<<endl;
	    else
	    {
		for(i=1;i!=pos && temp!=NULL;temp=temp->next,i++);//temp points to node to be deleted
		if(i<pos || i>pos)cout<<"\nNo such Node!!";
		else if(i==pos && temp!=NULL)
		    {
			if(temp->prev==NULL && temp->next==NULL)//temp is first & only node
			    {
				cout<<"\nNode at position "<<i<<" deleted,has data :"<<temp->data<<endl;
				free(temp);*h=NULL;
			    }
			else if(temp->prev==NULL)//temp is first node
			    {
				cout<<"\nNode at position "<<i<<" deleted,has data :"<<temp->data<<endl;
                                temp->next->prev=NULL;
				*h=temp->next;
                                free(temp);
                            }
                        else if(temp->next==NULL)//temp is last node
                            {
                                temp->prev->next=NULL;
                                cout<<"\nNode at position "<<i<<" deleted,has data :"<<temp->data<<endl;
                                free(temp);
                            }
                        else//temp is middle node
                            {
                                cout<<"\nNode at position "<<i<<" deleted,has data :"<<temp->data<<endl;
					  temp->next->prev=temp->prev;
                                temp->prev->next=temp->next;
                                free(temp);
                            }
                    }
            }
    }
void node::display(node *h)
    {
        int c=0;
        if(h==NULL)
            cout<<"\nQueue Empty!!"<<endl;
        else
        while(h!=NULL)
            {
                cout<<h->data<<"\t";c++;
                h=h->next;
	     }
	cout<<"\nNo of nodes in DLL is :"<<c<<endl;
    }
void node::reverse(node **h)
    {
	node *temp=*h,*r=NULL,*s;
	if(*h==NULL)
	    cout<<"\nList Empty!!"<<endl;
	else
	    {
		while(temp->next!=NULL)//temp is not the only node
		{
		    s=r;
		    r=temp;
		    temp=temp->next;
		    r->next=s;
		    r->prev=temp;
		}
	    temp->next=r;
	    temp->prev=NULL;
	    cout<<"\nList Reversed!!"<<endl;
	    *h=temp;
	    }
    }
int main()
{
    node *head=NULL,h;
    int ch,pos;char *str;
    flushall();
    do
    {
    cout<<"\nMENU\n1.append\n2.add at beg\n3.delete at beg\n4.del at end\n5.del at pos\n6.display\n7.reverse\n8.exit\nEnter your choice :";
    cin>>ch;
    switch(ch)
	{
	    case 1:
	    cout<<"\nEnter the string :";
	    cin>>str;
		h.append(&head,str);
		break;
		case 2:
		cout<<"\nEnter the string :";
	    cin>>str;
		h.addatbeg(&head,str);
	    break;
	    case 3:
	    h.delatbeg(&head);
	    break;
	    case 4:
	    h.delatend(&head);
	    break;
	    case 5:
	    cout<<"\nEnter the position of the node to be deleted :";
	    cin>>pos;
	    h.delatpos(&head,pos);
	    break;
	    case 6:
	    h.display(head);
	    break;
	    case 7:
	    h.reverse(&head);
	    break;
	    case 8:
	    exit(0);
	}
    }while(ch!=8);
return 0;
}