Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Java Tutorial: How to use the Arrays utility to make your arrays more dynamic

array

  • Please log in to reply
4 replies to this topic

#1 Chall

Chall

    CC Addict

  • Senior Member
  • PipPipPipPipPip
  • 349 posts
  • Location:Cedar Rapids, IA
  • Programming Language:Java
  • Learning:C, Java, C++, C#, Python, JavaScript, Assembly

Posted 07 October 2012 - 05:33 PM

Introduction


Have you ever been angry when you wanted to store data in an array, but never knew exactly how big to make it? This is quite common, especially when gathering information from a source or sources that may vary. If you have this problem, you should make your own "array" type that allows the array to expand or contract, depending on what is required.






Getting started


For this tutorial, I am going to guide you step by step on how to make your own dynamic array type. I am going to assume that you already know quite a bit about Java, such as flow control, data types, and how to make/create objects. Since you are going to be making your own, I recommend making a new file, and calling it DynamicArray. Since our class is going to be a type, we do not need to mess with the main method. To start out, you should make a code skeleton with the name DynamicArray, and the methods add(Object value), set(int index, Object value), setLength(int newLength), our getter get(int index), and possibly new(int newLength). Your code should look something like this:
public class DynamicArray {

public void add(Object value){

}

public void set(int index, Object value){

}

public void setLength(int newLength){

}

public Object get(int index){

}

public DynamicArray(int length){ // Optional, recommended though

}
}

With that, you should now add this to the imports:
import java.util.Arrays;
If you don't know where to add imports, you add them before you declare the class. You should also add an internal, private array to work with. Call it array, and make it of type Object, as I won't get into generics in this tutorial, and we want it to be able to contain any object. You should have this:
import java.util.Arrays;

public class DynamicArray {


private Object[] array = new Object[0]; // Making it of length zero, as it will expand if needed.

public void add(Object value){

}

public void set(int index, Object value){

}

public void setLength(int newLength){

}

public Object get(int index){

}

public DynamicArray(int length){ // Optional, recommended though
	 array = new Object[length]; // If you wanted.
}
}

Congrats! You now have the framework of your new DynamicArray type! Now it is time to add all the required functions.

To start, lets make our add method. We want it to add the value it has to the first possible slot in the array, so we will make it iterate over the array in search of a null value. If the array doesn't have a null value (empty slot), then we will add one using our setLength method. It should look something like this, ignore the comments:
public void add(Object value){
	 for(int i = 0; i < array.length; i++){ // int i = 0; if i is less than the length of array (our array), then increase i by one each time it loops around.
		 if(array[i] == null){ // If there is nothing inside the slot of "i", then do...
			 array[i] = value; // Set the slot of "i" in array to the desired value.
			 return; // Blank return, because there is no reason to continue, we already added the value.
		 }
	 }
	 setLength(array.length + 1); // Extend the length of the array one slot, using our method setLength(int).
	 array[array.length - 1] = value; // Set the final slot of array to value.
}
*Please note that with the add method, an alternative way to do the same process but faster would be to instantiate a variable in the body of the class, and then use it to store the index of the last known addition added so that when you used the add method, instead of looping through all the indexes, you could skip to the last known one. Also, instead of increasing the array size by one every time, you could just increase by a bigger number, and then let the add method use up the spaces before using the Arrays.copyOfRange, which has to create a new array each time. This would be faster, but it could be slightly less memory effective.*

Now that we have our main setter method, we should add the "internal" setter, to change values of a slot that might already contain something. We want it to over write whatever might already be in that slot, and only increase the size of array if that slot is non existant. You should get something like this, again, disregard the comments if necessary:
public void set(int index, Object value){
	 if(index< array.length && index >= 0){ // Make sure the slot already exists beforehand.
		 array[index] = value; // Set the value.
	 } else if( index < 0){
		 System.err.println(" Impossible index! Arrays cannot contain negative indexes! Your index is "+index); // Use the error stream to create print a message that tells user that that index is not possible because it is negative
	 } else if( index >= array.length){ // If array is to small for the index
		 setLength(index+1); // Set the length of the array to whatever index is, + 1 (because the length is 1 greater than the actual slots indexes).
		 array[index] = value; // Set the value.
	 }
}

Now that we have our setters, since both setters use the same method, why not define setLength next? We want setLength to copy all of the data in the current array into the same array, but with a new size. So it will maintain the old data, but make it a new length. We also want to make sure that the new length is not negative. You should get this, excluding comments:
public void setLength(int newLength){
	 if(newLength>=0){
		 array = Arrays.copyOfRange(array, 0, newLength); // Use the method copyOfRange in Arrays to create a new array of the same data, but a new length.
		 // copyOfRange uses the parameters (Ojbect anArray, int copyDataFrom, int copyDataTo).
	 } else {
		 System.err.println("Impossible length! Arrays cannot be negative! Trying to make it of length "+newLength);
	 }
}

Hooray! We're almost done! Now we just need a getter, so we can retrieve data from out array. We want the getter to return data from our array using an index provided in the parameters. If it doesn't exist, we are going to return null (nothing) because nothing is there. You could make it grow bigger at this point, but it is not needed for basic use. You should get this, excluding comments:
public Object get(int index){
	 if(index < array.length && index >= 0){ // Check and make sure index exists.
		 return array[index]; // Return the value at that index.
	 }
	 return null; // Return nothing. You might want the program to print an error message here telling the user why he is getting a null value.
}

Congrats! You have completed your dynamic array type! You should have this:

import java.util.Arrays;

