java - Java中LinkedList的更新性能

Question

在下面的代码中，我发现始终删除第一个列表节点并打印第一个节点比保持列表完整并迭代所有节点更有效(就执行时间而言)。我想知道这是因为当我总是删除第一个节点时，我只需将起始节点更新为下一个节点，然后获取第一个节点来打印值。如果通过保持列表不变来迭代整个列表，则 get 操作每次都会遍历列表到指定索引并获取值。现在我的问题是:1)我的理解正确吗？2)两种方式应该同时执行3)还有其他原因吗？

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("*************");
    }
}

Answer 1

你最初的推理是正确的，关键是 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每次迭代中的第 -th 元素，因为它跟踪迭代器内的所有内容。

实际上，这可能比 ArrayList 更有效。在某些情况下，因为每次删除元素时它不必memmove/shift连续的元素。