Array

[ile4]

I need to make an array using primitive array so I cannot use the class ArrayList.

At the moment I initialise my array as follows:

array = new new String[100];

But my array will need to hold hundreds of thousands of strings, so is there a way I can make the array of maximum size? Or, to expand its size each time a new word is added?

[JosAH]

I need to make an array using primitive array so I cannot use the class ArrayList.

At the moment I initialise my array as follows:

array = new new String[100];

But my array will need to hold hundreds of thousands of strings, so is there a way I can make the array of maximum size? Or, to expand its size each time a new word is added?

If you're not allowed to use an ArrayList you have to mimic its behaviour: you have to keep track of the number of elements in your array as well as the size of the array; when a new elements needs to be inserted and the array is full, allocate another (larger) array and copy everything over from the old array to the new array; now you can store the new element. How much larger the new array is going to be is crucial: you don't want to waste a lot of memory but you don't want to allocate a new array for every new item to be inserted.

kind regards,

Jos

[ile4]

I see what you mean, but the algorithm we use needs to work in nlogn time so wouldnt this be quite slow to make a new array and copy everything over? Would this run in nlogn time or better?

[JosAH]

I see what you mean, but the algorithm we use needs to work in nlogn time so wouldnt this be quite slow to make a new array and copy everything over? Would this run in nlogn time or better?

Copying an array over to another array takes O(n) steps when the length of the array is n and n < n*log(n). ArrayLists add n/2 elements to the new array, do your math ;-)

kind regards,

Jos

[ile4]

Hmm i don't know what O(n) means i am really new to programming. and i am not very good at maths, for small numbers isnt n > nlogn? So what time format will this work in? :confused:

[JosAH]

Hmm i don't know what O(n) means i am really new to programming. and i am not very good at maths, for small numbers isnt n > nlogn? So what time format will this work in? :confused:

Nope, n < n*log(n); (divide both the left and right sides by n) 1 < log(n); so if we use the 2log( ... ) if n > 2 the relation is true. In your case n is much larger than 2.

kind regards,

Jos

[ile4]

Ah okay, I don't know how to go about coding that. At the moment I have this:

public class MyArray {
    
    private String[] array;
    private int maximum = 10;
    
    public Anagrams () {
        array = new String[maximum];
    }
    
    public void add(String word) {
        for (int i = 0; i < maximum; i++) {
            if (array[i] == null) {
                array[i] = word;
                max++; 
                break;                
            }
        }
    }

So in my for loop would I need to create a new array of size max + 1 (because your adding one word at a time). But how would I go about copying all the words from my old array over to my new array?

[JosAH]

Ah okay, I don't know how to go about coding that. At the moment I have this:

public class MyArray {
    
    private String[] array;
    private int maximum = 10;
    
    public Anagrams () {
        array = new String[maximum];
    }
    
    public void add(String word) {
        for (int i = 0; i < maximum; i++) {
            if (array[i] == null) {
                array[i] = word;
                max++; 
                break;                
            }
        }
    }

So in my for loop would I need to create a new array of size max + 1 (because your adding one word at a time). But how would I go about copying all the words from my old array over to my new array?

Don´t do it like that; fill your array starting from the first element. You should keep track where the first unused element is. If the index of that element equals the size of the entire array, a new array should be allocated and the content of the old array should be copied to the new array. Something like this:

int free= 0; // the first free element
int[] array= new int[SOME_VALUE]; // the array 
...
void add(int element) {
   if (free == array.length) // this array is full
      newArray(); // create a larger one
   array[free++]= element;
}

Now you have to write the newArray() method.

kind regards,

Jos

[ile4]

Thank you for all your help so far, I have written the code. It is now creating a new array each time a new element needs to be added, so it starts off with length 0, then i add a new element and the size is 1, but when i add a second element the size is 2, the second element is in space 2 (well 1) but the first element is gone. So it the code is working how I want it to but in my newArray() method I need to clone the array and I cant figure out how I would do this.
I thought of storing all the elements in a field and then copying them over but the only field that can store multiple values is an array...! So how can I copy the current elements of an array over to a new array?

[JosAH]

Thank you for all your help so far, I have written the code. It is now creating a new array each time a new element needs to be added, so it starts off with length 0, then i add a new element and the size is 1, but when i add a second element the size is 2, the second element is in space 2 (well 1) but the first element is gone. So it the code is working how I want it to but in my newArray() method I need to clone the array and I cant figure out how I would do this.
I thought of storing all the elements in a field and then copying them over but the only field that can store multiple values is an array...! So how can I copy the current elements of an array over to a new array?

For the copying business have a look at the Arrays class or the System class. Both classes have methods for copying entire arrays. Also, if the array is full don't create an array with just room for one more element; that is extremely expensive; I'd create a new array of length 3*n/2 where n is the length of the original array.

kind regards,

Jos

[ile4]

Thank you for your help