Base class: 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.
Similarity: ArrayList and LinkedList are two classes of the Java Collection Framework used for storing lists of object references.
Usage:
List arr = new ArrayList();
List ll = new LinkedList();
Implementation: ArrayList is a resizable-array implementation of the List interface.
LinkedList is a doubly linked list implementation of the List interface.
Random Access 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.
Space Complexity: 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.
Tips: 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.
