A LinkedList is a linear data-structure composed of nodes. In a singly linked list, each node contains data and a reference. Here, the reference-part refers to the next node in the linked list.
In a doubly linked list, on the other hand, we have data and references to both previous and next nodes. Java provides a LinkedList implementation – java.util.LinkedList<T>, which works with a doubly linked list. This class inherits from the AbstractList class and implements the List<T> and Deque<T> interfaces. In this quick tutorial, we’ll learn to work with the LinkedList class in Java.
We can instantiate a linked list in Java in one of the following ways:
LinkedList<Integer> intList = new LinkedList<>(); LinkedList<Integer> intList1 = new LinkedList<>(intList);
i.e. this class provides two constructors:
To add elements to a LinkedList, we can use the of the flavors of the add() method from the List<T> interface. We can also use addFirst() or the addLast() which adds an element to the beginning or to the end respectively.
intList.add(1); // [1] intList.addFirst(2); // [2, 1] intList.addLast(3); // [2, 1, 3]
On the similar lines, to remove an item, we can use remove(index), remove(obj) methods from the List interface. Or else, we can also opt for removeFirst() or a removeLast() method:
int firstElement = intList.removeFirst(); int lastElement = intList.removeLast();
These methods both removes as well as returns the removed value.
Java LinkedList class also provides removeFirstOccurrence(Object obj) and removeLastOccurrence(Object obj) methods to remove the first and last occurrence of a given value respectively. These methods return false if no such value exists in our list.
boolean removed = intList.removeFirstOccurrence(1);
We have getFirst() and getLast() methods in LinkedList class, to query the first or the last element of our linked list:
int firstElement = intList.getFirst(); int lastElement = intList.getLast();
Since it’s a doubly-linked list implementation, both getFirst() and getLast() are constant-time operations.
If we know the index of the element to be retrieved, we can also use the get(int index) method of the List interface:
int elementAtIndex1 = intList.get(1);
We’ll iterate over a linked list, just like any other form of a list:
//Using a for loop for(int num : intList) { System.out.println(num); } //Using iterator ListIterator itr = intList.listIterator(); while(itr.hasNext()) { System.out.println(itr.next()); } //Using forEach construct intList.forEach( value -> System.out.println(value); );
Let’s outline the differences between the Java LinkedList and ArrayList classes:
LinkedList | ArrayList |
---|---|
Uses a doubly-linked list representation | Uses the concept of dynamic arrays |
Implements both List | Only implements List |
Not suitable for random-access | Great for random-access. If we know the index, it takes only O(1) time for retrieval |
O(1) insertions/removals at the beginning and end of a java linkedlist | Insertion of elements in an ArrayList might lead to resizing of the backing array, and so has an amortized cost of O(n). Also, insertion at the beginning of an ArrayList will need us shift all elements to the right by one position. |
Memory overhead of storing references to the previous and the next node | No additional information needs to be stored |
Feel free to learn more about ArrayList in this article. All the methods in the ArrayList class inherited from the List<T> interface are also available in the Java LinkedList.
In this quick tutorial, we explored some of the most popular methods of Java LinkedList class. We also covered the difference between a Java ArrayList and LinkedList.