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

Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:
Is there NO WAY AT ALL to make this operation atomic Jeff? Can't we somehow achieve a handle on the collection and lock it down when it is passed as an argument to the addAll() method


No. You can't "lock down" an arbitrary object. Mutual exclusion in Java only works when all concerned parties cooperate. If someone passes you a Collection, there's nothing you can do inside your method to force them not to modify that collection.

On the other hand, if they're operating in a multithreaded environment, it's their responsibility to know that your method will be reading their collection and to know if something else they're doing could be writing it, and to add their own mutual exclusion logic to handle it. In short, it's not your problem.

Why is it impossible?


Because Java does not provide a way to say "Nobody can call any methods on this object or access any of its members" for an arbitrary object.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8206
    
  23

Mansukhdeep Thind wrote:Is there NO WAY AT ALL to make this operation atomic Jeff?

Nope, because it depends entirely on what type of collection was passed and what the caller decides to do with it.

In general, cloning the way I suggested will either return some weakly consistent version of collection, or else it'll throw an exception. If you document it as such, at least it's then the client's own stupid fault if they decide to update it while you're cloning. If you don't clone, you run the risk of elements being added while you're filling your array, which could screw up that logic in ways that are trickier to analyse.

Winston

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

Joined: Oct 13, 2005
Posts: 39818
    
  28
You can put a lock on the add method (etc) which prevents two threads accessing the add method simultaneously. You can make the lock re-entrant and lock all the add methods, remove, etc, so only one of them can be called at any one time. But the Collection you are loading the elements from is probably not thread‑safe, so there is the possibility that it is added to or removed from while your addAll operation is proceeding.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Campbell Ritchie wrote:You can put a lock on the add method (etc) which prevents two threads accessing the add method simultaneously. You can make the lock re-entrant and lock all the add methods, remove, etc, so only one of them can be called at any one time. But the Collection you are loading the elements from is probably not thread‑safe, so there is the possibility that it is added to or removed from while your addAll operation is proceeding.


That's what. Atomicity is what I was thinking of. Anyways, let's move on to the next method. Lets clone () the list.


~ Mansukh
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39818
    
  28
Why clone? An iterator method would be far more interesting.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

So you want me to implement Iterable interface for my CustomArrayList class?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39818
    
  28
Why not? You need to work out how to create the Iterator and a ListIterator, and also how to get it to throw the concurrent modification exception. That won’t be easy.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8206
    
  23

Mansukhdeep Thind wrote:So you want me to implement Iterable interface for my CustomArrayList class?

Assuming that it implements java.util.List, you don't have any choice because a List is an Iterable.

Campbell Ritchie wrote:You need to work out how to create the Iterator and a ListIterator...

Ugh. Now's there's a dog's breakfast of an interface if there ever was one.

Why couldn't they simply have extended Iterator to provide a direction? I have never, in 12 years, needed to do next() followed by previous(); which is, arguably, not "iteration" at all.

Winston
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Winston Gutkowski wrote:Why couldn't they simply have extended Iterator to provide a direction? I have never, in 12 years, needed to do next() followed by previous(); which is, arguably, not "iteration" at all.

Winston


I did not understand this statement of yours Winston. What do you mean when you say
extended Iterator to provide a direction..
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Tried my hand at implementing Iterable interface for my custom list:

Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:
public final boolean hasNext() {
if(iterable[currentIndex]!=null){
return true;
}
return false;
}


So the only way that you ever don't have a next element is if you're currently pointing to null? Really?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Then how come the for-each and the while(hasNext()) are returning perfect results. All the elements are being printed correctly in order. If my hasNext() method is flawed as your say, which it is , then why is there no problem with the printing of the list?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:Then how come the for-each and the while(hasNext()) are returning perfect results. All the elements are being printed correctly in order. If my hasNext() method is flawed as your say, which it is , then why is there no problem with the printing of the list?


Don't get defensive. Just answer my question: Is the only way that you ever don't have a next element is if you're currently pointing to null?

