Implementing ArrayList class manually

[Campbell Ritchie]

Good grief!
I go to Newcastle for their beer festival, come back and find all this has happened while I wasn’t watching.

Right: implement indexOf without using return more than once.

[Mansukhdeep Thind]

Here it is :

/**
	 * Returns the index of the object passed to the method or 
	 * -1 if there is no such object in the list or object is null
	 * @param object - object whose index is to be found
	 * @return index of the object passed or -1 if it does not exist	or it is null 
	 */
	public final int indexOf(T object){

		int indexPos = -1;

		for(int i = 0; i < size; i++){
			if(values[i].equals(object)){
				indexPos = i;
			}
		}
		return indexPos;
	}

What would that achieve Campbell?

[Jeff Verdegan]

Mansukhdeep Thind wrote:

/**
	 * Returns the index of the object passed to the method or 
[SNIP]
		for(int i = 0; i < size; i++){
			if(values[i].equals(object)){
				indexPos = i;
			}
		}
		return indexPos;
	}

In Java's ArrayList, if the element is present multiple times, the first index where it occurs is what's returned. That seems the most intuitive approach. You don't specify it one way or the other. How is yours meant to behave in a multiple match situation? Or are you deliberately leaving that unspecified? Regardless, you should document what the caller can expect (or what he cannot expect, if that's the case).

And for what it's worth, I do not agree with the suggestion to get it down to a single return statement. I think it's easier to write and to read with multiple returns. That's just my opinion though.

[Campbell Ritchie]

Mansukhdeep Thind wrote: . . .
What would that achieve Campbell?

Finding the last index of the object. You are supposed to find the first index.

[Campbell Ritchie]

I know a lot of people disagree about multiple or single return. In this instance, it makes you think about how the loop runs.
I happen to disagree about not permitting nulls, but that is a constraint MT has put upon himself. In which case that method should prohibit seeking nulls, preferably with an Exception.

[Mansukhdeep Thind]

Jeff Verdegan wrote:

Mansukhdeep Thind wrote:

/**
	 * Returns the index of the object passed to the method or 
[SNIP]
		for(int i = 0; i < size; i++){
			if(values[i].equals(object)){
				indexPos = i;
			}
		}
		return indexPos;
	}

In Java's ArrayList, if the element is present multiple times, the first index where it occurs is what's returned. That seems the most intuitive approach. You don't specify it one way or the other. How is yours meant to behave in a multiple match situation? Or are you deliberately leaving that unspecified? Regardless, you should document what the caller can expect (or what he cannot expect, if that's the case).

OK Jeff. Here is the corrected version for returning only the first occurrence:

/**
	 * Returns the index of the first occurrence of the object passed to the method or 
	 * -1 if there is no such object in the list or object is null
	 * @param object - object whose index is to be found
	 * @return index of the object passed or -1 if it does not exist is null 
	 */
	public final int indexOf(T object){

		int indexPos = -1;

		for(int i = 0; i < size; i++){
			if(values[i].equals(object)){
				indexPos = i;
				break;
			}
		}
		return indexPos;
	}

Just needed to introduce the break statement.

Jeff Verdegan wrote:And for what it's worth, I do not agree with the suggestion to get it down to a single return statement. I think it's easier to write and to read with multiple returns. That's just my opinion though.

On what basis does one decide which route to take, what choice to make? Of course there are many schools of thought regarding one issue. How do you decide? Is it simply ones experiences over the years or is there something more to it?

[Campbell Ritchie]

If you don’t permit multiple return, you don’t permit break; either.

[Mansukhdeep Thind]

Campbell Ritchie wrote:If you don’t permit multiple return, you don’t permit break; either.

What do you mean?

[Campbell Ritchie]

Try writing that loop without break;

[Campbell Ritchie]

By the way: what will happen if you try myCustomList.indexOf(null)?

[Mansukhdeep Thind]

But it is working as expected. Why should I not use break? It is correctly returning the index of the first occurrence of the element if found, else -1. What are you getting at?

[Mansukhdeep Thind]

Campbell Ritchie wrote:By the way: what will happen if you try myCustomList.indexOf(null)?

It will return -1. nulls are not permitted in my custom list.

[Campbell Ritchie]

