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: 38818
    
  23
Winston Gutkowski wrote: . . . Blimey. The thread that refuses to die. . . .
But think how much he will learn if he ever finishes this class.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
Winston Gutkowski wrote: . . . Blimey. The thread that refuses to die. . . .
Blimey. Page 3.

And no girls in sight
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:
Winston Gutkowski wrote: . . . Blimey. The thread that refuses to die. . . .
But think how much he will learn if he ever finishes this class.


Forgive me for today guys. Went for a 10 km run. Will provide you the update tomorrow. I know it improving the add(T) method and reducing it to 2 lines has something to do with the ternary operator. Just wait till tomorrow.


~ Mansukh
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:
Winston Gutkowski wrote: . . . Blimey. The thread that refuses to die. . . .
Blimey. Page 3.

And no girls in sight


Now what is this supposed to mean? What is the relation between page 3 and girls?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
NSFW: Everybody in Britain knows about this sort of thing.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote: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.


I changed the add(T) method to :



Am I on correct track? There is a flaw though. Every time the condition evaluates to true, that index has a null value. How to assign the value and grow the array at same time , while also adhering to your order of writing it in 2 lines.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
Mansukhdeep Thind wrote: . . . Am I on correct track? . . .
No.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
I often tell students, these things are a lot simpler than you think. You can simplify that add method and make it look elegant and short and concise. But you need to relax and work out what you really need in that method. And I said two statements, not two lines.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
If you include return true; make that three statements.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:I often tell students, these things are a lot simpler than you think. You can simplify that add method and make it look elegant and short and concise. But you need to relax and work out what you really need in that method. And I said two statements, not two lines.


What I need is to add the element at index position = size. And if size becomes equal to 1 less than current capacity grow it and then add the element. That is what I am doing. How to achieve that using ternary operator? And what simpler if statement can ther possibly be. We have to check . How else do you propose I should decide to grow() it?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
You have already said under which circumstances you need to enlarge the array. Go back a page and you will find it.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:You have already said under which circumstances you need to enlarge the array. Go back a page and you will find it.


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


Got it.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Here you go Campbell:

The add(T ) method :




and the add(int,T) method is as follows:


Is this what you were expecting of me? Is it elegant enough to your British standards now? Or is it still too Indian for your liking?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
Mansukhdeep Thind wrote:Here you go Campbell:

The add(T ) method :

. . .
Yes, yes, yes
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
You can elide the size++; line in add(int, T) similarly. In add(int, T), throw the Exception at the beginning of the method.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:You can elide the size++; line in add(int, T) similarly. In add(int, T), throw the Exception at the beginning of the method.


Here is the improved add(int,T) method Campbell:



Why do you insist in throwing the exception at the beginning? So, that it does not have to interpret extra if() statements?

Learned a new word , elide.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
You throw the Exception early in the method because it is obvious to readers what is happening. You can still improve that method, however. I can see two things I would alter, possibly three.
You are saying that you can add something at index 2 if the List contains "Campbell" "Manskukhdeep" only, in the documentation.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:You throw the Exception early in the method because it is obvious to readers what is happening. You can still improve that method, however. I can see two things I would alter, possibly three.
You are saying that you can add something at index 2 if the List contains "Campbell" "Manskukhdeep" only, in the documentation.






Here is a shortened version. Anything else that can be chucked out?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

if(indexPos>size || indexPos<0){
System.out.println("Index passed must be between 0 and current size");
throw new IndexOutOfBoundsException();

}


If you were writing this as a real library class that you expected to be used in multiple applications, possibly by people other than yourself, you wouldn't want to be calling System.out.println() anywhere in your code.

When throwing an exception, you should include useful information about what was expected and what happened instead, to aid debugging:



Also, these are more subjective, but personally, I hate seeing unnecessary uses of "this":


And more standard whitespace around binary operators and between the pieces of the for loop header and between the closing paren and opening brace will make it easier to read:
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
Maybe you should throw an ArrayIndexOutOfBoundsException.
I was a little worried about the size++ in an unusual place. Risk of confusion. I would have put it after the loop.
myArray[size++] = ...; // Well‑recognised usage, but can be confusing to beginners
for (int i = size++; i > index; i--) {...} // Unusual usage, and potential cause for confusion.

Passing the message to the exception constructor, as Jeff showed you, that was the other thing I saw.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Here you go Campbell/Jeff:



