ArrayList underlying implementation is based on Traditional Array data structure. Read Arrays in Java , for details on Arrays.
This post focuses on internal working of ArrayList and LinkedList Collections.
java.util.ArrayList class, is internally implemented as array.
What is array data structure?
An Array is a simplest data structure, which stores same type of elements, sequentially in memory.
Advantage of array
Accessing an element is very fast. Since base address of array is known, the required element which need to be fetched, can be retrieved, just by doing some manipulations on base address.
Disadvantage of array
Adding an element in between or in the beginning is very slow. Reason is, other existing elements need to be moved right by one position, and new element can be added, to the free slot created. This hits performance of program, and hence it is not recommendable to use Arrays for such situations.
java.util.LinkedList class is internally implemented using linked list data structure.
What is linked list data structure
linked list is a data structure, whose elements are not stored sequentially in memory, and are scattered in the memory. As shown in below picture, each node has Element, and reference to next and previous nodes.
Advantage of link list data structure
An element can be added any where in between, just by changing previous and next references, as shown in below picture. This operation is slow in an array, as briefed above in array section.
Size of linked list can shrink or increase, during run time, based on the requirement.
Disadvantage of link list data structure
To Access an element, all elements need to be traversed, until the specific required element is reached. Hence searching an element is slower.
Another disadvantage of linked list is, there will be wastage of small memory, since each node need to store references to previous and next nodes.