• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Implementing ArrayList class manually

 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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).
 
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
may be this can help : https://coderanch.com/t/605166/java/java/Dynamic-Array-code
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
And I presume you have seen my mistake in the loop
 
Mansukhdeep Thind
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Agree. My solution was more elegant
 
Mansukhdeep Thind
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What about set and get? They should be very easy.
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Or remove(T)?
 
Mansukhdeep Thind
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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





Any flaws that you see?
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes. Neither set nor get should alter the size of the Collection.
 
Mansukhdeep Thind
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That looks good I forget what was next. Was that remove(T)?
 
Mansukhdeep Thind
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have not implemented remove(T). Will do and get back.
 
Mansukhdeep Thind
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Mansukhdeep Thind
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
How do you reckon I go about implementing the remove(T) method?
 
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Ranch Hand
Posts: 70
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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?
reply
    Bookmark Topic Watch Topic
  • New Topic