Looks prefect now?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
if(indexPos>size || indexPos<0){
System.out.println("Index passed must be between 0 and current size");
throw new IndexOutOfBoundsException();

}


If you were writing this as a real library class that you expected to be used in multiple applications, possibly by people other than yourself, you wouldn't want to be calling System.out.println() anywhere in your code.

When throwing an exception, you should include useful information about what was expected and what happened instead, to aid debugging:



Also, these are more subjective, but personally, I hate seeing unnecessary uses of "this":


And more standard whitespace around binary operators and between the pieces of the for loop header and between the closing paren and opening brace will make it easier to read:


Thank you Jeff. You just made me happy by correcting me, unknowingly though.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
Getting better all the time
Now let’s see a remove method.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:Getting better all the time
Now let’s see a remove method.


As long as you guys are present to teach me the right things the right way, this shall continue. I will become better and better at this. It is 35 degrees centigrade out there and I am going for a bike ride. An easy paced 3-4 hour work out. Will revert back after that.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
Mansukhdeep Thind wrote: . . . An easy paced 3-4 hour work out. . . .
So about 50 miles?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

No, the route has climbs ranging from 3-4 % to 7-8 % at places. More of a strength oriented workout. It ends up with the cyclometer tripping at 50 km not 50 miles. When I go for a route which is flat, I do at least 80-100 km. By the way, you are British, then why miles and not km?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
Kilometers are French
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:Kilometers are French


Something personal against the French it seems?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:Getting better all the time
Now let’s see a remove method.


Here you go Campbell:



Is that OK? Or can it be further improved upon?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
There is a pitfall which you have fallen into. I would have fallen into it myself, had I not read Joshua Bloch’s Effective Java™ (2/e) page 24. (In the first edition it is page 16.)
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
You have duplicated code in those add and remove methods. That should be refactored into a separate private method.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:There is a pitfall which you have fallen into. I would have fallen into it myself, had I not read Joshua Bloch’s Effective Java™ (2/e) page 24. (In the first edition it is page 16.)


Rectified the duplicated code part:



Here is the private method for validating the index:



Now back to your point about Joshua Bloch's rule of thumb regarding obsolete object references - It talks about eliminating obsolete object references by explicitly setting them to null. He says that any elements outside the active portion of the array are are termed as obsolete references. Active portion of the array means elements having their index less than size of the array. I do not understand where is the reference that has become obsolete in my remove(int) method. Any elements outside the active portion of the array are automatically becoming null when the loop inside the remove(int) method runs. Correct? Or is it the variable temp that you are hinting at?

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
Why have you got the if inside the method still? Why are you checking for != null when removing? If you are not permitting nulls at this stage, why are you permitting users to add them in the add methods?
The temp variable is a local variable which goes out of scope when that method completes.
Write down the structure of your List after you add a few elements and remove one:
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:Why have you got the if inside the method still? Why are you checking for != null when removing? If you are not permitting nulls at this stage, why are you permitting users to add them in the add methods?
The temp variable is a local variable which goes out of scope when that method completes.
Write down the structure of your List after you add a few elements and remove one:


Here are the updated add(int), add(int,T) , remove(int) and the utility methods:



If it is not a problem with the temp variable, then what is the issue? I tried doing what you asked me to, i.e.:



output is :

Size of list is 4
Capacity of list is 10
At index position :0 5
At index position :1 3
At index position :2 34
At index position :3 6


and after I do this:



output is :

Size of list is 3
Capacity of list is 10
At index position :0 5
At index position :1 3
At index position :2 6

What's wrong with this? All the elements beyond the size are null. So where is the problem that Joshua is talking about obsolete object references in the active array?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38818
    
  23
You have changed the class’ general contract. You used to permit null values and you don’t any more. Both options are valid, but you must decide which is correct and which you are using.
Don’t use a plain simple Exception. If you are going to thrown an Exception, try NullPointerException. Also that way, you are throwing an unchecked Exception, which is appropriate for incorrect arguments.
You have changed the return type of add(int, T); it used to be boolean, and it is now void (at least I think it was). I would have thought boolean as you used to have is better.
Why are you casting the elements in the array to (T)?
Have you printed out the no 3 element in the array? You are only printing up to < size. What happens when you print up to <= size?

