Assumed Knowledge
Learning Outcomes
  • Understand the underlying features of lists and how they differ from arrays.
  • Be able to use built-in Java lists
  • Be able to build a custom list class
  • Understand the time costs of various list operations

Author: Gaurav Gupta

What are lists?

Lists are data structures, much like arrays. The differences being,

2. Lists grow as required

The size of array needs to be specified at the time of creating an array. The size of a list need not be specified. You can add as many items as you want to a list (permitting system memory).

3. Lists have a range of instance methods

With arrays (assuming array name is arr), the only operators you have to work with are arr.length and arr[i]. Anything and everything you need to do must be done using these two operators. Several life-saving methods are applicable on list objects, such as:

  • get(int) //similar to arr[i]
  • size() //similar to arr.length
  • add(Object) //add item at the end of the list

Why use ArrayList instead of arrays?

Two reasons:

  1. Dynamic (grows as you insert items, resizes when you remove).
  2. Plenty of helpful methods (functions) for common tasks.

Comparison of solution with arrays with ArrayLists (Just to illustrate ArrayLists make life easier)

With arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public static boolean occursExactlyOnce(int[] data, int key) {
   int count = 0;
   boolean found = false;
   for(int i=0; i < data.length; i++) {
      if(data[i] == key) { //if found
         if(found) { //if found before
            return false; //this is the second time
         }
         else { //if not found before 
            found = true; //now it's found
         }
      }
   }
   return found == true; //ensure found once
}

With ArrayLists

IMPORTANT - Right now, you don’t need to understand the following code, just appreciate how much easier, compared to arrays, it is

1
2
3
4
5
6
7
8

public static boolean occursExactlyOnce(ArrayList<Integer> list, int key) {
   if(list.indexOf(key) >= 0)) { //if found
      if(list.indexOf(key) == list.lastIndexOf(key) { //if first and last occurrence is the same
	return true;
      }
   }
   return false; //in ALL other cases
}

Creating an ArrayList object

The syntax to create an ArrayList object is:

1
2
3
4
5

ArrayList<E> name = new ArrayList<E>();

//or

ArrayList<E> name = new ArrayList<>();

Here, E refers to the type of items it can store. Just one thing (until we cover Classes and Objects), this (E) cannot be a primitive data type, and needs to be a class (more on that when we cover Classes and Objects).

  • Instead of int, we use Integer.
  • Instead of double, we use Double.
  • Instead of char, we use Character.
  • Instead of boolean, we use Boolean.
  • We can use String as it’s already a class.

Some examples:

1
2
3
4

ArrayList<Integer> list1 = new ArrayList<Integer>(); //list of Integer objects (int values)
ArrayList<String> list2 = new ArrayList<>(); //list of String objects
ArrayList<Character> list3 = new ArrayList<>(); //list of Character objects (char values)
ArrayList<Boolean> list4 = new ArrayList<>(); //list of Boolean objects (boolean values)

List of selected methods in ArrayList class

Method Description
int size()                                 It is used to return the number of elements present in the list.
E get(int index) It is used to fetch the element from the particular position of the list.
boolean add(E e) It is used to append the specified element at the end of a list.
void add(int index, E element) It is used to insert the specified element at the specified position in a list.
void clear() It is used to remove all of the elements from this list.
boolean isEmpty() It returns true if the list is empty, otherwise false.
int indexOf(Object o) It is used to return the index in this list of the first occurrence of the specified element, or -1 if the List does not contain this element.
int lastIndexOf(Object o) It is used to return the index in this list of the last occurrence of the specified element, or -1 if the list does not contain this element.
boolean contains(Object o) It returns true if the list contains the specified element
E remove(int index) It is used to remove the element present at the specified position in the list.
boolean remove(Object o) It is used to remove the first occurrence of the specified element.
E set(int index, E element) It is used to replace the specified element in the list, present at the specified position.

Use of methods in examples

Each example builds on top of the previous example.

Example 1 - size() and add(Object)

1
2
3
4
5
6
7

ArrayList<Integer> data = new ArrayList<Integer>();
int a = data.size(); //a will be 0 since data doesn't contain any items
data.add(10); //data becomes [10]
data.add(70); //data becomes [10, 70]
data.add(20); //data becomes [10, 70, 20]
data.add(90); //data becomes [10, 70, 20, 90]
int b = data.size(); //b will be 4

Example 2 - add(int, Object)

1
2
3
4
5

//note data = [10, 70, 20, 90] already
data.add(0, 50); //data becomes [50, 10, 70, 20, 90]
data.add(data.size(), 40); //data becomes [50, 10, 70, 20, 90, 40]
data.add(-1, 100); //INVALID - throws IndexOutOfBoundsException
data.add(data.size()+1, 100); //INVALID - throws IndexOutOfBoundsException

Example 3 - set(int, Object)

1
2
3
4
5

//note data = [50, 10, 70, 20, 90, 40] already
data.set(0, 60); //data becomes [60, 10, 70, 20, 90, 40]
data.set(data.size()-1, 60); //data becomes [60, 10, 70, 20, 90, 60]
data.set(-1, 100); //INVALID - throws IndexOutOfBoundsException
data.set(data.size(), 100); //INVALID - throws IndexOutOfBoundsException

