I have to find dynamic array using in java. I know I can use ArrayList or List but i cant use them now, I really made an effort about finding this, but i couldn't find how to use non static(dynamic) array without Collections, thanks
4
-
2Why do you need to create a dynamic array? Why can't you use collections? What are you trying to do? How are you failing?npinti– npinti2012-04-03 06:02:03 +00:00Commented Apr 3, 2012 at 6:02
-
It is my project and I cope with this about 6 days and still i cant find how to create dynamic array without collections, just collections are prohibitedengineer– engineer2012-04-03 06:07:28 +00:00Commented Apr 3, 2012 at 6:07
-
If you can't use collections, you will have to either create an array each time you add something, like suggested below, or else, create a very large array the first time and keep adding stuff to it. If I where you I would go with the first choice.npinti– npinti2012-04-03 06:09:15 +00:00Commented Apr 3, 2012 at 6:09
-
you just see the source code of arraylist and understandBalaswamy Vaddeman– Balaswamy Vaddeman2012-04-03 06:13:30 +00:00Commented Apr 3, 2012 at 6:13
Add a comment
|
7 Answers
Arrays have fixed length in Java. There's no way around that.
If you want to add an N:th element to an array, arr with length N-1 then you'll have to
- Create a new array.
- Copy over the content of the old array to the new array
- Replace all references to the old array with references to the new on.
In code these steps correspond to
int[] newArr = new int[N];
System.arraycopy(arr, 0, newArr, 0, arr.length);
arr = newArr;
or, slightly shorter by using Arrays.copyOf from Java 6:
int[] newArr = Arrays.copyOf(arr, N);
arr = newArr;
7 Comments
engineer
It provides dynamic array using?
aioobe
No. It replaces the old array with a new array which is longer. There's no such thing as a dynamic array in Java. If you are prevented to use the Collections API, then I suggest you write your own list class that provides this functionality.
engineer
"own list class" can you brief this? I really new in java also
engineer
sorry but in this examples they have used static variable but i cant use them
|
Normal arrays in Java are not dynamic, so when you want to change the size of the array, you need to create a new one and copy the content of the previous one into it.
You can do that using Arrays#copyOf method to create and copy it in a simple way:
int[] myNewIntArray = Arrays.copyOf(oldIntArray, newArraySize);
You can implement your own dynamic array. Create an array of size 1 (or n if an initial size is provided), then double the size and copy existing elements once it reaches the capacity.
And this is going to have an amortized cost of 3 per operation, 3n for n elements, meaning you can maintain that in o(n) time.
A very simple naive implementation (for int array) would be:
class DynamicIntArray
{
private int capacity;
private int[] array;
private int size = 0;
public DynamicIntArray()
{
this(1);
}
public DynamicIntArray(int capacity)
{
this.capacity = capacity;
array = new int[this.capacity];
}
public void add(int a)
{
if (size == capacity)
resize();
array[size] = a;
size++;
}
private void resize()
{
capacity *= 2;
array = Arrays.copyOf(array, capacity);
}
// Implement the rest
}
Here is how you would use it:
DynamicIntArray dynamicArray = new DynamicIntArray();
dynamicArray.add(1);
dynamicArray.add(2);
dynamicArray.add(3);
If you change it to use generics you can use it for anything, not just integers.
19 Comments
engineer
how can use this ? It needs Static variable?
engineer
why did you use resize with (*2)? i cant understand thats why i am asking sorry
n0rmzzz
This is how I'm told in the algorithms class ;-) I think Java's ArrayList also does it. The key idea is to do less frequent copying when the array gets really big. You wouldn't mind copying on 1, 2, 4, 8, 16, etc. but you don't want this happening once you have 1000000 items every time you chuck in 10 more elements.
engineer
yes it is logical:-) so when i add new item to array it do this in same time?
engineer
class BookArrayBean { private int capacity; private Book[] array; private int size = 0; public BookArrayBean() { this(1); } public BookArrayBean(int capacity) { this.capacity = capacity; array = new Book[this.capacity]; } public void add(Book a) { if (size == capacity) resize(); array[size] = a; size++; } private void resize() { capacity *= 2; array = Arrays.copyOf(array, capacity); } // Implement the rest }
|
You just allocate them like this:
int[] array = new int[17];
1 Comment
vidstige
another terminology is used within c, this hinted me that OP came from a c background and just wanted to allocate an array.
You could use a Collection until the type array is needed and then get your array by using Collection.toArray() function.
Comments
You could mimick dynamic behaviour by creating a new array when it is close to getting full e.g., create a new array with twice the length of the original array, and copy all the elements over.
Comments
I think you would get even better answers if you explain what you are trying to do and why you can't/won't user Collections. What exactly is the problem you are trying to solve?
