CODEWITHSUNDEEP
javasearchobjectarraylistbinary-search
benny.bennett
benny.bennett

Reputation: 710

Searching For Object In ArrayList

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.

Upvotes: 4

Views: 4192

Answers (4)

driangle
driangle

Reputation: 11779

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.

Upvotes: 4

user684934
user684934

Reputation:

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.)

Upvotes: 2

Woot4Moo
Woot4Moo

Reputation: 24316

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.

Upvotes: 1

Retief
Retief

Reputation: 3217

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.

Upvotes: 1

Related Questions