List in Java


Reading time: 15 minutes | Coding time: 5 minutes

List is one of the most common data structures and it can be used in a variety of algorithms and applications. In Java, you do not have to reinvent it. There is a List interface in Java which is a child interface of Collection. The List interface supports access, insertion, deletion of the elements. Each element in List has its own index, starting at 0, then 1 and so on. Since List is an interface in Java, you have to use other classes to create List objects, such as ArrayList(), LinkedList(), Vector(), and Stack().

List arrayList = new ArrayList();
List linkedList = new LinkedList();
List vector = new Vector();
List stack = new Stack();

You can also restrict the type in List by using List<> instead of List. The difference is that, the elements in List can be of different types. We call this raw type. On the other hand, all elements in List<> must be the same one. Such List is a wildcard type. Here comes the idea of generics, but we will not go in details here.

List arr1 = new ArrayList();    // raw type
List<?> arr2 = new ArrayList(); // unbounded wildcard type. It can use any type, 
                                // but needs to be same once decided.
List<T> arr3 = new ArrayList(); // bounded wildcard type

Operations on List

Since List is an extension of Collection, it supports all the operations in Collection interface as follows:

1. Position Access

(a) void add (int index, E element)

Insert element to the specific index. The pre-existing elements at that position and the beyond ones will shift up, no one will be overwritten.

List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);
System.out.println(list); // will output [1,2]

(b) bool addAll (int index, Collection c)

Insert all elements in the collection c in the order. Same as add(), if there is already an element at index position, that element and the beyond ones will shift right by the size of c. addAll() returns true if the list changed and return false otherwise.

// list = [1,2]
List<Integer> l2 = new ArrayList<Integer>();
l2.add(3);
l2.add(4);
l2.add(5);

list.addAll(1, l2);
System.out.println(list); // will output [1,3,4,5,2]

(c) Object get (int index)

Return the element at the specified index.

// list = [1,3,4,5,2]
System.out.println(list.get(2)); // will output 4

(d) Object set (int index, Object new)

Replace the element at the specified index with the new one. Return the element which was just replaced by new element.

// list = [1,3,4,5,2]
list.set(3, 7);
System.out.println(list); // will output [1,3,4,7,2]

(e) Object remove (int index)
Remove the element at the specified index. Those elements beyond the index will shift left to fill up the hole. Return the removed element.

// list = [1,3,4,7,2]
list.remove(1);
System.out.println(list); // will output [1,4,7,2]

If the index is out of range (index < 0 or index >= list.size()), it will throw IndexOutOfBoundsException.

2. Searching

(a) int indexOf (Object obj)

Return the index where the first given element is found. If it does not exist in the list, then return -1.

// list = [1,2,2,3,3]
System.out.println(list.indexOf(2)); // will output 1 for the first 2 appears at index 1.
System.out.println(list.indexOf(4)); // will output -1 since 4 does not exist in list.

(b) int lastIndexOf (Object obj)

Return the index where the last given element is found. Return -1 if it does not exist in array.

// list = [1,2,2,3,3]
System.out.println(list.indexOf(2)); // will output 2 for the last 2 appears at index 2.
System.out.println(list.indexOf(4)); // will output -1 since 4 does not exist in list.

3. Iteration

Java provides ListIterator to traverse the list in either direction. You can create a ListIterator object as follows:

// list = [1,2,3,4,5]
Iterator iter = list.listIterator(1); // specify the start point

while (iter.hasNext()) {
    System.out.println (iter.next()); // iteratively print out the element.
    // will output [2,3,4,5]
}

IndexOutOfBoundsException will be thrown if the index of iterator is out of range.

Also, you can jusy simply iterate the element using for-loop by specifying the index.

// ver. 1
for (int i=0; i < list.size() ; i++) {
    System.out.println(list[i]);
}

// ver. 2
for (Object elem : list) {
    System.out.println(elem);
}

4. Range view

(a) Object subList(int start, int end)

Return a list containing elements from start index (including) to end index (excluding).

// list = [1,2,3,4,5]
System.out.println(list.subList(1,3)); // extract elements from index 1 to index 2.
// will output [2,3]

For an illegal endpoint index value (start < 0 or end > list.size() or start > end), IndexOutOfBoundsException will be thrown.

Convert List to Array

The List object can be converted to java array by using toArray(). Here is an example:

List<int> list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);

Object[] arr = list.toArray();

Which one is not the implementing class from List interface?

ArrayList
Stack
Set
Vector
ArrayList, LinkedList, Stack, Queue, and Vector are all the implementations from List interface. Set is another interface in Java.

If list = [4,5,7,8,2], what is the result of the following code: System.out.println(list.set(4,10));

output 10
output True
output 2
cause an error
2 will be printed since set() function returns the element which is going to be replaced.