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


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript 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

I was asked in an interview that how would I go about implementing the functionality that the current java.util.ArrayList class provides (like add, remove, indexOf, get(int) etc..). I was stumped and did not know what to say. Could someone give me some hint as to how to go about this task? I shall try and figure out the rest.


~ Mansukh
Akhilesh Trivedi
Ranch Hand

Joined: Jun 22, 2005
Posts: 1526
Are you allowed to use arrays or no?


Keep Smiling Always — My life is smoother when running silent. -paul
[FAQs] [Certification Guides] [The Linux Documentation Project]
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

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?
Akhilesh Trivedi
Ranch Hand

Joined: Jun 22, 2005
Posts: 1526
Mansukhdeep Thind wrote:How will you go about creating a growable array which can do all the things an ArrayList can?

You will have to manually grow the array with new size and do a copy.
Abhay Agarwal
Ranch Hand

Joined: Feb 29, 2008
Posts: 1086
    
    1

Hi Mansukhdeep

It is very well possible to write basic ArrayList implementation using Array class.
Arraylist is basically an auto growable collection of elements where in size of arraylist grows automatically. And also you can provide add/delete/modify array list elements.
So you just need to use Array to create a auto growable ArrayList

Just to give your starting point, below mentioned is the CustomArrayList class which is being initialized in constructor. You can furthur build CustomArrayList to increase size at runtime and can also add insertion/deletion methods

for example -



~abhay


Oracle Java Web Service Developer (1z0-897), Oracle certified Java 7 Programmer, SCJA 1.0, SCJP 5.0, SCWCD 5.0, Oracle SQL Fundamentals I
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38389
    
  23
I can see several ways you can improve that class. Apart from the poor formatting, that is.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

It is very well possible to write basic ArrayList implementation using Array class.


Which Array class? In the java.lang.reflect package? How is that going to help? Or do you mean by using the concept of creating a generic Object[] array? How does one make an array grow dynamically as and when elements are added to it? In Java language, arrays are defined as containers with a fixed size.
Abhay Agarwal
Ranch Hand

Joined: Feb 29, 2008
Posts: 1086
    
    1

Which Array class? In the java.lang.reflect package?


By Array class, I meant Array of Objects (like I have shown in my previous post in this thread). No Reflection API.

How is that going to help? Or do you mean by using the concept of creating a generic Object[] array?


If you do not want to hard code /use Object class (probably because at runtime, your CustomArrayList can contains elements of different types such as - String, Integer etc) then you can use Generic declaration in your CustomArrayList. for example -




How does one make an array grow dynamically as and when elements are added to it? In Java language, arrays are defined as containers with a fixed size.


Yes you are correct - In Java language, arrays are defined as containers with a fixed size. Just give a thought ... otherwise I shall post a pseudo code of it in this forum thread.

~abhay


Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Ok Abhay. I will try and work at it. One thing. What is the "sizeratio" for? What does it represent?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38389
    
  23
Mansukhdeep Thind wrote:. . . What is the "sizeratio" for? . . .
I think it is the less severe of the two errors I can see
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

I think it is the less severe of the two errors I can see
Hmm.. I am trying without referring to any other sources Ritchie. Why do you term this as an error? We have to start with some size. Then as we add elements, we have to increase the size proportionately. Correct?
Abhay Agarwal
Ranch Hand

Joined: Feb 29, 2008
Posts: 1086
    
    1

@Campbell - I shall be more than happy to know two errors that you forsee it this code.
My take is that you are probably referring to synchronization issues in my above code.

sizeratio is number by which arraylist size is initialized.

~ abhay
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7674
    
  19

Abhay Agarwal wrote:sizeratio is number by which arraylist size is initialized.

Then why not call it 'initialSize'?

This is one of the problems with posting ready-made solutions - quite apart from being against the ethos of this site, they WILL be critiqued.

@Mansukhdeep: Unfortunately, we don't really have enough information about this interview question: ie, Precisely what they wanted your "CustomArrayList" class to be able to do.

If it was simply an exercise in understanding how to build an outwardly "dynamic" array, I suspect you already have the understanding to do that - all you need to know is when you need to resize it.

The real problem is that ArrayList implements the List interface; and that has a pile of stuff - including two types of Iterator - that are likely to present you with a lot more problems than just the business of when and how to resize an array.

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

