Differences and Similarities between ArrayList and LinkedList in java
It’s very important to differentiate between java.util.ArrayList and java.util.LinkedList, so in this Collection framework tutorial we will learn what are differences and similarities between java.util.ArrayList and java.util.LinkedList in java.
Differences between java.util.ArrayList and java.util.LinkedList in java >

Property
java.util.ArrayList
java.util.LinkedList
1
Structure
java.util.ArrayList is index based structure in java.

A java.util.LinkedList is a data structure consisting of a group of nodes which together represent a sequence.
node is composed of a data and a reference (in other words, a link) to the next node in the sequence in java.

2
Resizable
ArrayList is Resizable-array in java.
New node is created for storing new element in LinkedList in java.
3
Initial capacity
java.util.ArrayList is created with initial capacity of 10 in java.
For storing every element node is created in LinkedList, so linkedList’s initial capacity is 0 in java.
4
Ensuring Capacity/ resizing.
ArrayList is created with initial capacity of 10.
ArrayList’s size is increased by 50% i.e. after resizing it’s size become 15 in java.
For storing every element node is created, so linkedList’s initial capacity is 0, it’s size grow with addition of each and every element in java.
5
RandomAccess interface
ArrayList implements RandomAccess(Marker interface) to indicate that they support fast random access (i.e. index based access) in java.
LinkedList does not implement RandomAccess interface in java.
6
AbstractList and AbstractSequentialList
ArrayList extends AbstractList (abstract class) which provides implementation to  List interface to minimize the effort required to implement this interface backed by RandomAccess interface.
LinkedList extends AbstractSequentialList (abstract class), AbstractSequentialList extends AbstractList.
In LinkedList, data is accessed sequentially, so for obtaining data at specific index, iteration is done on nodes sequentially in java.
7
How get(index) method works?
(Though difference has been discussed briefly in above 2 points but in this in point we will figure difference in detail.)
Get method of ArrayList directly gets element on specified index. Hence, offering O(1) complexity in java.
Get method of LinkedList iterates on nodes sequentially to get element on specified index. Hence, offering O(n) complexity in java.
8
When to use
Use ArrayList when get operations is more frequent than add and remove operations in java.
Use LinkedList when add and remove operations are more frequent than get operations in java.
9
Complexity offered by methods are different

Operation/ method
Worst case
Best case
add
O(n), when array is full it needs restructuring,
operation runs in amortized constant time in java.
O(1), when array does not need any restructuring in java.
remove
O(n), when removal is done from between restructuring is needed.
O(1), when removal is done at last position, no restructuring is needed.
get
O(1), it is index based structure. So, complexity of  get operation is always done in O(1) in java.
O(1) it is index based structure. So, complexity of  get operation is always done in O(1) in java.
set
O(1), it is index based structure, no restructuring is needed in set operation. So, complexity of operation is always O(1)
O(1), it is index based structure, no restructuring is needed in set operation. So, complexity of operation is always O(1)
iterator
O(n), because iteration is done over each and every element in java.
O(n), because iteration is done over each and every element in java.
listIterator
O(n), its same as iterator in java.
O(n), its same as iterator in java.
enumeration
O(n), its same as iterator in java.
O(n), its same as iterator in java.



Operation/ method
Worst case
Best case
add(E element)
O(1), Adds specified element to the end of LinkedList in java.
O(1), Adds specified element to the end of LinkedList in java.
add(int index, E element)
O(n), because iteration is done on all elements one by one to find out specified index.
Current element is placed at specified index and one is added to indices of subsequent elements on right in java.
O(n)
addFirst(E element)
O(1)
O(1)
addLast(E element)
O(1)
O(1)



remove()
O(1), Method retrieves and removes the first element (head) of this list in java.
O(1)
remove(int index)
O(n), because iteration is done on all elements one by one to find out specified index.
one is subtracted from indices of subsequent elements on right.
O(n)
remove(Object object)
O(n), because iteration is done on all elements one by one to find out specified object.
one is subtracted from indices of subsequent elements on right.
O(n)
removeFirst()
O(1)
O(1)
removeLast()
O(1)
O(1)
iterator
O(n), because iteration is done over each and every element.
O(n), because iteration is done over each and every element.
listIterator
O(n), its same as iterator in java.
O(n), its same as iterator in java.
enumeration
O(n), its same as iterator in java.
O(n), its same as iterator in java.



So far we have learned what are differences between ArrayList and LinkedList in java. Now we will learn similarities in ArrayList and LinkedList in Collection framework in java.
Similarity in java.util.ArrayList and java.util.LinkedList in java >

Property
java.util.ArrayList and java.util.LinkedList
1
synchronization
ArrayList and LinkedList both are not synchronized  (because 2 threads on same ArrayList/LinkedList object can access it at same time) in java.

I have created program to show see consequence of using ArrayList in multithreading environment.
In the program i will implement our own arrayList in java.
2
Iterator and listIterator are Fail-fast
Iterator and listIterator returned by ArrayList and LinkedList both are Fail-fast in java.
3
Enumeration is fail-fast
Enumeration of ArrayList and LinkedList both is fail-fast, means any modification made to ArrayList during iteration using Enumeration will throw ConcurrentModificationException in java.

Example/Code to throw ConcurrentModificationException in ArrayList (we may replace arrayList with linkedList )-
Enumeration<String> listEnum= Collections.enumeration(arrayList);
   while(listEnum.hasMoreElements()){
//adding element will throw   ConcurrentModificationException        System.out.println(listEnum.nextElement());
}

4
Insertion order
ArrayList and LinkedList both maintains insertion order in java.
5
Allows null
ArrayList and LinkedList both allows to store null in java.
6
Implements java.util.List
ArrayList and LinkedList both are implementation of the java.util.List interface.
7
Introduced in which java version
ArrayList and LinkedList both were introduced in second version of java (1.2) i.e. JDK 2.0


So in this Collection framework tutorial we learned what are important differences and similarities between java.util.ArrayList and java.util.LinkedList in java.


/** Copyright (c), AnkitMittal JavaMadeSoEasy.com */


Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.


RELATED LINKS>

ArrayList in java
Collection hierarchy >

List hierarchy in java - Detailed - ArrayList, LinkedList, vector, CopyOnWriteArrayList classes
Important Similarity and Differences >
List Differences >

ArrayList vs LinkedList - Similarity and Differences in java

ArrayList vs Vector - Similarity and Differences in java

List vs Set - Similarity and Differences in java

Collection vs Collections - Differences in java

List hierarchy tutorial in java - Detailed - java.util.ArrayList, java.util.LinkedList, java.util.vector, java.util.concurrent.CopyOnWriteArrayList classes



Important Similarity and Differences Collection classes in concurrent and non-concurrent packages >

ArrayList vs CopyOnWriteArrayList in java - Similarity and Differences with program

eEdit
Must read for you :