CODEWITHSUNDEEP
java
Jonathan Bishop
Jonathan Bishop

Reputation: 167

ArrayList vs. Queue time complexity

If I am trying to remove the first element (index 0), would it be more time efficient to do list.remove(0) <- removes index 0 or use a queue and queue.dequeue(). I know delete for arraylist is o(n), does this still hold true if you provide the index to remove from? I am new to Java and algorithms, please bear with me if this is a dumb question

Upvotes: 0

Views: 1782

Answers (2)

prem kumar
prem kumar

Reputation: 5877

If I am trying to remove the first element (index 0), would it be more time efficient to do list.remove(0) <- removes index 0 or use a queue and queue.dequeue().

If you are removing always from beginning i.e. index 0 , then queue is better because it just needs to shift the head index and complexity is O(1) whereas for arraylist it involves left shifiting and complexity is O(n). Otherwise list is the choice if you want to remove random index.

I know delete for arraylist is o(n), does this still hold true if you provide the index to remove from?

Yes. Because when you delete an element at particular index in an arraylist, it leaves a hole(or gap). This has to be filled because arrays are contiguous. So we have to left shift all elements that are towards the right of the removed element.

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59194

Yes, ArrayList is only fast adding and removing close to the end. It takes O(N) time to add or remove at or near the beginning even if you provide in index.

If you need a queue, use ArrayDeque. It's fast at both ends.

Upvotes: 1

Related Questions