Список массивов Vs. Связанный список

Question

Так что мне поручено сопоставить LinkedLists и ArrayLists для двух разных вещей.

часть 1) произвольного выбор места внутри списка и приращения этих значений от 1 для каждого типа списка

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

Я чувствую, что я достиг этого очень хорошо, но мой учитель говорит, что часть 1 ArrayList должна быть быстрее (что есть в моем коде). Он говорит, что LinkedList должно быть намного быстрее в части 2, что для меня совершенно противоположно ... путь медленнее. Я добавляю в SYSO's в разных местах, чтобы проверить правильность изменения списков и все, почему он не работает так, как он говорит, что это должно быть.

Может ли кто-нибудь определить, что я сделал неправильно (если что?). Большое спасибо

import java.util.ArrayList; 
import java.util.LinkedList; 
import java.util.List; 
import javax.swing.JOptionPane; 

public class LinkedListVersusArrayList { 

public static void main(String[] args) { 

    long startTime, endTime, duration; 
    List<Double> LL = new LinkedList<Double>(); 
    ArrayList<Double> AL = new ArrayList<Double>(); 
    int size = Integer.parseInt(JOptionPane.showInputDialog("Pick a list size (whole number only please)")); 

    //fills the Linked List with random doubles 
    for (int i = 0; i < size; i++){ 
     LL.add(Math.random()); 
    } 
    //fills the ArrayList with random doubles 
    for (int i = 0; i < size; i++){ 
     AL.add(Math.random()); 
    } 

    // 
    //Part 1 
    // 
    System.out.println("\nPART 1:\nBoth lists are now full of random numbers. \nI will now cycle through " 
      + "and incremiment random locations " +size+ " times for each list.\n"); 

    //testing the LinkedList first for random access 
    startTime = System.nanoTime(); 
    for (int i = 0; i < size; i++){ 
     int x = (int)(LL.size()*Math.random()); 
     double y = LL.get(x); 
     LL.set(x, y+1); 
    } 
    endTime = System.nanoTime(); 
    duration = (endTime - startTime); 
    System.out.println("Linked List took: " +(duration/1000000) +" milli seconds"); 

    //testing the ArrayList now for random access 
    startTime = System.nanoTime(); 
    for (int i = 0; i < size; i++){ 
     int x = (int)(AL.size()*Math.random()); 
     double y = AL.get(x); 
     AL.set(x, y+1); 
    } 
    endTime = System.nanoTime(); 
    duration = (endTime - startTime); 
    System.out.println("Array List took: " +(duration/1000000) +" milli seconds"); 

    // 
    //Part 2 
    // 
    System.out.println("\nPART 2:\nBoth lists will now get "+size+" slots added to them in random locations.\n" 
      + "After this is complete, we will remove "+size+" slots from each list at random\n"); 

    //testing the LinkedList first for random adding/subtracting 
    startTime = System.nanoTime(); 
    //add 
    for (int i = 0; i < size; i++){ 
     int x = (int)(LL.size()*Math.random()); 
     LL.add(x, 1.0); 
    } 
    //delete 
    for (int i = 0; i < size; i++){ 
     int x = (int)(LL.size()*Math.random()); 
     LL.remove(x); 
    } 
    endTime = System.nanoTime(); 
    duration = (endTime - startTime); 
    System.out.println("Linked List took: " +(duration/1000000) +" milli seconds"); 

    //testing the ArrayList now for random adding/subtracting 
    startTime = System.nanoTime(); 
    //add 
    for (int i = 0; i < size; i++){ 
     int x = (int)(AL.size()*Math.random()); 
     AL.add(x, 1.0); 
    } 
    //delete 
    for (int i = 0; i < size; i++){ 
     int x = (int)(AL.size()*Math.random()); 
     AL.remove(x); 
    } 
    endTime = System.nanoTime(); 
    duration = (endTime - startTime); 
    System.out.println("Array List took: " +(duration/1000000) +" milli seconds"); 
} 

}

Answer 1

Помимо всех вопросов, которые microbenchmarking ваш код не контролирует для ожидания своего учителя для случая 2, также неправильно. Он не учитывает стоимость доступа к случайному элементу LinkedList (предпосылка для вставки в это место) и переоценивает стоимость вставки в ArrayList. Стоимость копирования смежных блоков памяти намного ниже стоимости преследования длинной цепочки указателей, что и требуется для доступа к случайному элементу LinkedList.

В действительности LinkedList имеет очень узкую область применения, где есть любое улучшение по сравнению с ArrayList. Например, вы можете попытаться вставить только около передней части списка. Таким образом, вы будете подчеркивать стоимость перемещения элементов в ArrayList и снижать стоимость доступа к члену LinkedList.