CODEWITHSUNDEEP
javaalgorithmtime-complexity
WebQube
WebQube

Reputation: 8981

How does pop perform in O(1) in Java Queue Implementation?

I have read in here that Java's Queue pop in O(1).

We know that push and pop are constant time operations [O(1) to be precise (Do you know why?)].

What I don't Understand is - how? If it's a linked list then it can't be O(1) because it has to save the last item. If it's a doubly linked list then it can. But is it a doubly linked list?

Upvotes: 1

Views: 1000

Answers (2)

V G
V G

Reputation: 19002

Simply take a look at the implementation of the LinkedList: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#LinkedList (the Deque<E> interface extends the Queue<E> interface).

Upvotes: 0

Bartek Maraszek
Bartek Maraszek

Reputation: 1414

Quote from Java 7 API:

public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).

So yes, it's doubly-linked.

Upvotes: 4

Related Questions