ArrayDeque is useful as a heap-based work collection when an algorithm must add and remove nodes while traversing a structure. In particular, it can hold the intermediate state that recursive calls would otherwise keep on the Java stack, allowing a deep traversal to be expressed as a loop and limited by heap size rather than stack size. section 5.4.1 section 5.5
Replace recursive tree search with an explicit stack
For a deep tree, keep nodes still to visit in a Deque<Node>. Add the root, repeatedly remove the last node, test its name, and add its children. This avoids recursive calls, though the iterative version is longer and can be harder to read. Deque<Node> stack = new ArrayDeque<>(); stack.add(this); while (!stack.isEmpty()) { Node node = stack.pollLast(); if (node.name().equals(name)) return node; Collections.addAll(stack, node.children()); } return null; section 5.4.1
Do not accidentally turn an ArrayDeque field into shared mutable state with static. Two TreeWalker instances then use the same queue; concurrent traversals can retrieve nodes from the other tree. Because operations such as poll() and addAll() are not thread-safe, concurrent access can also corrupt the deque’s internal structure, sometimes surfacing as ArrayIndexOutOfBoundsException and sometimes not. section 3.11
Choose and use it with these constraints in mind:
- Prefer an explicit ArrayDeque work collection when non-tail recursion must be rewritten as iteration; use a record when each suspended state needs several variables. section 5.4.1
- Do not rely on ArrayDeque for concurrent collection access. When several threads genuinely need a deque, use a modern concurrent alternative such as ConcurrentLinkedDeque. section 3.11
- Do not assume queue equality is content-based. Content equality is required for List and Set implementations, not for queues such as ArrayDeque. section 7.2
Node find(String name) {
Deque<Node> stack = new ArrayDeque<>();
stack.add(this);
while (!stack.isEmpty()) {
Node node = stack.pollLast();
if (node.name().equals(name)) return node;
Collections.addAll(stack, node.children());
}
return null;
}
The listing shows a recursive descendant search rewritten around an ArrayDeque, making the deferred nodes explicit on the heap. section 5.4.1
