While you may have heard of linked lists, many developers have very little idea how they work, much less how to use them in their programs. So let’s clear that up here. By the end of this Java programming tutorial, you will know about the different kinds of linked lists (yes, there are more than one type!), how they are implemented in Java, and how to work with them in your programs.
Types of Linked Lists in Java
At it’s most basic, a linked list is one whose nodes contain a data field as well as a “next” reference (link) to the next node in the list:
There are other kinds of linked lists, such as the Circular linked list, which is a singly linked list in which the last node and next field points back to the first node in the sequence. It’s like a repeating MP3 track list:
The Java LinkedList class uses a Doubly linked list to store the elements. The nodes of a doubly linked list also contain a “prev” link field that points to the previous node in the sequence. That allows traversal in both the forward and backward direction:
More on the LinkedList Class
The LinkedList class shares many features with the ArrayList. For example, both are part of the Collection framework and resides in java.util package. However, as an implementation of the LinkedList data structure, elements are not stored in contiguous locations and every element is a separate object containing both a data and an address component. Another distinguishing factor of the LinkedList is that its elements are referred to as nodes.
If programmers need to do a lot of insertions and deletions of elements/nodes, the LinkedList is preferrable to an array or ArrayList. The downside is that nodes cannot be accessed directly; instead Java needs to start from the head and follow through the link to reach the node we wish to access. That makes accessing specific nodes a time consuming process.
You can read more about ArrayList in our tutorial: Overview of Java ArrayList Class.
Here are a few more important features about the Java LinkedList to bear in mind:
- The LinkedList class can contain duplicate elements.
- The LinkedList class maintains insertion order.
- The LinkedList class is non synchronized.
- As explained above, manipulation is fast because no shifting needs to occur.
- The LinkedList class can be used as a list, stack or queue because the LinkedList class implements the List and Deque interfaces. The full class declaration shows why that is possible:
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable
How to Create a LinkedList in Java
There are two main ways to create linked lists in Java. The first is to use the no-argument constructor:
LinkedList<Type> linkedList = new LinkedList<>();
That creates an empty LinkedList that developers can then add nodes to:
import java.util.LinkedList;
public class Main
{
public static void main(String[] args) {
LinkedList<String> linkedNodes = new LinkedList<String>();
for (int i=1; i<=5; i++) {
linkedNodes.add("node"+i);
}
// Add a new item at the specified index
linkedNodes.add(1, "another node1");
System.out.println(The other option is to employ the constructor that accepts a Collection:
LinkedList<Type> linkedList = new LinkedList<>();
Here is an example Java Program that creates an array of strings and then converts it to a List. Since Lists implement the Collections interface, we can pass it to the LinkedList constructor:
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class Main {
// Main driver method
public static void main(String[] args)
{
// Create a string Array
String[] nodes = { "node1", "node2", "node3", "node4", "node5" };
// Convert array to list
List<String> nodesList = Arrays.asList(nodes);
// Create a LinkedList and
// pass List in LinkedList constructor
LinkedList<String> linkedList = new LinkedList<>(nodesList);
// Display and print all elements of LinkedList
System.out.println(linkedList)Read: Top Online Courses to Learn Java Programming
Working with Items of a LinkedList in Java
LinkedList provides several methods that allow programmers to perform operations on LinkedLists, such as:
- Adding elements – add(item) and add(index, item)
- Accessing elements – get(index)
- Changing elements – set(index, item)
- Removing elements – remove(index)
Here is some example Java that demonstrates the use of all the above LinkedList methods:
import java.util.LinkedList;
public class Main
{
public static void main(String[] args) {
LinkedList<String> guitars = new LinkedList<>();
guitars.add("Fender");
guitars.add("Gibson");
guitars.add("Jackson");
System.out.println(guitars);
// Inserts new item in 2nd position
guitars.add(1, "Washburn");
System.out.println(guitars);
// Change Jackson to Charvel
guitars.set(3, "Charvel");
System.out.println(guitars);
// Removes 1st element
guitars.remove(0);
System.out.println(guitars);
}
}
The program output can be seen below:
Treating a LinkedList as a Deque and/or Queue
Since the LinkedList class also implements the Queue and the Deque interfaces, we can invoke methods of both. Here are some of the commonly used methods:
- addFirst() – adds the specified element at the beginning of the linked list
- addLast() – adds the specified element at the end of the linked list
- getFirst() – returns the first element
- getLast() – returns the last element
- removeFirst() – removes the first element
- removeLast() – removes the last element
- peek() – returns the first element (head) of the linked list
- poll() – returns and removes the first element from the linked list
- offer() – adds the specified element at the end of the linked list
If you are only interested in methods that are specific to one interface, i.e. List, Queue, or Deque, you can always instantiate your LinkedList as that interface! For example:
// create linkedlist using List List<String> list = new LinkedList<>(); // creating linkedlist using Queue Queue<String> queue = new LinkedList<>(); // creating linkedlist using Deque Deque<String> deque = new LinkedList<>();
Just keep in mind that, instantiating the LinkedList as a specific interface limits method access to those provided by that interface. So, in the above example, Queue cannot employ methods that are part of the Deque or List interfaces.
In the follwing program, the LinkList is acting as a Queue, so why not instantiate it as one?
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
public class Main
{
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
for (int i=1; i<=5; i++) {
queue.add("node"+i);
}
System.out.println(queue);
// access the first element
String str1 = queue.peek();
System.out.println("Accessed Element: " + str1);
// access and remove the first element
String str2 = queue.poll();
System.out.println("Removed Element: " + str2);
System.out.println("LinkedList after poll(): " + queue);
// add element at the end
queue.offer("node6");
System.out.println("LinkedList after offer(): " + queue);
}
}
As you can see in the program output below, everything works just fine, as long as we limit ourselves to methods of the Queue class:
Final Thoughts on the Java LinkedList Class
Java’s LinkedList class is a doubly linked list that allows traversal in both the forward and backward direction. It’s often preferable to an array or ArrayList when you need to do a lot of insertions and deletions of elements or require access to methods of the Queue and Deque interfaces.