As for "returning perfect results," that means either your testing is flawed by virtue of not covering the corner case my question is alluding to, I'm making an incorrect assumption. I'm asking the question to try to find out which it is.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
Mansukhdeep Thind wrote:Then how come the for-each and the while(hasNext()) are returning perfect results. All the elements are being printed correctly in order. If my hasNext() method is flawed as your say, which it is , then why is there no problem with the printing of the list?


Don't get defensive. Just answer my question: Is the only way that you ever don't have a next element is if you're currently pointing to null?


No Jeff. The correct logic would be to check successively if the next element is null or not. Am I thinking correct now?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:
Jeff Verdegan wrote:
Mansukhdeep Thind wrote:Then how come the for-each and the while(hasNext()) are returning perfect results. All the elements are being printed correctly in order. If my hasNext() method is flawed as your say, which it is , then why is there no problem with the printing of the list?


Don't get defensive. Just answer my question: Is the only way that you ever don't have a next element is if you're currently pointing to null?


No Jeff. The correct logic would be to check successively if the next element is null or not. Am I thinking correct now?


Current vs. next is a separate issue. Either one can work, depending on how you implement it. Given that your testing works so far, you probably have that right, and from your code, it looks like the index is indicating the item that will be returned on the next call to next(), so I don't think you have that off-by-one error, and that's not what I'm getting at.

Here's another hint: Will there always be at least one null element?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote: Here's another hint: Will there always be at least one null element?


No Jeff. If the list size becomes equal to its capacity, then we will have no null elements at all. But what's the point? I just modified the methods as follows:



These are also working perfectly.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:
Jeff Verdegan wrote: Here's another hint: Will there always be at least one null element?


No Jeff. If the list size becomes equal to its capacity, then we will have no null elements at all. But what's the point? I just modified the methods as follows:


The point is exactly the modification you just made. That's what I was getting it. Your earlier approach that only looked for the next (or current) element being null would throw ArrayIndexOutOfBoundsException if your array was full. I was asking because I didn't know if maybe you always resized before you get full, so that there would in fact always be at least one null at the end. (Although i think it would still be good practice to check for cur matching size, so that your hasNext() is less tightly coupled to your backing store implementation.)

There's another, smaller problem though. Your next() claims to throw NoSuchElementException, but it doesn't. It throws ArrayIndexOutOfBoundsException.

Your testing should include testing error conditions, to make sure that exceptions are thrown when expected, and that they're the correct exceptions.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
Mansukhdeep Thind wrote:
Jeff Verdegan wrote: Here's another hint: Will there always be at least one null element?


No Jeff. If the list size becomes equal to its capacity, then we will have no null elements at all. But what's the point? I just modified the methods as follows:


The point is exactly the modification you just made. That's what I was getting it. Your earlier approach that only looked for the next (or current) element being null would throw ArrayIndexOutOfBoundsException if your array was full. I was asking because I didn't know if maybe you always re-sized before you get full, so that there would in fact always be at least one null at the end. (Although i think it would still be good practice to check for cur matching size, so that your hasNext() is less tightly coupled to your backing store implementation.)


Ohhh.. OK NOW! Some new learning from Jeff Verdegan. I just realized the meaning of the last 4 posts. Since the backing array is growing as and when size becomes equal to capacity, there will always be at least 1 null element. Hence, the previous logic worked too. And obviously, this is the correct way it should have been done in the first place, regardless of the fact that whether we are growing the array or not, just to be safe.

Jeff Verdegan wrote:There's another, smaller problem though. Your next() claims to throw NoSuchElementException, but it doesn't. It throws ArrayIndexOutOfBoundsException.

Your testing should include testing error conditions, to make sure that exceptions are thrown when expected, and that they're the correct exceptions.


This is yet another thing on my to do list Jeff. I need to learn how to judge which exceptions will be thrown and when to throw them. Is there a tutorial for this? Or is it sheer experience of working with the language that helps one gauge it?
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8206
    
  23

