• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

ArrayList SubList method's add method

 
Greenhorn
Posts: 10
1
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello,

I was working through methods of ArrayList class and the method sublist didn't work the way I expected. Need a little help to understand this method's behavior. Two questions in this thread:

1. When subList(int, int) method is called, it returns an instance of AbstractList. Now, if I try to add an element in this sublist by calling add method on AbstractList instance I don't get an exception which is thrown in the AbstractList class in turn the element gets added. Not sure how this is working?

AbstractList's add method calls this method:



2. What's the point of ArrayList's subList method considering the fact that after its invocation:
- It doesn't allow structural modification to the backed List?

2.1 Also, why adding an element to the end of the subList works? Shouldn't the bounds of subList limit the addition of new elements? Think throwing ConcurrentModificationException when an element is added outside its bounds in the sublist make
more sense.

Adding supporting code snippet:


Output of above code:
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

G Batra wrote:
1. When subList(int, int) method is called, it returns an instance of AbstractList. Now, if I try to add an element in this sublist by calling add method on AbstractList instance I don't get an exception which is thrown in the AbstractList class in turn the element gets added. Not sure how this is working?

AbstractList's add method calls this method:




The subList() method returns a subclass of the AbstractList class -- and that method is overridden (to add the element at the specified point in the sublist backed by the array list, of course)

G Batra wrote:
2. What's the point of ArrayList's subList method considering the fact that after its invocation:
- It doesn't allow structural modification to the backed List?



It does allow structural modification ... see your previous question. The add() method worked right?

G Batra wrote:
2.1 Also, why adding an element to the end of the subList works? Shouldn't the bounds of subList limit the addition of new elements? Think throwing ConcurrentModificationException when an element is added outside its bounds in the sublist make more sense.



Adding an element to the end of the sublist inserts the element into the array list (at the correct location). This seems perfectly reasonable to me. Also, the JavaDoc clearly states that is how it works.

Henry
 
Ranch Hand
Posts: 47
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Not sure how this is working?



Just call System.out.println(yourList.subList(...).getClass()) to find out which class is really returned. It would be surely the subclass of AbstractList, but not itself
 
Sheriff
Posts: 11604
178
Hibernate jQuery Eclipse IDE Spring MySQL Database AngularJS Tomcat Server Chrome Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

G Batra wrote:1. When subList(int, int) method is called, it returns an instance of AbstractList. Now, if I try to add an element in this sublist by calling add method on AbstractList instance I don't get an exception which is thrown in the AbstractList class in turn the element gets added. Not sure how this is working?


That's a pretty easy one! AbstractList is an abstract class (as the name implies ), so the subList() method can't return an instance of AbstractList, because AbstractList can't be instantiated. So it's either another concrete class (which extends AbstractList) or an anonymous inner class of AbstractList. It's the first one, which can easily be confirmed by adding this line of code to your programwhich will print class java.util.ArrayList$SubList. So the subList() method returns an instance of the (private) inner class SubList which has an actual implementation of the add() method (and that's why you don't get an UnsupportedOperationException).

G Batra wrote:2. What's the point of ArrayList's subList method considering the fact that after its invocation:
- It doesn't allow structural modification to the backed List?


I think this one is already answered with my previous answer

G Batra wrote:2.1 Also, why adding an element to the end of the subList works? Shouldn't the bounds of subList limit the addition of new elements? Think throwing ConcurrentModificationException when an element is added outside its bounds in the sublist make more sense.


If you look at the javadoc of the subList() method, there's no mention of an exception being thrown when an element is added outside the index range. And that makes sense, because that could get very confusing very quickly. In your example you have a sub list ranging from index 2 to index 6 (exclusive). But in this sub list the element indexes range from 0 to 3 (inclusive). And then you call subList.add(5, "Y");, 5 is in the range of the sub list (because it ranges from 2 until 6, exclusive) so the element is added. But the sub list has only 4 elements (ranging from 0 to 3, inclusive). The element on index 5 will be "Y", but what will the element on index 4 be, maybe null? And what will the size of this subList be? It has to be 5 (otherwise adding one element will increase the size with 2). Then you call subList.get(4) and you expect to get "Y" as return value, but you'll get null (or some undefined value) instead. And if you want to get "Y" as return value, you have to call the get() method with an index greater than the size of the sub list. See how complicated it will get
If you are using a NavigableSet or NavigableMap you can create a sub set or sub map as well. And unlike with the sub list, you'll get a runtime exception when trying to add an element which is outside its range. But it's an IllegalArgumentException, not a ConcurrentModificationException, because the latter one is only used when a concurrent modification is detected when it's not allowed (e.g. one thread is modifying a collection while another one is iterating over this collection).

Hope it helps!
Kind regards,
Roel

PS. Have a cow for adding a supporting code snippet to your post. That's great!
 
G Batra
Greenhorn
Posts: 10
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

1. I think I should have been more specific here. Sorry for not mentioning clearly but what I meant was the subclass returned from the ArrayList.subList (int, int) method and not the abstractList itself. For some reason I thought it was implied but anyways. There's no add method in the SubList inner class of ArrayList, Roel:



add method gets inherited from the way up from the Collection (I) --> AbstractList (AbstractClass). The super AbstractList of inner class SubList provides an implementation of the add method which throws the exception. And Collection is an interface. So, I am really not sure which add method implementation is being invoked here? The exact method we're interested in is add(E) because add(int, E) is implemented in the inner class SubList.

