LinkedList and ArrayList

Array List	Linked List
1) ArrayList implements it with a dynamically re-sizing array.	1)  LinkedList implements it with a doubly-linked list.
2) There is no descendingIterator() in ArrayList , so we need to write our own code to iterate over the ArrayList in reverse direction.	2) LinkedList can be iterated in reverse direction using descendingIterator()
3) If the constructor  is not overloaded , then ArrayList creates an empty list of initial capacity 10	3) LinkedList only constructs the empty list without any initial capacity.
4) In ArrayList each index only holds the actual object(data).	4) Memory overhead in LinkedList is more as LinkedList needs to maintain the addresses of next and previous node.
5) Performance get(int index) is O(1) <--- main benefit of ArrayList<E> add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied. add(int index, E element) is O(n - index) amortized, but O(n) worst-case (as above) remove(int index) is O(n - index) (i.e. removing last is O(1)) Iterator.remove() is O(n - index) ListIterator.add(E element) is O(n - index)	5) Performance get(int index) is O(n) add(E element) is O(1) add(int index, E element) is O(n) remove(int index) is O(n) Iterator.remove() is O(1) <--- main benefit of LinkedList<E> ListIterator.add(E element) is O(1) <--- main benefit of LinkedList<E>

When to Use ArrayList and LinkedList :

In real world applications, you will more frequently use ArrayList than LinkedList. But in very specific situations LinkedList can be preferred.

1. ArrayList is preferred when there are more get(int) or search operations need to be performed as every search operation runtime is O(1).

2. If application requires more insert(int), delete(int) operations then the get(int) operations then LinkedList is preferred as they do not need to maintain back and forth like arraylist  to preserve continues indices.

public class ArrayLinkedList {

    public static void main(String[] args) {

           /*

            * transient Object[] elementData=                     DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //

            * non-private to simplify nested class access private static final

            * Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

            * Constructs an empty list with an initial capacity of 10.

            */

           ArrayList arrayList = new ArrayList();

           arrayList.add("Life is Awesome");

           arrayList.add("Intern is a good movie");

          

           // Doubly LInked list implemented and not singly implemented

           LinkedList<String> linkedList = new LinkedList<String>();

           linkedList.add("Life is Awesome");

           linkedList.add("Intern is a beautiful movie");

         

           System.out.println("ArrayList is "+ arrayList);

           System.out.println("LinkedList is "+ linkedList);

    }

}

Output:

ArrayList is [Life is Awesome, Intern is a good movie]

LinkedList is [Life is Awesome, Intern is a beautiful movie]