CODEWITHSUNDEEP
javaooparraylistcollections
ieXcept
ieXcept

Reputation: 1127

Why ArrayList doesn't implements Queue?

Maybe it's silly, but I have to know the answer. I am scratching my head looking at its source code and doesn't see any reason why authors implement Queue in LinkedList, but decided not to do the same with ArrayList, instead they have created separate class ArrayDeque.

Upvotes: 13

Views: 5662

Answers (3)

Nilay Kumar Paul
Nilay Kumar Paul

Reputation: 1

As Boris the Spider said, I am continuing his explantation.

Now, when we remove an item from the beginning and the end of an array or list, it takes O(1) running time, because it just goes there and removes it, no need to use the loop.

But, in the queue, if we use ArrayList.remove() method, it will remove the last element, it violates the principle of the queue, cause first in first out, we need to remove the first element as per the principle, which is not achievable with ArrayList. To delete the first item with the remove() method, we have to reach index 0 by using a loop then we can delete the value of that index. That takes O(n) running time. So, it is not beneficial for us.

We can use PriorityQueue(), LinkedList() implementation with Queue interface.

Upvotes: 0

Boris the Spider
Boris the Spider

Reputation: 61158

The interface Queue requires that add adds items to the end of the Queue and remove takes elements from the start of the Queue.

(pseudo code)

Queue<String> q = ...
q.add("A")
q.add("B")
q.add("C")
//q is now [A,B,C]
String a = q.remove()
// a is A and q is [B, C]

Now; with an ArrayList, the remove operation would be O(n) - I would imagine that the API designers decided that this performance is unacceptable.

remove is O(n) because it requires reindexing the whole list - B is now 0 and C is now 1. LinkedList does not have this problem as it uses a linked list datastructure; it just remove the head node and sets the child of that node to be the new head node.

ArrayDeque is a different design to support this in O(1) - it is therefore not a List.

Upvotes: 9

Kayaman
Kayaman

Reputation: 73558

Most likely because it wouldn't be very performant as a Queue, since adding to (well, removing from in the case of Queue) the beginning is an O(N) operation instead of O(1). ArrayDeque on the other hand is a different design, since it's not a List and therefore doesn't need to provide random access.

Upvotes: 1

Related Questions