How to find Middle Element of Doubly Linked List?

Today we will be discussing how to find middle element of doubly linked list. But if you are new to doubly linked list then please refer to this link where I have explained everything about linked lists. Suppose you have a doubly linked list like 1-2-3-4-5 then the middle of this list will be 3. So, let's discuss the procedure to solve this problem.

Procedure

1. First we will make a linked list.

2. Then we will count the number of nodes in the doubly linked list.

• A list which will have even number of nodes will have 2 middle nodes at position 'n/2' and 'n/2+1' (n is number of nodes in a list).
• A list which will have odd number of nodes will have 1 middle element only at position (n+1)/2 (n is number of nodes in a list).

3. Then depending on even or odd number of nodes we will iterate the list till the positions mentioned above and print the values.

Code

#include<iostream> using namespace std; struct node{ int data; struct node* next; struct node* prev; }; struct node* head=NULL; class doubly { public: void insert(int x) { struct node* temp=new node(); temp->data=x; if(head==NULL) { head=temp; temp->prev=NULL; temp->next=NULL; } else { struct node* temp1=head; while(temp1->next!=NULL) { temp1=temp1->next; } temp->prev=temp1; temp1->next=temp; temp->next=NULL; } } void middle() { struct node* temp=head; int c=0; while(temp!=NULL) { c++; temp=temp->next; } temp=head; int p=1; if(c%2==0) { int mid=c/2; while(temp!=NULL) { if(p==mid) break; p++; temp=temp->next; } cout<<temp->data<<" "<<temp->next->data<<endl; } else { int mid=(c+1)/2; while(temp!=NULL) { if(p==mid) break; p++; temp=temp->next; } cout<<temp->data<<endl; } } void disp() { struct node* temp=head; while(temp!=NULL) { cout<<temp->data<<" "; temp=temp->next; } } }; int main() { doubly l; l.insert(3); l.insert(5); l.insert(1); l.insert(4); l.insert(8); l.insert(7); l.insert(0); l.insert(2); l.disp(); cout<<endl; l.middle(); return 0; }

Explanation of Code (line by line)

1. First we will write a simple code of linked list which will have 2 functions:

     - insert() - which will insert elements in the doubly linked list.
     - disp() - which will display the doubly linked list.

2. Insert some values in the doubly linked list.
3. Now we have created a function named middle() which will print the middle element of doubly linked list.
4. First we have created a 'temp' which is pointer to node. Then we have created some other variables like 'c=0', 'mid', 'p=1'.
5. Then we have started a while loop to count number of nodes in the list. The number of nodes are stored in variable 'c'.
6. Then we have initialized temp to head.
7. Then there is an if condition which checks if c%2==0 or not i.e number of nodes in the list are even or not.
8. If the number of nodes in the list are even then we have stored the middle value c/2 in a variable mid.
9. Then we have started a while loop which will iterate till 'mid' in the list. If 'p' is equal to 'mid' then we will break out of the loop because we have reached the middle of the list. Otherwise we will increment p and temp.
     while(temp!=NULL)
     {
          if(p==mid)
                break;
          p++;
          temp=temp->next;
     }
10. Then we have printed the middle values. First we have printed temp->data which will display the first middle node the we have printed the second middle value by using temp->next->data which will point to the data part of the next of the first middle value.
11. If the number of nodes in the list are not even the they will be odd. So the next if condition where we have checked if c%2!=0 is for odd number of nodes.
12.  If the number of nodes in the list are odd then we have stored the middle value (c+1)/2 in a variable mid.
13. Then we have started a while loop which will iterate till 'mid' in the list. If 'p' is equal to 'mid' then we will break out of the loop because we have reached the middle of the list. Otherwise we will increment p and temp.
      while(temp!=NULL)
      {
             if(p==mid)
                    break;
             p++;
             temp=temp->next;
      }
14. Then we have simply printed the value at mid by using temp->data which is the middle element.



You can follow me here if you are interested : 

https://github.com/mayank171

https://www.linkedin.com/in/mayank-mewar-586090173/