List in Java

List is an ordered collection which means it maintains the order of the elements you have inserted and it is also known as a sequence. So you will have complete control on where in the list each element is inserted. You can access elements by their integer index (position in the list), and also search for elements in it. Lists (like Java arrays) are zero based which means the element numbering starts at 0 (ex: get(0)).

Lets start with the basic operations (this also include list specific methods at each operation for easy understanding):

  • Add objects to the list.
  • Remove objects from the list.
  • Find out if an object (or group of objects) is in the list.
  • Retrieve an object from the list (without removing it).


1. Add objects to the list

The List interface provides four methods to add elements to it

boolean add(E e): Appends the specified element to the end of this list. This method returns true, if this collection changed as a result of the call - basically when an element is successfully added to the list. It returns false if the collection implementation class does not allow this element for different reasons and this is totally implementation class specific. For example if the implementation class semantics does not permit duplicates and already contains the specified element then it returns false.

Ex: List<EmployeeVO> list1 = new ArrayList<EmployeeVO>();
    
    EmployeeVO employee1 = new EmployeeVO("John", "Vice Precident");
    EmployeeVO employee2 = new EmployeeVO("Steve", "Design Architect");

    boolean elementAdded = list1.add(employee1); 
    list1.add(employee2);  

Here the order of elements in the list are : employee1, employee2.

Note that if a collection refuses to add a particular element for any reason other than that it already contains the element, it must throw an exception rather than returning false. This preserves the invariant that a collection always contains the specified element after this call returns.


void add(int index, E element): Inserts the specified element at the specified position in the list

Ex: List<EmployeeVO> list1 = new ArrayList<EmployeeVO>();
    
    EmployeeVO employee1 = new EmployeeVO("John", "Vice Precident");
    EmployeeVO employee2 = new EmployeeVO("Steve", "Design Architect");

    list1.add(employee1);
    list1.add(0, employee2);

Here the order of elements in the list are : employee2, employee1.

boolean addAll(Collection<? extends E> c): Appends all of the elements in the specified collection to the end of the list, in the order that they are returned by the specified collection's iterator. The behavior of this operation is undefined if the specified collection is modified while the operation is in progress. This implies that the behavior of this call is undefined if the specified collection is this collection, and this collection is nonempty.

Ex: List<EmployeeVO> list3 = new ArrayList<EmployeeVO>(list1);
    list3.addAll(list2);

Adds all the elements in list2 to the end of the list3.

boolean addAll(int index, Collection<? extends E> c): Inserts all of the elements in the specified collection into this list at the specified position

Ex: List<EmployeeVO> list3 = new ArrayList<EmployeeVO>(list1);
    list3.addAll(0, list2);

Adds all the elements in list2 to the beginning of the list3.

"boolean add(E e)" and "boolean addAll(Collection<? extends E> c)" are inherited from Collection interface while "void add(int index, E element)" and "boolean addAll(int index, Collection<? extends E> c)" are specific to List interface.

2. Remove object/collection of objects from the list

boolean remove(Object o): Removes the first occurrence and a single instance of the specified element from the list, if it is present. More formally, removes an element e such that (o==null ? e==null : o.equals(e)), if this collection contains one or more such elements. It returns true if this collection contained the specified element (or if this collection changed as a result of the call).

Ex: List<EmployeeVO> list1 = new ArrayList<EmployeeVO>();
	
	EmployeeVO employee1 = new EmployeeVO("John", "Vice Precident");
	EmployeeVO employee2 = new EmployeeVO("Steve", "Design Architect");

	list1.add(employee1); 
	list1.add(employee2);  

	boolean elementRemoved = list1.remove(employee1);

Lets see another example where same instance is added multiple times to the list and this method is called on the list.

Ex: List<EmployeeVO> list1 = new ArrayList<EmployeeVO>();
	
	EmployeeVO employee1 = new EmployeeVO("John", "Vice Precident");

	list1.add(employee1); 
	list1.add(employee1);  
	list1.add(employee1);  

	boolean elementRemoved = list1.remove(employee1);

Only the first element in the list is removed. The size of the list after this operation is 2.

E remove(int index): Removes the element at the specified position in this list. This is specific to List interface. Not available in Collection interface.

Ex: From the listin above example,
EmployeeVO employee1 = list1.remove(0);

boolean removeAll(Collection<?> c): Removes from the list all of its elements that are contained in the specified collection. After this call returns, this collection will contain no elements in common with the specified collection.

