Are Java's collections interface and class hierarchy ill done?

Question

I came to know that in Java, LinkedList class implements both Deque and List interfaces. And this was somewhat confusing to me.

In computer science syllabus, I was never taught that queue can be a list, or more precisely queue can behave like a list. That is, there is stuff that lists can do, but queues can't. But the list can behave like a queue. For example, List interface has the following methods:

add(E e)
add(int index, E element)

But Queue has only the following:

add(E e)

So clearly Queue is not allowed to insert at specific index, which is allowed in List. The same is the case with other operations like Queue.remove() vs. List.remove(int index), List.get(int index) vs. Queue.peek(). In other words, list is a more generalized data structure and can emulate Queue.

Now being capable to emulate is different from having a contract subset. That is, Queue disallows certain operations (indexing) of Listand allows certain operations done only in a particular manner (insert only at the tail and remove only from the head). So Queue does not really do "addition" to the contracts of List. That is precisely why Queue does not extend List in Java collections framework, but both extend Collection interface. I believe that is also why it's incorrect for any class to implement both, as Queue's contract conflicts with the contract of List (which is why they fork out from Collection interface separately). However, LinkedList implements both the interfaces.

I also came across this answer:

The LinkedList implementation happens to satisfy the Deque contract, so why not make it implement the interface?

I still don't get how we can say "LinkedList implementation happens to satisfy the Deque contract". The concept of a queue does not allow insertion at an arbitrary index. Hence, the Queue interface does not have such methods.

However we can only enforce contracts through interfaces and cannot disallow implementation of certain methods. Being list (having "List" in its name), I feel it's not correct to have queue methods peek(), pop() and add(int index, E element) in LinkedList.

I believe, instead we should have separate class LinkedQueue which can have linked implementation for queue, similar to LinkedBlockingQueue which contains linked implementation of BlockingQueue.

Also note that LinkedList is the only class which inherits from both families of lists and queues, that is, there is no other class which implements both List and Queue (AFAIK). Can this be indication that LinkedList is ill done?

Am I plain wrong and thinking unnecessarily?

Answer 1

You're entirely missing the point of programming to interface.

If you need a Queue, you never write:

LinkedList<String> queue = new LinkedList<>();

Because, you're right, that would allow you to use non-queue methods. Instead, you program to the interface like this:

Queue<String> queue = new LinkedList<>();

Now you only have access to the 6 Queue methods (and all the Collection methods). So, even though LinkedList implements more methods, you no longer have access to them.

So, if you need a Queue, you choose the implementation of the Queue interface that best suits the performance, storage, and access characteristics you need, e.g.

• LinkedList uses more memory, but it shrinks when queue is emptied.

• ArrayDeque uses less memory, but it doesn't shrink.

• PriorityQueue is a non-FIFO queue with element priority.

• ConcurrentLinkedQueue, ConcurrentLinkedDeque supports multi-threaded concurrent access.

• and more...

---

I was never taught that queue can be a list, or more precisely queue can behave like a list.

Remember that implements defines a behaves like relationship. A LinkedList behaves like a List. A LinkedList behaves like a Deque. A LinkedList behaves like a Queue.

But just because LinkedList behaves like all of those, doesn't mean that List behaves like a Queue or that Queue behaves like a List. They do not.

The behaves like relation only goes one way.

Answer 2

@Andreas's answer is excellent, so mine targets your arguments about what you were or were not taught:

In computer science syllabus, I was never taught that queue can be a list or more precisely queue can behave like a list

A queue is not just any list, but a special kind of list, with its own special properties and constraints.

That is, there is stuff that lists can do, but queues can't.

No, List can do nothing. It provides possibilities to be implemented by a class and if that class decides to implement them then that class can do all that stuff.

But the list can behave like a queue.

No, List does not behave; it only suggests behaviors and classes that implement it can accept all or a subset of them or they can define new ones.