Collections in Java(1)

Posted on |

In this series, we will discuss the Java Collections Framework.

In Java, we have a Collection interface extended by other interfaces such as List, Set, and Queue. We also have a Map interface. The Map does not extend the Collection interface because it stores key-value pairs, and the classes that come under the Collection interface store only values.

Collection vs. Collections

  • A Collection is an interface, whereas Collections is a class.
  • A Collection interface provides the standard functionality of a data structure to List, Set, and Queue. However, the Collections class provides the utility methods that can be used to search, sort, and synchronize collection elements.

List in Java: ArrayList

ArrayList is an list based on array. Some of the salient features of an ArrayList are:

  • Elements are stored in the order of insertion.
  • It allows the storage of duplicate elements.
  • ArrayList also supports null elements.

An ArrayList stores data in a resizable array. After Java 8, when an ArrayList is created, an array of size zero is created. Only when the first element is inserted does the array size change to ten. This is called lazy initialization, and it saves a lot of memory.

In CS61B, we've discussed resizing an array in lecture 7, and also implemented it in project 1. The strategy we used is doubling the length. In real Java, the strategy is changing length from n to (n + n/2 + 1).

1
2
3
4
5
6
7
8
9
10
/** Create an ArrayList */

// no-args construction
List<Integer> L = new ArrayList<>();

// give initial capacity
List<Integer> L = new ArrayList<>(100);

// using existing collection
List<Integer> L = new ArrayList<>(L2);

Time Complexities for Operations

  1. Add an element

If an ArrayList is not full, it will take O(1) time.

However, if it is full, it will take extra time to do resizing ... O(N), where N is the number of elements of the ArrayList before adding.

  1. Remove an element

You can remove an element by giving its index, or giving itself.

  • Remove by index:
    • O(1) in the best case, ... remove the last element.
    • O(n) in the worst case. ... remove the first element, and copy the rest
  • Remove by element itself:
    • scan the array to find the element, then remove it if it exists.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/** Remove */

List<Integer> L = new ArrayList<>();

// remove an element at a particular index
int index = 4;
L.remove(index);

// remove a particular element
L.remove(new Integer(4));

// remove all elements within a range
// fromIndex is inclusive and toIndex is exclusive
// this method is not defined in the List class. 
// So, it can be used only when the reference type is also ArrayList and not List.
removeRange(int fromIndex, int toIndex)

// remove all elements within a given collection
L. removeAll(L2);

// remove all elements
L.clear();
  1. Fetch an element

Fetch an element from an ArrayList using index takes O(1) constant time.

1
2
3
4
5
6
7
/** Fetch */

int index = 4;
L.get(index);

// fetch the size of an ArrayList
L.size();
  1. Insert elements
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/** Insert */

List<Integer> L = new ArrayList<>();


// insert the element at the end
L.add(3);

// insert the element at a given index
int index = 4;
L.add(index, 3);

// insert multiple elements from another collection at the end
L.addAll(L1);

// insert multiple elements from another collection at a given index 
L.addAll(index, L1);
  1. Replace all elements in Java 8

A new method, replaceAll(UnaryOperator<E> operator), was added in Java 8. This method takes a single UnaryOperator type argument. The UnaryOperator interface is a functional interface that has a single abstract method, apply(), that returns a result of the same object type as the operand.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.ArrayList;
import java.util.List;

public class ArrayListDemo {

	public static void main(String args[]) {
		List<String> list = new ArrayList<>();
		list.add("apple");
		list.add("banana");

		list.replaceAll((element) -> element.toUpperCase());

		System.out.println(list);   // [APPLE, BANANA]
	}
}
  1. Update an element
1
2
3
4
5

// set the element at index to a new value
int index = 1;
String newStr = "peach";
list.set(index, newStr);
  1. Check existence
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
import java.util.ArrayList;
import java.util.List;

public class ArrayListDemo {