Ex: boolean elementsRemoved = list3.removeAll(list1);

boolean retainAll(Collection<?> c): Retains only the elements in this list that are contained in the specified collection. In other words, removes from this collection all of its elements that are not contained in the specified collection.

Ex: boolean elementsRetained = list3.retainAll(list2);

void clear(): Removes all of the elements from this list.

Ex: list1.clear();

"boolean remove(Object o)", "boolean removeAll(Collection<?> c)", "boolean retainAll(Collection<?> c)" and void clear()" are inherited from Collection interface while "E remove(int index)" is specific to List interface.

Tip: For many common List implementations, such as ArrayList, the performance of removing elements from the end of the list is substantially better than that of removing elements from the beginning.


3. Find out if an object (or group of objects) is in the list

boolean contains(Object o): Returns true if the list contains the specified element.

Ex: List<EmployeeVO> list1 = new ArrayList<EmployeeVO>();
    
    EmployeeVO employee1 = new EmployeeVO("John", "Vice Precident");
    EmployeeVO employee2 = new EmployeeVO("Steve", "Design Architect");

    list1.add(employee1); 
    list1.add(employee2);  

    boolean containsElement = list1.contains(employee1);

boolean containsAll(Collection<?> c): Returns true if the list contains all of the elements of the specified collection.

Ex: boolean containsAllElements = list2.containsAll(list1);

int indexOf(Object o): Returns the index of the first occurrence of the specified element in the list, or -1 if the list does not contain the element. Note that this operation is expensive.

Ex: int elementIndex = list1.indexOf(employee1);

int lastIndexOf(Object o): Returns the index of the last occurrence of the specified element in the list, or -1 if the list does not contain the element. Note that this operation is expensive.

Ex: int elementLastIndex = list1.lastIndexOf(employee1);

boolean isEmpty(): Returns true if this list contains no elements.

Ex: boolean isEmptyList = list1.isEmpty();

"boolean contains(Object o)", "boolean containsAll(Collection<?> c)" and "boolean isEmpty()" are inherited from Collection interface while "int indexOf(Object o)" and "int lastIndexOf(Object o)" are specific to List interface.

4. Retrieve an object/collection of objects from the list (without removing it)

E get(int index): Returns the element at the specified position in this list. Note that this operation is expensive than iterating through elements using Iterator. If you need elements in a sequence, use iterator. If you need an element in a specific position, use this operation..

Ex: List<EmployeeVO> list1 = new ArrayList<EmployeeVO>();
    
    EmployeeVO employee1 = new EmployeeVO("John", "Vice Precident");
    EmployeeVO employee2 = new EmployeeVO("Steve", "Design Architect");

    list1.add(employee1); 
    list1.add(employee2);  

    EmployeeVO emp = list1.get(1);

Returns employee2 object.

Iterator<E> iterator(): Returns an iterator over the elements in this list in proper sequence.

Ex: Iterator<EmployeeVO> itr = list1.iterator();
while(itr.hasNext()){
	EmployeeVO emp = itr.next(); //No need to typecast here
}

ListIterator<E> listIterator(): Returns a list iterator over the elements in this list (in proper sequence).

Ex: 
for (ListIterator<EmployeeVO> itr = list1.listIterator(); itr.hasPrevious(); ) {
	EmployeeVO emp = itr.previous();
	...
}

ListIterator<E> listIterator(int index): Returns a list iterator of the elements in this list (in proper sequence), starting at the specified position in this list.

Ex: 
for (ListIterator<EmployeeVO> itr = list1.listIterator(2); itr.hasPrevious(); ) {
	EmployeeVO emp = itr.previous();
	...
}

"E get(int index)", "ListIterator<E> listIterator()" and "ListIterator<E> listIterator(int index)" are inherited from Collection interface while "Iterator<E> iterator()" is specific to List interface.

Other methods inherited from collection

int size(): - Returns the number of elements in the the list.
Object[] toArray() : - Returns an array containing all of the elements in the collection.
<T> T[] toArray(T[] a): - Returns an array containing all of the elements in the collection; the runtime type of the returned array is that of the specified array.


