Java中的LinkedList更新性能

在下面这段代码中，我发现总是删除第一个listnode，并且打印第一个节点比保持列表完整并在所有节点上迭代更有效（就执行时间而言）。我想知道这是因为当我总是删除第一个节点时，我只需要将启动节点更新到下一个节点，然后只需获取第一个节点即可打印该值。如果通过保持list intanct遍历整个列表，则get操作每次都将遍历到指定的索引并获取该值。现在我的问题是： 1）我的理解是否正确？ 2）两种方式应该在同一时间执行 3）是否有其他推理？Java中的LinkedList更新性能

public class Ddbrw { 
public List<Integer> ListValidation() 
    { 
     List<Integer> lst = new LinkedList<>(); 
     for(int i = 0; i < 20; i++){ 
     lst.add(new Integer(1)); lst.add(new Integer(5)); 
     lst.add(new Integer(9)); lst.add(new Integer(7)); 
     lst.add(new Integer(5)); lst.add(new Integer(61)); 
     lst.add(new Integer(8)); lst.add(new Integer(12)); 
     } 
     return lst; 
    } 

public static void main(String[] args) 
    { 
    Ddbrw obj = new Ddbrw(); 
    Ddbrw obj2 = new Ddbrw(); 

    List<Integer> lst = obj2.ListValidation(); 
    int size = lst.size(); 
    long startTime = System.currentTimeMillis(); 
    for(int i = 0; i < size; i++) { 
     System.out.print(lst.get(i)); 
    } 
    long endTime = System.currentTimeMillis(); 
    System.out.println("*************"); 
    System.out.println(endTime-startTime); 
    System.out.println("*************"); 

    List<Integer> lst2 = obj.ListValidation(); 
    long startTime1 = System.currentTimeMillis(); 
    for(int k = 0; k < lst2.size();) { 
     System.out.print(lst2.get(k)); 
     lst2.remove(k); 
    } 
    long endTime1 = System.currentTimeMillis(); 
    System.out.println("*************"); 
    System.out.println(endTime1-startTime1); 
    System.out.println("*************"); 
    } 
}

来源

2016-06-23 user2138726

'新的整数（1）'从来不使用这个，总是用'Integer.valueof（1）' 。这对于大多数盒装原语都是如此。此外，这不是你如何基准Java程序的基准;你必须预热JVM。 –

更好的是，只需使用'1'。例如，'lst.add（1）;'。 – shmosel

您最初的推理是正确的，问题是，一个LinkedList并不意味着要高效使用随机访问。因此，每次按索引访问元素（例如lst.get(k)）时，都必须从列表的开头到达该元素。

但这并不意味着LinkedList无法在您的情况下有效使用，它只是您正在尝试使用它作为ArrayList。 List<T>提供了Iterator<T>，它在迭代列表时效率更高。

例如：

Iterator<Integer> it = lst.iterator(); 

while (it.hasNext()) 
    System.out.println(it.next()); 

for (int i : lst) 
    System.out.println(i);

这将遍历列表，而不必在每次迭代达到k个元素，因为它会跟踪迭代器里面的一切。

事实上，因为它不具有的memmove /移连续元素每次你删除一个元素，这可能会比在某些情况下的ArrayList更有效。

来源

2016-06-23 01:03:30 Jack

OP不关心删除元素。通过索引查找获得持续时间只是一个噱头。 – shmosel

是的，但重点不会改变。关键是OP应该使用'迭代器'，它将提供最适合迭代集合的方式。 – Jack

您的观察结果与链接列表有关，只是因为您正在遍历索引。 Java有一个RandomAccess接口来标识List实现，该实现可以在固定时间内进行索引，例如由ArrayList实现，但不是由LinkedList实现。

如果使用迭代器遍历列表，而不是，你会得到大致相同的性能：

for (Integer i : lst) { 
    System.out.println(i); 
}

来源

2016-06-23 01:04:37 shmosel

感谢您的建议。 – user2138726

Java中的LinkedList更新性能

回答

相关问题