Collections Framework – 2 [ List ]

OVO

List interface extends Collection interface and allows :

  • to contain duplicates;
  • to interact with an element by using its position;
  • to insert null elements.

What You Need

  • About 14 minutes
  • A favorite text editor or IDE
  • Java 8 or later
What You Will Learn
  1. 1.Methods of List Interface
  2. 2.Implementations of List Interface
  3. 3. The choice of a list implementation

1.Methods of List Interface

A special interface is defined to allow browsing in both directions of the list and to perform updates : listIterator.

List defines several methods that allow access to list elements from an index, to manage the elements, to find the position of an element, to obtain a partial list (sublist) and to obtain Iterators.

MethodRole
void add(int index, E e)Inserts the specified element at the specified position in this list.
boolean addAll(int index, Collection c)Inserts all of the elements in the specified collection into this list at the specified position.
E get(int index)Returns the element at the specified position in this list.
int indexOf(Object o)Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
int lastIndexOf(Object o)Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.
ListIterator listIterator()Returns a list iterator over the elements in this list.
ListIterator listIterator(int indx)Returns a list iterator over the elements in this list, starting at the specified position in the list.
E remove(int index)Removes the element at the specified position in this list.
E set(int index, E e)Replaces the element at the specified position in this list with the specified element.
List subList(int fromIndex, int toIndex)Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.

2.Implementations of List Interface

ImplementationRole
java.util.VectorA thread-safe implementation provided since Java 1.0, it is like the dynamic array which can grow or shrink its size
java.util.StackAn implementation of a stack, it inherits from the Vector class and provides operations of LIFO (Last In First Out)
java.util.ArrayListLike Vector but it is an implementation that is not thread-safe
java.util.LinkedListAn unsynchronized implementation of a doubly linked list, the insertions of new elements are very fast
java.util.concurrent.CopyOnWriteArrayListA thread-safe variant of the ArrayList class in which all operations modifying the contents of the list recreate a new copy of the array used to store the elements of the collection

2.1 Vector

The Vector class, present since Java 1.0, is an array whose size can vary depending on the number of elements it contains.

When creating a Vector type instance, it is possible to specify an initial capacity and an increment size using the corresponding overload of the constructor.

The Vector class predates the Collections API. Before the Collections API the Vector class was frequently used. It was later updated to implement the List interface. Therefore there are several redundant methods such as the add() and addElement() methods.

All the methods of the Vector class are synchronized.

Items are stored in the order in which they are added to the collection. An item can be added or removed at any position in the collection.

import java.util.Iterator;
import java.util.Vector;

public class VectorTest {
    public static void main(String[] args) {
        Vector<Integer> v = new Vector<>();

        v.add(1);
        v.add(2);
        v.addElement(3);
        v.addElement(4);

        System.out.println("Size of vector = " + v.size());

        Iterator<Integer> it = v.iterator();

        while (it.hasNext()) {
            Integer element = it.next();
            System.out.println(element);
        }

        v.remove(0);

        System.out.println(v);

        v.remove(Integer.valueOf(4));

        System.out.println(v);

        v.removeAllElements();

        System.out.println("Size of vector = " + v.size());
    }
}

Below is the output of above code snippet :

Size of vector = 4
1
2
3
4
[2, 3, 4]
[2, 3]
Size of vector = 0

2.2 Stack

The Stack class extends Vector class, it is based on the basic principle of last-in-first-out.

In addition to the basic push and pop operations, Stack class provides three more functions of empty, search, and peek.

import java.util.Stack;

public class StackTest {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println(stack.peek());

        System.out.println(stack.search(3));

        System.out.println();

        while (!stack.empty()) {
            System.out.println(stack.pop());
        }

        System.out.println();

        System.out.println(stack.search(3));
    }
}

The output of above code snippet is below :

3
1

3
2
1

-1

2.3 ArrayList

Arrays are part of the Java language and are easy to use, but their size cannot vary.

The ArrayList class is an array of objects whose size is dynamic : it uses an array whose size automatically adapts to the number of elements in the collection..

