Forums Register Login

Implementing ArrayList class manually

+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
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.



+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send

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.
+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send

@ 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.
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
 

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?
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
 

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.

+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
@ 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.
+Pie Number of slices to send: Send
Imagine you have a 16‑element array, all full (size == 16), and you attempt to add an element at position 11.
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
 

Mansukhdeep Thind wrote:This scenario will not arise. . . .

Oh yes it will!
+Pie Number of slices to send: Send
@ 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.
+Pie Number of slices to send: Send
 

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)

 
+Pie Number of slices to send: Send
I have rectified both these errors now. It is returning the correct size and no OutOfMemory error now. You can try:

+Pie Number of slices to send: Send
I bet I can break that list in under 5 minutes.
Your add(int, E) method is quite incorrect.
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
Hmm.. It is indeed incorrect. I will have to think it again from scratch.
+Pie Number of slices to send: Send
That is the nice thing about object‑oriented programming. You can change one method without upsetting the rest of your class.
+Pie Number of slices to send: Send
 

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?
+Pie Number of slices to send: Send
Did you ever complete this task? What did you write in the end?
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
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
+Pie Number of slices to send: Send
 

Campbell Ritchie wrote:What should take at least 5 minutes



Couldn't understand this remark..
+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
 

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

 
+Pie Number of slices to send: Send
Here you go forum leader Campbell Ritchie, the final code:



Have your 5 minutes of fun breaking it.
+Pie Number of slices to send: Send
 

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 …
+Pie Number of slices to send: Send
 

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.

+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
 

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.
You ridiculous clown, did you think you could get away with it? This is my favorite tiny ad!
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com


reply
reply
This thread has been viewed 20473 times.
Similar Threads
Implement a data structure that support a sorted Map.
Where does primitive data comes from
help on event listener
Question about toArray() method in ArrayList class
ArrayList from HeadFirstJava second addition
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
Should I use IndexOf List in this case?
implementing multiple view feature
difference between linked list and array list?
LinkedList question
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 29, 2024 05:39:45.