Mansukhdeep Thind wrote:I did not understand this statement of yours Winston. What do you mean when you say
extended Iterator to provide a direction..

It's simply an opinion, but I think that ListIterator is badly thought out and bloated for 99% of everyday use. It's rare for me to slag off Sun's designers but, in this case, I think they got it wrong.

An Iterator that works backwards? No problem. And, for a List, one that takes a start point I can also understand. But one that works in both directions at once? As I said above: very rare - and it's arguable then whether it even qualifies as an "Iterator".

Somewhere in between you have a DirectionalIterator (unfortunately, not defined by Sun) - ie, an Iterator that has a "direction" - you can can even implement one that allows you to change direction, but it only works in one direction at a time.

Indeed, that's how I generally design a ListIterator (if I need to).

Winston
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:Since the backing array is growing as and when size becomes equal to capacity, there will always be at least 1 null element.


So, if capacity is 10 (array.length is 10), then when you add the 10th element, so that now all the array slots are filled up, you resize the array before you return from add()? If so, then, yes, I was mistaken and you don't have to check for size == capacity. However, if you return from add() without resizing, then you will not have a null element.

This is yet another thing on my to do list Jeff. I need to learn how to judge which exceptions will be thrown and when to throw them. Is there a tutorial for this? Or is it sheer experience of working with the language that helps one gauge it?


You should throw an exception when something outside the expected "happy path" execution occurs. If something that's required to happen fails to happen, throw an exception (unless you can make things right in the code). The exception name, package, and class hierarchy should match the problem.

In the case of java.util.Collection, calling Iterator.next() when there are no more elements throws NoSuchElementException. That is an exception that was created specifically to mean "there are no more elements here, and you should know that, but you tried to get the next one anyway." It was actually created for Enumeration, but that's just an early form of Iterator. The "and you should know that" part is the reason its an unchecked exception.

In your case, ArrayIndexOutOfBoundsException might not necessarily be wrong, if your ArrayList stands alone, rather than being part of a collection library. In the case of java.util.Collection, however, ArrayIndexOutOfBoundsException doesn't make sense, because not all Collections are backed by arrays. So a general-purpose "this Collection has no more elments" exception was defined, to be thrown when you try to go past the end of any Collection. Like so many other things you've been hit with lately, it's about decoupling interface from implementation.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Winston Gutkowski wrote:you can can even implement one that allows you to change direction, but it only works in one direction at a time.


If I can change direction, how is that any more "one direction at a time" then just calling next(); previous(); next(); previous();? Are you talking about only being allowed to change direction after iterating the entire list?

I don't know that I think the current ListIterator is poorly designed, but, like you, I don't recall the last time I actually used one so I could call previous().

Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8206
    
  23

Jeff Verdegan wrote:If I can change direction, how is that any more "one direction at a time" then just calling next(); previous(); next(); previous();? Are you talking about only being allowed to change direction after iterating the entire list?

No, I mean that if you need an Iterator to work in either direction, give it one; don't proliferate methods. Why not just have next()/hasNext() work on the "next" element in whatever direction the Iterator is defined to travel?

Personally, I've always found it the easiest way to implement a ListIterator anyway; and it saves having to remember a load of "implementation-type" specification about how next() and previous() are supposed to work together.

Winston
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Winston Gutkowski wrote:
Jeff Verdegan wrote:If I can change direction, how is that any more "one direction at a time" then just calling next(); previous(); next(); previous();? Are you talking about only being allowed to change direction after iterating the entire list?

No, I mean that if you need an Iterator to work in either direction, give it one; don't proliferate methods. Why not just have next()/hasNext() work on the "next" element in whatever direction the Iterator is defined to travel?


So, instead of


it would be something like


?

Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:
Mansukhdeep Thind wrote:Since the backing array is growing as and when size becomes equal to capacity, there will always be at least 1 null element.


