Java - Get an object from a list?

Question

Hi all ,

While developing my project , I implemented a scenario like this. I am having a LinkedList which contains , 100 Student class objects.

My scenario is ,

I need to get one particular Student class object from the LinkedList where rollNo = 98. So I used the below code.

My pojo class is ,

public class Student {

    private int rollNo ;
    private String name;

    // getters & setters        
}

My main class is ,

public class MainClass {

    List<Student> list = null;

    public MainClass(){
        list = new LinkedList<Student>();
    }

    public static void main(String... args){
        MainClass mainClass = new MainClass();
        mainClass.addStudentDetail();
        Student obj = mainClass.getStudentObject(98);

        // other Stuff with obj
    }

    private void addStudentDetail() {
        for(int i=1; i<=100; i++){
            Student obj = new Student();
            obj.setRollNo(i);
            obj.setName("Name"+i);
            list.add(obj);
        }

    }

    private Student getStudentObject(int rollNo) {
        int listLength = list.size();

        for(int i=0; i<listLength; i++){

            if(list.get(i).getRollNo() == rollNo)
                return list.get(i);

        }
        return null;
    }
}

To get Student object where rollNo = 98 ,

This needs 98 iterations.

So What happens if my List size is 1,00,000 and I need the Student object where rollNo = 99,999 ?

Is there any other simple way to get one particular object with where condition ?

Note :

Sorry to say, I don't need to use HashMap with rollNo as key. My need is to use only LinkedList. That is my requirement.

Hope I will get a good solution here.

Answer 1

Use a Map with rollNo as a key and Student instance as a value. This is a common way to "index" such collections to make the lookup as performant as possible

UPDATE:

If you want to search fast, you need some sort of index. Take a look at Java's HashMap source code and see how the keys are stored, that might give you an idea for your case

Answer 2

If you uses a LinkedList, its true that it needs 98 iterations to find the student. You can use a Map, and find by key the student. The key can be the rollNo, and the value the student itself.

Answer 3

In java there are two types of Lists are mostly used, they are ArrayList and LinkedList. Both retain the order in which the data inserted into the List. So in this case there is no other way, you have to iterate one by one.

Alternate solution is Set. There are three types of Sets are frequently used, they are TreeSet, HashSet and LinkedHashSet.

LinkedHashSet : Retain the order in which the data inserted into the set. (No use in your case). Search will be in O(n).

TreeSet : It internally maintains the data in Red-Black tree. So the search will be fast. Search will be in O(log n).

HashSet : It internally maintains the data in HashMap. So the search will be much more faster than TreeSet. Search will be in O(1).

Answer 4

Since map is out of equation and you need to use list then you'll end up with that much iterations. Alternatively you could sort the list and implement a binary search like logic for better performance. However, if you are not very particular about List you could use HashSet. Its similar to list in most aspects but can contain only unique values. The documentations says this class offers constant time performance for the basic operations (add, remove, contains and size). But for this you need to override the equals and hashCode methods with respect to rollNo. Example

public class Student {

    private int rollNo;
    private String name;

    //Getters & Setters.

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + rollNo;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Student other = (Student) obj;
        if (rollNo != other.rollNo)
            return false;
        return true;
    }
}

Answer 5

Well, if you need to use a LinkedList, the only thing that occurs to me in order to improve the performance, is to divide the size of the list by 2, and check if the index you are looking for is in the upper range or in the lower range.

If it is in the upper half, then iterate through the collection in reverse order using descendingIterator(). If it is in the lower half, then use the normal iterator. It won't improve much its performance, but at least you will save quite a few iterations when you want an object in the upper half. After all, it is a double linked list.

However, I would use an implementation of Map, but since you cannot do that, try what I have explained.

Answer 6

Looks like roll no is unique. Why not use it as the index in the linkedlist itself? Place 98 roll no object in the 98th index of the linked list.

By the way hashmap is also fine. Though if roll no is unique, then the above way will be both faster and cheap on memory.

Answer 7

As you currently add students by a simple for loop, all students are nice and neat sorted. So you can say, that the student on the position x has the roll number x+1.

But now imagine, that some students will leave and others will come. After some time, the "x+1" does not work anymore. Maybe even the sequence at all won't be true anymore. So it's not 1, 2, 3 anymore, but 2, 3, 1?

Itterating, sorting, etc. on a set with >1 Million entries is useless.

What you need to do is: Use a database! If you can't use a server based DB, you can also use SQLite or similar.

You can then access the students record with roll number 99 (or 943,251) by a simple SQL statement and parse your result into a Student instance.

In my opinion, this is the fastest way which still keeps the code relative easy and small.

Answer 8

If you are limited to LinkedList then you can upgrade your code by not using get(i) in loop. This approach is very inefficient because as explained in

Why would iterating over a List be faster than indexing through it?

each get(i) iterates from start of list till i-th element, like

get(0) - item0
get(1) - item0 -> item1
get(2) - item0 -> item1 -> item2
get(3) - item0 -> item1 -> item2 -> item3

Instead of this approach you should use Iterator and its next method to get to next element based on previous one. Code like

Iterator<Student> it = list.iterator();
while ( it.hasNext() ){
    Student s = i.next();
    //handle s here - test it or something
}

will iterate this way

 next       next       next       next 
  ->  item0  ->  item1  ->  item2  ->  item3

instead of

get(0)    get(1)            get(2)                    get(3)
  -> item0  -> (item0->item1) -> (item0->item1->item2) -> (item0->item1->item2->item3)

BTW code above can be also written using for-each loop like

for (Student s : list){
    //handle s here
}

So change your

for(int i=0; i<listLength; i++){
    if(list.get(i).getRollNo() == rollNo)
        return list.get(i);

to

for(String s : list)
    if (s.getRollNo() == rollNo)
        return s;

---

If you are sure that list is ordered then you can improve searching performance of elements which are closer to size of list by iterating from its end using ListIteratot and its previous method like

ListIterator<String> it = list.listIterator(list.size());
while(it.hasPrevious())
    System.out.println(it.previous());