However, this adaptation has a cost because it requires the instantiation of a new array and the copying of the elements into this new array.

The operation of this class is similar to that of the Vector class. The difference with the Vector class is that the latter is thread safe.

To make an ArrayList thread safe, we can use its instance returned by Collections.synchronizedList(new ArrayList()).

The Iterators and ListIterators of the ArrayList class are of the fail-fast type : they can raise an exception of the ConcurrentModificationException type if a modification in the number of elements occurs during the browse without using their add() or remove() methods.

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

public class ArrayListTest1 {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();

        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

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

        while (it.hasNext()) {
            Integer element = it.next();

            if (element == 1) {
                it.remove();
            } else {
                System.out.println(element);
            }
        }

        System.out.println(list);
    }
}

Below is the output of above code snippet :

2
3
4
5
[2, 3, 4, 5]

We can convert an array to arraylist using following ways :

  • Using Arrays.asList() method – Pass the required array to this method and get a List object and pass it as a parameter to the constructor of the ArrayList class;
  • Collections.addAll() method – Create a new list before using this method and then add array elements using this method to existing list;
  • Iteration method – Create a new list. Iterate the array and add each element to the list.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class ArrayListTest2 {
    public static void main(String[] args) {
        String[] array = { "a", "b", "c", "d", "e" };

        // Method 1
        List<String> list1 = Arrays.asList(array);
        System.out.println(list1);

        // Method 2
        List<String> list2 = new ArrayList<String>();
        Collections.addAll(list2, array);
        System.out.println(list2);

        // Method 3
        List<String> list3 = new ArrayList<String>();
        for (String text : array) {
            list3.add(text);
        }
        System.out.println(list3);
    }
}

The output of above code snippet is below :

[a, b, c, d, e]
[a, b, c, d, e]
[a, b, c, d, e]

2.4 LinkedList

The LinkedList class is an implementation of a doubly linked list in which the elements of the collection are linked by pointers.

It manages a collection in an ordered way : the addition of an element can be done at the beginning or at the end of the collection.

Deleting or adding an element is done simply by modifying pointers.

So using a LinkedList is more advantageous over an ArrayList when elements need to be added or removed from the collection outside of its start or end.

However, direct access to an element of a LinkedList type collection is much less efficient because it must browse all the elements successively from the first element to the desired element.

It does not need to be resized regardless of the number of elements it contains and it is not thread safe as well like ArrayList.

import java.util.LinkedList;
import java.util.ListIterator;

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        list.add("A");
        list.add("B");
        list.addLast("C");
        list.addFirst("D");
        list.add(2, "E");

        System.out.println(list);

        ListIterator<String> it = list.listIterator();
        while (it.hasNext()) {
            String element = it.next();
            System.out.println(element);
        }

        list.remove("B");
        String removed = list.remove(3);
        System.out.println(removed + " has been removed from linked list");
        removed = list.removeFirst();
        System.out.println(removed + " has been removed from linked list");
        removed = list.removeLast();
        System.out.println(removed + " has been removed from linked list");

        System.out.println(list);
    }
}

The output of above code snippet is below :

[D, A, E, B, C]
D
A
E
B
C
C has been removed from linked list
D has been removed from linked list
E has been removed from linked list
[A]

2.5 CopyOnWriteArrayList

We already knew that to make an ArrayList thread safe, we can use its instance returned by Collections.synchronizedList(new ArrayList()).

However, using a synchronized wrapper of an ArrayList is not always advisable when there are many reads because it can introduce contention if several threads are doing reads competitors.

The CopyOnWriteArrayList class is a thread-safe variant of the ArrayList class in which all operations modifying the contents of the list recreate a new copy of the array, which allows other threads to read the contents of the original array without any synchronization.

Therefore, it is to be used in a Thread based environment where read operations are very frequent and update operations are rare.

import java.time.Instant;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicBoolean;

