LinkedList implements both List and Deque. It uses doubly-linked list data structure internally to store the elements. Like an ArrayList, LinkedList also allows duplicate elements and also it is not thread-safe.
A doubly linked list is composed of Nodes.A node has three things:
1.Previous Node Reference
2.Value
3.Next Node Reference
Elements can be added from both the ends.
LinkedList vs ArrayList vs Vector
ArrayList is implemented as a resizable array. It’s performance is good on get and set operations.
LinkedList is implemented as a doubly linked list. Its performance on add and remove is better than Arraylist, but worse on get and set operations.
Adding an element in an ArrayList takes more time than LinkedList as it may cause resizing of the internal array in case the number of elements in the ArrayList becomes more than the current capacity of the ArrayList.
Also adding elements in the start or middle of the ArrayList causes shifting of the elements to the right after the added element.Removing an element from the start or middle of an ArrayList also causes shifting of the elements to the left.
Searching with index is faster with ArrayList as it fetches the element directly from the internal array by using the index.In LinkedList we have to traverse upto the index starting from the head. So Random access is much faster (O(1)) in ArrayList whereas it is slow in LinkedList(O(n)).
Vector is similar with ArrayList, but it is synchronized. So operations are on Vector are much slower than ArrayList.