CODEWITHSUNDEEP
javadata-structures
suresh
suresh

Reputation: 177

ArrayList remove implementation

I was going through ArrayList remove sourceCode.

public E remove(int index) {
    rangeCheck(index);

    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null; // Let gc do its work
    return oldValue;
}

In above code we are returing oldValue but was not able to understand what is id purpose of below code 

int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null; // Let gc do its work

Can please someone walk me through code to make understand better.

Upvotes: 2

Views: 5661

Answers (3)

Thomas
Thomas

Reputation: 88747

That part checks if any elements to the right of the index being removed have to be shifted to close the "hole" created by the removal.

Example: let's say you have a list like this: "A","B","C","D","E". Internally it would be a Object[] array with a length greater than 5 (typically some power of 2 but it could by a different value), let's say of size 8. It thus would look like ["A","B","C","D","E",null,null,null].

Now you remove "C", i.e. index 2:

  • int numMoved = size - index - 1; will result in numMoved = 5 - 2 - 1 = 2, i.e. 2 elements ("D" and "E") to the right have to be moved and the if condition is satisfied.
  • System.arraycopy(elementData, index + 1, elementData, index, numMoved); "moves" (copies) the right portion of the array to the left, i.e. ["A","B","C","D","E",null,null,null] will be transformed to ["A","B","D","E","E",null,null,null].
  • elementData[--size] = null; will then do 2 things: it will decrement the size by 1 resulting in size = 4 and it will set the value at index 4 (i.e. the 5th element) to null resulting in the array looking like this: ["A","B","D","E",null,null,null,null]

Upvotes: 9

hellrocker
hellrocker

Reputation: 628

1) If you remove from the end of the list then you don't have to shift the elements , but in case if you remove from in between the list , then you have to shift the elements in right of currently removed element to left .

2) elementData[--size] = null;

this is used so that it can be garbage collected as you have already removed 1 element from the list , so there is no alive reference to this . so better to handled by garbage collector .

Upvotes: 0

Magnus
Magnus

Reputation: 8310

An ArrayList is backed by an Array.
When you move an item from the list all the items after it need to be shifted to the left so you don't end up with an empty gap.
The code above doesnt actually remove the indexed item from the array it just moves all the elements after it to the left then sets the last element in the array to null.

[1,2,3,4,5,6]
     ^Remove 3
[1,2,4,5,6,6]
     Shift left
[1,2,4,5,6,null]
     Set the last element to null

Upvotes: 0

Related Questions