Lists

1] ArrayList - This list implementation internally uses resizable arrays discussed earlier.Hence the elements of this list can be accessed using an index.Elements can be added, fetched or deleted from the list using index.

Performance impact -

1] Inserting/Deleting elements from the beginning or in the middle of the list (anywhere other than the last) would involve shifting of all the elements beginning from that position to the right/left as discussed earlier, for making room for the new element/removing the element.The shifting overhead grows significantly as the size of the collection increases because the number of elements that need to be copied with each insertion increases.Hence it would make sense to use some other implementation as this would take more time.

2] Fetching an element using an index is very fast as we already know the index of the element.

e.g. list.get(3) would fetch the third element directly from the underlying array.

Ordering -

The elements of the list are maintained in the insertion order.i.e. if the order of insertion is 1|2|3

then the order of the elements will also be the same i.e. 1|2|3.

Functionality -

This list implementation is not thread safe.Hence if this implementation is being shared and manipulated by multiple threads then there is a possibility of the list getting corrupted.Hence its advisable not to use this list as an instance variable in a class if multiple threads manipulate the list.

e.g. If there are two threads - one removing elements from the list and the other printing the elements of the list, then there is a possibility of ArrayIndexOutOfBound exception being thrown if one thread removes an element from the list when another is still printing the elements of the list.

However its possible to make this list thread safe by using the static utility methods present in the Collections class.We will look into this in future.

2] Vector - This list implementation internally also uses resizable arrays discussed earlier.Hence the elements of this list can be accessed using an index.Elements can be added, fetched or deleted from the middle of the list.

Performance impact -

1] Inserting/Deleting elements from the beginning or in the middle of the list would involve shifting of all the elements beginning from that position to the right/left as discussed earlier, for making room for the new element/removing the element.Hence it would make sense to use some other implementation as this would take more time.

2] Fetching an element using an index is very fast as we already know the index of the element.

e.g. list.get(3) would fetch the third element directly from the underlying array.

Ordering -

The elements of the list are maintained in the insertion order.i.e. if the order of insertion is 1|2|3

then the order of the elements will also be the same i.e. 1|2|3.

Functionality -

This list implementation is thread safe.Hence this implementation can be shared and manipulated by multiple threads without getting corrupted.Hence it can be used as an instance variable in a class if multiple threads manipulate the list.

3] LinkedList - This list implementation internally uses doubly linked list concept to store data.A linked list is basically a collection of nodes where each node contains two things - a) The data to be stored and b) The reference to the next node.So its kind of a chain.The nodes need not have sequential addresses like arrays. e.g. The first node contains "first" as the data part, stored at location address 1000 and the reference part contains the location of the next node which can be 5290 (and need not be 1001 as is the case in array). A doubly linked list on the other hand contains one more element that store a reference to the previous node.So it has the data,next node reference and previous node reference.

Performance impact -

1] Inserting/Deleting elements from the beginning or in the middle of the list would not involve shifting of all the elements as in the case of arrays.Here only the references needs to be re-referenced and pointed to the appropriate node.
2] The linked list suffers from performance overhead in case of indexed access.Since accessing an element at a particular index involves traversing multiple elements.Also adding elements to the collection suffers from the multiple node traversal access performance + further overhead in requiring to create a new node.So insertions-deletion overhead is mostly dependent on how far away the insertion-deletion index is from the ends of the collection.Hence its advisable to use this list when there are frequent insertions in the beginning or middle of a long list.

Ordering -

The elements of the list are maintained in the insertion order.i.e. if the order of insertion is 1|2|3

then the order of the elements will also be the same i.e. 1|2|3.

Functionality -

This list implementation is not thread safe.Hence extra care must be taken in case multiple threads are trying to manipulate the list.