public class DynamicArray {
private Object[] array = new Object[0];

public void add(Object value){
	 for(int i = 0; i < array.length; i++){
		 if(array[i] == null){
			 array[i] = value;
			 return;
		 }
	 }
	 setLength(array.length + 1);
	 array[array.length - 1] = value;
}

public void set(int index, Object value){
	 if(index< array.length && index >= 0){
	 array[index] = value;
	 } else if( index < 0){
		 System.err.println(" Impossible index! Arrays cannot contain negative indexes! Your index is "+index);
} else if( index >= array.length){
	 setLength(index+1);
	 array[index] = value;
}
}

public void setLength(int newLength){
	 if(newLength>=0){
		 array = Arrays.copyOfRange(array, 0, newLength);
	 } else {
		 System.err.println("Impossible length! Arrays cannot be negative! Trying to make it of length "+newLength);
	 }
}

public Object get(int index){
	 if(index < array.length && index >= 0){
		 return array[index];
	 }
	 return null;
}

public DynamicArray(int length){
	 array = new Object[length];
}
}

You should consider adding a getSize method, and possibly adding generics, but I will leave that to you, as you should be able to do that on your own. ;)

To use a copy of our DynamicArray, you would create a new one with DynamicArray name = new DynamicArray(); //Include a length inside parenthisis if you added a constructer to the class.

To add a new value, you would use add(value). To add or change an existing slot, you would use set(slot, value). To change the size manually, you would use setLength(newLength). To get a value, you would use get(index).

I hope this tutorial helped you, and please inform me if I made a mistake, or got my information wrong. Thanks for reading,
~Chall
  • 0
Speaks fluent Java

#2 Raindeer

Raindeer

    CC Lurker

  • New Member
  • Pip
  • 3 posts
  • Programming Language:Java, Lua
  • Learning:Java

Posted 16 October 2012 - 09:05 AM

Nice idea! Can you set the values to anything? Like images, integers, floats, strings and such? Also is it possible to add another array in it?
  • 0

#3 Chall

Chall

    CC Addict

  • Senior Member
  • PipPipPipPipPip
  • 349 posts
  • Location:Cedar Rapids, IA
  • Programming Language:Java
  • Learning:C, Java, C++, C#, Python, JavaScript, Assembly

Posted 16 October 2012 - 12:39 PM

You can make the array of any type you want, but I'm not sure about multi-dimensional arrays. I've tried it before, but I never could get it to work. I'm sure there is some way though. It's probably not possible (normally) because the copyOfRange() only accepts any value that is an array with 1 dimension.
  • 0
Speaks fluent Java

#4 lethalwire

lethalwire

    while(false){ ... }

  • Senior Member
  • PipPipPipPipPipPip
  • 766 posts
  • Programming Language:C, Java, PHP, JavaScript
  • Learning:PHP

Posted 16 October 2012 - 01:09 PM

Firstly, thanks for contributing this to the CC tutorial database. This is an informative way to teach programmers to create something similar to the ArrayList class and to realize how the ArrayList class works internally.
There are a couple of things I'd like to point out though.

The first:
In the case where you have an initial array of size 5 and you want to add 20 elements; then it becomes rather inefficient once you start adding the 5th, 6th, 7th, ..., i-th elements.
Once you begin to add these elements, you're increasing the size of the array by 1, but behind the scenes you're also creating a new array and copying n elements to the new array.
So by the time it's all said and done (once you've added the 20 elements), you've created and copied 15 arrays.

A solution to this would be to increase the size of your array by 5, 10, 10%, or whatever when it is full (instead of by 1). You may be losing a little more space, but at the cost of all the overhead you may get when creating/copying 15 arrays.

The second:
Your add method runs in linear time. (It takes n units of time to insert 1 element where n is the size of your array)

This can easily be fixed by adding an instance variable that keeps track of the current index of the last element you've inserted.
Think of the instance variable as a pointer to the next empty position in the array.

So if you've added 5 elements, your instance variable will hold the number 6 (or 5 in this case because indices start with 0).
With this, your add method runs in constant time except when you must increase the size of the array.
  • 0

#5 Chall

Chall

    CC Addict

  • Senior Member
  • PipPipPipPipPip
  • 349 posts
  • Location:Cedar Rapids, IA
  • Programming Language:Java
  • Learning:C, Java, C++, C#, Python, JavaScript, Assembly

Posted 16 October 2012 - 07:21 PM

Firstly, thanks for contributing this to the CC tutorial database. This is an informative way to teach programmers to create something similar to the ArrayList class and to realize how the ArrayList class works internally.
There are a couple of things I'd like to point out though.

The first:
In the case where you have an initial array of size 5 and you want to add 20 elements; then it becomes rather inefficient once you start adding the 5th, 6th, 7th, ..., i-th elements.
Once you begin to add these elements, you're increasing the size of the array by 1, but behind the scenes you're also creating a new array and copying n elements to the new array.
So by the time it's all said and done (once you've added the 20 elements), you've created and copied 15 arrays.

A solution to this would be to increase the size of your array by 5, 10, 10%, or whatever when it is full (instead of by 1). You may be losing a little more space, but at the cost of all the overhead you may get when creating/copying 15 arrays.

The second:
Your add method runs in linear time. (It takes n units of time to insert 1 element where n is the size of your array)

This can easily be fixed by adding an instance variable that keeps track of the current index of the last element you've inserted.
Think of the instance variable as a pointer to the next empty position in the array.

So if you've added 5 elements, your instance variable will hold the number 6 (or 5 in this case because indices start with 0).
With this, your add method runs in constant time except when you must increase the size of the array.

Thanks, adding your advice to the tutorial :)
  • 0
Speaks fluent Java





Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download