Why are arrays not good enough?

Example - copying over a subset

Consider an array src holding 100 integers. Some negative, some positive. We need to copy all negative items over to a new array dest.

As an example, if

src is {10, 20, 50, 0, -40, 30, 90, 60, -10, -50, 80}

dest should be {-40, -10, -50}

In order to do this, we need to,

1. Count the number of required (negative) values in the array src
2. Create an array dest of that size
3. Copy items over to dest.

Step 1

1
2
3
4
5
6
int count = 0;
for(int i=0; i < src.length; i++) {
	if(src[i] < 0) {
		count++;
	}
}

Step 2

1
int[] dest = new int[count];

Step 3

We are copying,

src[4] into dest[0]

src[8] into dest[1]

src[9] into dest[2]

So, in addition to the current index of src, we also need to keep track of the current index of dest into which the item must be copied.

1
2
3
4
5
6
7
int idx = 0; //index where item must be copied
for(int i=0; i < src.length; i++) {
	if(src[i] < 0) {
		dest[idx] = src[i]; //another item copied
		idx++; //move destination index forward
	}
}

Final solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int count = 0;
for(int i=0; i < src.length; i++) {
	if(src[i] < 0) {
		count++;
	}
}

int[] dest = new int[count];

int idx = 0; //index where item must be copied

for(int i=0; i < src.length; i++) {
	if(src[i] < 0) {
		dest[idx] = src[i]; //another item copied
		idx++; //move destination index forward
	}
}

Solution using List (just focus on how easy and intuitive it is)

A solution to the same problem when src and dest are lists instead of arrays is,

1
2
3
4
5
6
ArrayList<Integer> dest = new ArrayList();
for(int item: src) {
	if(item < 0) {
		dest.add(item);
	}
}

I KNOW!