The Java List Interface, Implementations and Examples

List interface is an ordered collection (sometimes called a sequence). Lists can contain duplicate elements. The user of a List interface generally has precise control over where in the each list element is inserted and can access elements by their integer index (position).

Additional Operations Supported by “List” Interface over “Collection”

The additional operations supported by List interface over Collection interface are:

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.
Iteration extends Iterator semantics to take advantage of the sequential nature of the list.
Range-view performs arbitrary range operations on the list.

public interface List<E> extends Collection<E> {

   // Positional access
   E get(int index);
   E set(int index, E element); //optional operation
   boolean add(E element); //optional operation
   void add(int index, E element); //optional operation
   E remove(int index); //optional operation
   boolean addAll(int index, Collection<? extends E> c); //optional operation

   // Search
   int indexOf(Object o);
   int lastIndexOf(Object o);

   // Iteration
   ListIterator<E> listIterator();
   ListIterator<E> listIterator(int index);

   // Range-view
   List<E> subList(int from, int to);

}

Implementations of List Interface

ArrayList:

ArrayList is resizable-array implementation of the List interface. It implements all optional list operations and permits all elements and even allows NULL. And it is more or less equal to Vector, except that it is not synchronized. To prevent accidental unsynchronized access to the ArrayList you need to do the following during creation time.

List list = Collections.synchronizedList(new ArrayList(...));

Here are some highlights about ArrayList:

Offers constant-time positional access
Gives you fast iteration and fast random access
It is an ordered collection (by index), but not sorted.
Most commonly used implementation.

LinkedList:

Linked list is a linear collection of data elements. It is a data structure consisting collection of nodes represented in sequence. Each nodes contains two members: data and reference. Reference is nothing but a link to the next node in the sequence.

This data structure allows to efficiently insert or remove elements from any position in the sequence during iteration.

Here are some highlights about Linked List:

The access time is linear.
Faster access, such as random access is not feasible.
The principal benefit of linked list over a conventional array is that they are dynamic i.e., the list elements can be easily inserted or removed without reallocation or reorganization of entire structure.

Example : List Interface and ArrayList

package com.sneppets.corejava.collections;

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

/**
 * Program to demonstrate List Implementation ArrayList
 * @author sneppets.com
 */
public class ListInterfaceArrayListExample {
	
	public static void main (String[] args)
	{		
		List<String> al = new ArrayList<String>();
		al.add("AB");
		al.add("BC");
		al.add("CD");
		al.add("DE");
		
		// 1. positional access
		System.out.println("Element at index 1 -> " + al.get(1));
		
		// 2. search
		System.out.println("Index of element 'CD' -> " + al.indexOf("CD"));
		
		// 3. Iteration
		ListIterator<String> itr = al.listIterator();
		System.out.println("Elements in the forward direction");
		while(itr.hasNext())
		{
			System.out.println(itr.next());
		}
		System.out.println("Elements in the backward direction");
		while(itr.hasPrevious())
		{
			System.out.println(itr.previous());
		}
		
		// 4. Range-View
		System.out.println("Sublist from index 1 to 3 -> " + al.subList(1, 3));
		
	}

}

Output

Element at index 1 -> BC

Index of element 'CD' -> 2

Elements in the forward direction
AB
BC
CD
DE

Elements in the backward direction
DE
CD
BC
AB

Sublist from index 1 to 3 -> [BC, CD]

ListIterator Interface

ListIterator interface is an iterator for lists that allows to traverse the list in either direction. A list iterator has no current element and its cursor position always lies between the elements. So an iterator for a list of length n has n+1 possible cursor positions as shown below.

                      Element(0)   Element(1)   Element(2)   ... Element(n-1)
 cursor positions:  ^            ^            ^            ^                  ^

Example: LinkedList

package com.sneppets.corejava.collections;

import java.util.LinkedList;

/**
 * Program to demonstrate List Implementation LinkedList
 * @author sneppets.com
 */
public class ListInterfaceLinkedListExample {
	
	public static void main(String[] args)
	{
		LinkedList<String> ll = new LinkedList<String>();
		ll.add("AB");
		ll.add("BC");
		ll.add("CD");
		ll.add("DE");
		
		//display linked list content
		System.out.println("Linked List Content: " + ll);
		
		//positional access
		System.out.println("Element at index 1 -> " + ll.get(1));
		
		//add last element
		System.out.println("Inserting new elements in the begining and end...");
		ll.addFirst("AA");
		ll.addLast("EE");
		
		//display linked list content
		System.out.println("Linked List Content: " + ll);
		
		//positional access
		System.out.println("Element at index 1 -> " + ll.get(1));
	}

}

Output

Linked List Content: [AB, BC, CD, DE]

Element at index 1 -> BC

Inserting new elements in the begining and end...

Linked List Content: [AA, AB, BC, CD, DE, EE]

Element at index 1 -> AB

Related Posts

Reference

Oracle Documentation