2. Two cases:
Case 1: Simple case when add(E) is invoked on the subList reference. The element gets added at the end of the list in both the lists. Works fine. No RTE thrown. Behavior however, is inconsistent with NavigableSet and Map. But as Roel pointed out it is how the method was implemented.

Case 2: When add(E) is called on the backed list. RTE ConcurrentModificationException thrown. Why? The method call was just an attempt to add an element at the end of the list. Looks like this operation is independent of any impact on the sublist. Where's the concurrentModification? The excerpt from the Javadoc of subList method is vague:

"..... The semantics of the list returned by this method become undefined if the backing list (i.e., this list) is structurally modified in any way other than via the returned list......."


And Roel, if I try to add an element at position 5 on the sublist despite the list size of being 4, it throws RTE IndexOutOfBoundsException.

Thank you for the Cow and ofcourse your responses.
 
Roel De Nijs
Sheriff
Posts: 11604
178
Hibernate jQuery Eclipse IDE Spring MySQL Database AngularJS Tomcat Server Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

G Batra wrote:1. I think I should have been more specific here. Sorry for not mentioning clearly but what I meant was the subclass returned from the ArrayList.subList (int, int) method and not the abstractList itself. For some reason I thought it was implied but anyways. There's no add method in the SubList inner class of ArrayList, Roel:


I don't know where you are looking for the source code, but if I check AbstractList at GrepCode, I'll have these add() methodsAnd in SubList the add(int index, E element) method is overriddenSo there's indeed no add(E e) method in SubList, but it's just inherited from AbstractList.

G Batra wrote:Case 1: Simple case when add(E) is invoked on the subList reference. The element gets added at the end of the list in both the lists. Works fine. No RTE thrown. Behavior however, is inconsistent with NavigableSet and Map. But as Roel pointed out it is how the method was implemented.


You can't say it's inconsistent with NavigableSet and NavigableMap. Because List and NavigableXxx are two completely different things: the first one is an index-ordered collection, whereas the NavigableXxx interfaces are sorted collections. It would have been inconsistent behavior if NavigableSet had a range check and NavigableMap didn't, or the other way around. But not with List and NavigableXxx.

G Batra wrote:Case 2: When add(E) is called on the backed list. RTE ConcurrentModificationException thrown. Why? The method call was just an attempt to add an element at the end of the list. Looks like this operation is independent of any impact on the sublist. Where's the concurrentModification?


It's not the adding of the element itself to the backed list which throws a ConcurrentModificationException. It's when you are using the sub list after the element was added to the backed list which throws a ConcurrentModificationException. And according to the javadoc you made a structural change (because adding an element changes the size of the backed list) and then behavior is undefined. So this code runs without throwing a runtime exceptionBut this code will throw a ConcurrentModificationException at runtimeAnd that makes sense (again). Because adding an element to the backed list may result in an incorrect iteration of the sub list. Because if you executed l.add(3, "Y"); you would expect "Y" to be in the sub list as well, but on which index? Because the index of the list and the index of the sub list are not the same indexes (2 in the list = 0 in the sub list). For more detailed information, have a look at the modCount instance variable of AbstractList, it's incremented each time you make a structural modification.

And if you would be using a NavigableSet, it would have been a complete different story

G Batra wrote:And Roel, if I try to add an element at position 5 on the sublist despite the list size of being 4, it throws RTE IndexOutOfBoundsException.


Of course you'll get an IndexOutOfBoundsException! That's how a list is supposed to work. But that whole scenario I described was intended to illustrate how weird it would have been to have a sub list perform range checks (because in your OP you expected to have a range check: "Shouldn't the bounds of subList limit the addition of new elements?"). So if I invoke list.subList(2, 6);, I create a sub list with only 4 elements (ranging from index 0 to 3 inclusive) but I should be able to invoke subList.add(5, element); (as 5 is in between 2 and 6 which are the range limits of the sub list).

Hope it helps!
Kind regards,
Roel
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

G Batra wrote:
Case 2: When add(E) is called on the backed list. RTE ConcurrentModificationException thrown. Why? The method call was just an attempt to add an element at the end of the list. Looks like this operation is independent of any impact on the sublist. Where's the concurrentModification? The excerpt from the Javadoc of subList method is vague:

"..... The semantics of the list returned by this method become undefined if the backing list (i.e., this list) is structurally modified in any way other than via the returned list......."



The JavaDocs is saying ... The sublist is not designed to work if the backing list is modified (not by the sublist). This is the same behavior for the iterator too.

Henry
 
G Batra
Greenhorn
Posts: 10
1
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Roel,
When I posted the question about add(E) in subList I was pretty sure I was overlooking something and yes you were right. The add(int, E) method in the SubList inner class gets executed as it overrides the same method from AbstractList.
So call sequence: AbstractList.add(E) -> AbstractList.add(int, E) (Now overridden by SubList.add(int, E)) [Please ignore my static method style but you get the point.. ]

After carefully going through your post at least twice it has started to make some sense. Thank you for taking time out and putting effort in such an extraordinary post.
Exceptional explanation.

Thank you again for resolving yet another post.

Thank you Henry as well.



 
Roel De Nijs
Sheriff
Posts: 11604
178
Hibernate jQuery Eclipse IDE Spring MySQL Database AngularJS Tomcat Server Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

G Batra wrote:After carefully going through your post at least twice it has started to make some sense. Thank you for taking time out and putting effort in such an extraordinary post.
Exceptional explanation.

Thank you again for resolving yet another post.


Glad to hear your question is answered and doubts are cleared! Thanks for the very kind words. Highly appreciated!
 
reply
    Bookmark Topic Watch Topic
  • New Topic