Doubly linked list in c++

 

TABLE OF CONTENT

 

 Illustration for the following operations.

•      Insert First
•       Insert Before First
•        Insert After  (To insert node after the integer value given in the parameter list)
•        Insert Before Last
•        Delete First
•        Delete Last
•        Delete This (Delete the node with the given integer Value)

Implement the all seven mentioned operations in c++.

•          Insert First 
•      Insert Before First
• .       Insert After  (To insert node after the integer value given in the parameter list)
• .       Insert Before Last
• .       Delete First
• .       Delete Last
• .       Delete This (Delete the node with the given integer Value

Question No. 1

Draw illustration for the following operations of Doubly Link list of integer data.

8.      

•          Insert First 
•      Insert Before First
• .       Insert After  (To insert node after the integer value given in the parameter list)
• .       Insert Before Last
• .       Delete First
• .       Delete Last
• .       Delete This (Delete the node with the given integer Value

               DOUBLY LINKED LIST

A DOUBLY LINKED LIST IS THE COLLECTION OF NODES . NODE HAVE THREE PARTS DATA PARTS AND TWO POINTERS WHICH IS NEXT AND PREVIOUS.

                              

 

Doubly link list Representation

 

Each node carries a data field(s) and two pointers called next and prev.

Each node is linked with its next link using its next pointer.

Each node is linked with its previous link using its previous link.                                                                     The last next carries a link as null to mark the end of the list.

Insert first

                       

Insert Before First

 

 

 InsertAfter  (To insert node after the integer value given in the parameter list)

 

 

 Insert Before Last

 

 

 Delete First

 

 

Delete Last

 

 

Delete This (Delete the node with the given integer Value)

 

 

Question No. 2

Implement the all seven mentioned operations (in Question No. 1) in c++.

Insert First

node* insert_node(int value)
{
	
	node* first_node = new node;
	first_node->data=value;
	first_node->next=NULL;
	first_node->previous=NULL;
	head=first_node;
	tail=first_node;
	return first_node;
}

 

Insert Before First

node* insert_before_first(int value)
{

    node* new_node = new node;
    new_node->data=value;
    new_node->next=head;
    new_node->previous=NULL;
	if(head!= NULL)
	{
		head->previous=new_node;
	}
	
	head=new_node;
	return new_node;
}

Insert After  (To insert node after the integer value given in the parameter list)

node* insert_position (int value , int position)
{
	
	node * new_node = new node;
	node * temp= new node;
	temp = head;
	for(int i=1 ; i<position-1 ; i++)
	{
	     temp = temp->next;
	}
	new_node->data = value;
	new_node->next = temp -> next;
	new_node->previous = temp;
	temp->next = new_node;
	return new_node;
}

Insert Before Last

node * insert_before_last(int value)
{
	
	node * new_node = new node;
	node * current = new node;
	current = head;
	while(current->next!=NULL)
	{
		current=current->next;
	} 
	new_node->data = value;
	
	new_node->next=current;
	new_node->previous=current->previous;
	current->previous->next=new_node;
	return new_node;
}

Delete First

void delete_first ()
{
	node * temp = new node;
	temp = head;
	head = head->next;
	head->previous = NULL;
	delete temp;
}

Delete Last

void delete_last ()
{
	node *current = new node;
 	node *previous = new node;
 	current=head;
 	while(current->next!=NULL)
 	{
 		previous=current;
 		current=current->next;
	 }
	 tail=previous;
	 previous->next=NULL;
	 delete current;
	
}

Delete This (Delete the node with the given integer Value)

void delete_position( int pos)
{
	node * current = new node;
    current = head ;
    for(int i=1 ; i<pos ; i++)
    {
    	current = current->next;
	}
	current->previous->next=current->next;
	current->next->previous=current->previous;
	
	

}