File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/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


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Implementing ArrayList class manually" Watch "Implementing ArrayList class manually" New topic
Author

Implementing ArrayList class manually

Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Well, not a problem with me. But Campbell might have a different opinion. Anyways, getting back to your exercise, what are you trying to implement here?


~ Mansukh
David Blaine
Ranch Hand

Joined: Mar 23, 2013
Posts: 70
Mansukhdeep Thind wrote:Well, not a problem with me. But Campbell might have a different opinion. Anyways, getting back to your exercise, what are you trying to implement here?


I was trying to make a basic arraylist using an array as you had mentioned -
He said assume that Collections are not available in Java. You can use arrays. How will you go about creating a growable array which can do all the things an ArrayList can?


The code was just basic. I will be adding the other functionality/methods also.

Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Well, if you are willing to go the distance, let me start by putting you on track, like Campbell, Winston did for me. Lets go step by step and not try and get ahead of ourselves. Before implementing the other methods, let me first correct this existing code.

Lets look at the instance variables you have declared:



You surely do not need all four. What is the one thing that you need as instance variable when you initialize an array, apart from the declaration, to keep track of at the class level?

Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8008
    
  22

Mansukhdeep Thind wrote:What part am I duplicating?

As I already said: indexOf() - which we already spent almost an entire day on.

But I do not want to re use existing APIs.

If its purely for exercise then fine; but in reality, you should use existing APIs whenever possible. Also: System.arrayCopy() is about as fast as it gets.

Because it is a compilation error if I do not cast the value by doing:

Then I'd suggest you create a private setHelper(int, Object)) method to minimize the places you have to cast. I assume that your values array is defined as a T[].

Winston

Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Winston Gutkowski wrote:
Mansukhdeep Thind wrote:What part am I duplicating?

As I already said: indexOf() - which we already spent almost an entire day on.


I took care of that by defining the downCopy(int) private method. Go back a page and you will see.

Winston Gutkowski wrote:
Mansukhdeep Thind wrote:But I do not want to re use existing APIs.

If its purely for exercise then fine; but in reality, you should use existing APIs whenever possible. Also: System.arrayCopy() is about as fast as it gets.


Yes, right now I only want to use pure Java constructs , not existing APIs.

Winston Gutkowski wrote:
Mansukhdeep Thind wrote:Because it is a compilation error if I do not cast the value by doing:
Then I'd suggest you create a private setHelper(int, Object)) method to minimize the places you have to cast. I assume that your values array is defined as a T[].


Winston


The array is declared as :



and initialized as




What's wrong with this ? It does throw a "Type safety: Unchecked cast from Object[] to T[]" warning. That's all. Why to create a separate helper method to do the cast? What's the difference if we cast just in time?
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8008
    
  22

Mansukhdeep Thind wrote:What's wrong with this ?

It means that you have to cast for both input and output.

The array should be defined as T[] and initialized exactly as you have done. Then, the only other cast that needs to be done is when setting a value from a method that specifically takes an Object (as opposed to a T), which is why I suggested a private setter method.

If you want to get really fancy, you could even do something like:caching arrayType the first time you get an actual object to add, and then use newArray() to initialize (or "grow") values.

The advantage of this is that your toArray() methods become extremely simple and are guaranteed to be castable.
Many people are still quite surprised that:compiles OK, but throws a runtime exception.

The above suggestion comes at the cost of a null check on arrayType every time you run a set() of course; unless you're prepared to add a
Class<T> elementClass
parameter to all your constructors.

Winston

[Edit] Actually, caching is probably not a good idea since the first object you add could be a subclass of T. Basically, with my suggestion, you must supply the element class at construction time.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

If I declare the array to be of type T, then while printing the elements I get a java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.Integer;.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8008
    
  22

Mansukhdeep Thind wrote:If I declare the array to be of type T, then while printing the elements I get a java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.Integer;.

Which is probably the worst reason for not defining it as T[], since it has absolutely nothing to do with the class's public API.

