Why does java linkedlist implementation use the interface deque?
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.
The LinkedList
implementation happens to to satisfy the Deque
contract, so why not make it implement the interface?
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.
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.
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.
精彩评论