Menu
The ArrayDeque class implements the Deque interface In fact, the Java API documentation even states that the ArrayDeque class will often times be faster than a Queue or a Stack. This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
ArrayDeque as a StackTo implement a LIFO (Last-In-First-Out) stacks in Java, it is recommended to use a deque over the Stack class. The ArrayDeque class is likely to be faster than the Stack class. ArrayDeque provides the following methods that can be used for implementing a stack.
ArrayList is resized to a new size of oldCapacity + (oldCapacity >> 1) , resulting in an increse of ~50%. The default capacity is 10, resulting in a capacities after resize of 15, 22, 33, 49, 73, 109, 163, 244, 366... ArrayDeque is always resized to a power of 2. On resize, the capacity is doubled.
Unlike Queue, we can add or remove elements from both sides. Null elements are not allowed in the ArrayDeque. ArrayDeque is not thread safe, in the absence of external synchronization. ArrayDeque has no capacity restrictions.
Linked structures are possibly the worst structure to iterate with a cache miss on each element. On top of it they consume way more memory.
If you need add/remove of the both ends, ArrayDeque is significantly better than a linked list. Random access each element is also O(1) for a cyclic queue.
The only better operation of a linked list is removing the current element during iteration.
I believe that the main performance bottleneck in LinkedList is the fact that whenever you push to any end of the deque, behind the scene the implementation allocates a new linked list node, which essentially involves JVM/OS, and that's expensive. Also, whenever you pop from any end, the internal nodes of LinkedList become eligible for garbage collection and that's more work behind the scene.
Also, since the linked list nodes are allocated here and there, usage of CPU cache won't provide much benefit.
If it might be of interest, I have a proof that adding (appending) an element to ArrayList or ArrayDeque runs in amortized constant time; refer to this.
All the people criticizing a LinkedList, think about every other guy that has been using List in Java probably uses ArrayList and an LinkedList most of the times because they have been before Java 6 and because those are the ones being taught as a start in most books.
But, that doesn't mean, I would blindly take LinkedList's or ArrayDeque's side. If you want to know, take a look at the below benchmark done by Brian (archived).
The test setup considers:
- Each test object is a 500 character String. Each String is a different object in memory.
- The size of the test array will be varied during the tests.
- For each array size/Queue-implementation combination, 100 tests are run and average time-per-test is calculated.
- Each tests consists of filling each queue with all objects, then removing them all.
- Measure time in terms of milliseconds.
Test Result:
- Below 10,000 elements, both LinkedList and ArrayDeque tests averaged at a sub 1 ms level.
- As the sets of data get larger, the differences between the ArrayDeque and LinkedList average test time gets larger.
- At the test size of 9,900,000 elements, the LinkedList approach took ~165% longer than the ArrayDeque approach.
Graph:
Takeaway:
ArrayList or ArrayDeque with a good guess of maximum capacity
that the list may be required to be because of strict memory constraint.LinkedList so tread carefully when deciding to use a ArrayDeque especially because it DOESN'T implement the List interface(I think that's reason big enough). It may be that your codebase talks to the List interface extensively, most probably and you decide to jump in with an ArrayDeque. Using it for internal implementations might be a good idea...ArrayDeque is new with Java 6, which is why a lot of code (especially projects that try to be compatible with earlier Java versions) don't use it.
It's "better" in some cases because you're not allocating a node for each item to insert; instead all elements are stored in a giant array, which is resized if it gets full.
ArrayDeque and LinkedList are implementing Deque interface but implementation is different.
Key differences:
The ArrayDeque class is the resizable array implementation of the Deque interface and LinkedList class is the list implementation
NULL elements can be added to LinkedList but not in ArrayDeque
ArrayDeque is more efficient than the LinkedList for add and remove operation at both ends and LinkedList implementation is efficient for removing the current element during the iteration
The LinkedList implementation consumes more memory than the ArrayDeque
So if you don't have to support NULL elements && looking for less memory && efficiency of add/remove elements at both ends, ArrayDeque is the best
Refer to documentation for more details.
although ArrayDeque<E> and LinkedList<E> have both implemented Deque<E> Interface, but the ArrayDeque uses basically Object array E[] for keeping the elements inside its Object, so it generally uses index for locating the head and tail elements.
In a word, it just works like Deque (with all Deque's method), however uses array's data structure. As regards which one is better, depends on how and where you use them.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With