CODEWITHSUNDEEP
c++c++11memory-managementlinked-listqueue
Redwanul Haque Sourave
Redwanul Haque Sourave

Reputation: 584

How to destroy a queue efficiently?

I implemented a queue data structure of my own. I implemented the queue using unidirectional linked list. And it is implemented in a class definition. The head of the linked list is pointing to the front of the queue and the tail of the linked list is pointing to the end of the queue. Note, I kept the tail only to make the push operation in O(1) time.

Now the push function of the class dynamically allocates memory for a value and then pushes it to the end of list. And the pop function frees the memory allocated for the value at the front.

When the queue is being destructed (Goes out of the scope) I wanted to free the allocated memory, and so I wrote a destructor for the queue. My destructor traverses the whole linked list and deletes each element of the linked list. The time complexity of this is O(n). Is there any way to reduce the time complexity of the queue? Is it possible to destroy the queue in O(1)? If I had only deallocated the head of the linked list, the rest elements of the linked list will not be deleted, and as the head will be deleted, there will be no way to delete the other elements of the linked list. How is the STL queue's destructor is implemented? Does it destroys the whole queue in O(1) or O(n)?

Here's the code of the destructor of my_queue:

/*
Node is a struct which is the nodes of the linked list.
It has two attributes: val(of type char) and next(of type node*)
*/
my_queue :: ~my_queue(){
    node * temp;
    while(head != NULL){
        temp = head;
        head = head->next;
        delete temp;
    }
    sz = 0;
    tail = NULL;
}

Upvotes: 1

Views: 8054

Answers (1)

eerorika
eerorika

Reputation: 238311

Is it possible to destroy the queue in O(1)?

Not if you intend to keep using a linked list. O(n) is optimal asymptotic complexity for destruction of a linked list (or any node based data structure).

Also not if you store objects with non-trivial destructors. You cannot call N destructors in constant time.

If you choose another data structure to implement your queue, then perhaps. A dynamically growing array (i.e. a vector) can be destroyed in constant time, if the elements are trivially destructible.

How is the STL queue's destructor is implemented? Does it destroys the whole queue in O(1) or O(n)?

std::queue is just a wrapper for a lower level container. Its destructor simply destroys the underlying container, that you have chosen. The complexity is whatever the complexity of that container's destructor is. O(n) for any container of objects with non-trivial destructor, and for all std::deque or std::list, O(1) for std::vector of elements with trivial destructor.

Here, the complexity is descibed in terms of calls to free or whatever deallocates the memory. The complexity of free itself might not be guaranteed to be constant.

Upvotes: 1

Related Questions