Queue<Integer> q = new LinkedList<Integer>()

Question

Here is an answer to "How do I instantiate a Queue object in java?",

Queue is an interface. You can't instantiate an interface directly except via an anonymous inner class. Typically this isn't what you want to do for a collection. Instead, choose an existing implementation. For example:

Queue q = new LinkedList();

or

Queue q = new ArrayDeque();

Typically you pick a collection implementation by the performance and concurrency characteristics you're interested in.

How does this work? What does it mean for Queue, an interface, to take on the implementation of LinkedList?

Does that mean objects can be dequeued in a FIFO (first-in-first-out order), and calling linked list methods on q would work?

Solution

To explain with a (perhaps somewhat flawed) metaphor - think of a LinkedList as a piece of paper. Think of the assignment to a Queue as covering all but a little part of this piece of paper which reveals that it's a Queue.

If you call a Queue method on it, it will still do things like a LinkedList normally would, since that that's what the piece of paper is.

Given that most of it is covered, you can't see it's a LinkedList, all you can see is that it's a Queue, so you can only call the Queue methods on it.

The whole piece of paper is still there - you could simply remove the covering, which would be synonymous to casting it back to a LinkedList, which would then allow you to call any LinkedList method on it again.

---

Now for a bit more technical details:

By the way a LinkedList "normally would" do things I mentioned above, I mean a LinkedList is always a linked-list, even if you assign it to a Queue - it doesn't suddenly start using an array as the underlying implementation, as an ArrayDeque would (which also implements Queue), or something else.

Queue doesn't actually need to be FIFO (see the docs) (if it needed to be, a LinkedList would also need to be), so LinkedList would have quite a bit of freedom in this regard, so let's continue this explanation using Deque - it has methods to support addition and removal from either the front or the back.

Because LinkedList implements Deque, it needs to implement the addFirst function. Based on the docs, the addFirst function needs to add to the front of the Deque, and indeed, with a LinkedList, it will add to the front of the LinkedList (while the front of the LinkedList doesn't need to be the front of the Deque, by looking at the Deque methods implemented in LinkedList, we see that the front of the Deque is the front of the LinkedList, and all the methods add to / remove from one of the sides, do so from the correct side).

Now for an important albeit somewhat confusing note - LinkedList can, for example, implement Deque and have an addFirst that doesn't do what it's supposed to - it can just, for example, print some random text. There's nothing in the language itself that prevents this - since, as far as the compiler is concerned, implementing Deque just requires that you define a bunch of methods - there's no enforcement of what these methods are supposed to do. In terms of the Java API, and any decent library, it should be safe to assume that every class implementing an interface will conform to what that interface claims to do, but just keep in mind that there isn't something stopping it from not conforming when it comes to more shady libraries or less experienced programmers.

Comments

[user3301555]

How does its doing things like a LinkedList "normally would" do affect the add method in Queue? Would it still be FIFO?

[Bernhard Barker]

@user3301555 I edited my answer with quite a bit more details which I hope will answer your question.