Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why changes in sublist are reflected in the original list?

I know that Collections in Java are mutable when you pass them through references.
I want to know exactly what happens in memory addresses of original-list and sublist/s of it.
Do the sublist and original list refer to the same object?

Following is code sample reflecting changes made in sublist to main original list.

List<String> list = new ArrayList<String>();
list.add("1");
list.add("2");
list.add(1, "3");

List<String> list2 = new LinkedList<String>(list);

list.addAll(list2);

list2 = list.subList(2, 5);
list2.clear();               //Changes are made to list

System.out.println(list);
like image 291
Shubham Kharde Avatar asked Jul 21 '15 13:07

Shubham Kharde


3 Answers

As per the JavaDoc on the matter:

List subList(int fromIndex, int toIndex)

Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive. (If fromIndex and toIndex are equal, the returned list is empty.) The returned list is backed by this list, so non-structural changes in the returned list are reflected in this list, and vice-versa. The returned list supports all of the optional list operations supported by this list.

The sub list will point to the same elements present within the original list, thus, any changes made through the sub list will be reflected within the original list since you are changing the same objects.

EDIT: As per your comment, assume that the original list has the following references: 0x00 0x01 0x02 0x03 0x04 0x05 and these map to locations in memory where objects exist.

Doing sublist(0, 2) on the above will yield a list which contains pointers to the following memory locations 0x00 0x01 0x02 which are the same as in original list.

What this means is that if you do sublist.get(0).setFoo(foo), this will in turn seek out the object present at 0x00 and set some property. However, 0x00 is also being referenced to by original list, which is why changing the sub list means that you will be changing the source list since both lists point to the same objects. The same also holds should you change your elements through original list.

like image 65
npinti Avatar answered Nov 20 '22 04:11

npinti


In line

list2 = list.subList(2, 5);

you are calling subList method of ArrayList referred from list. Its code looks like this

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

so after confirming valid range list2 will store result of

new SubList(this, 0, fromIndex, toIndex);

where private class SubList extends AbstractList<E> is class defined inside ArrayList and code of this constructor looks like this

SubList(AbstractList<E> parent,
        int offset, int fromIndex, int toIndex) {
    this.parent = parent;
    this.parentOffset = fromIndex;
    this.offset = offset + fromIndex;
    this.size = toIndex - fromIndex;
    this.modCount = ArrayList.this.modCount;
}

so its parent field will store reference to original ArrayList (new SubList(this, ...)).

Now when you call

list2.clear();

code of clear() method inherited by SubList from AbstractList will be invoked

public void clear() {
    removeRange(0, size());
}

which will internally invoke removeRange overridden in SubList

protected void removeRange(int fromIndex, int toIndex) {
    checkForComodification();
    parent.removeRange(parentOffset + fromIndex,
                       parentOffset + toIndex);
    this.modCount = parent.modCount;
    this.size -= toIndex - fromIndex;
}

So as you see, as result you are calling

parent.removeRange(parentOffset + fromIndex,
                   parentOffset + toIndex);

where as you remember parent holds reference to ArrayList on which subList was called. So effectively by calling clear you are invoking removeRange from original list from which you created sublist.

like image 3
Pshemo Avatar answered Nov 20 '22 04:11

Pshemo


Here are simplified visualizations of a memory for the code sample based on the java source code as addition to Pshemo's great answer:

List<String> list = new ArrayList<String>();
list.add("1");
list.add("2");
list.add(1, "3");

List<String> list2 = new LinkedList<String>(list);

list.addAll(list2);

enter image description here


list2 = list.subList(2, 5);

SubList has a reference to an original list with an offset to know where a sublist starts and a size to know where a sublist ends.

enter image description here


list2.clear();

Actions on list elements are forwarded to an original list.

enter image description here

Note that this elements are removed by coping reference from index 5 to index 2 and filling array's indexes 3, 4 and 5 with nulls.

like image 3
user12145540 Avatar answered Nov 20 '22 06:11

user12145540