So, if capacity is 10 (array.length is 10), then when you add the 10th element, so that now all the array slots are filled up, you resize the array before you return from add()? If so, then, yes, I was mistaken and you don't have to check for size == capacity. However, if you return from add() without resizing, then you will not have a null element.


Regardless which one I choose to implement, I learned a new thing. I shall stick to the modified version. Loose coupling, as you said, should be the aim.

Jeff Verdegan wrote:
Mansukhdeep Thind wrote:This is yet another thing on my to do list Jeff. I need to learn how to judge which exceptions will be thrown and when to throw them. Is there a tutorial for this? Or is it sheer experience of working with the language that helps one gauge it?


You should throw an exception when something outside the expected "happy path" execution occurs. If something that's required to happen fails to happen, throw an exception (unless you can make things right in the code). The exception name, package, and class hierarchy should match the problem.

In the case of java.util.Collection, calling Iterator.next() when there are no more elements throws NoSuchElementException. That is an exception that was created specifically to mean "there are no more elements here, and you should know that, but you tried to get the next one anyway." It was actually created for Enumeration, but that's just an early form of Iterator. The "and you should know that" part is the reason its an unchecked exception.

In your case, ArrayIndexOutOfBoundsException might not necessarily be wrong, if your ArrayList stands alone, rather than being part of a collection library. In the case of java.util.Collection, however, ArrayIndexOutOfBoundsException doesn't make sense, because not all Collections are backed by arrays. So a general-purpose "this Collection has no more elments" exception was defined, to be thrown when you try to go past the end of any Collection. Like so many other things you've been hit with lately, it's about decoupling interface from implementation.


So how would I throw the NoSuchElementException then Jeff? Something like this:




Is this the correct way?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

That's one way. But you're forgetting to use your own methods again.

What's the logic of next()? "If the list has a next element, return it, otherwise, throw an exception."
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8206
    
  23

Jeff Verdegan wrote:it would be something like?

You've got it. My DirectionalIterator simply adds a nextIndex() method (already defined in ListIterator) to the Iterator spec, and I also have a TwoWayIterator (not wild about the name though) that further adds a Direction enum and get/setDirection() methods.

The idea is that the first one is for iterators that have their direction set at construction time, and the second is a building block for a ListIterator as well as being an Iterator that can simply "change direction". I've considered writing a JSR for it, but I'm not sure of the procedure.

Winston
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39818
    
  28
That might be better design than ListIterator, but the List interface has a listIterator() method which returns a ListIterator, so you are stuck with hasPrevious() and previous().
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8206
    
  23

Campbell Ritchie wrote:That might be better design than ListIterator, but the List interface has a listIterator() method which returns a ListIterator, so you are stuck with hasPrevious() and previous().

True, but what if the listIterator() methods returned a DirectionalIterator instead? If ListIterator was defined as an extension of DirectionalIterator, you wouldn't be breaking any existing code; and whether or not people creating their own ListIterator want it to also extend TwoWayIterator would be entirely up to them.

Like I said, the main reason I use it is to rationalize the business of implementing ListIterator for myself, but I reckon it could also make the business of implementing Lists simpler and more flexible.

Winston
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Jeff Verdegan wrote:That's one way. But you're forgetting to use your own methods again.

What's the logic of next()? "If the list has a next element, return it, otherwise, throw an exception."


Yeah,already changed it Jeff.



But if I try and write this using the ternary operator in a single statement Jeff, it throws a casting issue. Is this the shortest, most concise form possible, or can it be further reduced?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Now, after reading all this fuss created about the ListIterator and Winston's terming it as a dog's breakfast, I am having second second thoughts whether I should go ahead and implement it at all?
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8206
    
  23

Mansukhdeep Thind wrote:Now, after reading all this fuss created about the ListIterator and Winston's terming it as a dog's breakfast, I am having second second thoughts whether I should go ahead and implement it at all?

Like I said: you don't have any choice. My post was simply a rant about ListIterator.

