Lists in Java with Examples

A list is an ordered collection of values. In Java, lists are part of the Java Collections Framework. Lists implement the java.util.List interface, which extends java.util.Collection.

Sorting a generic list

The Collections class offers two standard static methods to sort a list:

  • sort(List list) applicable to lists where T extends Comparable, and
  • sort(List list, Comparator c) applicable to lists of any type.

Applying the former requires amending the class of list elements being sorted, which is not always possible. It might also be undesirable as although it provides the default sorting, other sorting orders may be required in different circumstances, or sorting is just a one off task.

Consider we have a task of sorting objects that are instances of the following class:

Related Article: List vs Set

public class User {
    public final Long id;
    public final String username;
    public User(Long id, String username) {
        this.id = id;
        this.username = username;
    }
    @Override
    public String toString() {
         return String.format("%s:%d", username, id);
    }
}

In order to use Collections.sort(List list) we need to modify the User class to implement the Comparable interface. For example

public class User implements Comparable {
      public final Long id;
      public final String username;

      public User(Long id, String username) {
          this.id = id;
          this.username = username;
      }

      @Override
      public String toString() {
           return String.format("%s:%d", username, id);
      }
      @Override
      /** The natural ordering for 'User' objects is by the 'id' field. */
      public int compareTo(User o) {
           return id.compareTo(o.id);
      }
}

(Aside: many standard Java classes such as String, Long, Integer implement the Comparable interface. This makes lists of those elements sortable by default, and simplifies implementation of compare or compareTo in other classes.)

With the modification above, the we can easily sort a list of User objects based on the classes natural ordering. (In this case, we have defined that to be ordering based on id values). For example:

List users = Lists.newArrayList(
    new User(33L, "A"),
    new User(25L, "B"),
    new User(28L, ""));
Collections.sort(users);

System.out.print(users);
// [B:25, C:28, A:33]

However, suppose that we wanted to sort User objects by name rather than by id. Alternatively, suppose that we had not been able to change the class to make it implement Comparable.

This is where the sort method with the Comparator argument is useful:

Collections.sort(users, new Comparator() {
    @Override
    /* Order two 'User' objects based on their names. */
    public int compare(User left, User right) {
         return left.username.compareTo(right.username);
    }
});
System.out.print(users);
// [A:33, B:25, C:28]
Version ≥ Java SE 8

In Java 8 you can use a lambda instead of an anonymous class. The latter reduces to a one-liner:

Collections.sort(users, (l, r) -> l.username.compareTo(r.username));

Further, there Java 8 adds a default sort method on the List interface, which simplifies sorting even more.

users.sort((l, r) -> l.username.compareTo(r.username))

Convert a list of integers to a list of strings

List nums = Arrays.asList(1, 2, 3);
List strings = nums.stream()
    .map(Object::toString)
    .collect(Collectors.toList());

That is:

  1. Create a stream from the list
  2. Map each element using Object::toString
  3. Collect the String values into a List using Collectors.toList()

Classes implementing List – Pros and Cons

The List interface is implemented by different classes. Each of them has its own way for implementing it with different strategies and providing different pros and cons.

Related Article: List vs Set in Java

Classes implementing List

These are all of the public classes in Java SE 8 that implement the java.util.List interface:

  1. Abstract Classes:
    • AbstractList
    • AbstractSequentialList
  2. Concrete Classes:
    • ArrayList
    • AttributeList
    • CopyOnWriteArrayList
    • LinkedList
    • RoleList
    • RoleUnresolvedList
    • Stack
    • Vector

Pros and Cons of each implementation in term of time complexity ArrayList

public class ArrayList
extends AbstractList
implements List, RandomAccess, Cloneable, Serializable

ArrayList is a resizable-array implementation of the List interface. Storing the list into an array, ArrayList provides methods (in addition to the methods implementing the List interface) for manipulating the size of the array.

Initialize ArrayList of Integer with size 100

List myList = new ArrayList(100); // Constructs an empty list with the specified initial capacity.

PROS:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. So getting and setting each element of the List has the same time cost:

int e1 = myList.get(0); // \
int e2 = myList.get(10); // | => All the same constant cost => O(1)
myList.set(2,10); // /

CONS:

Being implemented with an array (static structure) adding elements over the size of the array has a big cost due to the fact that a new allocation need to be done for all the array. However, from documentation:

The add operation runs in amortized constant time, that is, adding n elements requires O(n) time

Removing an element requires O(n) time.

AttributeList
On coming

CopyOnWriteArrayList

On coming

LinkedList
public class LinkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, Serializable

LinkedList is implemented by a doubly-linked list a linked data structure that consists of a set of sequentially linked records called nodes.

Iitialize LinkedList of Integer

List myList = new LinkedList(); // Constructs an empty list.

PROS:

Adding or removing an element to the front of the list or to the end has constant time.

myList.add(10); // \
myList.add(0,2); // | => constant time => O(1)
myList.remove(); // /

CONS: From documentation:

Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

Operations such as:

myList.get(10); // \
myList.add(11,25); // | => worst case done in O(n/2)
myList.set(15,35); // /

RoleList
On coming

RoleUnresolvedList
On coming

Stack
On coming

Vector
On coming

Finding common elements between 2 lists

Suppose you have two lists: A and B, and you need to find the elements that exist in both lists.

You can do it by just invoking the method List.retainAll().

Example:

public static void main(String[] args) {
    List numbersA = new ArrayList<>();
    List numbersB = new ArrayList<>();
    numbersA.addAll(Arrays.asList(new Integer[] { 1, 3, 4, 7, 5, 2 }));
    numbersB.addAll(Arrays.asList(new Integer[] { 13, 32, 533, 3, 4, 2 }));
    
    System.out.println("A: " + numbersA);
    System.out.println("B: " + numbersB);
    List numbersC = new ArrayList<>();
    numbersC.addAll(numbersA);
    numbersC.retainAll(numbersB);

    System.out.println("List A : " + numbersA);
    System.out.println("List B : " + numbersB);
    System.out.println("Common elements between A and B: " + numbersC);
}
In-place replacement of a List element

This example is about replacing a List element while ensuring that the replacement element is at the same position as the element that is replaced.

This can be done using these methods:

  • set(int index, T type)
  • int indexOf(T type)

Consider an ArrayList containing the elements “Program starting!”, “Hello world!” and “Goodbye world!”

List strings = new ArrayList();
strings.add("Program starting!");
strings.add("Hello world!");
strings.add("Goodbye world!");

If we know the index of the element we want to replace, we can simply use set as follows:

strings.set(1, "Hi world");

If we don’t know the index, we can search for it first. For example:

int pos = strings.indexOf("Goodbye world!");
if (pos >= 0) {
strings.set(pos, "Goodbye cruel world!");
}

Notes:

  • The set operation will not cause a ConcurrentModificationException.
  • The set operation is fast ( O(1) ) for ArrayList but slow ( O(N) ) for a LinkedList.
  • An indexOf search on an ArrayList or LinkedList is slow ( O(N) ).

LEAVE A REPLY

Please enter your comment!
Please enter your name here