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
}

Bernhard Barker · Accepted Answer · 2014-05-13 01:19:10Z

2

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.

answered May 13, 2014 at 1:19

Bernhard Barker

55.7k14 gold badges111 silver badges143 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Don U Over a year ago

Thank You. Simply fell off my mind to consider the entire code. a "Max" array size was created previously. thanks again.

Leo · Accepted Answer · 2014-05-13 01:05:04Z

0

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

answered May 13, 2014 at 1:05

Leo

6,5804 gold badges40 silver badges52 bronze badges

1 Comment

Don U Over a year ago

shifting "implies" that the size of an immutable array can be extended. I am simply trying to reason out the logic. I like to be able to tell it like a story.

Collectives™ on Stack Overflow

Ordered array insert

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related