From the above methods, you must have got that in addition to the operations inherited from Collection, the List interface includes operations for:

  • Positional access manipulates elements based on their numerical position in the list
  • Search searches for a specified object in the list and returns its numerical position. The List interface provides two methods to search for a specified object. From a performance standpoint, these methods should be used with caution. In many implementations they will perform costly linear searches
  • Iteration (ListIterator) extends Iterator semantics to take advantage of the list's sequential nature
  • Range-view (subList) performs arbitrary range operations on the list (List<E> subList(int fromIndex, int toIndex)) which is explained below as another subtopic.

A word about Iterators

Check here for complete article on Iterators.

As you all know, Iterator returns the elements of the list in proper sequence. List also provides another iterator, called a ListIterator, which allows you to traverse the list in both directions - forward and backward, modify the list during iteration, and obtain the current position of the iterator in addition to the normal operations that the Iterator interface provides.

Here is the ListIterator interface:

public interface ListIterator<E> extends Iterator<E> {
	boolean hasNext();
	E next();
	boolean hasPrevious();
	E previous();
	int nextIndex();
	int previousIndex();
	void remove(); //optional
	void set(E e); //optional
	void add(E e); //optional
}

The three methods - hasNext, next, and remove are inherited from Iterator and does the same thing in both interfaces. The hasPrevious and the previous (refer to the element before the cursor) operations are exact analogues of hasNext and next (refer to the element after the cursor) operations. The previous operation moves the cursor backward, whereas next operation moves the cursor forward.

Here's how you iterate the list backward.

for (ListIterator<T> itr = list.listIterator(list.size()); itr.hasPrevious(); ) {
	T t = itr.previous();
	...
}

The List interface has two forms of the listIterator method.
ListIterator<E> listIterator(): Returns a list iterator positioned at the beginning of the list (in proper sequence).
ListIterator<E> listIterator(int index): Returns a list iterator of the elements in this list (in proper sequence), starting at the specified position in this list.

To get complete insight on iterators, check this article.


We can also get subset of a list which is actually a (sub)view of list and what it means, it physically does not exist. Hence any changes made in the list will reflect in the sublist.

Way to get subset/Range - view of list

List<E> subList(int fromIndex, int toIndex): The range-view operation, subList(int fromIndex, int toIndex), returns a List view of the portion of this list whose indices range from fromIndex, inclusive, to toIndex, exclusive

This typically replaces the below for loop.

for (int i = fromIndex; i < toIndex; i++) {
	...
}

Since subList is a view of List, any changes in the former (Parent List) List are reflected in the latter (Sub List).

You can perform any operations in this range (subList)

For example, the following idiom removes a range of elements from a List.
list.subList(fromIndex, toIndex).clear();

To search for an element in a range:

int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);

Note that the preceding idioms return the index of the found element in the subList, not the index in the backing List.

Note: The semantics of the List returned by subList become undefined if elements are added to or removed from the backing (parent) List in any way other than via the returned List. Thus, it's highly recommended that you use the List returned by subList only to perform one or a sequence of range operations on the backing List.


Unlike sets, lists allow duplicate elements and also null elements (any number of elements)

Yes, lists allow duplicate elements and also null elements.

Lets take a simple example.

public class EmployeeVO {

  public EmployeeVO(){

  }

  public EmployeeVO(String n, String d){
    name = n;
    desg = d;
  }

  private String name;
  private String desg;

  public String getName() {
    return name;
  }
  public void setName(String name) {
    this.name = name;
  }
  public String getDesg() {
    return desg;
  }
  public void setDesg(String desg) {
    this.desg = desg;
  }

  @Override public String toString() {
    return "Name : " + name + " - Designation : " + desg;
  }
	
}

public class ListSample {

  public static void main(String args[]){
    EmployeeVO emp1 = new EmployeeVO("John", "Vice President");
    EmployeeVO emp2 = new EmployeeVO("Steve", "Design Engineer");
    EmployeeVO emp3 = null;

    List<EmployeeVO> list = new ArrayList<EmployeeVO>>();

    list.add(emp1);
    list.add(emp1);
    list.add(emp2);
    list.add(emp2);
    list.add(emp3);
    list.add(emp3);

    System.out.println("The list size : " + list.size()); //Size is 6

    System.out.println("******** Printing List *********** ");

    for (ListIterator<EmployeeVO> itr = list.listIterator(); itr.hasNext(); ) {
      EmployeeVO employee = itr.next();
      if(employee != null) {
        System.out.println("The employee is = " + employee.toString());
      }else{
        System.out.println("The employee is = " + employee);
      }
    }


    //If you want to check if the element address is same or not.
    emp1.setName("JohnNew");

    System.out.println("******** Printing List Again after updating object emp1*********** ");

    for (ListIterator<EmployeeVO> itr = list.listIterator(); itr.hasNext(); ) {
      EmployeeVO employee = itr.next();
      if(employee != null) {
        System.out.println("The employee is = " + employee.toString());
      }else{
        System.out.println("The employee is = " + employee);
      }
    }

  }
}


