Enhanced for loop

Until now, we’ve use out classic counter-based loop to traverse through arrays and lists.

But when you don’t really need the index and just want to use a construct where it says,

“For every item (current) in the collection, use current for something”

This kind of traversal is provided by the enhanced for loop.

Syntax

1
2
3
for(type current: array/list) {
	use current
}

Example with array

1
2
3
4
5
6
int[] data = {10, 70, 20, 90};

int total = 0;
for(int item: data) {
	total = total + item;
}

Example with list

1
2
3
4
5
6
7
8
9
10
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(10);
list.add(70);
list.add(20);
list.add(90);

int total = 0;
for(int item: list) {
	total = total + item;
}

When should I use the enhanced for loop?

Enhanced for loops are used when you don’t need the index for anything besides accessing the item at that index.

Examples of when enhanced for loop should be used

• Finding the sum of all items in array/list
• Finding the sum of all items (that optionally satisfy some condition(s)) in array/list
• Finding the highest/smallest item in an array/list

Examples when it’s better (IMO) to use a counter-based loop

• Checking if array/list is sorted (because you need to compare an item with the item after it, so you need to access items at index i and i+1).
• Finding the location of the highest/smallest item in an array/list.
• Finding if an array/list contains any duplicates.
• Sorting an array/list.
• Performing binary search over a sorted array/list.

Iterator

There is a powerful and consistent way to traverse almost all data structures in Java including lists - Iterator.

The two important methods belonging to Iterator interface are:

1. hasNext(): returns true if there is an item in front of the current position of the iterator.
2. next(): returns the item in front of the current position of the iterator (if any), and moves the iterator forward. Throws NoSuchElementException if the iteration has no more elements.

A class that implements Iterator interface can add other methods too. ListIterator is one such class.

We will focus only on hasNext() and next().

The advantages of using an iterator are,

1. It’s consistent across any class that implements the Iterator interface.
2. It’s intuitive as in “while the collection has another item, access it”.

Creating and using a ListIterator on a List object

A ListIterator iter is created on a List object list as:

1
ListIterator<Integer> iter = list.listIterator();

Assuming the list is [10, 70, 20, 90, 30, 80], the initial state of iter is represented by the red block.

You can check if there is an item in front of the current position of the iterator as:

1
boolean itemExists = iter.hasNext();

Once you check an item exists, you can access it as:

1
Object item = iter.next();

This (accessing an item) results in the iterator moving forward by one.

Complete example

1
2
3
4
5
6
ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(10, 70, 20, 90, 30, 80));
ListIterator<Integer> iter = list.listIterator();
while(iter.hasNext()) {
  System.out.print(iter.next()+" ");
}
//displays 10 70 20 90 80 30

Initial state

After first iteration

After second iteration

After third iteration

After fourth iteration

After fifth iteration

After sixth iteration

Starting from a specific index

You can pass the index of the item BEFORE which you want the iterator to be placed.

Assuming ArrayList list holds the values [10, 70, 20, 90], the following code will display 20 90.

1
2
3
4
ListIterator<Integer> iter = list.listIterator(2);
while(iter.hasNext()) {
	System.out.print(iter.next()+" ");
}

Back to front iteration

Just like hasNext() and next(), the methods hasPrevious() and previous() also exist.

You can traverse a list from back to front as:

1
2
3
4
ListIterator<Integer> iter = list.listIterator(list.size());
while(iter.hasPrevious()) {
	System.out.print(iter.previous()+" ");
}

Assuming ArrayList list holds the values [10, 70, 20, 90], the following code will display 20 70 10.

1
2
3
4
ListIterator<Integer> iter = list.listIterator(3);
while(iter.hasPrevious()) {
	System.out.print(iter.previous()+" ");
}

Custom-built arraylist

In this chapter, we’ll see how an arraylist holds items and how to implement it.

NOTE! The built-in class for ArrayList in Java holds a collection of objects, not primitive data type, but in our example, we’ll create a collection of double items, for simplicity.

What an ArrayList class looks like

The ArrayList class has an instance variable array that holds the items. If, at the time of triying to add an item, the array is full, then:

1. a bigger array is created,
2. items from the instance variable array are copied over
3. instance variable array is re-referenced to refer to the new, bigger array

Let’s create one such class holding an array of doubles

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class MyArrayList {
	private double[] data;
	private int nItems;

	public MyArrayList() {
		data = new double[5];
		nItems = 0; //no item added yet
	}

	public void add(double itemToAdd) { //THERE IS A PROBLEM HERE
		data[nItems] = itemToAdd;
		nItems++;
	}
}

The client can create an object of class MyArrayList as:

1
2
3
4
5
6
MyArrayList list = new MyArrayList();
list.add(10);
list.add(70);
list.add(20);
list.add(90);
list.add(30);

Five items were added to the list, which is ok. But as soon as you try to add a sixth item using,

