wood burning stoves 2.0*
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

Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7640
    
  19

Mansukhdeep Thind wrote:I have improved it a bit. See the get method now:

It still seems overly complex to me. You hopefully have a size() method to work with, so that really should be all you need to check for; a negative index will throw ArrayIndexOutOfBoundsException by default. It also sounds like you're making distictions for "null" elements. I hope you've documented it.

Concurrent modification is when more than one thread is trying to access my custom ArrayList at same time. Correct?

No. It's usually thrown by an Iterator if someone tries to change the List while you're iterating it.

Are you hinting that I should make my class thread safe? I could not fully grasp this point.

Personally, I wouldn't bother at the moment. Just get the basics working first.

What is meant by parametrization of a class?

Bascially, I think what he means is that you should define it as:
public class CustomArrayList<T> implements Iterable<T> { ...
rather than the way you have.

HIH

Winston

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

Joined: Oct 13, 2005
Posts: 38340
    
  23
Mansukhdeep Thind wrote: . . .
Is this what you were expecting it to look like? . . .
There is a much simpler way to implement that method, without double return or anything.

. . .
a) size() : returns the size of the current list.
b) add(E) : adds an element to the end of the list (already implemented)
c) add(int,E) : adds an element at a specified position in the custom list
d) get(int) :returns the element at the specified position (already implemented)
e) set(int, E) : Replaces the element at the specified position with the one passed.
f) remove(int) : removes the element specified int value
Is that correct Ritchie?
Yes.
. . . Concurrent modification is when more than one thread is trying to access my custom ArrayList at same time. Correct? . . .
No. Concurrent modification is when you structurally alter the collection while there is an Iterator extant. Read the Iterator documentation.

. . . What is meant by parametrization of a class?
Winston has already answered that.
. . . So, you want me to remove the initialSize field and directly hard code the size inside the constructor. Something like:



Correct?
Don’t call your field nextIndex. That field represents how many elements there are in the list, so it needs a different name. I would also give a different name, maybe values, to the array. I suggest you start by adding another constructor:-Now work out how to implement the no‑arguments constructor.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

The following syntax is incorrect. Java does not allow us to write :

It has to be sure what "T" is. So, should I do like:

? But then it warns of "unchecked type casting". That in turn throws class cast exception at run-time because an Object cannot be cast to a String/Integer etc. What to do? How do I go about parameterizing my class?

Here is my latest code:



@ Ritchie/Winston: I have some queries:

a) I have implemented the no-argument constructor as above. It constructs a default array of size 10. Is it OK? Or were you expecting something else?

b) There are compile time warnings at 3 places saying "Unchecked type casting". (line numbers 22,33 and 42) Is that OK? How to manage those?

c) I am unable to print out the added elements using a simple for lop now. Line 154 throws ClassCastException. This is happening because Object is not a T(Integer in this case) I believe there is something wrong in my parametrization of the class. Please give clue as to what it is.

d) I have implemented the all the basic methods. But I am unable to test them because of the class cast exception problem. They are logically correct.




~ Mansukh
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7640
    
  19

Mansukhdeep Thind wrote:But then it warns of "unchecked type casting". That in turn throws class cast exception at run-time because an Object cannot be cast to a String/Integer etc. What to do? How do I go about parameterizing my class?

You have two choices:
1. Use an Object[] internally and cast elements when you return them (eg, for get(int)) - I think this is what ArrayList does.
2. Use Array.newInstance() to create your array and cast that. Unfortunately, you then need to provide a Class, object or array of the correct type to get the component type. There might also be a way to do it from the lists's own Type, but I don't know how.

a) I have implemented the no-argument constructor as above. It constructs a default array of size 10. Is it OK? Or were you expecting something else?

Seems reasonable. I think ArrayList uses either 10 or 16. I forget.

b) There are compile time warnings at 3 places saying "Unchecked type casting". (line numbers 22,33 and 42) Is that OK? How to manage those?

No. You'll have to do one of the things I said above.

c) I am unable to print out the added elements using a simple for lop now. Line 154 throws ClassCastException. This is happening because Object is not a T(Integer in this case) I believe there is something wrong in my parametrization of the class. Please give clue as to what it is.

Again, it's telling you that the component type is wrong. You'll need to adopt one of the options above. Personally, I'd go for #1; it's the easiest.

Winston
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7640
    
  19

Winston Gutkowski wrote:2. Use Array.newInstance() to create your array and cast that. Unfortunately, you then need to provide a Class, object or array of the correct type to get the component type...

