Java method: Finding object in array list given a known attribute value

Question

I have a couple of questions actually.

I have a class Dog with the following instance fields:

private int id;
private int id_mother;
private int id_father;
private String name="";
private String owner="";
private String bDate="";

I also have a class Archive which can instantiate Dog and put Dog objects into an ArrayList.

I am trying to write a method in Archive which takes an integer as ID and looks through the ArrayList, and returns the object containing that ID.

private Dog getDog(int id){
 Dog dog = new Dog();
 int length=getSize();
 int i=0;

 dog=al.get(i);
 i++;

 while(dog.getId()!=id && i<length)
  dog=al.get(i);
  i++;

 if(dog.getId()!=id)
  dog=null;
 return dog;
}//end getDog

There are two problems with this method (the other methods I use work). First of all it's not working, and I can't see why. I'm while-looping through (potentially) all the objects in the arraylist, for then after the loop is finished, checking whether the loop finished because it ran out of objects to search through, or because it found an object with the given ID. Secondly, that seems like an immensely time-consuming process. Is there some way to speed this up?

Answer 1

A while applies to the expression or block after the while.

You dont have a block, so your while ends with the expression dog=al.get(i);

while(dog.getId()!=id && i<length)
                dog=al.get(i);

Everything after that happens only once.

There's no reason to new up a Dog, as you're never using the dog you new'd up; you immediately assign a Dog from the array to your dog reference.

And if you need to get a value for a key, you should use a Map, not an Array.

Edit: this was donwmodded why??

Comment from OP:

One further question with regards to not having to make a new instance of a Dog. If I am just taking out copies of the objects from the array list, how can I then take it out from the array list without having an object in which I put it? I just noticed as well that I didn't bracket the while-loop.

A Java reference and the object it refers to are different things. They're very much like a C++ reference and object, though a Java reference can be re-pointed like a C++ pointer.

The upshot is that Dog dog; or Dog dog = null gives you a reference that points to no object. new Dog() creates an object that can be pointed to.

Following that with a dog = al.get(i) means that the reference now points to the dog reference returned by al.get(i). Understand, in Java, objects are never returned, only references to objects (which are addresses of the object in memory).

The pointer/reference/address of the Dog you newed up is now lost, as no code refers to it, as the referent was replaced with the referent you got from al.get(). Eventually the Java garbage collector will destroy that object; in C++ you'd have "leaked" the memory.

The upshot is that you do need to create a variable that can refer to a Dog; you don't need to create a Dog with new.

(In truth you don't need to create a reference, as what you really ought to be doing is returning what a Map returns from its get() function. If the Map isn't parametrized on Dog, like this: Map<Dog>, then you'll need to cast the return from get, but you won't need a reference: return (Dog) map.get(id); or if the Map is parameterized, return map.get(id). And that one line is your whole function, and it'll be faster than iterating an array for most cases.)

Answer 2

You have to loop through the entire array, there's no changing that. You can however, do it a little easier

for (Dog dog : list) {
  if (dog.getId() == id) {
    return dog; //gotcha!
  }
}
return null; // dog not found.

or without the new for loop

for (int i = 0; i < list.size(); i++) {
  if (list.get(i).getId() == id) {
    return list.get(i);
  }
}

Answer 3

To improve performance of the operation, if you're always going to want to look up objects by some unique identifier, then you might consider using a Map<Integer,Dog>. This will provide constant-time lookup by key. You can still iterate over the objects themselves using the map values().

A quick code fragment to get you started:

// Populate the map
Map<Integer,Dog> dogs = new HashMap<Integer,Dog>();
for( Dog dog : /* dog source */ ) {
    dogs.put( dog.getId(), dog );
}

// Perform a lookup
Dog dog = dogs.get( id );

This will help speed things up a bit if you're performing multiple lookups of the same nature on the list. If you're just doing the one lookup, then you're going to incur the same loop overhead regardless.

Answer 4

I was interested to see that the original poster used a style that avoided early exits. Single Entry; Single Exit (SESE) is an interesting style that I've not really explored. It's late and I've got a bottle of cider, so I've written a solution (not tested) without an early exit.

I should have used an iterator. Unfortunately java.util.Iterator has a side-effect in the get method. (I don't like the Iterator design due to its exception ramifications.)

private Dog findDog(int id) {
    int i = 0;
    for (; i!=dogs.length() && dogs.get(i).getID()!=id; ++i) {
        ;
    }

    return i!=dogs.length() ? dogs.get(i) : null;
}

Note the duplication of the i!=dogs.length() expression (could have chosen dogs.get(i).getID()!=id).

Answer 5

Assuming that you've written an equals method for Dog correctly that compares based on the id of the Dog the easiest and simplest way to return an item in the list is as follows.

if (dogList.contains(dog)) {
   return dogList.get(dogList.indexOf(dog));
}

That's less performance intensive that other approaches here. You don't need a loop at all in this case. Hope this helps.

P.S You can use Apache Commons Lang to write a simple equals method for Dog as follows:

@Override
public boolean equals(Object obj) {  
   EqualsBuilder builder = new EqualsBuilder().append(this.getId(), obj.getId());      
   return builder.isEquals();
}