Why is ArrayDeque better than LinkedList

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:

• If your requirement is storing 100 or 200 elements, it wouldn't make much of a difference using either of the Queues.
• However, if you are developing on mobile, you may want to use an ArrayList or ArrayDeque with a good guess of maximum capacity that the list may be required to be because of strict memory constraint.
• A lot of code exists, written using a 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 and LinkedList are implementing Deque interface but implementation is different.

Refer to Oracle documentation for more details.

Key differences:

1. The ArrayDeque class is the resizable array implementation of the Deque interface and LinkedList class is the list implementation
2. NULL elements can be added to LinkedList but not in ArrayDeque
3. 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
4. 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

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.

I don't think ArrayDeque is better than LinkedList. They are different.

ArrayDeque is faster than LinkedList on average. But for adding an element, ArrayDeque takes amortized constant time, and LinkedList takes constant time.

For time-sensitive applications that require all operations to take constant time, only LinkedList should be used.

ArrayDeque's implementation uses arrays and requires resizing, and occasionally, when the array is full and needs to add an element, it will take linear time to resize, resulting the add() method taking linear time. That could be a disaster if the application is very time-sensitive.

A more detailed explanation of Java's implementation of the two data structures is available in the "Algorithms, Part I" course on Coursera offered by Princeton University, taught by Wayne and Sedgewick. The course is free to the public.

The details are explained in the video "Resizing Arrays" in the "Stacks and Queues" section of "Week 2".

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.

Most of other answers mention about memory consumption. As far as I understand the story is that, as the number of elements increases, so does the difference between LinkedList and ArrayDeque memory usage to support those elements.

But what happens as the number of elements decreases back to a small amount?

I just wanted to mention this special case, because it seems to me (based on the currently-latest OpenJDK version 24 implementation for example) that the ArrayDeque only grows. When elements are removed, it seems that, the internal array never gets smaller. Thus one could expect that after adding for example 10 million objects and then removing almost all the first elements, leaving for example only 3, then ArrayDeque will have an array of at least 10 million (null) references internally, but LinkedList only 3 nodes (in the corresponding example). I did not test this, but I assume LinkedList would then occupy less memory at that point.

Of course one could argue that such a scenario would be rarely (if at all) needed, or that if you can already fit 10 million references at some point in time, why care when they are deallocated at some other point, etc... But I consider it as a valid scenario because it can happen, as well as a problematic situation since almost all the internal array is occupying unused memory (which is taken away from other processes).

One way to workaround this issue is to clone the ArrayDeque when needed to reduce memory footprint (which cannot happen in place), or use a trimToSize method similar to ArrayList (assuming it gets added in the future). But this could also require to monitor the size of the internal array (assumptions for its internal implementation should be made then by client code, which seems like breaking the whole purpose of encapsulation).

That's not always the case.

For example, in the case below linkedlist has better performance than ArrayDeque according to leetcode 103.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> rs=new ArrayList<>();
        if(root==null)
            return rs;
        // 👇 here ,linkedlist works better
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        boolean left2right=true;
        while(!queue.isEmpty())
        {
            int size=queue.size();
            LinkedList<Integer> t=new LinkedList<>();
            while(size-->0)
            {
                TreeNode tree=queue.remove();
                if(left2right)  
                    t.add(tree.val);
                else
                    t.addFirst(tree.val);
                if(tree.left!=null)
                {
                    queue.add(tree.left);
                }
                if(tree.right!=null)
                {
                    queue.add(tree.right);
                }
            }
            rs.add(t);
            left2right=!left2right;
        }
        return rs;
    }
}

I'm not sure how ArrayDeque is implemented, but I have implemented something similar in C++ years ago, and I'm quite sure they do the same. the collection is actually an ArrayList which is considered "cyclic", i.e. the next item after a[n-1] is a[0]. the deque also keeps two pointers (integer) to the first and last item in the deque. When you addFirst you decread "first" (cyclic) and when addLast increase "last". It's quite simple and efficient.

Another big not obvious advantage of using ArrayDeque is .clone() implementation.

for LinkedList it is traversing through the whole list in O(n):

    /**
     * Returns a shallow copy of this {@code LinkedList}. (The elements
     * themselves are not cloned.)
     *
     * @return a shallow copy of this {@code LinkedList} instance
     */
    public Object clone() {
        LinkedList<E> clone = superClone();

        // Put clone into "virgin" state
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;

        // Initialize clone with our elements
        for (Node<E> x = first; x != null; x = x.next)
            clone.add(x.item);

        return clone;
    }

and for the ArrayDeque we have System.arrayCopy() (if you dig deeper than Arrays.copyOf()) which is way more effective, it is probably linear too, but with way less inclination

    /**
     * Returns a copy of this deque.
     *
     * @return a copy of this deque
     */
    public ArrayDeque<E> clone() {
        try {
            @SuppressWarnings("unchecked")
            ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
            result.elements = Arrays.copyOf(elements, elements.length);
            return result;
        } catch (CloneNotSupportedException e) {
            throw new AssertionError();
        }
    }