Randomly access a linked list in Java

Question

I have a class that is supposed to store a question, 4 answers and 1 correct answer.

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;
}

}

From the main class I have used a linked list to add elements to the class.

   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"));

Although I am able to sequentially call these using an Iterator but is there any way to randomly access these elements from the list? P.S. I am unable to use a .get(int) function.

Don't use a list for random access. Use an array-type container instead. — Bathsheba, Feb 09 '17 at 14:44
Linked Lists by definition aren't meant to work like that. See Wikipedia: https://en.wikipedia.org/wiki/Linked_list — Chris, Feb 09 '17 at 14:45
There's an interface that `ArrayList` implements, but `LinkedList` doesn't. That interface is... `RandomAccess`. — Olivier Grégoire, Feb 09 '17 at 14:48

score 3 · Answer 1 · edited May 23 '17 at 12:33

3

Random access in a LinkedList does not make sense per definition, since every element is only linked to it's direct neighbors. Either you have to implement it by yourself with an iterator and random numbers or you can use an ArrayList instead (see here for an example).

edited May 23 '17 at 12:33

Community

1
1

answered Feb 09 '17 at 14:46

Julian Heinovski

1,822
3
16
27

1

This is really helpful. Thank you. – Aniruddha Bera Feb 09 '17 at 14:52
1

LinkedList implements the List interface, which defines the get(int) function. Therefore there is no need for an own implementation with an iterator to access the elements in the list. – toongeorges Feb 09 '17 at 15:15
Well, you are right. But I assume that it uses the iterator internally, so you can use it as well. However, this is still very unperformant to use so I recommend an ArrayList for direct access to the random position in the list. – Julian Heinovski Feb 09 '17 at 16:13

jack jay · Accepted Answer · 2017-02-09T14:55:13.323

For random access LinkedList are not made, its good to use array based approach which would provide you random access.

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

Then you can access any question as qset[index], knowing its index.

Or you can use ArrayList over Array. advantages of ArrayList over 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) would be used to any object in arraylist at position denoted by index. Also qset.size() would give you size of arraylist.

CloudPotato · Answer 3 · 2017-02-09T14:57:15.957

1

You better use an ArrayList.

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

You can use qset.size() to get the amount of elements in the list. And then random access one of these. Like this:

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

You have to import java.util.Random for this

Btw: qset as name for a list and questionconstructor as name for a class are not a good choice

edited Feb 09 '17 at 14:57

answered Feb 09 '17 at 14:52

CloudPotato

1,255
1
17
32

What does Random have to do with this? The question is about random access as opposed to sequential access, not about selecting a random value. – toongeorges Feb 09 '17 at 15:11

score 1 · Answer 4 · answered Feb 09 '17 at 15:07

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

I understand that you ask if you can access an element in a linked list in a constant time.

That is not what a linked list is designed for, it is designed to allow for removal or insertion of an element at any position in a constant time. The trade off is that selection of an element at any position is not in a constant, but linear time.

Here is the relevant implementation code of 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;
    }

Elements in the list are accessed sequentially, not by random access.

If you want random access, convert the linked list either to an Array with

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

or to an ArrayList with

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

Randomly access a linked list in Java

4 Answers4