链表时间遍历上的迭代器

Question

我写了一个程序，它在 linkedlist 中存储了一些整数，它还测试了它使用迭代器和 get(index) 遍历列表的时间，我对我的程序有 100% 的把握，但是当我运行给我这个错误的程序：

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 20000, Size: 20000 at java.util.LinkedList.checkElementIndex(LinkedList.java:555) at java.util.LinkedList.get(LinkedList.java:476) at Homework2.MyLinkedList.main(MyLinkedList.java:72)

您可以在下面找到我的代码。我需要帮助

import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Scanner;

public class MyLinkedList {
  public static void main(String[] args) {

    Scanner in = new Scanner(System.in);

    // System.out.print("Enter the size of your list: ");
    // int size = in.nextInt();

    int n1 = 20000;
    int n2 = 200000;
    int n3 = 2000000;

    LinkedList < Integer > list1 = new LinkedList();

    for (int i = 1; i <= n1; i++) {
      list1.add(i);
    }

    long t1Start = System.currentTimeMillis();
    ListIterator < Integer > iterator1 = list1.listIterator();
    while (iterator1.hasNext()) {
      iterator1.next();
    }
    long t1Stop = System.currentTimeMillis();

    long t1Final = t1Stop - t1Start;

    //////////////////////////////////////////

    LinkedList < Integer > list2 = new LinkedList();

    for (int i = 1; i <= n2; i++) {
      list2.add(i);
    }

    long t2Start = System.currentTimeMillis();
    ListIterator < Integer > iterator2 = list1.listIterator();
    while (iterator1.hasNext()) {
      iterator1.next();
    }
    long t2Stop = System.currentTimeMillis();

    long t2Final = t2Stop - t2Start;

    //////////////////////////////////////////

    LinkedList < Integer > list3 = new LinkedList();

    for (int i = 1; i <= n2; i++) {
      list2.add(i);
    }

    long t3Start = System.currentTimeMillis();
    ListIterator < Integer > iterator3 = list1.listIterator();
    while (iterator1.hasNext()) {
      iterator1.next();
    }
    long t3Stop = System.currentTimeMillis();

    long t3Final = t3Stop - t3Start;

    //////////////////////////////////////////

    long get1Start = System.currentTimeMillis();
    for (int i = 1; i <= n1; i++) {
      list1.get(i);
    }
    long get1Stop = System.currentTimeMillis();
    long get1Final = get1Stop - get1Start;

    //////////////////////////////////////////

    long get2Start = System.currentTimeMillis();
    for (int i = 1; i <= n2; i++) {
      list2.get(i);
    }
    long get2Stop = System.currentTimeMillis();
    long get2Final = get2Stop - get2Start;

    //////////////////////////////////////////

    long get3Start = System.currentTimeMillis();
    for (int i = 1; i <= n3; i++) {
      list3.get(i);
    }
    long get3Stop = System.currentTimeMillis();
    long get3Final = get3Stop - get3Start;

    //////////////////////////////////////////

    System.out.println("n\t\titerator,seconds\t\tget(index),seconds");
    System.out.println(n1 + "\t\t" + t1Final + "\t\t" + get1Final);
    System.out.println(n2 + "\t\t" + t2Final + "\t\t" + get2Final);
    System.out.println(n3 + "\t\t" + t3Final + "\t\t" + get3Final);

  }
}

Answer 1

问题在

for (int i = 1; i <= n1; i++) {
    list1.get(i);
}

索引从 0 到大小 - 1。当 i 等于 n1 时，您将得到 IndexOutOfBoundsException，因为列表的最大索引是 n1 - 1。将其更改为

for (int i = 0; i < n1; i++) {
    list1.get(i);
}

list2 和 list3 也是如此。

此外，正如@Paul Boddington 提到的，您永远不会向 list3 添加任何内容，而是向 list2.

插入两次值

链表时间遍历上的迭代器

Iterators on LinkedList Time Traversing

java

iterator

traversal

linked-list