java: Non-Recursive Depth First Search using ArrayDeque or LinkedList or LinkedBlockingDeque?

Question

public void traverse(Node root){
    ArrayDeque<Node> queue = new ArrayDeque<Node>();
        queue.add(root);

    while(!queue.isEmpty()){
        Node currentNode = queue.pollFirst();   
        List<Node> nl = getChildrenfromDB(currentNode);
        queue.addAll(nl);
    }

so should I be using ArrayDeque or LinkedList or LinkedBlockingDeque? what would happen when I set int value of 10? Does this mean the queue will only hold 10 at a time? what if the Collection retrieved from DB's size is larger than 10? Is this bound value define the "snapshot" of the queue?

public void traverse(Node root){
    LinkedBlockingDeque<Node> queue = new LinkedBlockingDeque<Node>(10);
        queue.add(root);

    while(!queue.isEmpty()){
        Node currentNode = queue.pollFirst();   
        List<Node> nl = getChildrenfromDB(currentNode);
        queue.addAll(nl);
    }

Answer 1

Don't use an ArrayList -- use one of the implementations of the Deque interface. For example, use a LinkedBlockingDeque, which is designed for this sort of thing. Use the addFirst(), addLast(), pollFirst(), and pollLast() methods as needed.

If, for some reason, you really need to use a List, use a LinkedList -- adding to the front of an ArrayList is extremely inefficient, as all elements need to be moved.

Answer 2

You could read the javadocs for ArrayList

public void add(int index, E element)

Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

queue.add(0,myObject);

JavaDocs are your friend.

That being said, as others have mentioned; not the best data structure to use. If you don't need random access into the list, a LinkedList or ArrayDeque are more efficient.

Answer 3

Why do not you use Stacks. Stack is the way to go for DFS. See this article to see why Stack will solve the problem. See this useful tutorial also :)