Result:
-------
The list size : 6
******** Printing List *********** 
The employee is = Name : John - Designation : Vice President
The employee is = Name : John - Designation : Vice President
The employee is = Name : Steve - Designation : Design Engineer
The employee is = Name : Steve - Designation : Design Engineer
The employee is = null
The employee is = null

******** Printing List Again after updating object emp1*********** 
The employee is = Name : JohnNew - Designation : Vice President
The employee is = Name : JohnNew - Designation : Vice President
The employee is = Name : Steve - Designation : Design Engineer
The employee is = Name : Steve - Designation : Design Engineer
The employee is = null
The employee is = null


In the above example, I am inserting duplicate elements (emp1, emp2) and null elements (emp3). When I print the size of the list, it displays 6 - including duplicate and null elements. Now I print the element itself, it printed duplicate and null elements. Then I updated element emp1 and printed the elements again. Since list holds the address of the elements, any updates to elements will be reflected in the list too. Final print proves the same.


Like the Set interface, two List objects can be compared for logical equality without regard to their implementation classes. Two List objects are equal if they contain the same elements in the same order.

The List interface places additional restrictions, beyond those specified in the Collection interface, on the contracts of the iterator, add, remove, equals, and hashCode methods.

Few important points to note:

  • Although its permissible for lists to contain themselves as elements, the equals and hashCode methods are no longer well defined on such a list.
  • Always perform a null check when accessing elements in a list as list allows null elements.
  • Some list implementations have restrictions on the elements that they may contain. Throw appropriate exception when list implementation is restricted and attempting to perform an ineligible operation.
  • For many common List implementations, such as ArrayList, the performance of removing elements from the end of the list is substantially better than that of removing elements from the beginning.
  • Positional access and Search operations execute in time proportional to the index value for some implementations (the LinkedList class, for example). Thus, iterating over the elements in a list is typically preferable to indexing through it if the caller does not know the implementation.
  • Extending the previous point - the List interface provides two methods to search for a specified object. From a performance standpoint, these methods should be used with caution. In many implementations they will perform costly linear searches


Summary of List Algorithms

Most algorithms in the Collections class apply to List. These algorithms, such as the replace and shuffle examples, also works with the List returned by subList.

sort Sorts the specified list into ascending order using a merge sort algorithm, which provides a fast, stable sort. A stable sort is one that does not reorder equal elements. All elements in the list must implement the Comparable interface and must be mutually comparable (that is, e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the list). The specified list must be modifiable, but need not be resizable.

There are two implementations in Collections class for this operation: 1) Collections.sort(List<T> list) 2) Collections.sort(List<T> list, Comparator<? super T> c) - Sorts the specified list according to the order induced by the specified comparator. Parameters: list - the list to be sorted. c - the comparator to determine the order of the list. A null value indicates that the elements' natural ordering should be used. Throws: ClassCastException - if the list contains elements that are not mutually comparable using the specified comparator. UnsupportedOperationException - if the specified list's list-iterator does not support the set operation. IllegalArgumentException - (optional) if the comparator is found to violate the Comparator contract

shuffle randomly changes the elements in a specified List using a default source of randomness. All permutations occur with approximately equal likelihood. There are two implementations in Collections class for this operation: 1)Collections.shuffle(List<?> list) 2) Collections.shuffle(List<?> list, Random rnd)

These implementations traverse the list backwards, from the last element up to the second, repeatedly swapping a randomly selected element into the "current position". Elements are randomly selected from the portion of the list that runs from the first element to the current position, inclusive. If the specified list does not implement the RandomAccess interface and is large, these implementations dump the specified list into an array before shuffling it, and dump the shuffled array back into the list. These methods runs in linear time. Parameters: list - the list to be shuffled. rnd - the source of randomness to use to shuffle the list. Throws: UnsupportedOperationException - if the specified list or its list-iterator does not support the set operation.