You have tried to change too many things all at once. By doing so, you have messed up some things which used to work
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Campbell Ritchie wrote:If you are going to thrown an Exception, try NullPointerException.


I prefer IllegalArgumentException. Either one is valid, and it really comes down to personal preference. I prefer to let NPE only be thrown when a null pointer is actually dereferenced (or when I call into a library that throws it in situations like this, which I can't control ). I think IAE is more descriptive of what went wrong here. The fact that the argument was null doesn't make it an NPE, IMHO. Again, though, totally subjective. Pick whichever one you think fits better. The key points are that it should be more descriptive than Exception and it should be an unchecked exception.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:You have changed the class’ general contract. You used to permit null values and you don’t any more. Both options are valid, but you must decide which is correct and which you are using.


I want to disallow null elements. I will be sticking to that.

Campbell Ritchie wrote:Don’t use a plain simple Exception. If you are going to thrown an Exception, try NullPointerException. Also that way, you are throwing an unchecked Exception, which is appropriate for incorrect arguments.


OK.

Campbell Ritchie wrote:You have changed the return type of add(int, T); it used to be boolean, and it is now void (at least I think it was). I would have thought boolean as you used to have is better.



I have made it like Joshua Bloch's ArrayList's add(int,T) method. That also has return type as void. Why do you think boolean is better?


Campbell Ritchie wrote:Why are you casting the elements in the array to (T)?


Otherwise it is a compile time error.


Campbell Ritchie wrote:Have you printed out the no 3 element in the array? You are only printing up to < size. What happens when you print up to <= size?


No. 3 element prints as null after removing the 3rd element. What are you getting at?

You have tried to change too many things all at once. By doing so, you have messed up some things which used to work
Campbell Ritchie
Sheriff

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

No. 3 element prints as null after removing the 3rd element. What are you getting at?
. . .
You are right. By using i + 1 you have correctly copied the null in no 3 to no 2, so you are not getting the memory leak. I was mistaken about that. Sorry.

Are you sure there is no chance that you will get an array out of bounds exception from remove(int) if size == values.length?
If you are using void return type for add(), then change both add methods to the same return type. Then you can reduce add(T) to the dreaded two statements.
You either have to cast the array when you create it, or cast each element as you extract it from the array. I would prefer the former, but java.util.ArrayList prefers the latter approach.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
Campbell Ritchie wrote:If you are going to thrown an Exception, try NullPointerException.


I prefer IllegalArgumentException. Either one is valid, and it really comes down to personal preference. I prefer to let NPE only be thrown when a null pointer is actually dereferenced (or when I call into a library that throws it in situations like this, which I can't control ). I think IAE is more descriptive of what went wrong here. The fact that the argument was null doesn't make it an NPE, IMHO. Again, though, totally subjective. Pick whichever one you think fits better. The key points are that it should be more descriptive than Exception and it should be an unchecked exception.


I will go for IllegalArgumentException.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:
Mansukhdeep Thind wrote: . . .

No. 3 element prints as null after removing the 3rd element. What are you getting at?
. . .
You are right. By using i + 1 you have correctly copied the null in no 3 to no 2, so you are not getting the memory leak. I was mistaken about that. Sorry.


No problem Campbell. Everyone makes mistakes, even Britishers.

Campbell Ritchie wrote:Are you sure there is no chance that you will get an array out of bounds exception from remove(int) if size == values.length?


You are correct. I am getting this IndexOutOfBoundsException when trying to remove the element when size==values.length. Hence, I was using the size==values.length-1 condition to grow the array rather than size==values.length. Here are the rectified add(int), add(int,T), ensureCorrectIndex(int) methods:




Campbell Ritchie wrote:If you are using void return type for add(), then change both add methods to the same return type. Then you can reduce add(T) to the dreaded two statements.


But Joshua does it like this in his implementation of java.util.ArrayList. See here. Why do you say both methods should have the same return type? How do we decide what return type a method should have? I am merely following Joshua. But what is the logic that we use for deciding return types when we are dealing methods which could make do with either void or boolean return types?

Campbell Ritchie wrote:You either have to cast the array when you create it, or cast each element as you extract it from the array. I would prefer the former, but java.util.ArrayList prefers the latter approach.


You mean to say when either in the overloaded constructor OR as and when I do values[indexPos]?
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Implementing ArrayList class manually