It's possible that, like me, you may find it easier to think of a ListIterator as an extension to an Iterator that has a "direction" and implement it that way - ie, exactly the way Jeff described it:
  • next() = setDirection(FORWARDS) + getNextElement()
  • previous() = setDirection(BACKWARDS) + getNextElement()
  • but it's entirely up to you.

    Winston
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    The remove() method has been marked as an optional operation. What does that mean? It says
    Removes from the underlying collection the last element returned by the iterator (optional operation).
    What is the meaning of optional? Can I get away without implementing it?
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 8206
        
      23

    Mansukhdeep Thind wrote:What is the meaning of optional? Can I get away without implementing it?

    Sure. The usual way is to simply have it throw UnsupportedOperationException.

    Winston
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 39818
        
      28
    As Winston says, you have no choice.
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Winston Gutkowski wrote:
    You've got it. My DirectionalIterator simply adds a nextIndex() method (already defined in ListIterator) to the Iterator spec, and I also have a TwoWayIterator (not wild about the name though) that further adds a Direction enum and get/setDirection() methods.

    The idea is that the first one is for iterators that have their direction set at construction time, and the second is a building block for a ListIterator as well as being an Iterator that can simply "change direction". I've considered writing a JSR for it, but I'm not sure of the procedure.


    I gotta admit, I really don't see what the benefit is to this approach. It's not like next() vs. previous() is a complex concept to get one's head around. What's the difference between calling setDirection(REVERSE) ; next(); and just calling previous();? What do we gain by making "current direction" part of the state of the iterator rather than just implied by the method call? I think I'm missing some key point somewhere.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Winston Gutkowski wrote:
    Mansukhdeep Thind wrote:What is the meaning of optional? Can I get away without implementing it?

    Sure. The usual way is to simply have it throw UnsupportedOperationException.

    Winston


    Like this:



    Is that it?
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Yup.

    You might choose to put a bit more detail in the message, such as which class and method.


    Some may say that's redundant, since the stack trace contains all that. Others may say it's useful to have it self-contained in the exception's message. It's a judgment call, and pretty much comes down to personal preference. I'm just throwing it out there as something for you to keep in mind.
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Campbell Ritchie wrote:As Winston says, you have no choice.


    I just went through the documentation of the ListIterator interface. I don't see any specific thing that I can't do with what I have currently as my public APIs. Why do I need to implement this interface if it does not serve any particular purpose at all? Can you give an example of some use case which can not be tackled by existing APIs and the Iterator functionality already implemented, except for traversal in reverse direction, which I think is more or less useless? Isn't it Campbell?
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Mansukhdeep Thind wrote:
    Campbell Ritchie wrote:As Winston says, you have no choice.


    I just went through the documentation of the ListIterator interface. I don't see any specific thing that I can't do with what I have currently as my public APIs. Why do I need to implement this interface if it does not serve any particular purpose at all? Can you give an example of some use case which can not be tackled by existing APIs and the Iterator functionality already implemented, except for traversal in reverse direction, which I think is more or less useless? Isn't it Campbell?


    ListIterator adds backward traversal and the ability to add an element during iteration. I don't know if I've ever used either one of those, but regardless of whether you or I or Campbell or Winston think they're useful, apparently somebody did at one point, and so now, whether we think they're useful or not, if we're implementing java.util.List, we have no choice but to provide implementations for those methods. (Of course, those implementations can throw UnsuppportedOperationException, so it's not required that they actually work, only that they're present.)
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    Jeff Verdegan wrote:Yup.

    You might choose to put a bit more detail in the message, such as which class and method.


    Some may say that's redundant, since the stack trace contains all that. Others may say it's useful to have it self-contained in the exception's message. It's a judgment call, and pretty much comes down to personal preference. I'm just throwing it out there as something for you to keep in mind.


    It is good that you bring such things up now and then Jeff. Keeping things organized and following the correct practices does help in the long run.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Implementing ArrayList class manually