1. Introduction
LinkedList is a doubly-linked list implementation of the List and Deque interfaces. It implements all optional list operations and permits all elements (including null).
2. Features
Below you can find the most important properties of the LinkedList:
- Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index
- It is not synchronized
- Its Iterator and ListIterator iterators are fail-fast (which means that after the iterator’s creation, if the list is modified, a ConcurrentModificationException will be thrown)
- Every element is a node, which keeps a reference to the next and previous ones
- It maintains insertion order
Although LinkedList is not synchronized, we can retrieve a synchronized version of it by calling the Collections.synchronizedList method, like:
List list = Collections.synchronizedList(new LinkedList(...));
3. Comparison to ArrayList
Although both of them implement the List interface, they have different semantics – which will definitely affect the decision of which one to use.
3.1. Structure
An ArrayList is an index based data structure backed by an Array. It provides random access to its elements with a performance equal to O(1).
On the other hand, a LinkedList stores its data as a list of elements and every element is linked to its previous and next element. In this case, the search operation for an item has execution time equal to O(n).
3.2. Operations
The insertion, addition and removal operations of an item are faster in a LinkedList because there is no need to resize an array or update the index when an element is added to some arbitrary position inside the collection, only references in surrounding elements will change.
3.3. Memory Usage
A LinkedList consumes more memory than an ArrayList because of every node in a LinkedList stores two references, one for its previous element and one for its next element, whereas ArrayList holds only data and its index.
4. Usage
Here are some code samples that show how you can use LinkedList:
4.1. Creation
LinkedList<Object> linkedList = new LinkedList<>();
4.2. Adding Element
LinkedList implements List and Deque interface, besides standard add() and addAll() methods you can find addFirst() and addLast(), which adds an element in the beginning or the end, respectively.
4.3. Removing Element
Similarly to element addition this list implementation offers removeFirst() and removeLast().
Also, there is convenient method removeFirstOccurence() and removeLastOccurence() which returns boolean (true if collection contained specified element).
4.4. Queue Operations
Deque interface provides queue-like behaviors (actually Deque extends Queue interface):
linkedList.poll();
linkedList.pop();
Those methods retrieve the first element and remove it from the list.
The difference between poll() and pop() is that pop will throw NoSuchElementException() on empty list, whereas poll returns null. The APIs pollFirst() and pollLast() are also available.
Here’s for example how the push API works:
linkedList.push(Object o);
Which inserts the element as the head of the collection.
LinkedList has many other methods, most of which should be familiar to a user who already used Lists. Others that are provided by Deque might be a convenient alternative to “standard” methods.
The full documentation can be found here.
5. Conclusion
ArrayList is usually the default List implementation.
However, there are certain use cases where using LinkedList will be a better fit, such as preferences for constant insertion/deletion time (e.g., frequent insertions/deletions/updates), over constant access time and effective memory usage.
Code samples can be found over on GitHub.
