How can we dynamically allocate and generate an array

Question

I am working on a project, but I cannot use existing Java data structures (e.g. ArraysList, trees, etc.)

I can only use arrays. Therefore, I need to dynamically update the array with new memory.

I read from a text file, and I pre-allocate 100 for the memory of arrays:

String [] wordList; int wordCount = 0; int occurrence = 1; int arraySize = 100; wordList = new String[arraySize]; while ((strLine = br.readLine()) != null) { // Store the content into an array Scanner s = new Scanner(strLine); while(s.hasNext()) { wordList[wordCount] = s.next(); wordCount++; } } 

Now this works fine for less than 100 list items. br.readline is a buffered reader passing through each line of a text file. Then I save each word in the list, and then increase the index (wordCount).

However, as soon as I have a text file with more than 100 elements, I get a selection error.

How can I dynamically update this array (and thereby rethink the wheel)?

Thanks!

Answer 1

You can do something like this:

 String [] wordList; int wordCount = 0; int occurrence = 1; int arraySize = 100; int arrayGrowth = 50; wordList = new String[arraySize]; while ((strLine = br.readLine()) != null) { // Store the content into an array Scanner s = new Scanner(strLine); while(s.hasNext()) { if (wordList.length == wordCount) { // expand list wordList = Arrays.copyOf(wordList, wordList.length + arrayGrowth); } wordList[wordCount] = s.next(); wordCount++; } } 

Using java.util.Arrays.copyOf(String[]) basically does the same thing:

 if (wordList.length == wordCount) { String[] temp = new String[wordList.length + arrayGrowth]; System.arraycopy(wordList, 0, temp, 0, wordList.length); wordList = temp; } 

except for one line of code instead of three. :)

Answer 2

You select a new array (for example, double the capacity) and move all the elements into it.

Basically you need to check if wordCount is going to press wordList.size() when it does, create a new array with double the length of the previous one and copy all the elements into it (create a helper method for this) and assign wordList your new array.

You can use System.arraycopy to copy the content, but I'm not sure if this is allowed with your limitations, so you can just copy the elements one at a time:

 public String[] createNewArray(String[] oldArray){ String[] newArray = new String[oldArray.length * 2]; for(int i = 0; i < oldArray.length; i++) { newArray[i] = oldArray[i]; } return newArray; } 

Proceed.

Answer 3

Take a look at the Java ArrayList implementation. Java ArrayList internally uses a fixed-size array and reallocates the array when the number of elements exceeds the current size. You can also implement similar strings.

Answer 4

you cannot increase the size of an array dynamically better than you copy to a new array . Use System.arrayCopy for this, it is better than copying each element to a new array. For reference Why is System.arraycopy native in Java? .

 private static Object resizeArray (Object oldArray, int newSize) { int oldSize = java.lang.reflect.Array.getLength(oldArray); Class elementType = oldArray.getClass().getComponentType(); Object newArray = java.lang.reflect.Array.newInstance( elementType, newSize); int preserveLength = Math.min(oldSize, newSize); if (preserveLength > 0) System.arraycopy(oldArray, 0, newArray, 0, preserveLength); return newArray; } 

Answer 5

You need to manually create a new larger array and copy the elements.

it can help

Answer 6

Visual Basic has a nice feature: ReDim Preserve .

Someone kindly wrote an equivalent function - you can find it here . I think that he does exactly what you ask for (and you do not reinvent the wheel - you copy someone else's) ...

Answer 7

Let's look at the case when you have an array of 1 element and you want to increase the size to dynamically hold 1 million elements.

Case 1:

 String [] wordList = new String[1]; String [] tmp = new String[wordList.length + 1]; for(int i = 0; i < wordList.length ; i++){ tmp[i] = wordList[i]; } wordList = tmp; 

Case 2 (increase in size with the addition coefficient):

 String [] wordList = new String[1]; String [] tmp = new String[wordList.length + 10]; for(int i = 0; i < wordList.length ; i++){ tmp[i] = wordList[i]; } wordList = tmp; 

Case 3 (increase in size by multiplication factor):

 String [] wordList = new String[1]; String [] tmp = new String[wordList.length * 2]; for(int i = 0; i < wordList.length ; i++){ tmp[i] = wordList[i]; } wordList = tmp; 

When you increase the size of the array dynamically, using Array.copy or iterating over the array and copying the elements to the new array using the for loop, it actually iterates over each element of the array. This is an expensive operation. Array.copy will be clean and optimized, still expensive. So, I would suggest increasing the length of the array by a multiplication factor.

How does that help

In case 1, to place 1 million elements, you need to increase the size of the array 1 million - 1 times, i.e. 999,999 times.

In case 2, you need to increase the size of the array 1 million / 10 - 1 times, that is 99,999 times.

In case 3, you need to increase the size of the array by log ₂ 1 million - 1 times, that is, 18.9 (hypothetically).

Answer 8

 public class Arr { public static void main(String[] args) { // TODO Auto-generated method stub int a[] = {1,2,3}; //let a[] is your original array System.out.println(a[0] + " " + a[1] + " " + a[2]); int b[]; //let b[] is your temporary array with size greater than a[] //I have took 5 b = new int[5]; //now assign all a[] values to b[] for(int i = 0 ; i < a.length ; i ++) b[i] = a[i]; //add next index values to b b[3] = 4; b[4] = 5; //now assign b[] to a[] a = b; //now you can heck that size of an original array increased System.out.println(a[0] + " " + a[1] + " " + a[2] + " " + a[3] + " " + a[4]); } } 

Output for the above code:

1 2 3

1 2 3 4 5