Introduction:

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.

Construct a LinkedList:

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:

• LinkedList(): creates an empty linked list
• LinkedList(Collection c): creates a linked list and initializes it with the contents of c as its elements

Adding Elements:

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]

Removing Elements:

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);

Querying Elements:

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);

Iterating over a LinkedList:

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); );

LinkedList vs ArrayList:

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 and Deque interfaces	Only implements List interface
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.

Conclusion:

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.