public class CopyOnWriteArrayListTest {
    public static void main(String[] args) throws InterruptedException {
        CopyOnWriteArrayList<Integer> counter = new CopyOnWriteArrayList<>(new Integer[] { 0 });

        AtomicBoolean writen = new AtomicBoolean(false);

        Runnable reader = () -> {
            while (!writen.get()) {
                System.out.println(
                        "[" + Instant.now() + "] " + Thread.currentThread().getName() + " : " + counter.get(0));
                try {
                    TimeUnit.MILLISECONDS.sleep(500);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        };

        Runnable writer = () -> {
            counter.set(0, counter.get(0) + 1);
            System.out.println();
            System.out.println("[" + Instant.now() + "] " + Thread.currentThread().getName() + " : " + counter.get(0));
            System.out.println();
        };

        int nReader = 10;
        int nWriter = 3;

        List<Thread> threads = new ArrayList<>();

        for (int i = 0; i < nReader; i++) {
            Thread thread = new Thread(reader, "Reader_" + i);

            thread.start();

            threads.add(thread);
        }

        for (int j = 0; j < nWriter; j++) {
            Thread thread = new Thread(writer, "Writer_" + j);

            TimeUnit.SECONDS.sleep(1);

            thread.start();

            threads.add(thread);
        }

        TimeUnit.SECONDS.sleep(1);

        writen.set(true);

        for (Thread thread : threads) {
            thread.join();
        }
    }
}

Below is the output of above code snippet :

[2025-03-31T09:07:44.564413787Z] Reader_9 : 0
[2025-03-31T09:07:44.558328040Z] Reader_3 : 0
[2025-03-31T09:07:44.561813924Z] Reader_5 : 0
[2025-03-31T09:07:44.557729106Z] Reader_1 : 0
[2025-03-31T09:07:44.558147269Z] Reader_2 : 0
[2025-03-31T09:07:44.559575727Z] Reader_4 : 0
[2025-03-31T09:07:44.557711805Z] Reader_0 : 0
[2025-03-31T09:07:44.562083722Z] Reader_6 : 0
[2025-03-31T09:07:44.562305636Z] Reader_7 : 0
[2025-03-31T09:07:44.564342238Z] Reader_8 : 0
[2025-03-31T09:07:45.103507338Z] Reader_4 : 0
[2025-03-31T09:07:45.103371721Z] Reader_1 : 0
[2025-03-31T09:07:45.102906129Z] Reader_5 : 0
[2025-03-31T09:07:45.102817741Z] Reader_9 : 0
[2025-03-31T09:07:45.102817622Z] Reader_3 : 0
[2025-03-31T09:07:45.110264297Z] Reader_2 : 0
[2025-03-31T09:07:45.113717349Z] Reader_6 : 0
[2025-03-31T09:07:45.115084200Z] Reader_8 : 0
[2025-03-31T09:07:45.115933546Z] Reader_7 : 0
[2025-03-31T09:07:45.117416045Z] Reader_0 : 0

[2025-03-31T09:07:45.568689485Z] Writer_0 : 1

[2025-03-31T09:07:45.605091508Z] Reader_4 : 1
[2025-03-31T09:07:45.606009690Z] Reader_1 : 1
[2025-03-31T09:07:45.606667258Z] Reader_5 : 1
[2025-03-31T09:07:45.607456896Z] Reader_3 : 1
[2025-03-31T09:07:45.607401277Z] Reader_9 : 1
[2025-03-31T09:07:45.611668100Z] Reader_2 : 1
[2025-03-31T09:07:45.615191739Z] Reader_6 : 1
[2025-03-31T09:07:45.615989702Z] Reader_8 : 1
[2025-03-31T09:07:45.618731099Z] Reader_7 : 1
[2025-03-31T09:07:45.619194936Z] Reader_0 : 1
[2025-03-31T09:07:46.106172307Z] Reader_4 : 1
[2025-03-31T09:07:46.106703581Z] Reader_1 : 1
[2025-03-31T09:07:46.108818761Z] Reader_5 : 1
[2025-03-31T09:07:46.110470464Z] Reader_3 : 1
[2025-03-31T09:07:46.112685916Z] Reader_2 : 1
[2025-03-31T09:07:46.112377270Z] Reader_9 : 1
[2025-03-31T09:07:46.116581604Z] Reader_6 : 1
[2025-03-31T09:07:46.117084253Z] Reader_8 : 1
[2025-03-31T09:07:46.119576864Z] Reader_7 : 1
[2025-03-31T09:07:46.120235521Z] Reader_0 : 1

[2025-03-31T09:07:46.570327674Z] Writer_1 : 2

[2025-03-31T09:07:46.607083168Z] Reader_4 : 2
[2025-03-31T09:07:46.607502617Z] Reader_1 : 2
[2025-03-31T09:07:46.609233979Z] Reader_5 : 2
[2025-03-31T09:07:46.613463359Z] Reader_3 : 2
[2025-03-31T09:07:46.614144331Z] Reader_2 : 2
[2025-03-31T09:07:46.614194752Z] Reader_9 : 2
[2025-03-31T09:07:46.618905798Z] Reader_8 : 2
[2025-03-31T09:07:46.621811201Z] Reader_0 : 2
[2025-03-31T09:07:46.619932498Z] Reader_6 : 2
[2025-03-31T09:07:46.620662985Z] Reader_7 : 2
[2025-03-31T09:07:47.109116282Z] Reader_4 : 2
[2025-03-31T09:07:47.109529334Z] Reader_1 : 2
[2025-03-31T09:07:47.110739405Z] Reader_5 : 2
[2025-03-31T09:07:47.115323614Z] Reader_3 : 2
[2025-03-31T09:07:47.115434045Z] Reader_2 : 2
[2025-03-31T09:07:47.116175480Z] Reader_9 : 2
[2025-03-31T09:07:47.123014846Z] Reader_8 : 2
[2025-03-31T09:07:47.122720203Z] Reader_0 : 2
[2025-03-31T09:07:47.125407755Z] Reader_7 : 2
[2025-03-31T09:07:47.126266404Z] Reader_6 : 2

[2025-03-31T09:07:47.571806517Z] Writer_2 : 3

[2025-03-31T09:07:47.611759449Z] Reader_4 : 3
[2025-03-31T09:07:47.612214928Z] Reader_5 : 3
[2025-03-31T09:07:47.611743890Z] Reader_1 : 3
[2025-03-31T09:07:47.617161335Z] Reader_9 : 3
[2025-03-31T09:07:47.618942750Z] Reader_3 : 3
[2025-03-31T09:07:47.619331690Z] Reader_2 : 3
[2025-03-31T09:07:47.625025467Z] Reader_8 : 3
[2025-03-31T09:07:47.628617345Z] Reader_0 : 3
[2025-03-31T09:07:47.630394546Z] Reader_7 : 3
[2025-03-31T09:07:47.630978298Z] Reader_6 : 3
[2025-03-31T09:07:48.112329334Z] Reader_4 : 3
[2025-03-31T09:07:48.112829487Z] Reader_5 : 3
[2025-03-31T09:07:48.115498902Z] Reader_1 : 3
[2025-03-31T09:07:48.117761471Z] Reader_9 : 3
[2025-03-31T09:07:48.120270715Z] Reader_2 : 3
[2025-03-31T09:07:48.119862301Z] Reader_3 : 3
[2025-03-31T09:07:48.125750339Z] Reader_8 : 3
[2025-03-31T09:07:48.129935545Z] Reader_0 : 3
[2025-03-31T09:07:48.130754743Z] Reader_7 : 3
[2025-03-31T09:07:48.132170970Z] Reader_6 : 3

3. The choice of a list implementation

If there is no concurrent access on the collection, the choice must be made between the ArrayList and LinkedList classes :

  • If the addition or deletion of elements is mainly done at the end of the collection, then the ArrayList class should be used;
  • If the additions or deletion of elements are done at a random position in the collection, then the LinkedList class must be used.

If concurrent access must be managed then :

  • If the collection is infrequently updated, then the copyOnWriteArrayList class must be used, which allows non-blocking reads but the updates imply a duplication of the collection;
  • Otherwise, use the instance returned by the synchronizedList() method of the Collections class, passing it an ArrayList or LinkedList type instance as a parameter.

Related Posts