aspose 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

Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Implemented the ensureCapacity(int) method:



~ Mansukh
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

I tried my hand at implementing the addAll(Collection <? extends T>) method:



It is functioning properly. One doubt though. The API documentation says that it throws NullPointerException if collection is null. Am I supposed to cater for that in my method too? I ask this because NullPointerException is a Run time type, unchecked exception.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7838
    
  21

Mansukhdeep Thind wrote:Implemented the ensureCapacity(int) method:

Which doesn't do what you document it to (which is not necessarily wrong; just inconsistent). What if minimumCapacity is less than values.length?

Winston

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

Joined: Mar 17, 2011
Posts: 7838
    
  21

Mansukhdeep Thind wrote:I tried my hand at implementing the addAll(Collection <? extends T>) method:

Again, you're waaay overthinking this ... and you've still got it wrong.
1. There's absolutely no need to convert the collection to an array.
2. You already have a perfectly good method for adding elements, so why not use it?

It is functioning properly.

Then I'd say your testing isn't up to snuff. Try it with a collection that breaks the array capacity.

One doubt though. The API documentation says that it throws NullPointerException if collection is null. Am I supposed to cater for that in my method too? I ask this because NullPointerException is a Run time type, unchecked exception.

That latter point is irrelevant. Basically, there's nothing that says you have to slavishly follow the superclass method, but if you vary from it you must document the fact. There's also a difference between semantics and intent: changing things like how you do error-checking is probably fine, but you should be very careful not to change the intent of a superclass method; otherwise you may cause clients problems because they've assumed that your method works as documented for the interface. Once again, whatever you decide, DOCUMENT IT.

Winston
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Winston Gutkowski wrote:
Mansukhdeep Thind wrote:Implemented the ensureCapacity(int) method:

Which doesn't do what you document it to (which is not necessarily wrong; just inconsistent). What if minimumCapacity is less than values.length?

Winston


Why would someone call this method to reduce the capacity? It is meant to facilitate the increase of the list's current capacity. If I say ensureCapacity(100), it shall increase the capacity to 100. I don't understand how is it inconsistent with what I have documented it to do. The documentation clearly says "Increases.....".
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Winston Gutkowski wrote:
Mansukhdeep Thind wrote:I tried my hand at implementing the addAll(Collection <? extends T>) method:

Again, you're waaay overthinking this ... and you've still got it wrong.
1. There's absolutely no need to convert the collection to an array.
2. You already have a perfectly good method for adding elements, so why not use it?


Yes, I missed the part to grow the array in case size == values.length? Anyways, that is besides the point here. How do I re-use the add(T) method to add the elements of the passed collection to this list? That method only adds a single object of type T to the end of the list. How to get that object from the passed collection reference? The iterator.next() runs into an infinite loop if I try and retrieve elements of the collection one by one. Why is that happening?

EDIT: Here is the rectified addAll(Collection <? extends T>) method Winston:



No exceptions now. Works like a charm.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7838
    
  21

Mansukhdeep Thind wrote:The documentation clearly says "Increases.....".

But you haven't enforced it. Right now it's just a "resize" method - which you've already written.

Winston
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Winston Gutkowski wrote:
Mansukhdeep Thind wrote:The documentation clearly says "Increases.....".

But you haven't enforced it. Right now it's just a "resize" method - which you've already written.

Winston


Right, so does this look better:



Now it shall only increase the capacity, otherwise the capacity will remain unchanged. Is it correct now Winston?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:




Is that how you always use an Iterator? That's kind of messed up.

1. You should be using a foreach loop, rather than an explicit Iterator.

2. Even if you do use an explicit iterator, you shouldn't be counting up to size().

3. Even if you're counting up to size(), there's no need to call size() on every iteration.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:
values = resizeArray(values, minimumCapacity);


Why are you passing values as an argument to that method? Do you sometimes pass a different array?
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7838
    
  21

Jeff Verdegan wrote:Why are you passing values as an argument to that method? Do you sometimes pass a different array?

