Ordered array insert

Question

Here is an exert from "Data Structures & Algorithms in Java" Second Edition by Robert Lafore. We are working with an ordered array attempting to insert an item in the array. I usually like to understand the lines while i code, but this seems to escape me. I understand what the first half is doing--searching for where to put the value in.

now the second part starting from for(int k=nElems; k>j; k--) is where i get stuck. I think this is what its trying to say: set k equal to the size of the original array and decrements till its k is of size j. set array location k equal to k-1(or perhaps j-1?) then... then i get stuck in a[j] = value;.

Can someone please explain whats going on there? I thought arrays were immutable once created. One would think a brand new array is would be created.

public void insert(long value)    // put element into array
{
int j;

for(j=0; j<nElems; j++)         // find where it goes
if(a[j] > value) // (linear search)
    break;

for(int k=nElems; k>j; k--)     // move bigger ones up
    a[k] = a[k-1];
a[j] = value;                   // insert it
nElems++;                       // increment size
} 

Answer 1

int k=nElems

Start at the end.

k > j

While we haven't reached the target position...

a[k] = a[k-1];

Move the current element up one position to the right.

k--

And move to the left.

---

So, shift all elements between the target position and the end one position to the right.

I thought arrays were immutable once created.

The array size is fixed once created - the element at any index can be modified or reassigned however you see fit.

What was probably done here - a larger array was created and nElems was used to indicate the number of populated values - the remaining indices would just be null. Wikipedia's article on dynamic arrays briefly mentions this - the concept of capacity versus size - the capacity would be a.length, the size would be nElems. This is identical to how an ArrayList works.

Answer 2

It's shifting the existent elements before inserting to make room for the new element