Skip to Content

ArrayList or LinkedList ..??

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.

Be the first to leave a comment
You must be Logged on to comment or reply to a post.