List Interface and implementations

List

1. It is the child interface of Collection.
2. It allows duplicate insertions
3. Insertion order is preserved
4. Most of methods based on index, so index play main role in List

Methods of List

1. void add( int index, Object o)
2. boolean addAll(int index, Collection c)
3. object get (int index)
4. object remove(int index)
5. object set(int index, Object new)
6. int indexOf(Object o)
7. int lastIndexOf(object o)
8. ListIterator listIterator();

 Note: - With these methods collection method is also available as it is extending Collection(Interface).

There are 3 implementation of List interface

1. ArrayList
2. LinkedList
3. Vector

Note: - Stack is child class of Vector.

ArrayList

1. Resizable or grow able Array
2. Duplicates are allowed
3. Insertion order is preserved
4. Heterogeneous objects are allowed
5. Null insertion is possible.
6. Insertion/Deletion in between of Arraylist then ArrayList is worst option, because it need to rearrange all element i.e need to shift all element.
7. Using RandomAccess interface(marker Interface) which allow to fast retrieval.
8. Initial capacity is 10, when next element(i.e 11^th element) is coming it grows to 10*1.5+1.

NewCApacity = currentCapacity * 1.5 +1.

From java doc: - RandomAccess Interface is marker interface used by List implementations to indicate that they support fast (generally constant time) random access.  The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

Constructor of arraylist

1. public ArrayList();

 // Constructs an empty list with an initial capacity of ten.

2. public ArrayList(int initialCapacity);

1. Constructs an empty list with the specified initial capacity.

       2. initialCapacity  the initial capacity of the list @throws 

  IllegalArgumentException if the specified initial capacity is negative

3. public ArrayList(Collection<? extends E> c)

1. Constructs a list containing the elements of the specified      

collection, in the order they are returned by the collection's iterator.

       2. c the collection whose elements are to be placed into this list  

          throws NullPointerException if the specified collection is null

             

Notes: -

1. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list.
2. This class is roughly equivalent to Vector, except that it is unsynchronized.
3. The size, isEmpty, get, set, iterator, and listIterator operations run in constant time.
4. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time.
5. All of the other operations run in linear time (roughly speaking).
6. The constant factor is low compared to that for the LinkedList implementation.
7. Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size.
8. An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.
9. Note that this implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list. If no such object exists, the list should be "wrapped" using the Collections.synchronizedList method. This is best done at creation time, to prevent accidental unsynchronized access to the list:

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

LinkedList

1. Doubly-linked list implementation of the List and Deque interfaces.
2. Implements all optional list operations
3. Permits all elements (including null).
4. Insertion order is preserved
5. Duplicates are allowed.
6. Hetrogeneouse Objects are allowed(if not using generic)
7. Implements Serializable and clonable too
8. Best option if frequent operation is Insertion and deletion in the middle.
9. Worst choice if frequent operation is retrieval (Because it is retrieve object by navigating one by one i.e if we need to get 5^th element then it will go from 0^th element to 5^th element)

Methods other than Lists

1. Void addFirst();
2. void addLast()
3. Object getFirst();
4. Object getLast();
5. Object removeFirst();
6. Object removeLast();

  

Constructors

1. public LinkedList() // Constructs an empty list.
2. public LinkedList(Collection<? extends E> c)

 1. Constructs a list containing the elements of the specified collection, in the order they     are returned by the collection's iterator.

2. c the collection whose elements are to be placed into this list @throws         

    NullPointerException if the specified collection is null

   

Vector

1. It is thread safe
2. Resizable or grow able Array
3. Duplicates are allowed
4. Insertion order is preserved
5. Heterogeneous objects are allowed
6. Null insertion is possible.
7. Insertion/Deletion in between of Arraylist then ArrayList is worst option, because it need to rearrange all element i.e need to shift all element.
8. Using RandomAccess interface(marker Interface) which allow to fast retrieval.
9. Initial capacity is 10, when next element(i.e 11^th element) is coming it grows to 10*2.

NewCapacity = currentCapacity * 2

  

Methods other than List/Collection Interface

1. addElement (object o)
2. removeElement(Object o)
3. removeElementAt(int index)
4. removeAllElements()
5. Object elementAt(int index)
6. Object firstElement()
7. Object lastElement()
8. Int size()
9. Int capacity
10. Enumeration elements()

Constructors

1. public Vector()
2. public Vector(int initialCapacity)
3. public Vector(Collection<? extends E> c)
4. public Vector(int initialCapacity, int capacityIncrement)

As capacity of vector is filled then it’s capacity get doubled, but this constructor variable capacityIncrement  tell how much capacity to increase.

Suppose vector capacity is 2000 and it is full then new capacity will be 2000+ capacityIncrement.