A generic array list
Hi everyone,
I am trying to write a generic version of array list. I hava a method called 'removeElement()' which returns the element removed from the array list. I got the code right, but the compiler is showing me an error message:"This method must return a result of type E".
public E removeElement(int i)
throws IndexOutOfBoundsException{
try{
if (!isValidIndex(i))
thrownew IndexOutOfBoundsException("Invalid " +
"Array Index");
//E[] temp = (E[]) new Object[1];
//temp[1] = A[i];
E temp = A[i];
for (int j = i; j < size-1; j++){
A[j] = A[j+1];
}// end of for
size--;
return temp;
}// end of try
catch(IndexOutOfBoundsException error){
System.out.println("Error: " + error.getMessage());
}// end of catch block
}// end of removeElement()
Any help will be greatly appreciated.
cheers!
[1783 byte] By [
buteForcea] at [2007-11-26 13:52:43]
# 1
If you get an IndexOutOfBoundsException, you don't return anobject of type E. You don't return anything, in fact.Either don't catch the exception, or re-throw it.
# 2
Hi Eric,
Thank you for your reply. Here is how fixed the error few minutes ago:
public E removeElement(int i)
throws IndexOutOfBoundsException {
E[] contentReturn = (E[]) new Object[1];
try {
if (!isValidIndex(i))
throw new IndexOutOfBoundsException("Invalid " +
"Array Index");
contentReturn[0] = A[i];
for (int j = i; j < size-1; j++) {
A[j] = A[j+1];
} // end of for
size--;
} // end of try
catch(IndexOutOfBoundsException error) {
System.out.println("Error: " + error.getMessage());
} // end of catch block
return contentReturn[0];
} // end of removeElement()
I did not write the driver program yet, but the error is not there any more.
# 3
Okay, so, first, why are you adding a method that performs the
same functionality as remove()? This makes no sense.
Second, why does your method declare that it throws a method
which it does not, in fact, throw? All you're doing is trading a
IOOBE for a NullPointerException. What do you think this is
buying you?
Third, why are you allocating an array for contentReturn when
it's only a single value?
Fourth, what does any of this have to do with algorithms?
One of us is very confused, and I have this strong feeling that it's you.
# 4
> ...> I got the code right, but the compiler is showing me an> error message: > ...Let me get this straight: your code is correct, but the compiler is giving you a hard time?
# 5
> ...> One of us is very confused, and I have this strong> feeling that it's you.Apparently his compiler is the one that's confused!; )
# 6
>>Fourth, what does any of this have to do with algorithms?
Well if you notice carefully you will see that, the removeElement() method of Array List implementation is shifting down when the user removes an element. If you have n elements in an Array List and you are trying to delete the last element of the Array List, this method will shift down upto O(n) elements. Imagine if you have 1 million element in your array list, what is going to be the performance? We can overcome this shortcoming by using a generic Linked List, which does the same job in O(1) time.
Since I am working with the performance issue of a datastructure, the algorithm forum is the place to go.
Take it easy!
# 7
> Since I am working with the performance issue of a
> datastructure, the algorithm forum is the place to go.
It looks like your question is related to the programming language, and not the algorithm. It should have been posted in New to Java Programming.
You should add "learning when to throw and catch exceptions" to the list of things you need to learn.
# 8
> We can> overcome this shortcoming by using a generic Linked> List, which does the same job in O(1) time.How can you do this? In my understanding the removal in a linked list will take O(n) time.
# 9
> How can you do this? In my understanding the removal
> in a linked list will take O(n) time.
People who do this calculation only ever look at the time required to do the removal. They never notice that in an ArrayList it takes O(1) to find the element to remove whereas in a LinkedList it takes O(n) to find that element.
# 10
> Well if you notice carefully you will see that, the
> removeElement() method of Array List implementation
There is no removeElement() method in java.util.ArrayList.
There is one in java.utilVector.
So what are you talking about here?
> is shifting down when the user removes an element.
Yes!
> If
> you have n elements in an Array List and you are
> trying to delete the last element of the Array List,
> this method will shift down upto O(n) elements.
No. In that case it will shift 0 elements.
The problem arises if you want to remove the first element.
> Imagine if you have 1 million element in your array
> list, what is going to be the performance?
Still better than your implementation in the code above!
> We can
> overcome this shortcoming by using a generic Linked
> List, which does the same job in O(1) time.
Well, if i want to have a generic Linked List, i would use java.util.LinkedList.
> Since I am working with the performance issue of a
> datastructure, the algorithm forum is the place to
> go.
Hm, seems more like you are creating a performance issue with a data structure!
Why do you want to catch the Exception?
# 11
> > How can you do this? In my understanding the
> removal
> > in a linked list will take O(n) time.
>
> People who do this calculation only ever look at the
> time required to do the removal. They never notice
> that in an ArrayList it takes O(1) to find the
> element to remove whereas in a LinkedList it takes
> O(n) to find that element.
Only if you alread yhave the index in question.
But in an ArrayList it will takes O(n) to remove while in a LinkedList it requires O(1).
If you are scanning a List via an Iterator to remove some elements that match some criteria the LinkedList definitely is the better choice, because ListIterator.remove requires O(1) for every element to remove.
