Spring Avoid LinkedList performance issues through use of ArrayDeque

Triggered by gh-25650 which replaces LinkedList all over the place in the 5.3 codebase, we've identified several spots where the use of ArrayDeque instead of LinkedList specifically avoids performance issues (e.g. for a larger number of elements). In particular, StringUtils.cleanPath, FastByteArrayOutputStream and ParseState benefit from such a change in the 5.2.x line as well.

Comment From: dreis2211

@jhoeller Could you elaborate on the for size determination aspect?

LinkedList:

    public int size() {
        return size;
    }

vs.

ArrayDeque

    public int size() {
        return (tail - head) & (elements.length - 1);
    }

Naively, the implementation of ArrayDeque seems to be more expensive - or let's say it differently. Both seem to be O(1). Am I missing something?

Comment From: jhoeller

That's true, of course, not sure how I arrived at that :-) I'll remove the size determination part from the rationale above.