Find middle element of a double linked list in constant time complexity -

i trying find middle element of double linked list in constant time complexity . came across following http://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation/ solution. don't understand how use middle pointer. can please me understand or give me better solution .

i've re-written code in c++ explanation purposes:

#include <iostream>  typedef class node* pnode; class node{ public:     pnode next;     pnode prev;     int data;     node(){         next = nullptr;         prev = nullptr;         data = 0;     } };  class list{ private:     //attributes     pnode head;     pnode mid;     int count;     //methods     void updatemiddle( bool _add );  public:     //constructors      list(){         head = nullptr;         mid = nullptr;         count = 0;     }     ~list(){         while( head != nullptr ){             this->delmiddle();             std::cout << count << std::endl;         }     }     //methods     void push( int _data );     void pop();     int findmiddle();     void delmiddle(); };  void list::updatemiddle( bool _add ){     if( count == 0 ){         mid = nullptr;     }     else if( count == 1 ){         mid = head;     }     else{         int remainder = count%2;         if(_add){             if( remainder == 0 ){                 mid = mid->prev;             }         }         else{             if( remainder == 1 ){                 mid = mid->next;             }         }     } }  void list::push( int _data ){     pnode new_node = new node();      new_node->data = _data;     new_node->prev = nullptr;     new_node->next = head;      if( head != nullptr ) head->prev = new_node;     head = new_node;     count++;      updatemiddle( true ); }  void list::pop(){     if( head != nullptr ){         pnode del_node = head;         head = head->next;           if( head != nullptr ) head->prev = nullptr;          delete del_node;         count--;         updatemiddle(false);     }     else if( count != 0 ){         std::cout << "error";         return;     } }  int list::findmiddle(){     if( count > 0 ) return mid->data;     else return -1; }  void list::delmiddle(){     if( mid != nullptr ){         if( count == 1 || count == 2){             this->pop();         }         else{             pnode del_mid = mid;             int remainder = count%2;              if( remainder == 0 ){                 mid = del_mid->next;                 mid->prev = del_mid->prev;                 del_mid->prev->next = mid;                 delete del_mid;                 count--;             }             else{                 mid = del_mid->prev;                 mid->next = del_mid->next;                 del_mid->next->prev = mid;                 delete del_mid;                 count--;             }         }     } } 

the push , pop functions self-explanatory, add nodes on top of stack , delete node on top. in code, function updatemiddle in charge of managing mid pointer whenever node added or deleted. parameter _add tells whether node has been added or deleted. info important when there more 2 nodes.

note when updatemiddle called within push or pop, counter has been increased or decreased respectively. let's start base case, there 0 nodes. mid nullptr. when there 1 node, mid 1 node.

now let's take list of numbers "5,4,3,2,1". mid 3 , count, amount of nodes, 5 odd number. let's add 6. "6,5,4,3,2,1" , count 6 number. mid should 4, first in middle, still hasn't updated. however, if add 7 "7,6,5,4,3,2,1", count 7, odd number, notice mid wont change, should still 4.

a pattern can observed this. when adding node, , count changes odd, mid stays same, odd mid changes position. more specifically, moves 1 position left. updatemiddle does. checking whether count odd or after adding or deleting node, decides if mid should repositioned or not. important tell whether node added or deleted because logic works in reverse adding when deleting. logic being applied in code linked.

this algorith works because position of mid should correct @ times before adding or deleting, , function updatemiddle assumes changes addition or deletion of node, , prior addition or deletion position of mid correct. however, make sure of making attributes , our function updatemiddle private, , making modifiable through public functions.