How to I add in the middle of an array?

Question

I am trying to make a method called insertAt that takes 3 parameters (int index, int n, int value) so that if I call: list.insertAt(2, 4, 98) on an array of [12, 42, 8, 934], it should now store [12, 42, 98, 98, 98, 98, 8, 934].

int index is where I start to put the values

int n is how many values

int value is the actual value or number I want to put in.

I am making this method in a class called ArrayIntList:

public class ArrayIntList {
    private int[] elementData; // list of integers
    private int size;          // current # of elements in the list 
}

I tried making the method below but I am still stuck on what I am missing. If you guys can help me out I would appreciate it a lot!

public void insertAt(int index, int n, int value) {
    if (index < 0 || index > size || n < 0) {
        throw new IllegalArgumentException();
    }
    size = size + n;
    for (int i = 0; i < n; i++) {
        elementData[(size - 1) - i] = elementData[(size - n) + i];
        elementData[n + i] = value;
    }
}

Answer 1

The array you have in the example only holds 4 values, but you try to add 4 additional ones. Which is not possible as arrays have a fixed length. So you have to create a new array of length size + n:

int[] newElements = new int[size + n];

you then have to copy all elements from 0 up to index and the elements of index up to size from the old into the new array:

System.arraycopy(elementData, 0, newElements, 0, index);
System.arraycopy(elementData, index, newElements, index + n, size - index);

Then you have to insert your new element n times into the array:

Arrays.fill(newElements, index, index + n, value);

And at last you have to reassign the new array to the old instance one and set the new size:

elementData = newElements;
size += n;

I've used some helper methods from the JDK, like System.arraycopy which has the following signature:

void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

It copies the elements from src ranging from srcPos up to srcPos+length into dest ranging from destPos to destPost+length

Array.fill is also a nice helper with the following signature:

void fill(int[] a, int fromIndex, int toIndex, int val)

It fills the array a from fromIndex to toIndex with the value val

Answer 2

The Answer by Lino is correct. In addition, for this kind of work you likely should be using another data structure other than a simple array.

When you need more flexibility, use the Java Collections framework.

List

A List interface keeps track of elements in a sequential order.

The Java Collections store only objects, not primitives. So we must use the wrapper classes. In your case, Integer rather than int. In most situations the auto-boxing feature of Java will handling's

ArrayList

One implementation of List is ArrayList. This class is backed by a simple array. So inserting in the middle results in the kind of rigamarole described by Lino. But at least the class is doing the work, with code that has already been thoroughly tested unlike code that you or I would be writing.

List< Integer > integers = new ArrayList<>() ;
integers.add( 7 ) ;   // Add first element to the empty list.
integers.add( 42 ) ;  // Append to the end of the list.
integers.add( 1 , Integer.valueOf( 1999 ) ) ;   // Insert in the middle. Using zero-based index counting. So `1` means the second item.
integers.

Or in practice, I would use the ordinal number 2, and subtract 1 for the index number.

integers.add( 2-1 , Integer.valueOf( 1999 ) ) ; // Insert. Do math to convert from ordinal number (2, the second position) to index number (1).

LinkedList ⬅ Much faster!

Better would be the use of the LinkedList class that implements List. Where an array packs items together contiguously in memory, a linked list has items floating around memory separately, with each item tracking the memory location of the successive item.

So inserting in the middle is much less expensive: Just change the previous item to point to the new item, and the new item points to the successive item. No need to rebuild the list or move a bunch of items around.

Insert in a LinkedList by calling LinkedList::add( index , element) where the index is the zero-based position counter, and element is the object you are inserting.

Notice the addAll​(int index, Collection<? extends E> c) method on List. Your method that generates the multiple numbers can produce a list, then insert that list into the target list. Using this single-insert approach will be much faster than multiple inserts, as traversing the linked list to find the insert position is expensive.

// Make a list of values to be inserted into the main list.
int count = 3 ; 
List< Integer > inserts = new ArrayList<>( count );
for (int i = 0; i < count; i++) {
    inserts.add( 98 ) ;
}
// Insert into main list.
integers.add( 2-1 , inserts ) ;  // Do math to convert from ordinal number (2, the second position) to index number (1).

How to choose which List:

• If you do much traversing, or much jumping to a specific element in the list by its position number, use ArrayList. Because the elements are contiguous, jumping by position is very cheap.
• If you do much inserting or removing, use LinkedList. Because the elements are tied to one another successively, inserting/removing affects only one element, so is very cheap.

There are many other List implementations available, some bundled with Java, others available from 3rd-parties. Generally ArrayList and LinkedList are the main workhorses, used by most people in most work.