What are Lists?
The java.util.List interface is a subtype of the
java.util.CollectionThe 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
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 ofLinkedList<E>ListIterator.add(E element)is O(1) <--- main benefit ofLinkedList<E>
ArrayList<E>get(int index)is O(1) <--- main benefit ofArrayList<E>add(E element)is O(1) amortized, but O(n) worst-case since the array must be resized and copiedadd(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)
- void add(int index,E obj)
- boolean addAll(int index, Collection c)
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)
- ListIterator listIterator( )
- ListIterator listIterator(int 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.
.jpg)
.jpg)
