5

I was looking at the java implementation of LinkedList, and found this:

public class LinkedList<E> 
       extends AbstractSequentialList<E> implements List<E>,
               Deque<E>, Cloneable, java.io.Serializable

Why should a LinkedList support the Deque interface? I understand the desire to add elements to the end of the linked list, but those methods should have been incuded in the List interface.

Abhijeet Kashnia
  • 12,290
  • 8
  • 38
  • 50
  • 1
    Just because you can implement a queue with a linkedlist? – Thomas Jungblut May 05 '11 at 10:25
  • 3
    Not all Lists are Deques and not all Deques are Lists. – Peter Lawrey May 05 '11 at 10:33
  • I now understand that the list interface cannot be changed just because one of the implementations happens to be a linked list, and linked list can easily accommodate the deque operations. I probably would have defined a linkedlist interface which extends the list interface and the deque interface. And then defined a linkedlistImpl class. So, I guess "The LinkedList implementation happens to to satisfy the Deque contract, so why not make it implement the interface?" response by Qwerky is appropriate. Thanks. – Abhijeet Kashnia May 05 '11 at 12:57

4 Answers4

6

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

Qwerky
  • 18,217
  • 6
  • 44
  • 80
4

As the JavaDocs states:

These operations allow linked lists to be used as a stack, queue, or double-ended queue.

The List interface is just a List i.e. you can add or remove. So a basic implementation of the List interface has to just provide those simple methods e.g. ArrayList. The Deque interface is the double ended Queue and iava's LinkedList IS-A Double Ended Queue.

planetjones
  • 12,469
  • 5
  • 50
  • 51
4

IIRC, deque stands for double end queue. In the case you mention, it's not logical to define a generic List as a deque. For instance, an ArrayList is not designed for the Deque interface. Insertions will be efficient in the end of the list, but absolutely not at its beginning (because it will cause the re-allocation of a whole array, I think).

The LinkedList is, on the other end, perfectly designed for the Deque interface, as it is a double linked list.

Agemen
  • 1,525
  • 9
  • 18
1

Because a double-ended queue might be implemented using something other than a LinkedList and one's code may depend on anything with such functionality, so the Deque interface needs to be available separately.

List should not itself implement/extend Deque because adding to/removing from the start of a list may not be something that can be (easily) supported by every implementation.

eggyal
  • 122,705
  • 18
  • 212
  • 237