Linkedlist in java

Java LinkedList
A LinkedList is a data structure or collection which is made up of different nodes. Each node holds an element as well as an address or reference to another node.
LinkedList are dynamically sized meaning they can grow or shrink in size as the elements are added or removed from them, unlike java arrays which have a fixed size.
Java LinkedList are doubly linked, which means that each node holds a reference to its next node as well as to its previous node.

First element of the list is called Head while the last element is called Tail. Previous reference of Head node and next reference of Tail node are null.
Implementation of a Java LinkedList is written as java.util.LinkedList class. This class provides methods to add, remove elements, update their value and iterate over the list.
We will look at all these methods in detail in this article.

Java LinkedList hierarchy
java.util.LinkedList implements List, Deque, Cloneable interfaces directly and extends AbstractSequentialList.
AbstractSequentialList extends AbstractList, which in turn, also implements List interface.
Complete class hierarchy of LinkedList class is shown in the image below.

Creating LinkedList
A LinkedList in java can be created using the constructor of LinkedList class as shown below.

This will create a LinkedList whose elements are of type String.
Another way to create a linked list is by using another constructor which takes a collection as argument.
So, if you have a List of string values, you can convert it to a LinkedList as below

Adding elements to Java LinkedList
java.util.LinkedList provides add() method to add an element to the linked list. add() method accepts an argument, which is the element to be added to the list.
Data type of the element should be the same as the data type of linked list, String in this case. Example,

LinkedList<String> list = new LinkedList<>();
list.add("a");
list.add("b");

add() will add the element to the end of the linked list.

Thus, add() method will simply create a new node, point its previous reference to the last list node and point the next reference of the last node to the new node as shown below.

There are two more methods to add an element to a linked list.

1. addFirst(E e)
This method accepts a value and adds it to the beginning of the list.
It creates a new node whose next reference points to the first list element and previous reference is null. Also, the previous reference of the first node(which was null earlier) now points to the new node.
2. addLast(E e)
This method creates a new node and adds it to the end of the list. It behaves similar to the add() method outlined above.
Add element example
Below is an example program of adding elements to a Java LinkedList.

// create a linked list
LinkedList<String> list = new LinkedList<>();
// add elements
list.add("a");
list.add("b");
list.add("c");
// add first element
list.addFirst("d");
System.out.println(list);

This prints

Notice how addFirst() adds the element at the start.

Remove from Java LinkedList
Removing an item(or node) from a linked list is simply updating the references of next and previous nodes.

So, to removing a node B requires following operations
1. Update the next reference of A to point to C. This was previously pointing to B.
2. Update the previous reference of C to point to A. This was previously pointing to B.
3. Set the element(or data) of the deleted node to null, just to help Garbage Collection.

Below image will clarify the concept.

Java LinkedList provides many methods to remove an element.
1. remove()
This method removes the first list node and returns its value.
Internally, the next reference of the first node and previous reference of the second node are set to null so that the first node is unlinked.
If the list is empty, it throws NoSuchElementException.

2. removeFirst()
Removes the first element from the list, works the same as remove().

3. removeLast()
Removes the last element from the list. This involves setting the next references of the previous(or second last) node to null.

4. remove(int index)
Removes the node at the given index. Nodes in a linked list are indexed with the first node having index 1, second as index 2 and so on.
If the index is negative or greater than the size of the list, IndexOutOfBoundsException is thrown.

5. remove(Object o)
This method takes a value and removes the node whose value matches with the supplied value. If the linked list is of user-defined objects such as Student, Cat, Apple etc., then the class must override equals() method for the object to be compared correctly.

6. removeFirstOccurrence(Object o)
Removes the first node whose item or data value matches with the argument object. It works the same as remove(Object o), explained above.
This method was added in java 1.6.

7. removeFirstOccurrence(Object o)
Removes the last node whose item or data value matches with the argument object. This method was added in java 1.6.
Remove element Example
Below is an example program of removing elements from a Java LinkedList.
Go through the code and output of this program to understand removal of elements.

