LinkedList in Java

Last updated by Vartika Rai on Sep 25, 2024 at 11:00 PM

| Reading Time: 3 minutes

LinkedList is a crucial data structure in Computer Science. It is often used in programming interviews to assess a candidate’s grip on fundamentals. Many problems involve using linked lists and dealing with corner cases, so every candidate preparing for interviews must be familiar with this topic. This article discusses all the essential details regarding linked lists that you must know before your software engineering interview.

In this article, weâ€™ll cover:

What Is LinkedList in Java?
How to Create a Linked List in Java?
Constructors in the LinkedList class
Why Do We Need a Linked List When We Have Array As a Linear Data Structure?
LinkedList Class Implementation In Java
ArrayList vs. LinkedList
When to Use ArrayList and LinkedList
What Are the Various LinkedList Methods?
FAQs on Java LinkedList

What Is LinkedList in Java?

Letâ€™s visualize first what a linked list is. Have you ever seen a train carrying goods from one place to another like in the diagram below:

In the image above, we can see that the train has two compartments that carry goods and are connected and an engine that connects to a compartment. Linked lists work similarly. Typically, a linked list also consists of nodes containing data connected via reference to the next node. The first node is referred to as theÂ head,Â which we can think of as the engine in the train.

Formally, the LinkedList class in Java is a part of the java.util package. This class is the doubly-linked list implementation of the List and Deque interfaces. So it is a linear data structure where the storage of elements does not occur in contiguous locations; instead, every element is an object that stores data and references to the next and the previous object. As a result, we cannot randomly access the nodes of a linked list. These elements are called nodes.

How to Create a Linked List in Java?

To create LinkedList in Java, we need first to import it from the java.util package and then create an object of that class. Below is the syntax to create it.

import java.util.*;

LinkedList<T> linkedList = new LinkedList<>();

Here we created a linked list of generic type <T>.

We can also create a linked list of string , double or integers as below:

LinkedList<String> linkedList = new LinkedList<>();

LinkedList<Integer> linkedList = new LinkedList<>();

LinkedList<Double> linkedList = new LinkedList<>();

Constructors in the LinkedList Class

The LinkedList class provides two types of constructors that we can use to create an object of the LinkedList class.

1. Default Constructor

/**
* Constructs an empty list.
*/
public LinkedList() {
}

This is the default constructor present in the LinkedList class, and so if we do not pass any parameters, this constructor will be invoked.

Example:

LinkedList<T> linkedList = new LinkedList<>();

2. Parameterized Constructor

// We pass a collection to this Constructor
public LinkedList(Collection<? extends E> c) {
Â Â Â addAll(c);
}

This is the parameterized constructor present in the LinkedList class.

Hereâ€™s an example for invoking this constructor:

LinkedList<String> oldLinkedList = new LinkedList<>();

// Adding elements into the LinkedList

oldLinkedList.add(“Prepare”);

oldLinkedList.add(“for”);

oldLinkedList.add(“interviews”);

oldLinkedList.add(“from”);

oldLinkedList.add(“InterviewKickstart”);

LinkedList<String> copyLinkedList = new LinkedList<>(oldLinkedList);

The code above will construct a list containing all the elements of theÂ oldLinkedListÂ in the order returned by the iterator object.Â

Why Do We Need a Linked List When We Have Array as a Linear Data Structure?

Arrays are also a linear data structure, but they have some limitations.

We get a fixed-size array when we create an array. So in case, the need arises for more size, we would need to create one more array of the required size and copy all elements from the original array to the new array. Moreover, if we initially create a large array and later don’t store elements to the arrayâ€™s total capacity, it’s a waste of memory.
Inserting a new element at a given index is costly as we will have to shift several items to make space for the new item.
Deleting an item is also costly in arrays as it requires shifting all the items after the deleted item to the left.
In the case of arrays, we require contiguous memory locations to store values.

The above limitations are handled by LinkedList very easily:

They allow dynamic memory allocation, which means the allocation of memory occurs at runtime, and hence we do not need to specify size at the beginning.
Insert and delete are not costly operations if the relevant node is passed as a parameter since both require only changing the references stored in the previous and next node. We no longer need to shift elements.
Contiguous memory allocations are not needed as elements are linked to each other by keeping a reference of the next node.

LinkedList Class Implementation in Java

Let us now look at how LinkedList Class is implemented in Java with the help of an example.

Code:

import java.util.LinkedList;

public class Main {

public static void main(String[] args)Â {

// creating a LinkedList in Java.

LinkedList<String> linkedList = new LinkedList<>();

// Adding elements into the LinkedList

linkedList.add(“Prepare”);

linkedList.add(“for”);

linkedList.add(“interviews”);

linkedList.add(“from”);

linkedList.add(“InterviewKickstart”);

// Printing all the elements in the linkedList.

System.out.println(“Initial Elements: “+linkedList);

// Insert an element into the linkedlist at a specified index

// Here we insert an element at position 2

linkedList.add(2, “software”);