java: Non-Recursive Depth First Search using ArrayDeque or LinkedList or LinkedBlockingDeque?
-
16-02-2021 - |
题
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);
}
解决方案
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.
其他提示
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.