CODEWITHSUNDEEP
linked-list
Newbie
Newbie

Reputation: 2708

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

I am trying to find the middle element of a double linked list in constant time complexity . I came across the following http://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation/ solution. But I don't understand how to use the middle pointer. Can anyone please help me understand this or give me a better solution .

Upvotes: 0

Views: 2078

Answers (2)

Ediac
Ediac

Reputation: 853

I've re-written this code in C++ for 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 and pop functions are self-explanatory, they add nodes on top of the stack and delete the node on the top. In this code, the function UpdateMiddle is in charge of managing the mid pointer whenever a node is added or deleted. Its parameter _add tells it whether a node has been added or deleted. This info is important when there is more than two nodes.

Note that when the UpdateMiddle is called within push or pop, the counter has already been increased or decreased respectively. Let's start with the base case, where there is 0 nodes. mid will simply be a nullptr. When there is one node, mid will be that one node.

Now let's take the list of numbers "5,4,3,2,1". Currently the mid is 3 and count, the amount of nodes, is 5 an odd number. Let's add a 6. It will now be "6,5,4,3,2,1" and count will now be 6 an even number. The mid should also now be 4, as it is the first in the middle, but it still hasn't updated. However, now if we add 7 it will be "7,6,5,4,3,2,1", the count will be 7, an odd number, but notice that the mid wont change, it should still be 4.

A pattern can be observed from this. When adding a node, and count changes from even to odd, the mid stays the same, but from odd to even mid changes position. More specifically, it moves one position to the left. That is basically what UpdateMiddle does. By checking whether count is currently odd or even after adding or deleting a node, it decides if mid should be repositioned or not. It is also important to tell whether a node is added or deleted because the logic works in reverse to adding when deleting. This is basically the logic that is being applied in the code you linked.

This algorith works because the position of mid should be correct at all times before adding or deleting, and function UpdateMiddle assumes that the only changes were the addition or deletion of a node, and that prior to this addition or deletion the position of mid was correct. However, we make sure of this by making the attributes and our function UpdateMiddle private, and making it modifiable through the public functions.

Upvotes: 1

johnjps111
johnjps111

Reputation: 1170

The trick is that you don't find it via a search, rather you constantly maintain it as a property of the list. In your link, they define a structure that contains the head node, the middle node, and the number of nodes; since the middle node is a property of the structure, you can return it by simply accessing it directly at any time. From there, the trick is to maintain it: so the push and pop functions have to adjust the middle node, which is also shown in the code.

More depth: maintaining the middle node: we know given the count that for an odd number of nodes (say 9), the middle node is "number of nodes divided by 2 rounded up," so 9/2 = 4.5 rounded up = the 5th node. So if you start with a list of 8 nodes, and add a node, the new count is 9, and you'll need to shift the middle node to the "next" node. That is what they are doing when they check if the new count is even.

Upvotes: 1

Related Questions