If you decide to go with this option, one possibility would be to postpone allocating the array until you get your first add; maybe something like:then your array will be the correct type. Unfortunately, you then have to add that check to any method that accesses the array.

Like I said, I reckon option 1 is probably easier.

Winston
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157


You have two choices:
1. Use an Object[] internally and cast elements when you return them (eg, for get(int)) - I think this is what ArrayList does.
2. Use Array.newInstance() to create your array and cast that. Unfortunately, you then need to provide a Class, object or array of the correct type to get the component type. There might also be a way to do it from the lists's own Type, but I don't know how.


I decided to go with option 1 for now. Will try second one later.

Seems reasonable. I think ArrayList uses either 10 or 16. I forget.
It is 10.

@ Winston/Ritchie/Jeff: Have a look at the final code. The methods are functioning correctly as per my testing. Let me know if I have missed some finer point. Then I can move on to implementing other interfaces /* List<E>, */ Iterable<E>/*, /*Serializable*/, RandomAccess */



@ Winston: Don't you think that introduction of generics has created more problems than it has solved? It gave me a hard time certainly. What is your view on this? I agree that it ensures compile time safety. But the run time has no way of knowing the actual object type anyways.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7640
    
  19

Mansukhdeep Thind wrote:Let me know if I have missed some finer point.

Well, just off the top of my head:
1. If values is an Object[], there's no need for growArray() to return a T[].
2. Your size() method doesn't really need to go through the array (although there's nothing logically wrong with it). Why not just maintain a size field?
3. Your remove() method doesn't work like List's. There's nothing particularly wrong with this, but you should document that your List can contain "holes". You may also find that it makes your Iterator (and particularly ListIterator) logic more complex - unless you're happy for them to return null elements - although, as I say, there's nothing particularly "wrong" with what you're doing.

Winston
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157


@ Winston :

1. If values is an Object[], there's no need for growArray() to return a T[].
Done.

2. Your size() method doesn't really need to go through the array (although there's nothing logically wrong with it). Why not just maintain a size field?
Roger that. Done.

3. Your remove() method doesn't work like List's. There's nothing particularly wrong with this, but you should document that your List can contain "holes".


By saying that my list contains "holes", I infer that you are referring to the gap between 2 consecutive non-null elements in the list. For example, {1,2,3,4,5, null, null, null, null 6, null ,45}. Correct?

You may also find that it makes your Iterator (and particularly ListIterator) logic more complex - unless you're happy for them to return null elements - although, as I say, there's nothing particularly "wrong" with what you're doing.
You are correct Winston. The for-each construct is currently returning only the first non-null consecutive elements in the list. If there is a null, it assumes there is no other element. I will have to change the iterator logic to accommodate for such a case.

@ Ritchie : Waiting for you to pitch in and tell me which interface to implement next.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Winston Gutkowski wrote:You may also find that it makes your Iterator (and particularly ListIterator) logic more complex - unless you're happy for them to return null elements


If he lets them return the nulls, then he's violating List's contract, since those nulls are not elements of the List.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:
@ Ritchie : Waiting for you to pitch in and tell me which interface to implement next.


By this time perhaps you've had enough guidance through the process of doing one little piece at a time that you could decide for yourself which piece to do next?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

By this time perhaps you've had enough guidance through the process of doing one little piece at a time that you could decide for yourself which piece to do next?


There are 3 left. RandomAccess, Serializable and List. RandomAccess is a marker interface. So is Serializable. How to implement those? Do I just declare these along with class declaration? Also, I just saw that List has a whole bunch of methods which remain to be implemented. Will be starting with those shortly.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:
By this time perhaps you've had enough guidance through the process of doing one little piece at a time that you could decide for yourself which piece to do next?


There are 3 left. RandomAccess, Serializable and List. RandomAccess is a marker interface. So is Serializable. How to implement those? Do I just declare these along with class declaration?


Yes, you do, IF your class meets the requirements for those methods.

For Serializable, all your non-static fields must be primitives or references to types that are themselves Serializable, or else they must be declared transient and you'll reset their values explicitly on deserialization. Note that you can't control what types somebody adds to the list. If they add something non-serializable, that breaks serialization, but that's their fault and their problem. It's expected that a Java programmer using serialization will know that.