That was my suggestion. Basically, it allows the method to be used for both resizing and initialization.

Winston
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Winston Gutkowski wrote:
Jeff Verdegan wrote:Why are you passing values as an argument to that method? Do you sometimes pass a different array?

That was my suggestion. Basically, it allows the method to be used for both resizing and initialization.

Winston


You mean the client can pass in an array to use? That doesn't sound good. Or am I misunderstanding what you mean by initialization?
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7838
    
  21

Mansukhdeep Thind wrote:Right, so does this look better:

Much. When you're writing methods, try to see if you can re-use code.

Winston
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
Mansukhdeep Thind wrote:




Is that how you always use an Iterator? That's kind of messed up.

1. You should be using a foreach loop, rather than an explicit Iterator.

2. Even if you do use an explicit iterator, you shouldn't be counting up to size().

3. Even if you're counting up to size(), there's no need to call size() on every iteration.


Yes Jeff, that is indeed messed up. Here you go:



Better now?
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7838
    
  21

Jeff Verdegan wrote:You mean the client can pass in an array to use? That doesn't sound good. Or am I misunderstanding what you mean by initialization?

You have to go back about 30 posts.

The problem with arrays in a generic class like this is that they have to be cast at least once, and a method that takes a previous array and a size allows it to be used for initialization (if the passed array is null) or resizing if there is a "previous" array; hence, one - and only one - cast, and a consistent method for all forms of allocation. It can also be stuck in a utility class.

Winston
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Winston Gutkowski wrote:
Jeff Verdegan wrote:You mean the client can pass in an array to use? That doesn't sound good. Or am I misunderstanding what you mean by initialization?

You have to go back about 30 posts.


No thanks. I'll just trust you on this one.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
Winston Gutkowski wrote:
Jeff Verdegan wrote:You mean the client can pass in an array to use? That doesn't sound good. Or am I misunderstanding what you mean by initialization?

You have to go back about 30 posts.


No thanks. I'll just trust you on this one.


Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

The addAll(indexPos, Collection<? extends T>) method :



Did I miss anything? Any scope for improvement?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Are you asking why did I put indexPos++ inside the loop?

EDIT: Why can't I see your post Jeff? I just saw it about a minute ago.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Here's one place where I wouldn't take the simplest approach. If the collection you're adding has M elements, and there are N elements in your existing list at or after indexPos, you'll be doing M * N moves, just moving the same N elements M times. You could just move them once, changing that part of this method from O(M*N) to simply O(N).
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:Are you asking why did I put indexPos++ inside the loop?

EDIT: Why can't I see your post Jeff? I just saw it about a minute ago.


I removed my post because I didn't pay enough attention to what you were doing, so my comment was irrelevant.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
Mansukhdeep Thind wrote:Are you asking why did I put indexPos++ inside the loop?

EDIT: Why can't I see your post Jeff? I just saw it about a minute ago.


I removed my post because I didn't pay enough attention to what you were doing, so my comment was irrelevant.


Smart move. Caught red handed though.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:Here's one place where I wouldn't take the simplest approach. If the collection you're adding has M elements, and there are N elements in your existing list at or after indexPos, you'll be doing M * N moves, just moving the same N elements M times. You could just move them once, changing that part of this method from O(M*N) to simply O(N).


Not sure what you are suggesting here? Do you want me to shift all the elements to the right of the indexPos at once by number of positions equal to size of the collection? And then insert the collection.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:
Jeff Verdegan wrote:Here's one place where I wouldn't take the simplest approach. If the collection you're adding has M elements, and there are N elements in your existing list at or after indexPos, you'll be doing M * N moves, just moving the same N elements M times. You could just move them once, changing that part of this method from O(M*N) to simply O(N).


Not sure what you are suggesting here? Do you want me to shift all the elements to the right of the indexPos at once by number of positions equal to size of the collection? And then insert the collection.


Yes. Exactly that.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Is this close to what you wanted Jeff:

Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7838
    
  21

Mansukhdeep Thind wrote:Is this close to what you wanted Jeff:

