CODEWITHSUNDEEP
data-structuresqueuetime-complexity
Mitch A
Mitch A

Reputation: 2118

how do queues provide O(1) performance on takes/puts?

I assume the constant time performance of takes/puts is achieved by allowing consumers and producers to access the tail/head of the queue without locking each other. How is this achieved for in-memory queues? Does the answer change for durable queues (probably)? How is this solved in system that imposes a limit on producers and consumers of 1 each? How about when the system allows concurrent access?

Upvotes: 0

Views: 134

Answers (1)

Pritam Banerjee
Pritam Banerjee

Reputation: 18958

Queue uses doubly linked list as it's data structure. In fact queue in Java is declared like this:

Queue<SomeClass> q = new LinkedList<>();

LinkedList in Java is doubly linked list by default.

Now offer() or insertion at head is always O(1) as you don't need to traverse the whole list and same with poll() where you remove the tail and return it.

Now as far as concurrent access is concerned it should not have any effect on the time complexity of the code.

Upvotes: 0

Related Questions