@Mansukhdeep: Unfortunately, we don't really have enough information about this interview question: ie, Precisely what they wanted your "CustomArrayList" class to be able to do.


He asked me to design a custom class similar to ArrayList which:

a) When instantiated, would result in creation of reference to an array of objects which would grow dynamically as and when elements are added to it.

b) I should implement add and remove functionality given the index or the element.

c) I should be able to find the index of the element provided.

all you need to know is when you need to resize it.
I believe I need to re-size it whenever I am adding a new element. Correct?

The real problem is that ArrayList implements the List interface; and that has a pile of stuff - including two types of Iterator - that are likely to present you with a lot more problems than just the business of when and how to resize an array


Let me go step by step. Let me successfully implement the first three basic requirements. Then we can move the more complicated stuff.

I will try now. Will come back if I am stuck somewhere.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7674
    
  19

Mansukhdeep Thind wrote:I believe I need to re-size it whenever I am adding a new element. Correct?

Sounds good to me. Some dynamic lists also "shrink", but it doesn't sound like that was part of your remit.

The main thing you need to work out is: when do you resize?

Winston
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:I believe I need to re-size it whenever I am adding a new element. Correct?


That's one approach you could take. It would lead to poor performance though. Adding an element would be an O(N) operation, whereas in the existing ArrayList it's O(1). If I were the interviewer, I'd deduct points for that.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38389
    
  23
Abhay Agarwal wrote:. . .
My take is that you are probably referring to synchronization issues in my above code.
Not at all. The code does not have anything in which needed synchronisation. The errors I saw were much simpler. Real “beginning Java” stuff.
sizeratio is number by which arraylist size is initialized.

~ abhay
Apart from what Winston has already told you, and the poor formatting of the name: why on earth do you want a static field with the initial size at all? It is something which is only used locally in the constructor, so why not defy the style suggestion about magic numbers and simply write 10. It should be a local variable in the constructor. Add a comment explaining that you are initialising it to 10 elements. And, if you overload your constructor, make sure to do that correctly, otherwise I shall find another error.

I think the second error is more serious, but you won’t notice it if your class remains that small.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Adding an element would be an O(N) operation, whereas in the existing ArrayList it's O(1). If I were the interviewer, I'd deduct points for that.


What is meant by O(N) operation and O(1) operation? What functions are you referring to? The time it takes to add the element?
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7674
    
  19

Jeff Verdegan wrote:
Mansukhdeep Thind wrote:I believe I need to re-size it whenever I am adding a new element. Correct?

That's one approach you could take. It would lead to poor performance though...

Hmmm. A subtle difference between 'when' and 'whenever'...I take your point though.

@Mansukhdeep: And so should you.

Winston
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:
Adding an element would be an O(N) operation, whereas in the existing ArrayList it's O(1). If I were the interviewer, I'd deduct points for that.


What is meant by O(N) operation and O(1) operation?


http://en.wikipedia.org/wiki/Big_o_notation

In short, it's roughly "How fast does CPU or memory usage grow relative to how input size grows?"

Saying, "Adding an element is an O(N) operation," means that the time it takes to add an element is proportional to the size of your list (N). So it takes 5 times as long to add an element to a list that's already at size 50 as it does to add an element to a list of size 10. O(1) means it's a constant-time operation. Adding an element doesn't depend on the size of the list.

What functions are you referring to? The time it takes to add the element?


Yes, when I said "adding an element," I was referring to the time it takes to add an element.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38389
    
  23
Mansukhdeep Thind wrote: . . . What is meant by O(N) operation and O(1) operation? . . .
Wikipedia link.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7674
    
  19

Jeff Verdegan wrote:O(1) means it's a constant-time operation. Adding an element doesn't depend on the size of the list.

<nitpick>
Strictly speaking, all docs for ArrayList say that adds work in amortized O(1) time - and that's because of the internal algorithm that the class uses for expansion - it would be quite easy to pick one that doesn't work in O(1) time, amortized or otherwise.
</nitpick>

Ain't Fridays great?

Winston
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Winston Gutkowski wrote:
Jeff Verdegan wrote:O(1) means it's a constant-time operation. Adding an element doesn't depend on the size of the list.

<nitpick>


Yeah, yeah, I know. I didn't want to throw too much new stuff out there at once.

