A List is an ordered collection of elements (also known as sequence). List interface implements Collection interface. Lists can store duplicate elements and allows indexed access to its element.
ArrayList and LinkedList are two classes of the Java Collection Framework used for storing lists of object references.
List arr = new ArrayList();
List ll = new LinkedList();
ArrayList is a resizable-array implementation of the List interface.
LinkedList is a doubly linked list implementation of the List interface.
Random access in an ArrayList has a fixed time where as in LinkedList time to do a random access is proportional to the size of the list.
LinkedList does not implements the RandomAccess interface, where as ArrayList implements the RandomAccess interface.
Time Complexity of various operations:
Adding (or removing) an element in an ArrayList involves moving of all the existing elements back (or forward) by one place requiring lot of copying and has a cost that’s proportional to the list size.
Adding (or removing) an element in a LinkedList means allocating (or deallocating) an internal record for the element and then realigning a couple of links and has a fixed cost.
Appending an element to an ArrayList typically involves setting an internal array location to the element reference, but occasionally results in the array being reallocated and has a fixed averaged cost.
Appending an element to a LinkedList just involves allocating an internal object and the cost is uniform.
An ArrayList has space overhead as the list of objects has to be preallocated which means empty elements at the end of the list.
A LinkedList has space overhead for storing the references to the previous and next element in the list for every element.
Consider the following code examples for traversing a LinkedList:
the above code example would be would be very slow as LinkedList does not support random access and there is a huge overhead while travesing for each iteration.
Better approach would be to used the following code instead for improved performance.