You sure it will return -1?
And I would like to see that you know how to write the loop without break. It might be faster to use break, but it is a skill any programmer should have, to be able to follow the conventions of structured programming.

[Campbell Ritchie]

You are right; since you cannot get nulls into your List, you will not suffer any Exceptions in that loop. If you permit null arguments, you might do well to wrap the entire loop in an if (object != null)… block.

[Jeff Verdegan]

Campbell Ritchie wrote:I happen to disagree about not permitting nulls, but that is a constraint MT has put upon himself. In which case that method should prohibit seeking nulls, preferably with an Exception.

I don't think it should be an exception. Searching for something that can't be there in the first place should be no different than searching for something that could be there but doesn't happen to be at the moment. "Where is X?" "Not here. (-1)" Basically the same situation as when you look for a String in a List<Integer>.

On the other hand, I can see why in some cases it might make sense to throw the exception. For instance, if we're calling binarySearch() on a sorted list that doesn't allow null. Since the list doesn't allow null, our ordering method might not have rules for how it compares, and hence it's not defined what value to return for "the negative of the index where it would go if it were present."

Other cases might be if you have something optimized for performance in such a way that simply checking for null isn't a viable option if you want to keep that optimization (though I can't imaging how that might arise). Or if you just simply don't want to clutter your code with null checks all over the place.

In this particular case though, I don't see a reason to throw an exception just because somebody looks for null.

[Campbell Ritchie]

I take your point, Jeff. That method will simply ignore nulls. If it were me writing it, I would permit nulls in the list, so they would be handled without any Exceptions.

[Mansukhdeep Thind]

Campbell Ritchie wrote:You sure it will return -1?
And I would like to see that you know how to write the loop without break. It might be faster to use break, but it is a skill any programmer should have, to be able to follow the conventions of structured programming.

How to go about doing it without the help of a break statement? What is structured programming?

[Campbell Ritchie]

1: It is easy.
2: Structured programming uses sequence, iteration and selection exclusively. No goto, break, continue, etc. Böhm and Jacopini 1966. Recursion is permitted since recursion and iteration are semantically identical.

[Mansukhdeep Thind]

Campbell Ritchie wrote:1: It is easy.
2: Structured programming uses sequence, iteration and selection exclusively. No goto, break, continue, etc. Böhm and Jacopini 1966. Recursion is permitted since recursion and iteration are semantically identical.

This is what I could think of :

/**
	 * Returns the index of the first occurrence of the object passed to the method or 
	 * -1 if there is no such object in the list or object is null
	 * @param object - object whose index is to be found
	 * @return index of the object passed or -1 if it does not exist is null 
	 */
	public final int indexOf(T object){

		int [] indexPos = new int[size];

		for(int i = 0; i < size; i++){
			if(values[i].equals(object)){
				indexPos[i] = i;
				//break;
			}
		}

		for(int j = 0; j < size; j++){
			if (indexPos[j] != 0){
				return indexPos[j];
			}			
		}
		return -1;

	}

[Campbell Ritchie]

Not convinced. Missing out the break and multiple returns should make the method shorter. And you don’t need two loops. Remember you can only return 1 value. You only want 1 value: the first location you found your object at. You need to terminate the loop without using break;

[Mansukhdeep Thind]

Campbell Ritchie wrote:Not convinced. Missing out the break and multiple returns should make the method shorter. And you don’t need two loops. Remember you can only return 1 value. You only want 1 value: the first location you found your object at. You need to terminate the loop without using break;

/**
	 * Returns the index of the first occurrence of the object passed to the method or 
	 * -1 if there is no such object in the list or object is null
	 * @param object - object whose index is to be found
	 * @return index of the object passed or -1 if it does not exist is null 
	 */
	public final int indexOf(T object){

		for(int i = 0; i < size; i++){
			if(values[i].equals(object)){
				return i;
			}
		}

		return -1;

	}

Convinced?

[Jeff Verdegan]

