File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes Implementing ArrayList class manually Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Implementing ArrayList class manually" Watch "Implementing ArrayList class manually" New topic
Author

Implementing ArrayList class manually

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
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
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Here it is :



What would that achieve Campbell?


~ Mansukh
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:



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
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
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
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
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
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
Mansukhdeep Thind wrote:



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:



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
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
If you don’t permit multiple return, you don’t permit break; either.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

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


What do you mean?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
Try writing that loop without break;
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
By the way: what will happen if you try myCustomList.indexOf(null)?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

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
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

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
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
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
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
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
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

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
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
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
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

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
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
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
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

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 :

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
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
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

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;




Convinced?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

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
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
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.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
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
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
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

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

Joined: Mar 17, 2011
Posts: 8421
    
  23

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):There are loads of ways of skinning a cat.

Winston

Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Here is the remove(T) method Campbell:

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
If you are going to permit nulls, what about this?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.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
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

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


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
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:If you are going to permit nulls, what about this?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.


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:



Please explain the parts that I have not understood.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

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


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
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
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.



Please explain the parts that I have not understood.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

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
Bartender

Joined: Mar 17, 2011
Posts: 8421
    
  23

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: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
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
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
Bartender

Joined: Mar 17, 2011
Posts: 8421
    
  23

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

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

Winston
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

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:



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



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



Should we move on the the next method Campbell?
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8421
    
  23

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
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

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:




If I remove the cast, it is a compile time error.
David Blaine
Ranch Hand

Joined: Mar 23, 2013
Posts: 70
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.

 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Implementing ArrayList class manually