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!

I think the fastest solution would be to count the lines in the input file (wc -l filename in 'nix) and allocate the array to the right size first time. All this copying is much slower than rewinding the file and reading it twice... — Floris
– Floris, Commented Feb 12, 2013 at 16:36

Ted Hopp · Accepted Answer · 2013-02-12 16:34:13Z

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. :)

pcalcao · Accepted Answer · 2013-02-12 16:31:48Z

5

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 < oldArray.length; i++) {
        newArray[i] = oldArray[i];
    }

    return newArray;
}

Proceed.

answered Feb 12, 2013 at 16:31

pcalcao

16k1 gold badge49 silver badges65 bronze badges

2 Comments

Ted Hopp Over a year ago

Or you could just use array = Arrays.copyOf(array, newLength).

pcalcao Over a year ago

Yes, I know that. Like I said, that suggestion is stated in case he cannot use the builtin methods... the same way he cannot use an ArrayList, etc.

MoveFast · Accepted Answer · 2013-02-12 16:35:01Z

3

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.

answered Feb 12, 2013 at 16:35

MoveFast

3,0253 gold badges30 silver badges54 bronze badges

1 Comment

Ted Hopp Over a year ago

Or just use array = Arrays.copyOf(array, newLength).

Community · Accepted Answer · 2017-05-23 12:17:33Z

3

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 > 0)
      System.arraycopy(oldArray, 0, newArray, 0, preserveLength);
   return newArray;
}

edited May 23, 2017 at 12:17

CommunityBot

11 silver badge

answered Feb 12, 2013 at 16:33

Subhrajyoti Majumder

41.3k13 gold badges84 silver badges103 bronze badges

5 Comments

Ted Hopp Over a year ago

Or you could just use array = Arrays.copyOf(array, newLength).

Brian Roach Over a year ago

Sure ... if you consider a bad re-implementation of a standard library method "the same".

Subhrajyoti Majumder Over a year ago

@BrianRoach I hope you checked the library implementation, what do you mean bad implementation? could you please be specific.

Brian Roach Over a year ago

Exactly that. You re-invented the wheel (unnecessary) and made it so explicit casts are required.

Brian Roach Over a year ago

I'm not saying it doesn't have value showing the OP how it works, just that the right answer is to use the standard library (and maybe change your example to use generics)

Community · Accepted Answer · 2017-05-23 12:32:27Z

0

You have to manually create a new bigger array and copy over the items.

this may help

edited May 23, 2017 at 12:32

CommunityBot

11 silver badge

answered Feb 12, 2013 at 16:33

Massimiliano Peluso

26.8k6 gold badges65 silver badges75 bronze badges

Comments

Floris · Accepted Answer · 2013-02-12 16:34:28Z

0

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)...

answered Feb 12, 2013 at 16:34

Floris

46.6k7 gold badges73 silver badges128 bronze badges

Comments

Ashwin Aggarwal · Accepted Answer · 2016-02-10 16:05:24Z

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).

Aitha Ranjeeth · Accepted Answer · 2017-09-15 14:23:19Z

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 is:

1 2 3

1 2 3 4 5

Collectives™ on Stack Overflow

How can we dynamically allocate and grow an array

8 Answers 8

Comments

2 Comments

1 Comment

5 Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

8 Answers 8

Comments

2 Comments

1 Comment

5 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related