Search code examples
javadepth-first-searchnon-recursive

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

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);
    }
Solution

  • 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.