ArrayList vs LinkedList

• Both ArrayList and Vector use array to store the elements
• ArrayList implements the RandomAccess interface, and LinkedList does not. The commonly used ArrayList implementation uses array for internal storage. Therefore an ArrayList is much faster than a LinkedList for random access, that is, when accessing arbitrary list elements using the get method.
• Adding and deleting at the start and middle of the ArrayList is slow, because all the later elements have to be copied forward or backward using System.arrayCopy(). But Linked lists are faster for inserts and deletes anywhere in the list, since all you do is update a few next and previous pointers of a node.
• When an element is inserted into the middle of the list the elements that follow the insertion point must be shifted to make room for the new element. The LinkedList is implemented using a doubly linked list, an insertion requires only the updating of the links at the point of insertion. So, the LinkedList allows for fast insertions and deletions.
• Ie:- LinkedList is made up of a chain of nodes. Each node stores an element and the pointer to the next node. A singly linked list only has pointers to next. A doubly linked list has a pointer to the next and the previous element. This makes walking the list backward easier
• Each element of a linked list (especially a doubly linked list) uses a bit more memory than its equivalent in array list, due to the need for next and previous pointers.