@Mansukhdeep, this bit isn't important for what you're trying to do, but if you're curious, what this means, roughly, is that averaged over many adds, it approaches O(1). The first N adds will be O(1). Then at some point, an add triggers a resize of the backing array. That operation is O(N). Then the next M adds take O(1) again, and then a resize, and so on. By making sure the number of adds between resizes is larger each time around, the O(1) adds overshadow the O(N) add-plus-resize operations. Choosing when to resize, and by how much has implications for CPU and memory. And as is often the case, making more efficient use of one results in less efficient use of the other.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

I succeeded in implementing a dynamically growable array. I did this by copying the array. But I am stuck at a point. When I add a new element, it is getting added to the next index position correctly, but the previous element becomes null.

This is happening because I am creating a new copiedArray[] object inside the addElement() method. Where should I construct the new copiedArray so that it retains the last added element and adds the new one to it?

0
1
2
3
Original array size is 10
New array size is 13
null // this one
null // this one
null // this one
34
null
null
null
null
null
null
null
null
null
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Break your problem down into independent pieces. Write, compile, test, debug each piece independently of the others. Use methods for distinct operations.

Since your problem is with growing the array...



...your job is to complete the above code.

The expected output is (approximately):


x before grow: [A, B, C, D]
x after grow: [A, B, C, D, null, null, null, null]



This is how you should always approach coding. Do this from the start, rather than writing a whole bunch of code to solve your entire problem, and only then testing it.

And when you do have a larger bunch of code put together, and some piece isn't working, write a smaller program to do only that piece, get that part working, and then re-integrate it with your larger project.

Once you get the above method working, you will place it into your ArrayList class. And I don't mean just copy the body of the method and stick it inside your add() method inline. I mean copy the whole method. So then your add() method will look something like:


Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

OK Jeff. Will put in some effort in this direction.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7674
    
  19

Mansukhdeep Thind wrote:OK Jeff. Will put in some effort in this direction.

And when you do, please DontWriteLongLines. I've broken up the ones in your previous post.

Thanks

Winston
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157



It gives the output:

x before grow: [A, B, C, D]
x after grow: [A, B, C, D, null, null, null, null, null]

Is this what you were expecting of me?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff. Got it. You are correct. I have to learn to break down the task in to manageable and logical constructs. Add is working properly with the array growing dynamically. I shall proceed with remove tomorrow. Went for a 10km run. So tired. Good night guys.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:
It gives the output:

x before grow: [A, B, C, D]
x after grow: [A, B, C, D, null, null, null, null, null]

Is this what you were expecting of me?


Yup! Good work!

