Java: нерекурсивный поиск в глубину в первую очередь с использованием ArrayDeque или LinkedList или LinkedBlockingDeque? - PullRequest
Новая
       34

Java: нерекурсивный поиск в глубину в первую очередь с использованием ArrayDeque или LinkedList или LinkedBlockingDeque?

0 голосов
/ 30 октября 2011 
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);
    }

так я должен использовать ArrayDeque или LinkedList или LinkedBlockingDeque? что произойдет, если я установлю значение int 10? Означает ли это, что очередь будет содержать только 10 одновременно? Что если Коллекция, полученная из БД, имеет размер больше 10? Это связанное значение определяет «снимок» очереди? 

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

Ответы [ 3 ]

1 голос
/ 30 октября 2011

Вы можете прочитать Javadocs для ArrayList

public void add (int index, E element)

Вставляет указанный элемент в указанную позицию в этом списке. Смещает элемент, находящийся в данный момент в этой позиции (если есть), и любые последующие элементы вправо (добавляет один к их индексам). 

queue.add(0,myObject);

JavaDocs - ваш друг .

Сказанное, как уже упоминали другие; не лучшая структура данных для использования. Если вам не нужен произвольный доступ к списку, LinkedList или ArrayDeque более эффективны.

1 голос
/ 30 октября 2011

Не используйте ArrayList - используйте одну из реализаций интерфейса Deque. Например, используйте LinkedBlockingDeque, который предназначен для такого рода вещей. При необходимости используйте методы addFirst(), addLast(), pollFirst() и pollLast().

Если по какой-то причине вам действительно нужно использовать List, используйте LinkedList - добавление в начало ArrayList крайне неэффективно, поскольку все элементы необходимо переместить.

0 голосов
/ 30 октября 2011

Почему вы не используете стеки. Стек - это путь для DFS. См. эту статью, чтобы понять, почему Stack решит проблему. Смотрите этот полезный учебник также:)

...