Example 4 - contains(Object), indexOf(Object), lastIndexOf(Object)

1
2
3
4
5
6
7
8
9
10

//note data = [60, 10, 70, 20, 90, 60] already
data.
boolean status = data.contains(70); //status is true
boolean status = data.contains(50); //flag is false
int a = data.indexOf(60); //a is 0
int b = data.lastIndexOf(60); //b is 5
int c = data.indexOf(70); //c is 2
int d = data.lastIndexOf(70); //d is 2
int e = data.indexOf(80); //e is -1 (80 not found)
int f = data.lastIndexOf(80); //e is -1 (80 not found)

Example 5 - remove(int), remove(Object)

1
2
3
4

//assumption: data = [60, 10, 70, 20, 90, 60] already
data.remove(0); 		//data = [10, 70, 20, 90, 60]
data.remove(data.size()-1); 	//data = [10, 70, 20, 90]
data.remove(2); 		//data = [10, 70, 90]

1
2
3
4

//assumption: data = [60, 10, 70, 20, 90, 60] already
data.remove(10);
//IndexOutOfBoundsException since 10 is treated as int, 
//and hence remove(int) is called

1
2
3
4

//assumption: data = [60, 10, 70, 20, 90, 60] already
data.remove((Integer)10); //data = [60, 70, 20, 90, 60]
data.remove((Integer)60); //data = [70, 20, 90, 60]
data.remove((Integer)60); //data = [70, 20, 90]

1
2
3
4
5
6
7
8

//removing all occurrences of a specific item -
//assumption: data = [70, 20, 90, 80, 80, 80, 80, 80]
while(data.contains(80)) {
	data.remove((Integer)80); 
	//remember, data.remove(80) will 
	//try to remove item at index 80
}
//data = [70, 20, 90]

Example 6 - isEmpty(), clear()

1
2
3
4

//note data = [70, 20, 90[ already
boolean g = data.isEmpty(); //g is false
data.clear(); //data = [] now
boolean h = data.isEmpty(); //h is true

Passing ArrayList to functions

ArrayLists are objects and a reference copy of the actual parameter is made into the formal parameter when they are passed to functions.

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

import java.util.ArrayList;

public class ListToFunctionClient {
	public static void main(String[] args) {
		ArrayList<Integer> data = new ArrayList<Integer>();
		data.add(10);
		data.add(70);
		data.add(20);
		data.add(90);
		System.out.println(sum(data)); //190
		increment(data); //data becomes [11, 71, 21, 91]
		System.out.println(sum(data)); //194
	}

	public static int sum(ArrayList<Integer> list) {
		int result = 0;
		for(int i=0; i < list.size(); i++) {
			result+=list.get(i);
		}
		return result;
	}

	public static void increment(ArrayList<Integer> list) {
		for(int i=0; i < list.size(); i++) {
			list.set(i, list.get(i)+1);
		}
	}
}

For-each loop

The for-each loop helps simplify list (or array) traversal where the index is not required besides accessing the item. Syntax:

1
2
3

for(Object obj: ArrayList) {
	//use obj
}

Example:

1
2
3
4
5
6
7
8
9
10

ArrayList<Integer> data = new ArrayList<Integer>();
data.add(10);
data.add(70);
data.add(20);
data.add(90);
int total = 0;
for(Integer item: data) {
	total+=item;
}
//total = 190

In the above example, item becomes a reference copy of,

  • First item (10) in the first iteration of the loop
  • Second item (70) in the second iteration of the loop
  • Third item (20) in the third iteration of the loop
  • Fourth item (90) in the fourth iteration of the loop

Since java handles casting between Integer and int, you can also write:

1
2
3

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

Here, the value of the Integer object is copied into item during each iteration.

Creating and using lists of user-defined classes

IMPORTANT: If ArrayLists are covered before Classes and Objects, this part will be covered during the second or third lecture on Classes and Objects.

So, the idea is to cover:

  1. ArrayLists of built-in classes like Integer, Boolean, …
  2. Cover design and implementation of classes (user-defined classes).
  3. Revisit ArrayLists to now create lists of user-defined classes.

These examples assume the existence of the following Rectangle class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Rectangle {
	public int length, breadth;
	public Rectangle(int len, int bre) {
		length = len;
		breadth = bre;
	}

	public String toString() {
		return length + " by " + breadth;
	}

	public int area() {
		return length * breadth;
	}

	public boolean isSquare() {
		return length == breadth;
	}
}

Take the following example -

1
2
3
4
5
6
7
8
9
10
11

ArrayList<Rectangle> rects = new ArrayList<Rectangle>();
for(int i=0; i < 5; i++) {
	if(i!=3) {
		Rectangle temp = new Rectangle(1+i/3, 1+i%3);
		rects.add(temp);
	}
	else {
		rects.add(null);
	}
}
System.out.println(rects);

At the end of the execution of the above code, the output will be:

1

[1 by 1, 1 by 2, 1 by 3, null, 2 by 2]

The memory diagram is provided below: