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

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39828
    
  28
If you have a full 10‑length array, and remove the 3rd element, you will then try to copy the elements from element3→element2 until you get to element10→element9. And there you get the Exception. There is no need to copy into element9, because we already know what it should be: null. So you can do your copying up to element9→element8, then set element9 to null. The quickest way to do that is probably to combine the -- operator (or one of the -- operators ‍) with an assignment in the array. And you will have to make a few changes to i+1/i/i-1 in the copying loop.
I thought we had discussed casting earlier in this thread. But that was about 97 years ago, so you may have forgotten. I think we decided you can either cast the whole array, once in the constructor, or each element as you retrieve it from the arrayI had never noticed that add(E) and add(int, E) had different return types. That seems very strange. I presume the List interface has the different return types, too. Just one of those things. I would have designed it with the same return type for both. You need a boolean return for add(E) because it is the same add method as used by Set (overridden from Collections), which sometimes does and sometimes doesn’t complete the addition. But add(int, E) can only operate on a List, so obviously it always adds the E successfully (or throws an Exception).
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:If you have a full 10‑length array, and remove the 3rd element, you will then try to copy the elements from element3→element2 until you get to element10→element9. And there you get the Exception. There is no need to copy into element9, because we already know what it should be: null. So you can do your copying up to element9→element8, then set element9 to null. The quickest way to do that is probably to combine the -- operator (or one of the -- operators ‍) with an assignment in the array. And you will have to make a few changes to i+1/i/i-1 in the copying loop.


So should I undo the changes to the above 3 methods add(T), add(int,T), ensureCorrectIndex(int) and only change remove(int) method as per your suggestion here i.e. copy up until the (size-1) and then explicitly set values[size] =null? Correct?

Campbell Ritchie wrote:I thought we had discussed casting earlier in this thread. But that was about 97 years ago, so you may have forgotten. I think we decided you can either cast the whole array, once in the constructor, or each element as you retrieve it from the array



That is exactly how my overloaded constructor looks like. But still you ought to cast the element being removed using remove(int), or else there is a compile time error i.e. I have to do this:




Campbell Ritchie wrote:I had never noticed that add(E) and add(int, E) had different return types. That seems very strange. I presume the List interface has the different return types, too. Just one of those things. I would have designed it with the same return type for both. You need a boolean return for add(E) because it is the same add method as used by Set (overridden from Collections), which sometimes does and sometimes doesn’t complete the addition. But add(int, E) can only operate on a List, so obviously it always adds the E successfully (or throws an Exception).


Yes, one of those things.


~ Mansukh
Sumit Suresh Rao
Greenhorn

Joined: Feb 16, 2009
Posts: 13
may be this can help : http://www.coderanch.com/t/605166/java/java/Dynamic-Array-code
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39828
    
  28
Mansukhdeep Thind wrote: . . . But still you ought to cast the element being removed using remove(int), or else there is a compile time error . . .
Good grief! Another triumph of Java generics.
Keep the ensureCorrectIndex method unchanged. I think this is what you had for add(E), which we were happy about:-The only problem with the remove(int) method is that you might run out of array when you are copying from values[i+1]→values[i], so the only bit in that method which needs changing is the loop. And that only needs subtle changes.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39828
    
  28
And I presume you have seen my mistake in the loop
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

This is what I could come up with:



It works. But can it be be made more concise? How to use the -- operator inside the loop to make the code as short as possible as you have advised above?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39828
    
  28
Mansukhdeep Thind wrote: . . . But can it be be made more concise? . . .
Yes, but I don’t think I said to use the -- operator inside the loop.

I think you could make that loop more elegant, and get rid of the following if. Draw a diagram of the List, as we had earlier:-Now use a pencil to work out the logic of removing element 1, for example.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

I got rid of the if:



But how to make the for loop more elegant? The logic to remove the element at any position simply calls for copying the (n+1)th index elements repeatedly to the nth index element up until the penultimate element is reached. What more is there to the logic that this?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39828
    
  28
I would suggest
for (int i = index + 1; i < size; i++)
{
  values[i - 1] = values[i];
}
That is about it Well, I think it is more elegant.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18902
    
    8

Sounds like a job for System.arrayCopy to me. That wouldn't produce "elegant" code -- I always have to look up the documentation to make sure I have the right parameters in the right order -- but it's the right tool for the job in this case. In my opinion that is.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39828
    
  28
I have been keeping quiet about arraycopy because it doesn’t look as elegant. It does avoid any out by one errors, which loops are prone to, however.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:I would suggest
for (int i = index + 1; i < size; i++)
{
  values[i - 1] = values[i];
}
That is about it Well, I think it is more elegant.


Please use code tags when writing Java code Campbell:



See, ain't that much more elegant?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39828
    
  28
Agree. My solution was more elegant
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

I would like to keep it the way it is. On a more serious note though, now that the remove(int) method is through too, what next?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39828
    
  28
What about set and get? They should be very easy.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39828
    
  28
Or remove(T)?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:What about set and get? They should be very easy.




Any flaws that you see?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39828
    
  28
Yes. Neither set nor get should alter the size of the Collection.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:Yes. Neither set nor get should alter the size of the Collection.


Done Campbell:



Anything else? Or shall we move ahead?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39828
    
  28
That looks good I forget what was next. Was that remove(T)?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

I have not implemented remove(T). Will do and get back.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

I have implemented the indexOf(T) method first Campbell. Here it is:



It is working properly.

As for the remove(T) method, it is supposed to remove the first occurrence of the object in the list. In other words, if we find the object in the list, then, starting from the current index till the size, we need to copy the (i+1)th element to (i)th element. Correct?
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8219
    
  23

Mansukhdeep Thind wrote:It is working properly.

Is it? My assumption is that you don't allow null entries then (or maybe it was already stated somewhere back in the dim and distant); I hope you've documented the fact.

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

Winston Gutkowski wrote:
Mansukhdeep Thind wrote:It is working properly.

Is it? My assumption is that you don't allow null entries then (or maybe it was already stated somewhere back in the dim and distant); I hope you've documented the fact.

Winston


Yes, I am not allowing null elements any more. That makes it more difficult to implement the methods correctly. I am following Joshua's ArrayList implementation. Here is the code with the null element check implemented:

Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8219
    
  23

Mansukhdeep Thind wrote:Here is the code with the null element check implemented...

Actually, you can do it just as easily with the implementation given to you in the docs, viz;and then worry about null values simply when adding (or setting).

Of course an exception does short-circuit invalid requests, but you could just as validly return -1.

Winston
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

How do you reckon I go about implementing the remove(T) method?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:


Why throw an exception if someone looks for null? Why not just return false? Not allowing us to add null shouldn't prevent us from asking if null is present.

Also, if you wrote that method to use an iterator rather than accessing the backing array directly, you could promote the implementation to an abstract base class and re-use that same method implementation for LinkedList and other List implementations.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:How do you reckon I go about implementing the remove(T) method?


As with any other method, start by figuring out the steps you'd follow to do it "manually" without any regard for Java or any other programming language.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
Mansukhdeep Thind wrote:


Why throw an exception if someone looks for null? Why not just return false? Not allowing us to add null shouldn't prevent us from asking if null is present.


Not false Jeff, -1 , since the return type is an int. Here is the improved method:


I have made it final too as Winston so often advises.



Jeff Verdegan wrote:Also, if you wrote that method to use an iterator rather than accessing the backing array directly, you could promote the implementation to an abstract base class and re-use that same method implementation for LinkedList and other List implementations.


Not sure I understand what you mean by this.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8219
    
  23

Jeff Verdegan wrote:Also, if you wrote that method to use an iterator rather than accessing the backing array directly, you could promote the implementation to an abstract base class and re-use that same method implementation for LinkedList and other List implementations.

Damn fine point.

@Manshukdeep: And that (what Jeff said) is all about design. WhatNotHow (←click).

Winston
David Blaine
Ranch Hand

Joined: Mar 23, 2013
Posts: 70
Campbell Ritchie wrote:
Mansukhdeep Thind wrote:. . . What is the "sizeratio" for? . . .
I think it is the less severe of the two errors I can see


Exactly. I don't know why the poster did not test the code before. Here is one link related to the buggy answer - What's the reason I can't create generic array types in Java?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
Mansukhdeep Thind wrote:How do you reckon I go about implementing the remove(T) method?


As with any other method, start by figuring out the steps you'd follow to do it "manually" without any regard for Java or any other programming language.


The only way I can think of is, if a matching element is found, then , starting from the index of the element to be removed up until the size of the list, copy the (i+1)th element to the (i)th element . Something like :



Look good to you Jeff. Any flaws that you see? Any fine tuning that can be done? I don't know where is Campbell. Usually, he is the one at the other end.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8219
    
  23

Mansukhdeep Thind wrote:not sure I understand what you mean by this.

He's saying that you've tied yourself into a specific way of doing something - almost always a bad idea; and almost always because you're thinking about how you're going to do it (the code), rather than what needs to be done (see above).

Winston
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:
Jeff Verdegan wrote:
Why throw an exception if someone looks for null? Why not just return false? Not allowing us to add null shouldn't prevent us from asking if null is present.


Not false Jeff, -1 , since the return type is an int.


Oops. Yes, my bad.

Here is the improved method:


I have made it final too as Winston so often advises.