1
list.add(80);

The method add will cause,

1
data[5] = 80; //ArrayIndexOutOfBoundsException

Therefore, we must first check if the internal array is full.

1
2
3
4
5
6
7
8
9
//inside class MyArrayList
public boolean isFull() {
	if(nItems == data.length) {
		return true;
	}
	else {
		return false;
	}
}

The method add should be modified as,

1
2
3
4
5
6
7
8
//inside class MyArrayList
public void add(double itemToAdd) {
	if(isFull()) {
		???
	}
	data[nItems] = itemToAdd;
	nItems++;
}

If the internal array is full,

1. a bigger array is created,
2. items from the instance variable array are copied over
3. instance variable array is re-referenced to refer to the new, bigger array

These steps are performed in a method grow().

1
2
3
4
5
6
7
8
9
public void grow() {
	double[] temp = new double[data.length + 5]; //5 extra items

	for(int i=0; i < data.length; i++) { //copy all items over
		temp[i] = data[i];
	}

	data = temp; //make instance variable array refer to the bigger array
}

Updated class definition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class MyArrayList {
	private double[] data;
	private int nItems;

	public MyArrayList() {
		data = new double[5];
		nItems = 0; //no item added yet
	}

	public boolean isFull() {
		if(nItems == data.length)
			return true;
		else
			return false;
	}

	private void grow() { //should not be called by outside code
		double[] temp = new double[data.length + 5]; //5 extra items

		for(int i=0; i < data.length; i++) { //copy all items over
			temp[i] = data[i];
		}

		data = temp; //make instance variable array refer to the bigger array
	}

	public void add(double itemToAdd) {
		if(isFull()) {
			grow();
		}
		data[nItems] = itemToAdd;
		nItems++;
	}
}

Method to add an item at an arbitrary index

Say, the list contains items [12.5, 6.4, 8.5, 9.6, -3.4] and we want to add an item 16.42 at index 0. All items in the array need to move forward by 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean add(int idx, double itemToAdd) {
	if(idx < 0 || idx > nItems) {
		return false; //to indicate failure
	}

	if(isFull()) {
		grow();
	}
	for(int i=nItems - 1; i >= idx; i--) {
		data[i+1] = data[i];
	}

	data[idx] = itemToAdd;
	nItems++;

	return true; //to indicate success
}

Method to remove an item from an arbitrary index

Say, the list contains items [12.5, 6.4, 8.5, 9.6, -3.4] and we want to remove the item at index 0. All items in the array need to move backward by 1.

The method should return the item removed.

If we keep the return type as double, what do we return if the index is invalid and therefore no item exists at that index?

Hence, we keep the return type Double since we can return null as error code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public Double remove(int idx) {
	if(idx < 0 || idx >= nItems) {
		return null; //error code
	}

	double itemToRemove = data[idx];

	for(int i= idx; i < nItems - 1; i++) {
		data[i] = data[i+1];
	}
	nItems--;

	return itemRemoved; //can return double variable as Double
}

Complete class and client (including homework)

• MyArrayList.java (contains several incomplete methods for practice)
• MyArrayListClient.java

Homework tasks

1. Percentage used

Add an instance method percentageUsed that returns the percentage of the instance array being used. For example, if data.length = 15 and nItems = 12, method returns the value 80.0.

2. indexOf

Add an instance method indexOf that when passed a double, returns the index of the first occurrence of the item. Return -1 if item doesn’t exist. Method header is:

1
public int indexOf(double target)

3. lastIndexOf

Add an instance method lastIndexOf that when passed a double, returns the index of the last occurrence of the item. Return -1 if item doesn’t exist. Method header is:

1
public int lastIndexOf(double target)

4. isValidIndex

Add an instance method isValidIndex that when passed an int (index), returns true if the index is valid, and false otherwise. Method header is:

1
public boolean isValidIndex(int index)

For example, if nItems = 7, indices from 0 to 6 (inclusive on both sides) are valid, and all other indices are invalid.

5. set

Add an instance method set that when passed an int (index) and a double (updated value), sets the item at given index (if within range) to the updated value and returns true. If the index is invalid, return false. Method header is:

1
public boolean set(int index, double updated)

6. Modified growth

Modify the method grow such that the array grows only if full. If the array is not full, it should not grow. Original method (that grows the array irresepective of being full or not) provided below:

1
2
3
4
5
6
7
8
9
public void grow() {
	double[] temp = new double[data.length + 5]; //5 extra items

	for(int i=0; i < data.length; i++) { //copy all items over
		temp[i] = data[i];
	}

	data = temp; //make instance variable array refer to the bigger array
}

7. Remove an item

Add an instance method remove that when passed a double, removes the first occurrence of the item from the list (if any). The method should return true if there was an instance of the item that was removed, and false if there was no instance of the item in the list. Method header is:

1
public boolean remove(double itemToRemove)

