Обход гигантского LinkedList

Question

Для проекта мне требуется написать метод, который проходит через обход LinkedList, заполненный 5 миллионами случайных целых чисел, с помощью listIterator, а затем методом get (index) LinkedList.

У меня не возникло проблем с перемещением его с помощью ListIterator, и он завершился примерно в 75 мс. ОДНАКО, после попытки пройти метод get на 5 миллионов целых чисел, я просто прекратил работу примерно 1,5 часа.

Метод getTraverse, который я использовал, например, как код ниже (однако моя группа была сгруппирована с другими методами в классе и была нестатической, но работает одинаково).

public static long getTraverse(LinkedList<Integer> list) { 
    long start = System.currentTimeMillis(); 
    for (int i = 0; i < linkedList.size(); i++) { 
     linkedList.get(i); 
    } 
    long stop = System.currentTimeMillis(); 
    return stop - start; 
} 

Это работало прекрасно для LinkedLists от Целые размеров 50, 500, 5000, 50000, и потребовалось некоторое время, но для завершения 500000.

Мой профессор, как правило, крайне неопределенными с инструкциями и очень бесполезно, когда подходили к вопросам. Итак, я не знаю, нарушен ли мой код, или если он увлекся целями в руководящих принципах. Любой вход оценивается.

Answer 1

Подумайте о том, как реализован LinkedList - как цепочка узлов - и вы увидите, что для того, чтобы добраться до определенного узла, вы должны начать с головы и пройти к этому узлу.

Вы звоните .get() на LinkedList через п раз, что требует перемещения по списку, пока он не достигнет этого показателя. Это означает, что ваш метод getTraverse() принимает O (n^2) (или квадратичное) время, потому что для каждого элемента он должен пройти (часть) списка.

Как сказал Эллиотт Фриш, я подозреваю, что вы обнаруживаете, что именно ваш инструктор хотел, чтобы вы обнаружили - разные алгоритмы могут иметь совершенно разные времена автономной работы, даже если в принципе они делают то же самое.

Answer 2

A LinkedList оптимизирован для вставки, что является постоянной операцией времени.

Для поиска LinkedList требуется выполнить итерацию по каждому элементу, чтобы найти тот, который вы хотите. Вы указываете индекс методу get, но под обложками он перемещает список по этому индексу.

Если вы добавили некоторые операторы печати, вы, вероятно, увидите, что первые X-элементы извлекаются довольно быстро и замедляются с течением времени, когда вы индексируете элементы дальше по списку.

ArrayList (поддерживается массивом) оптимизирован для извлечения и может индексировать нужный элемент в постоянное время. Попробуйте изменить код, чтобы использовать ArrayList и посмотреть, насколько быстрее выполняется get.