There are a few implementation details that could use improvement.

  • I wouldn't bother passing the array to the method. That method is just meant to work on one specific, well-known member variable. It's not for growing an arbitrary array that's passed to it.
  • I would also do away with passing the new size. I would just calculate it on the fly based on the size of the original array. However, if you have some other approach to computing the new size, it may be appropriate for you to pass it.
  • Instead of iterating and copying yourself, you could use System.arraycopy, and there may also be an equivalent method in java.util.Arrays. This saves you a small amount of code, and allows the copy mechanism to use faster native code for copying blocks of memory. Not a big deal, but worth keeping in mind.
  • And finally, growableArray should not be a member variable. It's a temporary variable that's only used during the execution of that method, so it should be local to that method.


  • The main thing though is that you embrace the technique of writing a small class with a small number of methods to work out how to solve the current problem.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Thank you for your guidance Jeff. Will come back tomorrow and meet you and the other guys to keep up the implementation.

    The main thing though is that you embrace the technique of writing a small class with a small number of methods to work out how to solve the current problem.


    Wise words. The answer is important, but the way you get to it is even more important.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    I wouldn't bother passing the array to the method. That method is just meant to work on one specific, well-known member variable. It's not for growing an arbitrary array that's passed to it.


    Amendment made.

    I would also do away with passing the new size. I would just calculate it on the fly based on the size of the original array. However, if you have some other approach to computing the new size, it may be appropriate for you to pass it.
    Taken care of.

    And finally, growableArray should not be a member variable. It's a temporary variable that's only used during the execution of that method, so it should be local to that method.
    Done.



    Once you get the above method working, you will place it into your ArrayList class. And I don't mean just copy the body of the method and stick it inside your add() method inline. I mean copy the whole method.
    Also done.

    Now I need to be able to iterate over the elements of the list. So I need to implement the Iterable interface. Will that be good as the next assignment?
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38389
        
      23
    Mansukhdeep Thind wrote:I succeeded in implementing a dynamically growable array.
    No you didn’t. There is no such thing. What you are doing is replacing it with a larger array. Its implications have already been discussed.
    . . .
    I am please to see you have escaped the more serious of the two errors I mentioned earlier. And I haven’t yet told anybody what it is.
    Still some things I would query in your code:
  • 1: Why does it implement Cloneable when you haven’t overridden clone()?
  • 2: Why does it implement Cloneable at all?
  • 3: Why do you have two arrays as fields?
  • 4: Why are you passing the list name to the add method?
  • There are also stylistic shortcomings, eg null ==, inconsistent indentation and spacing.

    The construct null == is needed in C/C++ because they can use any type instead of a boolean (in fact C doesn’t have booleans as such at all), but is never needed in Java; always use if (xyz == null)...
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    What you are doing is replacing it with a larger array.
    OK. I did a copy. I take back my words.
    Here is the latest code.


    No Cloneable implemented. That was a mistake.

    Why are you passing the list name to the add method?


    Then how to call the growArray() method without having a reference to the myList passed to addElement(..) method? I need an instance of the class to call it on. Right?
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38389
        
      23
    You already have an instance of the class to call it on. Sometimes called this.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    You already have an instance of the class to call it on. Sometimes called this.
    Things sound so simple when we first learn the basic concepts. But implementing those concepts wisely and in a fruitful manner when faced with a real time scenario is a whole different ball game.

    Next task--> My next objective is to make my custom list iterable i.e. I should be able to use the myList reference as a target in the for-each construct. I am thinking of implementing the java.lang.Iterable interface. The overridden method Iterator of this interface would return a reference to a CustomIterator class that will in turn implement java.util.Iterator interface for my custom collection class. It would fit in my current project like this:


    Am I on the right track?
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38389
        
      23
    Mansukhdeep Thind wrote: . . . Things sound so simple when we first learn the basic concepts. . . .
    Things are so simple when you implement them correctly

    Am I on the right track?
    Without even reading the code … no. You want to get the first part working correctly before you try any enhancements. Get one method working before you even think about the second method.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Hi Ritchie

    I have successfully implemented hasNext() and next(). I am now able to iterate over the elements of the custom list "myList" using both iterator and enhanced for loop. I am having trouble implementing the remove() method though. It should remove the last element of the underlying custom collection. How to do that?
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38389
        
      23
    Getting better, but it needs a lot of improvement yet. Your get method is unnecessarily complicated. You are still using null== and null!= which shouldn’t be used in Java.
    Start by implementing size(), add(E) add(int, E) get(int) set(int, E) and remove(int). Forget about the iterator until you have got all that lot working.
    You will need a modificationCount field, and use that to check concurrent modification, so you can throw an Exception from the Iterator as appropriate.
    I suggest you start by parameterising the class completely, so it isYou will not un‑comment those interfaces until you have implemented a lot more methods.
    You do not need initialSize as a field.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Your get method is unnecessarily complicated. You are still using null== and null!= which shouldn’t be used in Java.


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

    Is this what you were expecting it to look like? I have also rectified the null!=/null== style. But could you please tell me why? What is the problem with current style? Is it just a Java convention? Or is it something more serious?

    Start by implementing size(), add(E) add(int, E) get(int) set(int, E) and remove(int).


    I infer these methods will do the following tasks:

    a) size() : returns the number of elements(non null) in 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 and moves the element(if present) at that position one index to right.

    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?

    Forget about the iterator until you have got all that lot working.
    OK.

    You will need a modificationCount field, and use that to check concurrent modification, so you can throw an Exception from the Iterator as appropriate.

    Concurrent modification is when more than one thread is trying to access my custom ArrayList at same time. Correct? Are you hinting that I should make my class thread safe? I could not fully grasp this point. Please elaborate what do you term as "concurrent modification". Also, how will I check if that is happening using a long type field?


    I suggest you start by parameterising the class completely, so it is


    What is meant by parametrization of a class?

    You will not un‑comment those interfaces until you have implemented a lot more methods.
    OK.

    You do not need initialSize as a field.


    So, you want me to remove the initialSize field and directly hard code the size inside the constructor. Something like:



    Correct?
     
    With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
     
    subject: Implementing ArrayList class manually