List<String> l = List.of("a", "b", "c", "d", "e", "f", "d");
LinkedList<String> list = new LinkedList<>(l);
System.out.println("Original list");
System.out.println(list);
System.out.println("Removing first element");
// remove first element
list.remove();
System.out.println(list);
System.out.println("Removing element with index");
// remove second element
list.remove(1);
System.out.println(list);
System.out.println("Removing element with value");
// list element with value
list.remove("d");
System.out.println(list);
System.out.println("Removing last element");
// remove last element
list.removeLast();
System.out.println(list);
System.out.println("Removing first occurrence with value");
// remove first occurrence with value
list.removeFirstOccurrence("d");
System.out.println(list);

Below is the output

Fetch element from Java LinkedList
LinkedList provides following methods to get value of an element.
1. get(int index)
Provide the numeric index of the node. Index should be between 0 and total number of list elements, otherwise IndexOutofBoundsException will be thrown.

2. getFirst()
Returns the first element of linked list. Throws IndexOutofBoundsException if the list is empty.

3. getLast()
Returns the last element of linked list. Throws IndexOutofBoundsException if the list is empty.
Iterating Java LinkedList
LinkedList provides an iterator to loop over its elements. There are following ways to iterate over a Java LinkedList.
1. iterator()
This method returns java.util.Iterator. Its next() method returns the next list element.
Before invoking next(), it is suggested to check the presence of next element with hasNext() method since next() throws NoSuchElementException, if next element is not there. Example,

List<String> l = List.of("a", "b", "c", "d");
// create a linked list from collection
LinkedList<String> list = new LinkedList<>(l);
// get iterator
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
  System.out.print(iterator.next() + " ");
}

2. listIterator()
This method returns an instance of Java ListIterator. This is a child class of java.util.Iterator and allows traversing the list in both directions.
With iterator, a list can be traversed in a single direction. Example of listIterator is given below,

List<String> l = List.of("a", "b", "c", "d");
LinkedList<String> list = new LinkedList<>(l);
ListIterator<String> listIterator = list.listIterator();
System.out.println("Iterating forward");
while (listIterator.hasNext()) {
  System.out.print(listIterator.next()+" ");
}
System.out.println("\nIterating backward");
while (listIterator.hasPrevious()) {
  System.out.print(listIterator.previous()+" ");
}

3. splitIterator()
SplitIterator interface was introduced in java 8 and is mainly used in parallel processing but it can also iterate over the elements of a linked list using its forEachRemaining() method.
forEachRemaining() accepts an argument of type Java Consumer and performs the action defined in this consumer on each list element.
Since java.util.function.Consumer is a functional interface, we can pass its definition as a Lambda expression. In below example, we are printing the current list element.

List<String> l = List.of("a", "b", "c", "d");
// create linked list from a collection
LinkedList<String> list = new LinkedList<>(l);
// get split iterator
Spliterator<String> spliterator = list.spliterator();
// iterate over linked list
spliterator.forEachRemaining(e -> System.out.println(e));

forEachRemaining() is a default interface method. It throws NullPointerException, if the argument is null.

4. Enhanced for loop
Java enhanced for loop or for-each loop can be used for iteration of linked list as shown below.

List<String> l = List.of("a", "b", "c", "d");
LinkedList<String> list = new LinkedList<>(l);
for (String e : list) {
  System.out.println(e + " ");
}

5. forEach() java 8
Java 8 introduced forEach() method or loop to iterate over a collection. forEach() accepts a Consumer as argument and executes this consumer over each list element.
Since Consumer is a functional interface, it can be represented as a Lambda expression. Example,

List<String> l = List.of("a", "b", "c", "d"); 
LinkedList<String> list = new LinkedList<>(l); 
list.forEach(e -> System.out.print(e + " "));

forEach() is defined as a default method in Iterable interface.
Update Java LinkedList
Value of an element of a LinkedList can be modified using its set() method.

set() accepts two arguments:
1. Index of the element whose value needs to be updated.
2. New value to update.

set() returns the old value of the element at the specified index. It throws a IndexOutOfBoundsException, if the index is outside the range of list elements. Example,

List<String> l = List.of("a", "b", "c", "d");
LinkedList<String> list = new LinkedList<>(l);
System.out.println("List is: " + list);
// update second element
String old = list.set(1, "x");
System.out.println("Updated is: " + list);
System.out.println("Old value is: " + old);

This prints

Hope the article was useful !!