There's one very simple optimization I would recommend for handling a null parameter.


Jeff Verdegan wrote:Also, if you wrote that method to use an iterator rather than accessing the backing array directly, you could promote the implementation to an abstract base class and re-use that same method implementation for LinkedList and other List implementations.


Not sure I understand what you mean by this.


You know that in java.util we have both ArrayList and LinkedList, right? If you look at their class hierarchies, you'll see there are a couple of abstract classes from which they both descend. There's a fair amount of code that can be written identically for AL, LL, or any other List implementation. That's why we have abstract classes. So that we can write common method implementations once, to be shared among multiple concrete type implementations, rather than duplicating the same code.

Anything that accesses the backing array directly in an AL, or that accesses the nodes directly in a LL, has to be abstract, left to be implemented in the concrete class. But there's a lot of stuff that doesn't have to access the backing store directly. For instance, an iteration can use the Iterator. You can use your own Iterator in your own code.

If you rewrite your indexOf() method to use an Iterator, rather than looking directly at the value array, then if you were to develop a LL class as well, you could have your AL and LL both extend AbstractList, and you could put indexOf() into AbstractList, so that your ArrayList and LinkedList can both use the same indexOf() implementation.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

David Blaine wrote:
Campbell Ritchie wrote:
Mansukhdeep Thind wrote:. . . What is the "sizeratio" for? . . .
I think it is the less severe of the two errors I can see


Exactly. I don't know why the poster did not test the code before. Here is one link related to the buggy answer - What's the reason I can't create generic array types in Java?


Lo and behold, the great magician from Great Britain is here. Welcome to the ranch David. Welcome to my thread of implementing ArrayList manually.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:
Look good to you Jeff. Any flaws that you see?


Unless I missed something, you're always returning false, even if you found the object, and you're always decreasing the size of the list, even if you didn't find it. You're calling ensureNonNull() twice, and again, I think it's bad design to throw an exception just because they ask to remove an element that can't possibly be in there in the first place. It should be no different than asking to remove an element that just happens to not be there.

I didn't look closely at the code for fencepost errors, and I don't intend to.

It looks like you just slapped something together as fast as you could, without thinking carefully about it, and now are asking others to debug it for you. You should be testing these things. You should write unit tests that cover all the corner cases, plus a couple of middle cases. Ideally you should write these tests before you write the code they're testing.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
Mansukhdeep Thind wrote:
Look good to you Jeff. Any flaws that you see?


Unless I missed something, you're always returning false, even if you found the object, and you're always decreasing the size of the list, even if you didn't find it. You're calling ensureNonNull() twice, and again, I think it's bad design to throw an exception just because they ask to remove an element that can't possibly be in there in the first place. It should be no different than asking to remove an element that just happens to not be there.

I didn't look closely at the code for fencepost errors, and I don't intend to.

It looks like you just slapped something together as fast as you could, without thinking carefully about it, and now are asking others to debug it for you. You should be testing these things. You should write unit tests that cover all the corner cases, plus a couple of middle cases. Ideally you should write these tests before you write the code they're testing.


Why is it always that I am the one making foolish mistakes and you guys are the ones correcting it? Need to change this trend.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8219
    
  23

Mansukhdeep Thind wrote:Why is it always that I am the one making foolish mistakes and you guys are the ones correcting it? Need to change this trend.

Then StopCoding (←click).

Winston
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Winston Gutkowski wrote:
Mansukhdeep Thind wrote:Why is it always that I am the one making foolish mistakes and you guys are the ones correcting it? Need to change this trend.

Then StopCoding (←click).

Winston


That is correct Winston. Lets take it easy as the Eagles said. This is the final role of the dice for today:



Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
Mansukhdeep Thind wrote:
Look good to you Jeff. Any flaws that you see?


Unless I missed something, you're always returning false, even if you found the object, and you're always decreasing the size of the list, even if you didn't find it. You're calling ensureNonNull() twice, and again, I think it's bad design to throw an exception just because they ask to remove an element that can't possibly be in there in the first place. It should be no different than asking to remove an element that just happens to not be there.


Oops. Apologies Jeff! I have corrected the mistakes. It was bad design to check for something that I am not allowing in the first place as an element(null). Take that back.

Jeff Verdegan wrote:I didn't look closely at the code for fencepost errors, and I don't intend to.


Respect that.

Jeff Verdegan wrote:It looks like you just slapped something together as fast as you could, without thinking carefully about it, and now are asking others to debug it for you. You should be testing these things. You should write unit tests that cover all the corner cases, plus a couple of middle cases. Ideally you should write these tests before you write the code they're testing.


Yes, I need to learn how to write test cases too Jeff. Any tutorial which can be of help?
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Implementing ArrayList class manually