Not including toArray() methods, There should be precisely two casts in your class (presuming you're using a cast Object[]):
  • 1. When you create or grow the array.
  • 2. When you set an element from a method that takes an Object, as opposed to a T.

  • If you use get() (or, probably even better, the List's iterator()) to print out elements, you'll have no such problems.

    If you have any other questions, show us your "print" logic.

    Winston
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    You are correct Winston. I was trying to print out the added elements using values[i] rather than get[i], which as you rightly said, has nothing to do with the class' public API. Foolish of me. Now, I have declared the array as :



    and there are exactly 2 places where I am casting the Object[] array to T[], one in the constructor and one while growing it. There is no method at present which takes an Object obj rather than T obj. Thank you.





    I wonder where is Campbell..
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 8008
        
      22

    Mansukhdeep Thind wrote:and there are exactly 2 places where I am casting the Object[] array to T[]...

    I suspect not, since growArray() returns an Object[].

    How about this:then, when you want you resize values, you call:
    values = resizeArray(values, values.length * 2);
    and when you want to simply initialize it (eg, in a constructor), you call:
    values = resizeArray(null, 16);
    (or something like it)

    Winston

    PS: Your code looks very "scrunched up". My advice: put more spaces in; it makes things easier to read.
    David Blaine
    Ranch Hand

    Joined: Mar 23, 2013
    Posts: 70
    Mansukhdeep Thind wrote:Well, if you are willing to go the distance, let me start by putting you on track, like Campbell, Winston did for me. Lets go step by step and not try and get ahead of ourselves. Before implementing the other methods, let me first correct this existing code.

    Lets look at the instance variables you have declared:



    You surely do not need all four. What is the one thing that you need as instance variable when you initialize an array, apart from the declaration, to keep track of at the class level?



    I don't understand the question. Are you saying that there should also be a static/class level variable ?
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    David Blaine wrote:
    Mansukhdeep Thind wrote:Well, if you are willing to go the distance, let me start by putting you on track, like Campbell, Winston did for me. Lets go step by step and not try and get ahead of ourselves. Before implementing the other methods, let me first correct this existing code.

    Lets look at the instance variables you have declared:



    You surely do not need all four. What is the one thing that you need as instance variable when you initialize an array, apart from the declaration, to keep track of at the class level?



    I don't understand the question. Are you saying that there should also be a static/class level variable ?


    No, not static. You should have a private int size variable. If you use a static variable, then that belongs to the entire class and not the instance of your custom list. So , essentially, you just need:



    Understood? If yes, then we can move on to rectifying your constructors.

    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Winston Gutkowski wrote:
    Mansukhdeep Thind wrote:and there are exactly 2 places where I am casting the Object[] array to T[]...

    I suspect not, since growArray() returns an Object[].

    How about this:then, when you want you resize values, you call:
    values = resizeArray(values, values.length * 2);
    and when you want to simply initialize it (eg, in a constructor), you call:
    values = resizeArray(null, 16);
    (or something like it)

    Winston

    PS: Your code looks very "scrunched up". My advice: put more spaces in; it makes things easier to read.


    I changed my growArray() method to :



    I changed the return type to T[], added necessary spaces to make it more legible. Casting is required only while creation as shown. Now is it OK?
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 39393
        
      28
    Why do you need a return type at all, if that is a private instance method. You can simply reassign the values array in that method.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Yes Campbell, you are correct. I do not need a return type at all here. The re assignment works just as good:



    What next?
    David Blaine
    Ranch Hand

    Joined: Mar 23, 2013
    Posts: 70
    Mansukhdeep Thind wrote:
    No, not static. You should have a private int size variable. If you use a static variable, then that belongs to the entire class and not the instance of your custom list. So , essentially, you just need:

    Understood? If yes, then we can move on to rectifying your constructors.


    Why do you want to replace it all by 1 variable ? What code design do you have in mind ? I am sure that my design is not good (i am n00b) , but i need to know what are the flaws.

    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    David Blaine wrote:
    Mansukhdeep Thind wrote:
    No, not static. You should have a private int size variable. If you use a static variable, then that belongs to the entire class and not the instance of your custom list. So , essentially, you just need:

    Understood? If yes, then we can move on to rectifying your constructors.


    Why do you want to replace it all by 1 variable ? What code design do you have in mind ? I am sure that my design is not good (i am n00b) , but i need to know what are the flaws.



    Let me ask you the same question. Why do you think you need them as instance members? Instead, why not have method local variables? Rest everything can be handled from within the APIs that we will be implementing. Understood?
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 8008
        
      22

    Mansukhdeep Thind wrote:Yes Campbell, you are correct. I do not need a return type at all here. The re assignment works just as good:

    You really don't like parameters, do you?

    Whether or not the method returns an array is very much a matter of style. Personally, I try to avoid methods that return void, because it hides information from the reader and relies on good naming for clarity; so I prefer to see:
    values = growArray();
    when I'm looking through a program, rather than simply:
    growArray();
    but there's no 'right' or 'wrong' about these sorts of decisions.

    Another argument for the "functional" style is that the method can be made static; and even placed in a utility class if you want, viz:
    private static final <T> T[] resizeArray(T[] oldArray, int newSize) { ...

    However, there's a much stronger reason to supply parameters to this method: It makes it more flexible.
    The way you've implemented it, you've forced yourself to cast in two places - once when you initialize values, and again inside the method itself.

    Finally, you've assumed that you're only ever going to grow the array. If you look at the API for ArrayList, you'll see that it has a trimToSize() method, and my implementation (and name) allows you to contract values as well as expand it.

    HIH

    Winston
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Winston Gutkowski wrote:
    Whether or not the method returns an array is very much a matter of style. Personally, I try to avoid methods that return void, because it hides information from the reader and relies on good naming for clarity; so I prefer to see:
    values = growArray();
    when I'm looking through a program, rather than simply:
    growArray();
    but there's no 'right' or 'wrong' about these sorts of decisions.


    My 2 cents:

    If this is a private method that is only used to alter a fixed set of member variables (such as replace a 10-element array with a 20-element array), then I generally return void, since the method's only purpose is its side-effect, and that side-effect always changes the same variable. So here, I'd have it return void. "Change the size of the backing array."

    If we had 2 arrays, and either of them might need to be resized, I'd have it return the new array, since even within the confines of my class, it's now a more general-purpose method.

    And of course, Winston, as you point out, since resizing an array is a very general-purpose activity that I might need to do in any given context, I'd create a separate utility class which would then of course have to return the result (or use an existing one if it's already available).
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    I have the source code, I have the power. I am keeping it as it is and moving on to implement the next method.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Here is the next method, contains(T):




    EDIT: Also implemented clear():



    Is it fine? Any flaws?
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Mansukhdeep Thind wrote:
    EDIT: Also implemented clear():



    Is it fine? Any flaws?


    You're still not paying enough attention to detail. And you're clearly not testing before asking for comments, or at least not testing thoroughly.



    Think, carefully and in detail, what it means for the list to be empty.
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 8008
        
      22

    Jeff Verdegan wrote:If this is a private method that is only used to alter a fixed set of member variables (such as replace a 10-element array with a 20-element array), then I generally return void...

    Why did I know that that might be the case?

    @Mansukhdeep: Which just goes to prove that there are many ways to think, and to do things, even among experienced bods.

    As to your contains() method, I think you're waaay overthinking it. Based on what I've seen so far, it should be 1 line long, regardless of how you write your code.

    Winston
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Jeff Verdegan wrote:
    Mansukhdeep Thind wrote:
    EDIT: Also implemented clear():



    Is it fine? Any flaws?


    You're still not paying enough attention to detail. And you're clearly not testing before asking for comments, or at least not testing thoroughly.





    Think, carefully and in detail, what it means for the list to be empty.



    It will be a list of initial size as default one with no elements in it. In this case, a list of 10 null elements. In the clear() method, I missed out on setting size = 0. Something like:


    Am I thinking correctly now Jeff? Or is there still something that I have missed?
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Winston Gutkowski wrote:
    Jeff Verdegan wrote:If this is a private method that is only used to alter a fixed set of member variables (such as replace a 10-element array with a 20-element array), then I generally return void...

    Why did I know that that might be the case?

    @Mansukhdeep: Which just goes to prove that there are many ways to think, and to do things, even among experienced bods.

    As to your contains() method, I think you're waaay overthinking it. Based on what I've seen so far, it should be 1 line long, regardless of how you write your code.

    Winston


    Yes, I was over thinking as I had chosen not to re-use any build it API. But since I myself created the indexOf(T) API, I will use it in the contains(T) method :



    OK NOW! Mansukhdeep Thind is learning many new things from Winston Gutkowski and Jeff Verdegan...
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Mansukhdeep Thind wrote:



    X ? true : false can be simplified.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Jeff Verdegan wrote:
    Mansukhdeep Thind wrote:



    X ? true : false can be simplified.


    Do you mean this can be further simplified Jeff?
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Mansukhdeep Thind wrote:
    Jeff Verdegan wrote:
    X ? true : false can be simplified.


    Do you mean this can be further simplified Jeff?


    Yes.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 39393
        
      28
    Mansukhdeep Thind wrote: . . . Do you mean this can be further simplified Jeff?
    You should know better than to use that smilie by now
    Yes, you can simplify that a lot; I would not use the == operator myself. I shall give you a hint, which was written back in 1999. Try ยง10.5.2.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    How in the world do I simplify a statement which is already a single line?

    I break the cage and I get this:



    High 5!!

    Also Campbell, is the clear() method rightly implemented:



    This is what clearing the list means in my opinion. Am I correct?
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 39393
        
      28
    Mansukhdeep Thind wrote: . . . . . .
    A lot better. You can see how much simpler things become when you get them right
    I would have written
    return indexOf(object) >= 0; // Not linked to not-found-index = -1
    Yes, that clear method will work correctly. The old array and all its contained references might now be garbage collected.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    OK Campbell. Here is the isEmpty() implementation:



    EDIT:

    Implemented the lastIndexOf(T) method too:



    Are they fine?
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 8008
        
      22

    Mansukhdeep Thind wrote:is the clear() method rightly implemented:

    Seems reasonable. However, it's another place that you're having to cast. Why not have all assignments to values use the same code?

    Winston
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    I didn't get your point Winston. I understand that the RHS of the values assignment is being duplicated, well almost, at 3 places:







    What are you hinting at here when you say use same code?
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 39393
        
      28
    WG probably means to refactor that into a private method.
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 8008
        
      22

    Mansukhdeep Thind wrote:What are you hinting at here when you say use same code?

    Campbell's right. And I even gave you a possible implementation earlier that you could use in all 3 places.

    Winston
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Yes Winston. Got your point now.





    But I still have one doubt . Why are we using ?
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Mansukhdeep Thind wrote:
    But I still have one doubt . Why are we using ?


    In what situations will that result in length = newSize and in what situations will it result in length = oldArray.length?

    Now think about what you'd use instead of Math.min(), and what results you'd get if you used that in each of the above situations.
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 8008
        
      22

    Mansukhdeep Thind wrote:But I still have one doubt . Why are we using [Math.min()]?

    Have a look at what I said about trimToSize(), and see if it makes any more sense then.

    And for precisely the same reason (minimizing casts), I'd suggest you also think about about implementing a private element setter method.

    Winston

    PS: Your docs don't fully explain the reasoning behind the method. For example, how about:
    @return A new array of the specified size, optionally filled with elements of oldArray (if not null).
    If newSize is < oldArray.length, the elements copied will be the leftmost ones.

    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Jeff Verdegan wrote:
    Mansukhdeep Thind wrote:
    But I still have one doubt . Why are we using ?


    In what situations will that result in length = newSize and in what situations will it result in length = oldArray.length?

    Now think about what you'd use instead of Math.min(), and what results you'd get if you used that in each of the above situations.



    So that the loop for copying the elements from oldArray to the newArray runs for minimum number of times which in turn depends on the values of newSize and the capacity of the oldArray. So, for example, if we have :

    and we want to trim it to optimize the storage of the list in the memory, we would want remove the last 3 null values. In this case, newSize would be 7 and oldArray.length would be 10. So, the loop would run 7 times.

    On the other hand, if we want to grow the list size, we would have oldArray.length < newSize and hence, the for loop will run the entire length of the oldArray.


    The objective, in both these cases, is to aim for minimum number of iterations of the for loop that are absolutely essential. Have I got it correct?
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Implementing ArrayList class manually