shiqidai1002 / javapractice Goto Github PK

My teacher George asked me to write some codes to create an array object that can automatically expand.

Yesterday, when I was driving, an idea came to my mind regarding how to realize the function of automatic extension.
My way is creating a new larger array each time before users add a new item, then copy each item from current array to the new one and return the newly finished larger array, waiting for adding the new item.

Here are my original codes:

public void add(String value){
                data = autoExpand(currentIndex);
		data[currentIndex] = value;
		currentIndex ++;
	}
	private String[] autoExpand(int currentIndex){
		String[] data2 = new String[defaultSize + initialSize + currentIndex + 1];
		for (int i = 0; i < data.length; i++){
			data2[i] = data[i];
		}
		return data2;
	}

Later, George taught me some knowledge about the mechanisms of computer memory and program's running speed. I recognized the problem of my solution---each time users adding a new item to the array, my solution always create a new larger array, which needs the computer find new space from the memory. However, the spaces occupied by previously abandoned arrays are not going to be released as quickly as new ones demand. That will cause some problems.

So, George advised me a new way to solve this. Here are the codes I wrote:

public void add(String value){
		//check occupation
		if(currentIndex == data.length)
			data = autoExpand(currentIndex);
		//add new item
		data[currentIndex] = value;
		currentIndex ++;
	}	
	private String[] autoExpand(int currentIndex){
		String[] data2 = new String[currentIndex * 2];
		for (int i = 0; i < data.length; i++){
			data2[i] = data[i];
		}
		return data2;
	}

I added a "check occupation" part before we add a new item based on George's suggestion. When the currentIndex equals to data.length, that means our current array is full. At this time, we call the autoExpand() method.

As for the autoExpand() method, previously, I set the new size to "defaultSize + initialSize + currentIndex + 1". I was thinking that to add one more space for each time can save more computing resource. However, after George's tutoring, I have learned that was wrong. So, the later codes indicated that the expanded size was set to "currentIndex * 2". As my teacher's mention, this is more efficient!

When I was lying in the bed few minutes before, I was thinking about the test file--TestInfiniteArray.java. Here show the codes:

public class TestInfiniteArray {
	public static void main(String[] args){
		InfiniteArray list = new InfiniteArray();
		System.out.println(list.size());
		list.add("lmao");
		list.add("things");
		list.add("omg");
		list.add("Don't listen to girls who say they will die for you. Fried chicken actually died for you. Fried chicken is love.");
		System.out.println(list.get(3)); // Should print the "Don't listen...." entry
		for ( int x = 0; x < 1000; x++ ) {
			list.add("load test" + " " + x);
		}
		System.out.println(list.get(666));
		list.set(0, "Deus Vult"); // should set "lmao" to "Deus Vult"
		System.out.println(list.get(0));
		System.out.println(list.size());
	}
}

In the end of the codes, I let the system show me the size of my InifiniteArray and the result was 1200+. I was thinking why it showed me 1200+, because I've set the auto-expanded size to the currentIndex * 2. And when I did the "load test" 1000 times in the test file, the currentIndex should be like 1000+, which means the auto-expanded size should be 2000+. However, soon, I found I was wrong. The result of size() method, 1200+, came from when the currentIndex was 600+. Since that time, our InfiniteArray had been auto-expanded to 1200+ and it had never been filled up! At this moment, I found the magic of this solution! The larger the size of InfiniteArray, the fewer times we need to create new arrays, which can remarkably improve the efficiency of our program!

So I decided to not sleeping anymore and to write it down.

This one is pretty easy though.

1. Take a look at this java doc: https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html
   1.5. (If you have trouble understanding that one, try reading this one instead: https://www.tutorialspoint.com/java/java_arraylist_class.htm )
2. Rewrite the test program using Java's built in ArrayList class, but keep the functionality of each line exactly the same.