在Java中随机访问链表

Question

我有一个类，它应该存储一个问题，4个答案和1个正确答案。

public class questionconstructor {
String ques;
String opt1;
String opt2;
String opt3;
String opt4;
String ans; 

questionconstructor(String q,String o1,String o2,String o3,String o4,String an)
{
    ques=q;
    opt1=o1;
    opt2=o2;
    opt3=o3;
    opt4=o4;
    ans=an;
}

}

在主类中，我使用了一个链表来向该类添加元素。

   LinkedList<questionconstructor> qset = new LinkedList<questionconstructor>();

    qset.add(new questionconstructor("What is the fastest animal in the world?","Falcon","Cheetah","Fly","Puma","Cheetah"));
    qset.add(new questionconstructor("What is the slowest animal in the world?","Tortoise","Turtle","Sloth","Crocodile","Tortoise"));
    qset.add(new questionconstructor("What is the largest animal in the world?","Girrafe","Elephant","Whale","Mammoth","Whale"));
    qset.add(new questionconstructor("What is the fastest car in the world?","Bugatti Veyron","Ferrari Enzo","SSC Ultimate Aero","Aston Martin DB7","Bugatti Veyron"));
    qset.add(new questionconstructor("Which is of these buildings has a replica in Las Vegas?","Taj Mahal","Great Wall of China","Big Ben","Eiffel Tower","Eiffel Tower"));

虽然我可以使用迭代器顺序调用它们，但是否有任何方法可以从列表中随机访问这些元素？ P.S. 我无法使用 .get(int) 函数。

- Aniruddha Bera

---

不要使用列表进行随机访问，而应该使用类似于数组的容器。 - Bathsheba

链表的定义并不是为了像那样工作。请参阅维基百科：https://en.wikipedia.org/wiki/Linked_list - Chris

有一个接口 ArrayList 实现了，但是 LinkedList 没有实现。那个接口就是……RandomAccess。 - Olivier Grégoire

Answer 1

按照定义，LinkedList中的随机访问没有意义，因为每个元素只与其直接相邻的元素链接。要么自己使用迭代器和随机数实现它，要么可以使用ArrayList代替（请参见此处的示例）。

- Julian Heinovski

---

这真的非常有帮助。谢谢你。 - Aniruddha Bera

LinkedList 实现了 List 接口，该接口定义了 get(int) 函数。因此，在访问列表中的元素时，无需使用迭代器编写自己的实现。 - toongeorges

你说得没错。但是我认为它内部使用了迭代器，所以你也可以使用它。不过，这种方法的性能仍然非常低，因此我建议使用ArrayList，直接访问列表中的随机位置。 - Julian Heinovski

Answer 2

对于需要随机访问的LinkedList，我们可以使用基于数组的方法来实现，这样可以提供随机访问的能力。请注意，LinkedList本身并不适合进行随机访问。

questionconstructor qset[] = new questionconstructor[size];

    qset[0] = new questionconstructor("What is the fastest animal in the world?","Falcon","Cheetah","Fly","Puma","Cheetah");
    qset[1] = new questionconstructor("What is the slowest animal in the world?","Tortoise","Turtle","Sloth","Crocodile","Tortoise");

//and many more items in you array like above

那么，您可以通过qset[index]访问任何问题，并知道它的index。

或者您可以使用ArrayList而不是Array。 ArrayList相对于Array的优势

    ArrayList<questionconstructor> qset = new ArrayList<questionconstructor>();

    qset.add( new questionconstructor("What is the fastest animal in the world?","Falcon","Cheetah","Fly","Puma","Cheetah"));
    qset.add(new questionconstructor("What is the slowest animal in the world?","Tortoise","Turtle","Sloth","Crocodile","Tortoise"));

//and many more items in you array like above

qset.get(index) 会用于获取位于 index 位置的 ArrayList 中的任意对象。 同样，qset.size() 可以返回 ArrayList 的大小。

- jack jay

Answer 3

你最好使用一个 ArrayList。

List<questionconstructor> qset = new ArrayList<questionconstructor>();

您可以使用qset.size()来获取列表中的元素数量。然后随机访问其中一个。就像这样：

int amount = qset.size();
Random rand = new Random();
int randomNumber = rand.nextInt(amount);
questionconstructor randomQuestion = qset.get(randomNumber);

你需要导入java.util.Random。

顺便说一下：qset作为列表的名称，questionconstructor作为类的名称并不是一个好选择。

- CloudPotato

---

随机访问与这有什么关系？ 这个问题是关于随机访问而不是顺序访问，不是关于选择随机值的问题。 - toongeorges

Answer 4

is there any way to randomly access these elements from the list?
P.S. I am unable to use a .get(int) function.

我了解您的问题是关于在常数时间内访问链表中的元素。

这不是链表的设计目的，它的设计目的是允许在常数时间内删除或插入任何位置的元素。但以此为代价的是，在任何位置选择元素的时间不是常数时间，而是线性时间。

以下是LinkedList的相关实现代码：

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }

列表中的元素是按顺序访问的，而不是随机访问。

如果您想进行随机访问，请将链接列表转换为数组，使用

questionconstructor[] array = qset.toArray(new questionconstructor[qset.size()]);

或者转换成一个ArrayList。

ArrayList<questionconstructor> arrayList = new ArrayList<>(qset);

- toongeorges