How can we dynamically allocate and grow an array

Question

I am working on a project  but I cannot use any existing java data structures  ie  ArraysList  trees  etc   I can only use arrays  Therefore  I need to dynamically update an array with new memory   I am reading from a text file  and I pre-allocate 100 for the arrays memory      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 under 100 list items  br readline is the buffered reader going through each line of a textfile  I have it then store each word into list and then increment my index  wordCount    However  once I have a text file with more than 100 items  I get an allocation error   How can I dynamically update this array  and thereby sort of reinvent the wheel    Thanks

User · Answer

Lets take a case when you have an array of 1 element, and you want to extend the size to accommodate 1 million elements dynamically.

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 (increasing size by a addition factor):

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 (increasing size by a 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 extending the size of an Array dynamically, using Array.copy or iterating over the array and copying the elements to a new array using the for loop, actually iterates over each element of the array. This is a costly operation. Array.copy would be clean and optimized, still costly. So, I'd suggest increasing the array length by a multiplication factor.

How it helps is,

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

In case 2, you have to increase the size of array 1 million / 10 - 1 times i.e. 99,999 times.

In case 3, you have to increase the size of array by log₂1 million - 1 time i.e. 18.9 (hypothetically).

User · Answer

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    is basically doing the same thing as   if  wordList length    wordCount        String   temp   new String wordList length   arrayGrowth       System arraycopy wordList  0  temp  0  wordList length       wordList   temp      except it is one line of code instead of three

User · Answer

Visual Basic has a nice function   ReDim Preserve   Someone has kindly written an equivalent function - you can find it here  I think it does exactly what you are asking for  and you re not re-inventing the wheel - you re copying someone else s

User · Answer

Take a look at implementation of Java ArrayList  Java ArrayList internally uses a fixed size array and reallocates the array once number of elements exceed current size  You can also implement on similar lines

User · Answer

You allocate a new Array  double the capacity  for instance   and move all elements to it   Basically you need to check if the wordCount is about to hit the wordList size    when it does  create a new array with twice the length of the previous one  and copy all elements to it  create an auxiliary method to do this   and assign wordList to your new array    To copy the contents over  you could use System arraycopy  but I m not sure that s allowed with your restrictions  so you can simply copy the elements one by one   public String   createNewArray String   oldArray       String   newArray   new String oldArray length   2       for int i   0  i  lt  oldArray length  i              newArray i    oldArray i              return newArray      Proceed

User · Answer

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  lt  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 is   1 2 3  1 2 3 4 5

User · Answer

You have to manually create a new bigger array and copy over the items   this may help

User · Answer

you can not increase array size dynamically better you copy into new array  Use System arrayCopy for that  it better than copying each element into 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  gt  0        System arraycopy oldArray  0  newArray  0  preserveLength      return newArray

[java] How can we dynamically allocate and grow an array

Examples related to java

Examples related to arrays

Examples related to word-count