complete c/c++ program to delete middle node from singly linked list

By | February 14, 2017

Deleting middle node from singly linked list means deleting the mid element/nth element out of existing linked list.

Before we jump into the Algorithm,lets understand main steps in solving the problem.we will go by step by step.

Move on…

Program to delete middle node from singly linked list

Program to delete middle node from singly linked list

Step 1: Move the Pointer up to “n” th node in linked list.

delete node from singly linkedlist diagram 1

                              delete node from singly linkedlist diagram 1

Step 2:   store (n-1)th node address into temporary variable.

delete node from singly linkedlist diagram 2

                                     delete node from singly linkedlist diagram 2

Step 3: connect (n-1)th  node to (n+1)node.

delete node from singly linkedlist diagram 3

                               delete node from singly linkedlist diagram 3

Step 4: free the memory of nth node.that is the Node “30”th.

You are done :).

If you understand,what we have done in the above diagrams,you have understood the 99% logic.

Let’s go to the Algorithm ( with simple If else conditions,we called it as pseudo code )

Algorithm to delete middle element of linked list.

Input: Head of the linked list,nth element to delete.

Begin:

                if (head == NULL)
                    print ("List is empty")
                End if
                Else Then
                    deleteElement= head
                    prevnode_delete = head

                    For i =2 to n do
                        prevnode_delete = deleteElement
                        deleteElement=  delete.next;
 
                        if ( deleteElement= NULL )
                        break;
                        End If
                    End For

                    if ( deleteElement!= NULL ) then
                        If ( deleteElement== head)
                        head = head.next
                        End if
                        prevnode_delete.next = delete.next
                        deleteElement.next = NULL
                        free (deleteElement)

                     End If

                 End Else
End

I have copied whole code ,which i have used for testing.



#include <bits/stdc++.h>
#include <string.h>
using namespace std;
// Structure of node.It contains two elements.one is string.
// Second one is Pointer to Node
 
struct node
{
 int data;
 struct node* next;
};
 
/* Function to create a new node with given data */
node* newNode(int data)
{
 node *new_node = new node;
 new_node->data = data;
 new_node->next = NULL;
 return new_node;
}
node* GenerateLinkedList(int n)
{
 int data;
 int i;
 
 struct node *temp;
 struct node *headtemp;
 struct node *head;
 struct node *newlycreatednode;
 
 printf("Enter the data of first node:-\n\n");
 cin >> data;
 cout << endl << endl;
 
 head = newNode(data);
 temp = head;
 //this loop will be executed,if it is more than 2 nodes.
 for(i=2; i<=n; i++)
 {
 printf("Enter the data of %d node:-\n\n",i);
 cin >> data;
 cout << endl << endl;
 newlycreatednode = newNode(data);
 newlycreatednode->next = NULL;
 
 temp->next = newlycreatednode;
 temp = temp->next;
 }
 
 printf("Linked List Created with nodes - %d successfully \n\n",n);
 
 return head;//return reference to head element of the linked list.
}

void displayLinkedList(node *head)
{
 struct node *temp;
 
 if(head == NULL)
 {
 printf("LinkedList is empty.\n\n");
 }
 else
 {
 temp = head;
 printf("Displaying linked List.\n\n");
 
 while(temp != NULL)
 {
 cout<<temp->data<<"=====>";
 temp = temp->next;
 }
 
 printf("END\n\n");
 }
}
void delete_nthElement(node* head,int deletePosition)
{
 int i;
 struct node *deleteElement, *prevnode_delete ;

 if(head == NULL)
 {
 printf("Linkedlist is empty,nothing to delete\n");
 
 }
 else
 {
 deleteElement = head;
 prevnode_delete = head;
 
 /* Below for loop is mainly used for finding given position is valid OR not */
 for(i=2; i<=deletePosition; i++)
 {
 prevnode_delete = deleteElement;
 deleteElement = deleteElement->next;

 if(deleteElement == NULL)
 break;
 }

 if(deleteElement != NULL)
 {
 if(deleteElement == head)
 head = head->next;

 prevnode_delete->next = deleteElement->next;
 deleteElement->next = NULL;

 printf("WE HAVE DELETED NODE VALUE - %d FROM LINKED LIST\n",deleteElement->data);
 
 free(deleteElement);

 printf("WE HAVE DELETED MEMORY of DELETED NODE FROM LINKED LIST\n");
 
 }
 else
 {
 printf("SORRY,WE DONT HAVE THE POSITION - %d ,WHICH YOU ARE TRYING TO DELETE FROM LIST.",deletePosition);
 
 }
 }
}

//Input Program to pass
//If we combine the all the characters in the String:Saippuakivikauppias
//Main program
int main()
{
 int n, position;
 int confirmation=0;
 int deletePosition;
 
 /* It will create Linked List with given N nodes*/
 printf("Enter the total number of nodes to create: \n\n");
 scanf("%d", &n);
 
 node* head=GenerateLinkedList(n);//Head of the linked list is stored in "head".
 
 printf("Existing Linked List Elements as Below \n");
 
 //Display created linked list.
 displayLinkedList(head);
 
 printf("Which Element,you want to delete from linked list ?? \n\n");
 printf("Option1 : Enter 1000 for deleting Middle Element,you can change value 1000->some other value,if you want ?? \n\n");
 printf("Option2 : Enter element less than size of the linked list for deleting Nth Element ?? \n\n");
 scanf("%d",&deletePosition);
 
 if(deletePosition == 1000)
 {
 printf("Deleting Mid Element = %d of Linked List \n\n",n/2 + 1);
 delete_nthElement(head,n/2 + 1); //Pass Mid Element to Method
 }
 else
 {
 printf("Deleting Nth=%d Element from Linked List \n\n",n);
 delete_nthElement(head,deletePosition); //Pass Mid Element to Method
 }
 
 printf("Existing Linked List Elements After Deletion of Head Element \n\n");
 
 //Display created linked list.
 displayLinkedList(head);
 
 return 0;
}

 

How to compile the Program.
C:\MinGW\bin>g++ deletemiddleelementlinkedlist.cpp -o deletemiddleelement.exe

How to Run the Program.
C:\MinGW\bin>deletemiddleelement.exe

Enter the total number of nodes to create:
3
Enter the data of first node:-
10
Enter the data of 2 node:-
20
Enter the data of 3 node:-
30
Linked List Created with nodes - 3 successfully
Existing Linked List Elements as Below

Displaying linked List.
10=====>20=====>30=====>END

Which Element,you want to delete from linked list ??
Option1 : Enter 1000 for deleting Middle Element,you can change value 1000->some other value,if you want ??
Option2 : Enter element less than size of the linked list for deleting Nth Element ??

1000
Deleting Mid Element = 2 of Linked List
WE HAVE DELETED NODE VALUE - 20 FROM LINKED LIST
WE HAVE DELETED MEMORY of DELETED NODE FROM LINKED LIST
Existing Linked List Elements After Deletion of Head Element

Displaying linked List.

10=====>30=====>END

C:\MinGW\bin>

Hope you have enjoyed the “Simplylearning” on the “delete middle node from singly linked list”

The following two tabs change content below.

SRINIVAS DARIPELLI

Myself SRINIVAS DARIPELLI. I have 15+ Years of Experience in Programming worked on multiple technologies.Apart from it,I am a blogger, writer, editor, artist and dad 🙂 .I believe in reality.I love to share the Helpful things around the Technology. Feel free to connect with me

Leave a Reply