Collections - Linked List vs Arrays and ArrayLists

Memory allocation

For Arrays and ArrayLists, the memory allocation is contiguous - which is why they can have indexes. For LinkedLists, the memory allocation is random.

Inserting or removing an element at the beginning of an array or an arraylist

 ┌─┐┌─┐┌─┐┌─┐┌─┐
 │3││7││2││1││8│
 └─┘└─┘└─┘└─┘└─┘

// Adding an element at index 0
arraylist.add(0, 5);
// All the elements have to be re-indexed again.

// Remove an element at index 0
arraylist.remove(0)  ;
// All the elements have to be re-indexed again.

Why insertion and deletion in ArrayList is slow compared to LinkedList ?

1. ArrayList internally uses an array to store the elements, when that array gets filled by inserting elements a new array of roughly 1.5 times the size of the original array is created and all the data of old array is copied to new array.
2. During deletion, all elements present in the array after the deleted elements have to be moved one step back to fill the space created by deletion.
3. In linked list, data is stored in nodes that have reference to the previous node and the next node so adding element is simple as creating the node an updating the next pointer on the last node and the previous pointer on the new node.
4. Deletion in linked list is fast because it involves only updating the next pointer in the node before the deleted node and updating the previous pointer in the node after the deleted node.

Linked List vs Arrays and ArrayLists

1. Since Array is an index based data-structure searching or getting element from Array with index is pretty fast. Array provides O(1) performance for get(index) method but remove is costly in ArrayList as you need to rearrange all elements. On the Other hand LinkedList doesn’t provide Random or index based access and you need to iterate over linked list to retrieve any element which is of order O(n).
2. Insertions are easy and fast in LinkedList as compared to ArrayList because there is no risk of resizing array and copying content to new array if array gets full which makes adding into ArrayList of O(n) in worst case, while adding is O(1) operation in LinkedList in Java. ArrayList also needs to update its index if you insert something anywhere except at the end of array.
3. Removal is like insertions. Better in LinkedList than ArrayList.
4. LinkedList has more memory overhead than ArrayList because in ArrayList each index only holds actual object (data) but in case of LinkedList each node holds both data and address of next and previous node.

Operations Provided	ArrayList Efficiency	LinkedList Efficiency
Random access	O(1)	O(n)
Add/remove at beginning	O(n)	O(1)
Add/remove at end	amortized O(1), worst O(n)	O(1)
Add/remove at iterator location	O(n)	O(1)

1. If you need to support random access, without inserting or removing elements from any place other than the end, then ArrayList offers the optimal collection. However, if you need to frequently add and remove elements from the middle of the list and only access the list elements sequentially, then LinkedList offers the better implementation.
2. Main difference between ArrayList and LinkedList is that ArrayList is implemented using resizable array while LinkedList is implemented using doubly LinkedList. ArrayList is more popular among Java programmer than LinkedList as there are few scenarios on which LinkedList is a suitable collection than ArrayList.

When to use LinkedList and ArrayList in Java

LinkedList is not as popular as ArrayList but still there are situation where a LinkedList is better choice than ArrayList in Java. Use LinkedList in Java if:

1. Your application can live without Random access. Because if you need nth element in LinkedList you need to first traverse up to nth element O(n) and you get data from that node.
2. Your application is more insertion and deletion driver and you insert or remove more than retrieval. Since insertion or removal doesn’t involve resizing its much faster than ArrayList.
3. Use ArrayList in Java for all the situations where you need a non-synchronized index based access. ArrayList is fast and easy to use, just try to minimize array resizing by constructing arraylist with proper initial size.
4. All the differences between LinkedList and ArrayList has their roots on difference between Array and LinkedList datastructure.