Searching For Object In ArrayList

Question

I'm a relative newbie to Java and am building an application for my programming course where users can enter, remove, search or edit a list of Students (an object which consists of an integer ID number, a String last name, and a double GPA). So far, I have had success with allowing the user to enter, remove, or edit entries. Right now, the list of 100+ students are in an ArrayList (each as a Student object with the three parameters).

My problem is that I don't know an efficient way to allow the user to search for a specific student based on ID number, last name, or GPA (and possibly GPA range in the future). I have been studying Big-O notation and would like to use a binary search because it would be great practice as well as a better choice if the Student list continues to grow. So far, for binary searches, we are using the high/low/mid method with a while loop (if that is any indication of my current skill level).

So here is my question:

What is an efficient way to search for a specific student based on this criteria? I am not looking for code or answers to my dilemma. I'm really looking for the names of techniques or tricks that Java programmers use to do such a thing, especially if those techniques can be used with other object-oriented programming languages.

are you doing searching based on exact matches or similar matches (ie: 'Gar' matches 'Garcia')? — driangle
– driangle, Commented Feb 7, 2012 at 2:15
Preferably, the searches for names will be exact (ignoring case). The searches for ID numbers must be exact. For GPA, I would like it to return all that apply, but only if it isn't overly complicated for my skill level. — benny.bennett
– benny.bennett, Commented Feb 7, 2012 at 2:17

driangle · Accepted Answer · 2012-02-07 05:33:02Z

4

I recommend looking into the HashMap data structure. It allows you to store elements in a collections mapped to a certain key, such that they can be later retrieved by that same key. In your example you could have different hash maps for searching on different fields. The key of the hash map would be the field (ie: ID, lastname, or GPA), and the value would be the corresponding student. For case insensitive searches, make sure to convert the key (last name) to lower case before saving an object and before retrieving an object.

to store ids:

Map<String, Student> idToStudent;

key: "23213233", value: "Some Student";

to take into account duplicate names or gpa, then use a map of type:

Map<String, List<Student>> lastNameToStudents;

key: "smith", value: ["John Smith", "Bob Smith", etc]

Map<Double, List<Student>> gpaToStudents:

key: "2.4", value: ["Student 1", "Student 2", etc];

Note, I'm using the string representation of a student's name for brevity, but in reality those represent Student instances.

edited Feb 7, 2012 at 5:33

answered Feb 7, 2012 at 2:20

driangle

11.8k6 gold badges50 silver badges56 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

benny.bennett Over a year ago

Great information. Definitely something I will look into. Thank you.

卢声远 Shengyuan Lu Over a year ago

Vote up. but duplicated name and GPA will be a problem.

卢声远 Shengyuan Lu Over a year ago

@ggreiner No duplicate problem, I cannot vote your answer twice:) btw: Guava Multimap is designed for such structure: 'Multimap<String, Student> mMap = ArrayListMultimap.create();'

user684934 · Accepted Answer · 2012-02-07 04:42:04Z

For binary search, you'd need the list to be sorted by the criteria you are searching with.

You could maintain three different lists, sorted by the three different criteria you need:

ArrayList<Student> sortedByName;
ArrayList<Student> sortedByGpa;
ArrayList<Student> sortedById;

public List<Student> getStudentByName(String name){
    return binarySearchOnName(sortedByName, name);
}
public List<Student> getStudentByGpa(double gpa){
    return binarySearchOnGpa(sortedByGpa, gpa);
}
...

Note that when you insert a new Student to your ArrayList, you should also insert that Student into the other, sorted ArrayLists in its correct place. (You can use binary search to do this, of course.)

Retief · Accepted Answer · 2012-02-07 02:25:44Z

1

Do you need duplicates or an arbitrary ordering? If not, think about using either a TreeSet or a HashSet. A TreeSet offers O(log(n)) access/insertion/deletion and automatically sorts its elements (so iterating over it gets the elements in sorted order. A HashSet provides amortized O(1) access/insertion/deletion, but iteration happens in some random order (that you have no control over). One of these sounds like the easiest way to accomplish your goals.

If you need to search by member, you probably want a HashMap/TreeMap, as long as you don't mind only getting exact matches. If you need to search by member for several members, you might want multiple maps with one map per key you want to search for. If you were to use ArrayLists and wanted better than O(n) lookup, you would need multiple lists anyway (1 list per lookup parameter sorted on that parameter).

In the end, O(n) lookup will be by far the easiest. As long as the list doesn't get too large (think 10000 elements as opposed to 100), performance will be fine, and this approach will minimize storage overhead. You don't want premature optimization -- until performance is a problem, the best technique is simply to iterate across the list.

edited Feb 7, 2012 at 2:25

answered Feb 7, 2012 at 2:17

Retief

3,21719 silver badges16 bronze badges

1 Comment

benny.bennett Over a year ago

I actually have not studied HashSets or TreeSets much yet, but thank you for the suggestion. I will certainly look into these. Thank you!

Woot4Moo · Accepted Answer · 2012-02-07 04:34:15Z

So I see three issues with one general problem. The general problem is that you want to be able to search on some criteria, with the three issues being the specific cases for each. So the only field that is guaranteed to be unique would be the Student ID field. This allows us to override the equals + hashcode methods. We want this to be the value we use to determine equality (at least in this very simple example). By doing this you will have exposed a mechanism for searches in a list without sorting, via the following call:

list.contains(Student);

Now in terms of the name, since this value is not guaranteed to be unique, we would want to do something similar to this:

 matchedStudents = new ArrayList<Student>();
    for(Student currentStudent : studentList)  
    {  
        if(currentStudent.getName().equalsIgnoreCase(searchString)  
        {
              matchedStudents.add(currentStudent);  
        }
    }  
      return matchedStudents;

In terms of the GPA we would essentially repeat the loop above just calling using where GPA == searchCriteria.

that being said it should be possible to write a function like so:

function searchStudent(String searchString, String type)  
{    
    //type is one of: GPA, name, ID  
    switch(type)  
    {  
       case gpa:  
       case id:  
       case name:
    }  
}

that should get you started.

Collectives™ on Stack Overflow

Searching For Object In ArrayList

4 Answers 4

3 Comments

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related