8. Remove all

Add an instance method removeAll that when passed a double, removes all occurrences of the item from the list. You can use the method remove already implemented. The method should return true if there was an instance of the item that was removed, and false if there was no instance of the item in the list. Method header is:

1
public boolean removeAll(double itemToRemove)

Array-based lists operation analysis

At the end of the day, an array-based list is an array. In this section, we’ll take a look at the three core operations on arrays:

1. accessing at item at a given index
2. adding an item at a given index
3. removing an item from a given index

Accessing an item at a given index

We need to understand how an array is stored to understand how array items are accessed.

An array is stored as a contiguous block of memory. So, if you have 100 items, you need a block of 400 bytes (given each integer is 4 bytes).

As an example, if there is an array of 6 integers, 24 bytes are reserved (4 per integer). The first item is stored in the first four bytes, the second item in the next four bytes and so on.

Thus,

• The address of the first item (at index 0) is the base address of the array (in this example, 600).
• The address of the second item (at index 1) is the base address of the array + 4 bytes.
• The address of the third item (at index 2) is the base address of the array + 2 * 4 bytes.
• …

• The address of the last item (at index 5) is:

  base address of the array + 5 * 4 bytes.

With a little tweak we can see:

• Address(data[0]) = baseAddress + 0 * 4
• Address(data[1]) = baseAddress + 1 * 4
• Address(data[2]) = baseAddress + 2 * 4
• …
• Address(data[data.length - 1]) = baseAddress + (data.length - 1) * 4

Putting it all together,

(address of item at index idx) = (base address of array) + (size of each item) * (idx);

This means, irrespective of the index accessed, it takes the same time to return an item. A sample table illustrating time taken against index is provided below. In this, x is the amount of time taken and could be any value more than 0.

If you plot a chart with index on x-axis and time taken on y-axis, you’ll get a (near) flat-line. We can this O(1) operation in terms of time complexity (but don’t stress, we will teach the formal terminology in subsequent units).

Example: Accessing an item

Let’s say we want to access data[3] in the following statement:

1
int item = data[3];

We start off with the reference held by data and getting the base address (600).

To that, we add 3 * 4 = 12 (3 being the index and 4 being size of each item), giving us the starting address of the item 612.

We grab 4 bytes starting at that address (so bytes 612 to 615) and present it packed as an integer: 90.

Growing the array

The grow method is as follows:

1
2
3
4
5
6
7
private void grow() { 
	double[] temp = new double[data.length + 5]; 
	for(int i=0; i < data.length; i++) { 			temp[i] = data[i];
	}

	data = temp; 	
}

The key operation in this method is the loop that iterates data.length number of times. The following table summarizes the time behaviour of the loop.

A chart plotted for this with current size on x-axis and time taken on y-axis would yield a straight (rising) line. We call this O(n) operation in terms of time complexity.

Inserting an item at a given index

There are four cases for inserting an item:

1. Array is not full and you are inserting an item at the end of the array: None of items need to be moved, array doesn’t need to be grown. This requires a fixed number of operations, irrespective of the current state of the array and hence O(1) operation.

2. Array is full and you are inserting an item at the end of the array: None of items need to be moved but array needs to be grown. Growing the array is O(n). Therefore, this is an O(n) scenario.

3. Array is not full but you are inserting an item somewhere (not at the end): Some items need to be moved but array doesn’t need to be grown. The worst case is when you are adding an item at index 0, in which case all items need to move, which is O(n). Therefore, this is also an O(n) scenario.

   For example, if there are 5 items currently being used in an array of size 8, and we try to insert an item 5.6 at index 0, all 5 items need to be moved forward.

These shifts are illustrated in the following diagram:

1. Array is full and you are inserting an item somewhere (not at the end): Double whammy, but O(n) + O(n) is still O(n), just the straight line is steeper.

Removing at item at a given index

There are two relevant cases for removing an item:

1. Best case: removing the last item: No items need to be moved. O(1).

2. Worst case: Removing the first item: All the items need to be moved. O(n) because of the loop that needs to iterate over each item.

   For example, if there are 5 items currently being used in an array of size 8, and we try to remove the first item, all 5 items need to be moved backward by one.

These shifts are illustrated in the following diagram:

Homework exercises

1. Explain the calculations performed during calculating the address of data[6] if the base address is 4000 and the array is of type double[]. Each double variable needs 8 bytes of memory.

2. Explain the calculations performed during calculating the address of data[40] if the base address is 3000 and the array is of type char[]. Each char variable needs 2 bytes of memory.

3. Consider an array data = {10, 70, 20, 90, 30, 80, 60}. Explain, with the help of a diagram, the shifts involved while removing the item 70.

4. Consider an array data = {10, 70, 20, 90, 30, 80, 60}. Explain, with the help of a diagram, the shifts involved during the process of adding the item 30 at index 1.