1

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?

Artjom B.
  • 61,146
  • 24
  • 125
  • 222
WebQube
  • 8,510
  • 12
  • 51
  • 93
  • 1
    I would guess this is the case because references to the first and last element are stored internally. – Codor Jul 18 '14 at 08:05
  • It would be quite cruel if they had implemented `LinkedList` as singly linked. "Hey, let's make sure nobody ever uses this!". – Kayaman Jul 18 '14 at 08:08
  • They use double-linked list for internal implementation. You can google more for this data structure :) – hqt Jul 18 '14 at 08:09
  • See also http://stackoverflow.com/questions/984925/what-is-a-data-structure-that-has-o1-for-append-prepend-and-retrieve-element – Raedwald Jul 18 '14 at 08:19
  • See also http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist – Raedwald Jul 18 '14 at 08:23

2 Answers2

4

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.

Bartek Maraszek
  • 1,404
  • 2
  • 14
  • 31
0

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).

V G
  • 18,822
  • 6
  • 51
  • 89