	public static void main(String args[]) {
		List<Integer> list = new ArrayList<>();
		list.add(10);
		list.add(20);
		list.add(30);
		list.add(40);
		list.add(10);

		list.set(1, 100);

        System.out.println(list);  // [10, 100, 30, 40, 10]

        // check if an element is present
        if (list.contains(30)) {    // true
            System.out.println("List contains 30");
        }

        // the index of the first occurrence
        System.out.println(
            "Index of first occurence of 10 is " + list.indexOf(10) // 0
        );
        System.out.println(
            "Index of last occurence of 10 is " + list.lastIndexOf(10)  // 4
        );
	}
}

Iteration

Using Iterator

In CS61B lecture 11, we have discussed enhanced for loop.

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
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ArrayListDemo {

	public static void main(String args[]) {
		List<Integer> list = new ArrayList<>();
		list.add(10);
		list.add(20);
		list.add(30);
		list.add(40);
		list.add(10);

		Iterator<Integer> itr = list.iterator();

		while(itr.hasNext()) {
			System.out.println(itr.next());
		}

		// Iterating using forEachRemaining() method
		System.out.println("Iterating using forEachRemaining() method");
		Iterator<Integer> newItr = list.iterator();
		newItr.forEachRemaining(element -> System.out.println(element));
	}
}

If we try to directly remove an element while iterating an ArrayList using an iterator is created, then ConcurrentModificationException will also be thrown. We should always use the remove() method in the iterator to remove an element from the ArrayList.

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
/** This program will fail because we are trying to delete the element from the list directly. */

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ArrayListPractice {

	public static void main(String args[]) {
		List<Integer> list = new ArrayList<>();
		list.add(10);
		list.add(20);
		list.add(30);
		list.add(40);
		list.add(10);

		Iterator<Integer> itr = list.iterator();

		while (itr.hasNext()) {
			int next = itr.next();
			
			if (next == 30) {
				list.remove(new Integer(30));
			}
		}
	}
}
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
/** This program is the correct way to delete an element from the list. */

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ArrayListDemo {

	public static void main(String args[]) {
		List<Integer> list = new ArrayList<>();
		list.add(10);
		list.add(20);
		list.add(30);
		list.add(40);
		list.add(10);

		Iterator<Integer> itr = list.iterator();

		while(itr.hasNext()) {
			int next = itr.next();
			if(next == 30) {
				itr.remove();
			}
		}
		System.out.println(list);
	}
}

If an element is added to the ArrayList after the iterator is created then also ConcurrentModificationException will be thrown.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;


public class ArrayListDemo {

	public static void main(String args[]) {
		List<Integer> list = new ArrayList<>();
		list.add(34);
		list.add(45);

		Iterator<Integer> itr = list.iterator();
		list.add(54);

		while(itr.hasNext()) {
			System.out.println(itr.next());	
		}
	}
}

Using ListIterator

The Iterator provides very limited capabilities as we can iterate only in the forward direction and we can’t update or insert an element to the list while iterating. To overcome these problems, we can use ListIterator.

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
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class ArrayListDemo {

	public static void main(String args[]) {
		List<Integer> list = new ArrayList<>();
		list.add(10);
		list.add(20);
		list.add(30);
		list.add(40);

		// Getting ListIterator
		ListIterator<Integer> listIterator = list.listIterator();

		// Traversing elements
		System.out.println("Forward Direction Iteration:");
		while (listIterator.hasNext()) {
			System.out.println("Next element is " + listIterator.next() + 
			" and next index is " + listIterator.nextIndex());
		}

		// Traversing elements, the iterator is at the end at this point
		System.out.println("Backward Direction Iteration:");
		while (listIterator.hasPrevious()) {
			System.out.println("Previous element is " + listIterator.previous() + 
			" and previous index is " + listIterator.previousIndex());
		}
	}
}

/*
Output:

Forward Direction Iteration:
Next element is 10 and next index is 1
Next element is 20 and next index is 2
Next element is 30 and next index is 3
Next element is 40 and next index is 4
Backward Direction Iteration:
Previous element is 40 and previous index is 2
Previous element is 30 and previous index is 1
Previous element is 20 and previous index is 0
Previous element is 10 and previous index is -1
*/

Besides, there are other methods such as remove(), set(E e), add(E e) etc.