Don't think so.

First: what Jeff is suggesting is an efficiency upgrade; so probably only worth thinking about once you have a working method.
And to me by far the simplest method is:All he's saying is that you can make it more efficient by simply copying elements once, viz:As always, it's just one possibility, and it relies on 'collection's size not changing while the method is running, but reuse existing code wherever you can.

Winston
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7838
    
  21

Actually, there's still a possible inefficiency in what I wrote (yet another reason, if any were needed, not to offer solutions ); I'll leave you to work out why - and it's not obvious.

Winston
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Well , I would stick to my first implementation. An update Winston, I got a job.

Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Winston Gutkowski wrote:Actually, there's still a possible inefficiency in what I wrote (yet another reason, if any were needed, not to offer solutions ); I'll leave you to work out why - and it's not obvious.

Winston


Well, for that I would first need to understand why you wrote what you just did. I think I would rather pass this one and move on to the next method.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7838
    
  21

Mansukhdeep Thind wrote:Well, for that I would first need to understand why you wrote what you just did. I think I would rather pass this one and move on to the next method.

I wrote it to illustrate Jeff's point. Resizing your array involves copying elements, so if you add many elements using code designed to add one (which is a perfectly reasonable point to start from), you may be copying the same stuff many times (hence O(n²)).

Furthermore, the method above is generally used to insert elements in the middle of your array, so even if you resize first, you still need to copy the "end" portion again. However, this is still far better than doing multiple resizes, so a simplified version might look something like:
Winston
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7838
    
  21

Mansukhdeep Thind wrote:I think I would rather pass this one and move on to the next method.

Fine. But don't forget it.

Winston
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

I got really close to what you just wrote. Didn't I Winston?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Winston Gutkowski wrote:
Mansukhdeep Thind wrote:I think I would rather pass this one and move on to the next method.

Fine. But don't forget it.

Winston


The only way I would have not forgotten it is if I had thought of it in the first place before you or Jeff. You guys catch me by the ear just when I am about to screw up things. I need to learn to do that to myself.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7838
    
  21

Mansukhdeep Thind wrote:I got really close to what you just wrote. Didn't I Winston?

Not really, because
(a) growArray() doesn't specify a size to grow to.
(b) You're not reusing methods you've already written.
(c) Your loop logic is incredibly tortured. If you want all the elements of a collection, use for-each. And if you're worried about making your method bomb-proof from updates to collection, just clone it first, viz:
collection = new ArrayList<T>(collection);

Winston
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Winston Gutkowski wrote: And if you're worried about making your method bomb-proof from updates to collection, just clone it first, viz:
collection = new ArrayList<T>(collection);


That doesn't really protect against collection changing. It just narrows the window a little. The whole class has no thread-safety in it, so I don't see any point in worrying about it here either. In fact, it's impossible to guarantee that collection won't be structurally modified while during addAll() from within this class. We need cooperation from the caller for that.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38910
    
  23
Not that there is any thread‑safety to its Sun/Oracle counterpart either.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7838
    
  21

Jeff Verdegan wrote:That doesn't really protect against collection changing. It just narrows the window a little...

True. However, it'll also cause the method to throw an exception quickly, if it does at all.

Winston
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
Winston Gutkowski wrote: And if you're worried about making your method bomb-proof from updates to collection, just clone it first, viz:
collection = new ArrayList<T>(collection);


That doesn't really protect against collection changing. It just narrows the window a little. The whole class has no thread-safety in it, so I don't see any point in worrying about it here either. In fact, it's impossible to guarantee that collection won't be structurally modified while during addAll() from within this class. We need cooperation from the caller for that.


Is there NO WAY AT ALL to make this operation atomic Jeff? Can't we somehow achieve a handle on the collection and lock it down when it is passed as an argument to the addAll() method to ensure that the collection does not change when it is being inserted in the list? Why is it impossible? Is it because Java uses pass by value? Would it have been possible in case of C++?
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Implementing ArrayList class manually