Collections: LinkedList pays for Deque flexibility with per-node memory

LinkedList and ArrayDeque both implement Deque and produce the same sequence of elements, but LinkedList allocates a node object with two pointers per element while ArrayDeque uses one resizable array; LinkedList also implements List, which ArrayDeque deliberately does not.

Code

Deque<Integer> linked = new LinkedList<>();
Deque<Integer> array = new ArrayDeque<>();
for (int i = 0; i < 5; i++) {
    linked.addLast(i);
    array.addLast(i);
}
System.out.println("LinkedList as Deque: " + linked);
System.out.println("ArrayDeque: " + array);
System.out.println("LinkedList implements List too: " + (linked instanceof List));
System.out.println("ArrayDeque implements List: " + (array instanceof List));

Output

LinkedList as Deque: [0, 1, 2, 3, 4]
ArrayDeque: [0, 1, 2, 3, 4]
LinkedList implements List too: true
ArrayDeque implements List: false