reverse reverses the order of the elements in a List. This method runs in linear time. Use method: Collections.reverse(List<?> list) Parameters: list - the list whose elements are to be reversed. Throws: UnsupportedOperationException - if the specified list or its list-iterator does not support the set operation.

rotate rotates the elements in a List by a specified distance. Use Method: Collections.rotate(List<?> list, int distance) Parameters: list - the list to be rotated. distance - the distance to rotate the list. There are no constraints on this value; it may be zero, negative, or greater than list.size(). Throws: UnsupportedOperationException - if the specified list or its list-iterator does not support the set operation.

swap swaps the elements at specified positions in the given List. Use Method: Collections.swap(List<?> list, int i, int j) Parameters: list - The list in which to swap elements. i - the index of one element to be swapped. j - the index of the other element to be swapped. Throws: IndexOutOfBoundsException - if either i or j is out of range (i < 0 || i >= list.size() || j < 0 || j >= list.size()).

replaceAll replaces all occurrences of one specified value in the list with another new value, such that (oldVal==null ? e==null : oldVal.equals(e)). Use Method: Collections.replaceAll(List<T> list,T oldVal,T newVal) Parameters: list - the list in which replacement is to occur. oldVal - the old value to be replaced. newVal - the new value with which oldVal is to be replaced. Returns: true if list contained one or more elements e such that (oldVal==null ? e==null : oldVal.equals(e)). Throws: UnsupportedOperationException - if the specified list or its list-iterator does not support the set operation.

fill replaces all elements in a List with the specified element. Use Method: Collections.fill(List<? super T> list, T obj):- This method runs in linear time. Parameters: list - the list to be filled with the specified element. obj - The element with which to fill the specified list. Throws: UnsupportedOperationException - if the specified list or its list-iterator does not support the set operation.

copy Copies all of the elements from source List into the destination List. After successful copy, the index of each copied element in the destination list will be identical to its index in the source list. The destination list must be at least as long as the source list else "IndexOutOfBoundsException" will be thrown. If it is longer, the remaining elements in the destination list are unaffected. Use Method: Collections.copy(List<? super T> dest, List<? extends T> src) :- This method runs in linear time. Parameters: dest - The destination list. src - The source list. Throws: IndexOutOfBoundsException - if the destination list is too small to contain the entire source List. UnsupportedOperationException - if the destination list's list-iterator does not support the set operation.

binarySearch searches for the specified element in the given ordered List using the binary search algorithm. The specified list must be sorted into ascending order according to the natural ordering of its elements before executing this method. If it is not sorted, the results are undefined. If the list contains multiple elements equal to the specified object, there is no guarantee which one will be found. Use Method: Collections.binarySearch(List<? extends Comparable<? super T>> list, T key) Parameters: list - the list to be searched. key - the key to be searched for. Returns: the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found. Throws: ClassCastException - if the list contains elements that are not mutually comparable (for example, strings and integers), or the search key is not mutually comparable with the elements of the list.

indexOfSubList returns the index of the first occurrence of the specified target list within the specified source list, or -1 if there is no such occurrence. Use Method: Collections.indexOfSubList(List<?> source, List<?> target) Parameters: source - the list in which to search for the first occurrence of target. target - the list to search for as a subList of source. Returns: the starting position of the first occurrence of the specified target list within the specified source list, or -1 if there is no such occurrence.

lastIndexOfSubList returns the index of the last occurrence of the specified target list within the specified source list, or -1 if there is no such occurrence. Use Method: Collections.lastIndexOfSubList(List<?> source, List<?> target) Parameters: source - the list in which to search for the last occurrence of target. target - the list to search for as a subList of source. Returns: the starting position of the last occurrence of the specified target list within the specified source list, or -1 if there is no such occurrence.


Finally final few general points:

  • Lists that guarantee that their size remains constant even though the elements may change are referred to as fixed-size. Lists that are not fixed-size are referred to as variable-size.
  • Lists that support fast (generally constant time) indexed element access are known as random access lists. Lists that do no support fast indexed element access are known as sequencial access lists. Any List implementation class implementing "RandomAccess" marker interface are random access lists.

List implementations are grouped into general-purpose and special-purpose implementations. There are two general-purpose List implementations - ArrayList, which is usually the better-performing implementation, and the LinkedList. CopyOnWriteArrayList is a special-purpose List implementation backed up by a copy-on-write array.





blog comments powered by Disqus