That's how I'd do it (except that I'd add one small optimization for handling null), but I think Campbell is suggesting you do it with a single return statement and without using break (although to be honest, I'm not really sure what he's driving at right now).

[Campbell Ritchie]

Mansukhdeep Thind wrote: . . . Convinced?

About your inability to read only one return, yes.

Shall I let you out of your misery? As I often say to our undergraduates, these things are simpler than you think. You have been overthinking things. You will of course get better performance with the version with break or two returns.

public int indexOf(T ob)
{
   int index = -1;
   if (ob != null)
   {
      for (int i = 0; i < size && index < 0; i++))
      {
         if (ob.equals(values[i])
         {
             index = i;
         }
      }
   }
   return index;
}

Because I wrapped the loop in a != null test, you can use both ob.equals and values[i].equals secure in the knowledge you won’t have a null exception. If ob == null and you don’t permit nulls in your List, there is no point in iterating it at all. Go straight to the end of the loop and to the return statement. And the && allows you to terminate the loop without using break or continue.

[Campbell Ritchie]

No need to write -1 if null in the documentation. It is unnecessary because your user should know he will never find a null anyway.

[Mansukhdeep Thind]

So, shall we proceed with the next method Campbell? Shall I show you remove(T)?

[Winston Gutkowski]

Campbell Ritchie wrote:You will of course get better performance with the version with break or two returns...

Or more.

@Mansukhdeep: One simple optimization you might want to consider is a "does my List allow null values?" flag (or, possibly even better, method). In your case, you simply set it to (or have it return) false, but then your method can be written to allow for the case where it does, viz (in "non-structured" style):

public int indexOf(T obj) {
   if (obj == null) {
      if (!nullsAllowed())
         return -1;
      for (int i = 0; i < size; i++) {
         if (values[i] == null)
            return i;
      }
   } else {
      for (int i = 0; i < size; i++) {
         if (obj.equals(values[i])
            return i;
      }
   }
   return -1;
}

There are loads of ways of skinning a cat.

Winston

[Mansukhdeep Thind]

Here is the remove(T) method Campbell:

/**
	 * Removes the first occurrence of the object from the list, if any,
	 * and returns a boolean true if the list changed as a result of a call to 
	 * this method. If the list does not contain the specified object, it returns false.
	 * @param object - element which needs to be removed from the list
	 * @return a boolean true or false
	 */
	public final boolean remove(T object){

		int currentIndex=0;

		for(int i = 0; i < size ; i++){
			if(values[i].equals(object)){
				currentIndex=i;
				for(int j = currentIndex; j < size; j++){

					values[j] = values[j+1];
				}
				size--;
				return true;
			}
		}
		return false;

	}

[Campbell Ritchie]

If you are going to permit nulls, what about this?

for (int i = 0; i < size; i++)
{
   if (ob == values[i] || ob != null && ob.equals(values[i]))
   {
      // etc
   }
}

If ob is null, then you get true if values[i] is null. The || means you never need to do the second half of the disjunction. If you get as far as the ob != null, and that bit returns false, then values[i] wasn’t null, so the whole thing evaluates to false. You can write it like this, but the additional () are redundant.

for (int i = 0; i < size; i++)
{
   if (ob == values[i] || (ob != null && ob.equals(values[i])))
   {
      // etc
   }
}

The new remove method has the potential memory leak because you are not nulling out the last element. I also think the code to move all elements down one is duplicated in the overridden remove methods, and should be re-factored into a private method. The currentIndex local variable is redundant; you can use i instead.

You can have a boolean removed (initialised to false) and change line 20 to removed = true; and line 23 becomes return removed;
In that case you might wish to add && !removed to the continuation condition in the loop. Or use i (not j) in the second loop, so at the end of the second loop i == size and both loops terminate.

Suggest you change the @return tag to read something like this
/** ... @return true if the element was removed from the list, otherwise false. ... */

[Jeff Verdegan]

Campbell Ritchie wrote:
Suggest you change the @return tag to read something like this
/** ... @return true if the element was removed from the list, otherwise false. ... */

... vs. the current

  * @return a boolean true or false 

All of Campbell's advice was good, but I'm going to focus on this bit to add my voice to. Please, never ever write comments that simply say exactly what the code says, but with more words. Assume people reading your code can read code. Comments like that are redundant and add no value, only clutter.

We already know it returns a boolean because the declaration tells us so, and we already know it will be true or false because we know those are the only two values possible for a boolean. You have used six words to say the same thing that you say a couple lines further down with one.

[Mansukhdeep Thind]

Campbell Ritchie wrote:If you are going to permit nulls, what about this?

for (int i = 0; i < size; i++)
{
   if (ob == values[i] || ob != null && ob.equals(values[i]))
   {
      // etc
   }
}

If ob is null, then you get true if values[i] is null. The || means you never need to do the second half of the disjunction. If you get as far as the ob != null, and that bit returns false, then values[i] wasn’t null, so the whole thing evaluates to false. You can write it like this, but the additional () are redundant.

for (int i = 0; i < size; i++)
{
   if (ob == values[i] || (ob != null && ob.equals(values[i])))
   {
      // etc
   }
}

But Campbell, my custom class does not allow null values to be added to the list in the first place. Why should I do all this?

Campbell Ritchie wrote:The new remove method has the potential memory leak because you are not nulling out the last element.

I do not understand. The last element is null after call to remove(T). Print out and see for yourself. Am I wrong?

Campbell Ritchie wrote: I also think the code to move all elements down one is duplicated in the overridden remove methods, and should be re-factored into a private method.

Which overridden remove methods are using this code Campbell?

Campbell Ritchie wrote:The currentIndex local variable is redundant; you can use i instead.

Fine.

Campbell Ritchie wrote:You can have a boolean removed (initialised to false) and change line 20 to removed = true; and line 23 becomes return removed;

Done.

Campbell Ritchie wrote:In that case you might wish to add && !removed to the continuation condition in the loop. Or use i (not j) in the second loop, so at the end of the second loop i == size and both loops terminate.

Not sure what you are hinting at.

Campbell Ritchie wrote:Suggest you change the @return tag to read something like this
/** ... @return true if the element was removed from the list, otherwise false. ... */

OK.


Here is the changed method:

/**
	 * Removes the first occurrence of the object from the list, if any,
	 * and returns a boolean true if the list changed as a result of a call to 
	 * this method. If the list does not contain the specified object, it returns false.
	 * @param object - element which needs to be removed from the list
	 * @return a boolean true if the element was found and removed from
	 * the list else returns false
	 */
	public final boolean remove(T object){	

		boolean removed = false;

		for(int i = 0; i < size ; i++){
			if(values[i].equals(object)){

				for(int j = i; j < size; j++){

					values[j] = values[j+1];
				}

				size--;
				removed = true;
			}
		}
		return removed;

	}

Please explain the parts that I have not understood.

[Mansukhdeep Thind]

Jeff Verdegan wrote:

Campbell Ritchie wrote:
Suggest you change the @return tag to read something like this
/** ... @return true if the element was removed from the list, otherwise false. ... */

... vs. the current

  * @return a boolean true or false 

All of Campbell's advice was good, but I'm going to focus on this bit to add my voice to. Please, never ever write comments that simply say exactly what the code says, but with more words. Assume people reading your code can read code. Comments like that are redundant and add no value, only clutter.

We already know it returns a boolean because the declaration tells us so, and we already know it will be true or false because we know those are the only two values possible for a boolean. You have used six words to say the same thing that you say a couple lines further down with one.

Correction made Jeff.

[Campbell Ritchie]

Mansukhdeep Thind wrote: . . . But Campbell, my custom class does not allow null values to be added to the list in the first place. Why should I do all this?

I said if you are permitting nulls. I would permit nulls, you wouldn’t. That bit is only relevant if you permit nulls, so you can ignore it.

I do not understand. The last element is null after call to remove(T). Print out and see for yourself. Am I wrong?

I think you are right. What happens when you have a List whose capacity and size are the same, however? Are you sure you won’t suffer an index out of bounds exception?

Which overridden remove methods are using this code Campbell?

Sorry. My mistake. I meant overloaded I am pretty sure you are using similar code in both remove methods, so you can refactor that.

. . .

Done.

Campbell Ritchie wrote:In that case you might wish to add && !removed to the continuation condition in the loop. Or use i (not j) in the second loop, so at the end of the second loop i == size and both loops terminate.

Not sure what you are hinting at.

If you are not using break or similar to terminate the loop, you need to do something else to terminate, otherwise you may end up removing the element twice.

Campbell Ritchie wrote:Suggest you change the @return tag to read something like this
/** ... @return true if the element was removed from the list, otherwise false. ... */

I have made some more changes. I shall let you check for out by one errors in those loops. There are all sorts of other changes you could make.

    /**
	 * Removes the first occurrence of the object from the list, if any,
	 * and returns a boolean true if the list changed as a result of a call to 
	 * this method. If the list does not contain the specified object, it returns false.
	 * @param object - element which needs to be removed from the list
	 * @return true if the element was found and removed from
	 * the list else returns false
	 */
    public final boolean remove(T object)
    {	
        boolean removed = false;
        for(int i = 0; i < size && !removed ; i++)
        {
            if(values[i].equals(object))
            {
               for (int j = i; j < size - 1; j++)
               {
                   values[j] = values[j + 1];
               }
               values[--size] = null;
               removed = true;
            }
        }
        return removed;
    }

Please explain the parts that I have not understood.

[Mansukhdeep Thind]

Thank you for the suggestions Campbell. I shall go through them later. I have an interview tomorrow. Preparing for that right now. Will get back to you after that. Good night.

Also check your inbox for an important admin message.

[Winston Gutkowski]

Mansukhdeep Thind wrote:

Campbell Ritchie wrote:If you are going to permit nulls, what about this?

Here is the changed method:...

Here's another possibility for you. Since you've just gone to all that trouble to write an indexOf() method that already checks for nulls, why not:

public final boolean remove(T object) {
  final int found = indexOf(object);
  if (found < 0)
     return false;
  --size;
  if (found < size)
     System.arrayCopy(values, found + 1, values, found, size - found);
  values[size] == null; // not strictly needed if you always use 'size'
  return true;
}

PS: I totally agree with Jeff's comments about documentation, and I'd add another bit of advice: Don't document historical changes - that's the business of a version control system or a change log - document was IS, not what used to be.

Winston

[Campbell Ritchie]

Winston Gutkowski wrote: . . .
Here's another possibility for you. Since you've just gone to all that trouble to write an indexOf() method . . .

Agree totally. About 6.00 (GMT) last night I thought that is the wrong way to write a remove(T) method. You should use a combination of index and remove(int)

[Winston Gutkowski]

Campbell Ritchie wrote:You should use a combination of index and remove(int)

Oh yer. Forgot about remove(int). Duh.

Winston

[Mansukhdeep Thind]

Campbell Ritchie wrote:

Mansukhdeep Thind wrote: . . . But Campbell, my custom class does not allow null values to be added to the list in the first place. Why should I do all this?

I said if you are permitting nulls. I would permit nulls, you wouldn’t. That bit is only relevant if you permit nulls, so you can ignore it.

Understood.

Campbell Ritchie wrote:

Mansukhdeep Thind wrote:I do not understand. The last element is null after call to remove(T). Print out and see for yourself. Am I wrong?

I think you are right. What happens when you have a List whose capacity and size are the same, however? Are you sure you won’t suffer an index out of bounds exception?

You were right. I am getting an IndexOutOfBoundsException when the size becomes equal to capacity. I changed the method as follows:

/**
	 * Removes the first occurrence of the object from the list, if any,
	 * and returns a boolean true if the list changed as a result of a call to 
	 * this method. If the list does not contain the specified object, it returns false.
	 * @param object - element which needs to be removed from the list
	 * @return a boolean true if the element was found and removed from
	 * the list else returns false
	 */
	public final boolean remove(T object){	

		boolean removed = false;

		for(int i = 0; i < size ; i++){
			if(values[i].equals(object)){
				downCopy(i);
				removed = true;
			}
		}
		return removed;

	}

Refactored the part of the code which was, as you correctly said, getting duplicated into a new method downCopy(int) as follows:

/**
	 * Copies the elements from the index position passed 
	 * up until one less than the size and sets the last element
         * explicitly to null to prevent memory 
	 * leak. Also, decrements the size by 1. 
	 * @param indexPos - the index position passed from the calling method
	 */
	private final void downCopy(int indexPos){
		for(int i = indexPos; i < size-1; i++){
			values[i] = values[i+1];
		}

		values[--size] = null;
	}
	

So the remove(int) method changes as follows too:

/**
	 * Removes the element at the specified index position,if any, and
	 * shifts the elements to the right of that index one place to the left
	 * i.e. subtracts 1 from the indices of all elements to right of element at indexPos
	 * @param indexPos - index position of element to be removed
	 * @return - element removed from the list
	 * @throws IndexOutOfBoundsException if indexPos is less than 0 or greater than size of the list
	 */
	public final T remove(int indexPos){

		ensureCorrectIndex(indexPos);

		T temp = (T)values[indexPos];

		downCopy(indexPos);

		return temp;			

	}

Should we move on the the next method Campbell?

[Winston Gutkowski]

Mansukhdeep Thind wrote:You were right. I am getting an IndexOutOfBoundsException when the size becomes equal to capacity. I changed the method as follows:...

Still not sure why you're doing the search in the method. You're duplicating code.

Refactored the part of the code which was, as you correctly said, getting duplicated into a new method downCopy(int) as follows:

which is also unnecessary, since System.arrayCopy() already does what you want.

So the remove(int) method changes as follows too:

Now that does seem reasonable.

I'm not quite sure why you're casting values[x] though; surely it's the correct type already? And if not, get(x) most certainly should be.

Winston

[Mansukhdeep Thind]

Winston Gutkowski wrote:

Mansukhdeep Thind wrote:You were right. I am getting an IndexOutOfBoundsException when the size becomes equal to capacity. I changed the method as follows:...

Still not sure why you're doing the search in the method. You're duplicating code.

What part am I duplicating?

Winston Gutkowski wrote:

Mansukhdeep Thind wrote:Refactored the part of the code which was, as you correctly said, getting duplicated into a new method downCopy(int) as follows:

which is also unnecessary, since System.arrayCopy() already does what you want.

But I do not want to re use existing APIs.

Winston Gutkowski wrote:

Mansukhdeep Thind wrote:So the remove(int) method changes as follows too:

Now that does seem reasonable.

OK

Winston Gutkowski wrote:

Mansukhdeep Thind wrote:I'm not quite sure why you're casting values[x] though; surely it's the correct type already? And if not, get(x) most certainly should be.

Winston

Because it is a compilation error if I do not cast the value by doing:

T temp = (T)values[indexPos];

If I remove the cast, it is a compile time error.

[David Blaine]

Here is my own implementation. If you want me to make a separate thread out of it instead of keeping it in your post, then please ask the moderators to delete this post.

import java.util.*;

public class GrowableArray<T>{
	
	private T[] array;
	private int increaseSizeBy;
	private int currentIndex;//That is first free position available
	private int lastIndex;
	
	public GrowableArray(){		
		this.array = (T[]) new Object[10];
		this.currentIndex = 0;
		this.lastIndex = 10-1;
		this.increaseSizeBy = 10;
	}
	
	
	public GrowableArray(int initialSize){
		this.array = (T[]) new Object[initialSize];
		currentIndex = 0;
		lastIndex = initialSize - 1;
		
	}

	public void increaseSizeBy(int size){
		this.increaseSizeBy = size;
		
	}
	
	
	public void add(T anObject){
		
		if(currentIndex > lastIndex){ ;
			//create a bigger array
			int oldLength = array.length;
			int newLength = oldLength + this.increaseSizeBy;
			Object [] biggerArray = Arrays.copyOf(array, newLength);
			array = (T[]) biggerArray;
			currentIndex = oldLength;
			lastIndex = array.length-1;
			
		}else{
			array[currentIndex] = anObject;
			currentIndex++;
			
		}
		
	}
	
	
	public void display(){
		
		System.out.println();
		
		for(int i = 0; i < this.currentIndex; i++){
			System.out.print(array[i] + ", ");
			
		}
		
		System.out.println();
		
	}
	
	
	public static void main(String[]args){
		
		GrowableArray<Integer> gArr = new GrowableArray<Integer>();
		
		for(int i = 0; i <= 35; i++){
			gArr.add(i);

		}
		
		gArr.display();
	
		gArr.add(300);
		gArr.add(301);
		gArr.add(302);
		gArr.add(303);
		gArr.add(304);
		gArr.add(305);
		
		
		gArr.display();
		
	}
	
	
}