For RandomAccess, your list has to provide efficient access to an element at an arbitrary index. (Check the docs. It may even specifically require O(1) access. I'm not sure.) If you've written your class correctly, such that it uses the array index to access an element for a requested index, rather than iterating to it, then you meet the requirement. Note that if you allow holes in your list, such that you have to iterate past them to get to the next element, then you do not meet the requirements for RandomAccess.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

For Serializable, all your non-static fields must be primitives or references to types that are themselves Serializable, or else they must be declared transient and you'll reset their values explicitly on deserialization. Note that you can't control what types somebody adds to the list. If they add something non-serializable, that breaks serialization, but that's their fault and their problem. It's expected that a Java programmer using serialization will know that.


Yes, I will duly do that. Should be a push over.

For RandomAccess, your list has to provide efficient access to an element at an arbitrary index. (Check the docs. It may even specifically require O(1) access. I'm not sure.) If you've written your class correctly, such that it uses the array index to access an element for a requested index, rather than iterating to it, then you meet the requirement. Note that if you allow holes in your list, such that you have to iterate past them to get to the next element, then you do not meet the requirements for RandomAccess.


I will read the specifications for RandomAccess interface and get back on this.

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38340
    
  23
Mansukhdeep Thind wrote:The following syntax is incorrect. Java does not allow us to write :

It has to be sure what "T" is. So, should I do like:
. . .
Damn! sorry.

I think I prefer Winston’s suggestion. I see winston has produced lots of help. I was hoping you would use the 1‑arg constructor like thisYou have a serious potential error in line 74. You might have corrected it already.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

@ Ritchie: Your no argument constructor looks neater. Changed mine to that style.

You have a serious potential error in line 74.


I am not able to understand what is the "potential problem" here.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38340
    
  23
Imagine you have a 16‑element array, all full (size == 16), and you attempt to add an element at position 11.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:Imagine you have a 16‑element array, all full (size == 16), and you attempt to add an element at position 11.


Got it. The iterator will run out of bounds for that use-case. I have now catered for that by correcting the check in the add(T) and add(int, T)as follows:



This works.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38340
    
  23
Mansukhdeep Thind wrote: . . . . . .
Earlier, I wrote: Imagine you have a 16‑element array, all full (size == 16), and you attempt to add an element at position 11.
Try again.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

This scenario will not arise. Reason being as soon as the user inserts an element at the index which makes size==capacity, it grows. Is that the use-case you are pointing at? There will be no ArrayIndexOutOfBounds Exception.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38340
    
  23
Mansukhdeep Thind wrote:This scenario will not arise. . . .
Oh yes it will!
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

@ Ritchie : Here is the final implementation



I have tested it thoroughly. The use-case that you are referring to does not arise. As soon as you add an element whose indexPos>=length-1, the array will be copied into a new array which will be twice the size of the original. How will this eventuality come into picture. I do not understand.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38340
    
  23
Mansukhdeep Thind wrote: . . .

I have tested it thoroughly. . . .
No, you haven’t. I have tried it. I can add 10 items and have it print size = 9. I can add 31 items to it and have it show size = 0. I can add 31 items and get this:-
$ java test.CustomArrayList
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at test.CustomArrayList.growArray(CustomArrayList.java:47)
at test.CustomArrayList.add(CustomArrayList.java:86)
at test.CustomArrayList.main(CustomArrayList.java:164)
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

I have rectified both these errors now. It is returning the correct size and no OutOfMemory error now. You can try:

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38340
    
  23
I bet I can break that list in under 5 minutes.
Your add(int, E) method is quite incorrect.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38340
    
  23
Earlier, I wrote:I bet I can break that list in under 5 minutes.
. . .
It took less than two minutes and three keystrokes in your main method to get:-
java test.CustomArrayList
Size of list is 32
Capacity of list is 10
The code you have written for that method looks as though you are guessing. If you sat down with paper and pencil and actually designed that method, it would shrink to half its current size, and spoil my fun getting errors and Exceptions out of that class.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Hmm.. It is indeed incorrect. I will have to think it again from scratch.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38340
    
  23
That is the nice thing about object‑oriented programming. You can change one method without upsetting the rest of your class.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:That is the nice thing about object‑oriented programming. You can change one method without upsetting the rest of your class.


What is the difference between object oriented approach to programming and procedural programming. Why can't I do this in procedural programming?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38340
    
  23
Did you ever complete this task? What did you write in the end?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Joined a course on Advanced Java recently Campbell. Go for those in the mornings nowadays 7-9 a.m. Then do the assignments they give. Evenings go into cycling / running workouts. Will have to stuff in time for following up on ranch assignments and answering ranch questions in addition to all of the above. Only the add(int,E) method remains to be implemented. Right now I am trying to close in on the Kth largest coding part. Will get back on this. Sorry if it caused you any inconvenience as moderator.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38340
    
  23
It hasn’t caused any inconvenience, but I was just interested to see what you ended up with. You just need to do add(int, E)? What should take at least 5 minutes
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:What should take at least 5 minutes


Couldn't understand this remark..
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7640
    
  19

Mansukhdeep Thind wrote:What is the difference between object oriented approach to programming and procedural programming.

There are whole books written on that subject....

Why can't I do this in procedural programming?

Nobody's saying you can't; just that you shouldn't. Why? Because Java is an Object-oriented language.

Winston
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38340
    
  23
Mansukhdeep Thind wrote:
Campbell Ritchie wrote:What should take at least 5 minutes


Couldn't understand this remark..
That is beccause I spelt is wronlgy. Sorry . It should have read
That should take at least 5 minutes
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Here you go forum leader Campbell Ritchie, the final code:



Have your 5 minutes of fun breaking it.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38340
    
  23
Mansukhdeep Thind wrote:Here you go forum leader Campbell Ritchie, the final code:


Have your 5 minutes of fun breaking it.
Change line no 155 to read myList.add(23, 35);

Now let’s beat your class into shape
Start by adding documentation comments to every method. For those methods which have an index position say the index must not be less than 0 and must be less than the current size. Once you have said that, you are entitled to throw Exceptions if the wrong index is given. Then you can say I ought not to try using 23 as an index. Then getting an Exception from myList.add(23, 35); no longer constitutes breaking the class.
Please check very carefully under which circumstance you need to enlarge the List, particularly in the add(int, T) method. The circumstances are really simple.
Write down carefully the structure of your list at the end of the main method (or better still, give it a toString() method and print it out). Print size elements of the array, not up to length. Call remover(4), and repeat the procedure. What has happened to the last element? By the way: a remove method ought to return the element removed. Don’t give it a boolean return type.

And remember, I have not read the whole of the class yet. There will be lots more to come …
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote: Start by adding documentation comments to every method. For those methods which have an index position say the index must not be less than 0 and must be less than the current size. Once you have said that, you are entitled to throw Exceptions if the wrong index is given. Then you can say I ought not to try using 23 as an index. Then getting an Exception from myList.add(23, 35); no longer constitutes breaking the class.


Done.

Campbell Ritchie wrote: Write down carefully the structure of your list at the end of the main method (or better still, give it a toString() method and print it out). Print size elements of the array, not up to length. Call remover(4), and repeat the procedure. What has happened to the last element? Don’t give it a boolean return type.


Rectified the issue with remove(int). I have changed the return type to return the element removed and also put in the logic to shift the elements one place to the left.


Please check very carefully under which circumstance you need to enlarge the List, particularly in the add(int, T) method. The circumstances are really simple.


Also done. The array should grow when the size of the current list becomes == its capacity.

Here is the code with documentation and other rectifications. Please beat it more so that it comes into shape.

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38340
    
  23
Now we’re getting somewhere
Mansukhdeep Thind wrote: . . . /**
* @throws exception - {@link ArrayIndexOutOfBoundsException}
*/ . . .
Change that to read @throws IndexOutOfBoundsException if index < 0 or index > current size.
Similarly for other @throws tags. You need to quote the class of the Exception immediately after the tag. You should check whether I have got that right here.

Look at your add(T) method. That can be simplified no end; you can actually reduce it to two statements, and use much simpler if statement. Why are you casting the element? When you have simplified that add method, you can similarly simplify the add(int, T) method.

And there is more to come.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7640
    
  19

Campbell Ritchie wrote:And there is more to come.

Blimey. The thread that refuses to die.

I will add one observation:
@Mansukhdeep - All your methods are public.

Now that may be all right; and certainly all the methods defined for List need to be public; but private helper methods can be very useful for normalizing logic, so if you find yourself doing the same thing more than once, put it in a private method.

Another little tip for you from the paranoid school of programming: Unless you know that a method is going to be overridden, make it final.
I even put it on private methods, and also when the class is defined as final although, strictly speaking, it's redundant in both cases.

The reason, oddly enough, is for flexibility. You can always remove final later on, but you can't add it. And if you change the visibility of a method (eg, from private to protected), you ensure that it starts out its new life as 'protected final', rather than 'protected [overridable]'.

Winston

PS: Please, please, please DontWriteLongLines. I think I've broken up most of them. I'd also suggest that you don't repeat ALL your code every time you post; just show us what you changed.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Implementing ArrayList class manually