Familiarisation of java lists

 What are Lists?

The java.util.List interface is a subtype of the java.util.Collection interface.
The List interface extends Collection and declares the behavior of a collection that stores a sequence of elements.

• Elements can be inserted or accessed by their position in the list, using a zero-based index.
• A list may contain duplicate elements.
• In addition to the methods defined by Collection, List defines some of its own, which are summarized in the following below Table.
• Several of the list methods will throw an UnsupportedOperationException if the collection cannot be modified, and a ClassCastException is generated when one object is incompatible with another.

How to initialise?

Since List is an interface you need to instantiate a concrete implementation of the interface in order to use it. You can choose between the following List implementations in the Java Collections API:

• java.util.ArrayList
• java.util.LinkedList
• java.util.Vector
• java.util.Stack

We can instantiate lists with above as:

List<E> AL = new ArrayList<>();
List<E> LL= new LinkedList<>();
List<E> V = new Vector<>();
List<E> S = new Stack<>();

We should give the generic class otherwise there would be unchecked/unsafe operation error. generic classes can be any predefined or user defined classes.

As with standard linked list and array operations, the various methods will have different algorithmic runtimes.
For LinkedList<E>

• get(int index) is O(n)
• add(E element) is O(1)
• add(int index, E element) is O(n)
• remove(int index) is O(n)
• Iterator.remove() is O(1) <--- main benefit of LinkedList<E>
• ListIterator.add(E element) is O(1) <--- main benefit of LinkedList<E>

For ArrayList<E>

• get(int index) is O(1) <--- main benefit of ArrayList<E>
• add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
• add(int index, E element) is O(n - index) amortized, but O(n) worst-case (as above)
• remove(int index) is O(n - index) (i.e. removing last is O(1))
• Iterator.remove() is O(n - index)
• ListIterator.add(E element) is O(n - index)

How to add elements?

List interface supports these functions for adding elements

• void add(E obj)

  Adds objects to the end of the list.

• void add(int index,E obj)  

          Inserts obj into the invoking list at the index passed in index. Any pre-existing elements at or beyond the point of insertion are shifted up. Thus, no elements are overwritten.

• boolean addAll(int index, Collection c)

          Inserts all elements of c into the invoking list at the index passed in index. Any pre-existing elements at or beyond the point of insertion are shifted up. Thus, no elements are overwritten. Returns true if the invoking list changes and returns false otherwise.

 Here are a few examples:

List<Integer> AL = new ArrayList<>();
AL.add(0);
AL.add(5);//adding elements at the end of list
AL.add(1,4);// adding elements at a specified index
List<Integer> tmp = new LinkedList<>();
tmp.add(1);
tmp.add(2);
tmp.add(3);
AL.addAll(1,tmp);// adding an another collection

System.out.println(AL);
//Now the above statement yields output
[0, 1, 2, 3, 4, 5]

How to access elements?

The functions used to access elements are:

• E get(int index)

 Returns the object stored at the specified index within the invoking collection.

•  ListIterator listIterator( )

Returns an iterator to the start of the invoking list. 

• ListIterator listIterator(int index)

Returns an iterator to the invoking list that begins at the specified index.

  

The order in which the elements are added to the List is stored, so you can access the elements in the same order. You can do so using either the get(int index) method, or via the Iterator returned by the iterator() method. Here is how:

List listA = new ArrayList();

listA.add("element 0");
listA.add("element 1");
listA.add("element 2");

//access via index
String element0 = listA.get(0);
String element1 = listA.get(1);
String element3 = listA.get(2);


//access via Iterator
Iterator iterator = listA.iterator();
while(iterator.hasNext(){
  String element = (String) iterator.next();
}


//access via new for-loop
for(E object : listA) {
    String element = (String) object;
}

When iterating the list via its Iterator or via the for-loop (which also uses the 

Iterator behind the scene), the elements are iterated in the same sequence they 

are stored in the list. 
 

How to delete elements?

These functions are used to remove elements:

• remove(E element) 

remove(E element) removes that element in the list, if it is present. All subsequent elements in the list are then moved up in the list. Their index thus decreases by 1. 

• remove(int index)

remove(int index) removes the element at the given index. All subsequent elements in the list are then moved up in the list. Their index thus decreases by 1. 

How to delete elements?

The list elements can be changed by the function E set(int index, E element) which replaces the element at the specified position in this list with the specified element