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

1.  
2. /**
3. * Constructs an empty list.
4. */
5. public LinkedList() {
6. }

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

7. // We pass a collection to this Constructor
8. public LinkedList(Collection<? extends E> c) {
9.    addAll(c);
10. }

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

        // print the updated linkedlist

        System.out.println("Updated Elements after insert at index 2: "+linkedList);

        // Insert at the beginning of list

        linkedList.addFirst("Hey!");

        // print the updated linkedlist

        System.out.println("Updated Elements after inserting at the beginning: "+linkedList);

        // Insert at the end of list

        linkedList.addLast("All the Best!");

        // print the updated linkedlist

        System.out.println("Updated Elements after inserting at the end: "+linkedList);

        // remove an element from the list if present.

        linkedList.remove("software");

        // print the updated linkedlist

        System.out.println("Updated Elements after removing the string - software: "+linkedList);

        // remove an element from the list if present.

        linkedList.remove("notPresent");

        // print the updated linkedlist

        System.out.println("Updated Elements after removing the string - notPresent: "+linkedList);

        // remove an element from the specified index.

        linkedList.remove(0);

        // print the updated linkedlist

        System.out.println("Updated Elements after removing the index 0: "+linkedList);

        //set the value at a specified index.

        linkedList.set(2 , "software interviews");

        // print the updated linkedlist

        System.out.println("Updated Elements setting the value at index 2: "+linkedList);

        // check if the list contains the value 'InterviewKickstart'.

        System.out.println("Does the list contain the value 'InterviewKickstart' "+linkedList.contains("InterviewKickstart"));

        // check if the list contains the value 'code'.

        System.out.println("Does the list contain the value 'code' "+linkedList.contains("code"));

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

        dummyLinkedList.add("I am ready");

        dummyLinkedList.add("for my next");

        dummyLinkedList.add("software");

        dummyLinkedList.add("interview");

        // add all the elements from the dummyLinkedList to our original LinkedList.

        linkedList.addAll(dummyLinkedList);

        System.out.println("Elements after adding all elements from dummy list: "+linkedList);

        // get the element at an index from the linkedList.

        // elements in linkedList are 0-indexed.

        System.out.println("Element at the index 4 in linkedList is: " + linkedList.get(4));

        // indexOf returns the index of the first occurrence of an element if present in linkedList.

        // if not present it returns -1;

        System.out.println("Index of 'InterviewKickstart' is "+linkedList.indexOf("InterviewKickstart"));

        System.out.println("Index of 'code' is "+linkedList.indexOf("code"));

        // poll() Retrieves and removes the first element (head) of the list.

        // so it returns the head of this list, or null if this list is empty.

        System.out.println("List before polling: "+linkedList);

        linkedList.poll();

        System.out.println("List after polling: "+linkedList);

    }

}

Output:

Initial Elements: [Prepare, for, interviews, from, InterviewKickstart]

Updated Elements after insert at index 2: [Prepare, for, software, interviews, from, InterviewKickstart]

Updated Elements after inserting at the beginning: [Hey!, Prepare, for, software, interviews, from, InterviewKickstart]

Updated Elements after inserting at the end: [Hey!, Prepare, for, software, interviews, from, InterviewKickstart, All the Best!]

Updated Elements after removing the string - software: [Hey!, Prepare, for, interviews, from, InterviewKickstart, All the Best!]

Updated Elements after removing the string - notPresent: [Hey!, Prepare, for, interviews, from, InterviewKickstart, All the Best!]

Updated Elements after removing the index 0: [Prepare, for, interviews, from, InterviewKickstart, All the Best!]

Updated Elements setting the value at index 2: [Prepare, for, software interviews, from, InterviewKickstart, All the Best!]

Does the list contain the value 'InterviewKickstart' true

Does the list contain the value 'code' false

Elements after adding all elements from dummy list: [Prepare, for, software interviews, from, InterviewKickstart, All the Best!, I am ready, for my next, software, interview]

Element at the index 4 in linkedList is: InterviewKickstart

Index of 'InterviewKickstart' is 4

Index of 'code' is -1

List before polling: [Prepare, for, software interviews, from, InterviewKickstart, All the Best!, I am ready, for my next, software, interview]

List after polling: [for, software interviews, from, InterviewKickstart, All the Best!, I am ready, for my next, software, interview]

Explanation: 

• Firstly, we start by creating a linked list and then insert elements into it. So the list contains :  [Prepare, for, software, interviews, from, InterviewKickstart]
• Next, we insert “software” at index 2 . So the updated linkedList will be : [Prepare, for, software, interviews, from, InterviewKickstart]
• Next, we insert “Hey!“ at the beginning of the linkedList : [Hey!, Prepare, for, software, interviews, from, InterviewKickstart]
• Next, we insert “All the Best“ at the end of the linkedList : [Hey!, Prepare, for, software, interviews, from, InterviewKickstart, All the Best!]
• Now we try to remove elements from the list. We first remove “software”. Result - [Hey!, Prepare, for, interviews, from, InterviewKickstart, All the Best!]
• We then first remove “notPresent”. Result remains the same as the string is not present in the linked list.
• Next, we remove the string at index 0, and we get the resultant linkedList as [Prepare, for, interviews, from, InterviewKickstart, All the Best!]
• Finally, we change the value at position 2 to “software interviews” using the set method of the linked list class. 

Result: 

[Prepare, for, software interviews, from, InterviewKickstart, All the Best!]

Next, we check if the list contains the word ‘InterviewKickstart’, and the result we get is true. Further, we check if the list includes the word ‘code’, and the result we get is false.

Next, we create a dummy list and add all elements of it into our original list using the addAll method. So the output is :

[Prepare, for, software interviews, from, InterviewKickstart, All the Best!, I am ready, for my next, software, interview]

Next, we explore the indexOf method, which returns the index of the first occurrence of the element in the list if it is present; else, it returns -1. So for the indexOf(‘InterviewKickstart’), we get output as 4 as its location is at index 4.

For indexOf(‘code’), we get output as -1, as code is not present in our list.

Finally, we explore the poll() method that retrieves and removes the list’s head (first element). Hence we get output as:

 [for, software interviews, from, InterviewKickstart, All the Best!, I am ready, for my next, software, interview]

ArrayList vs. LinkedList

ArrayList and LinkedList both implement the List interface and maintain the order in which elements are inserted. Moreover, both the classes are not synchronized; if multiple threads access it concurrently, then at least one of the threads structurally modifies the list. Here, structural modification is any operation that inserts or deletes one or more elements into the list.

Here are some differences between them:

Here are the worst-case complexities of performing operations on LinkedList vs. ArrayList:

When to Use ArrayList and LinkedList

We should use LinkedList should when

• We frequently need to add or remove from various positions in the list.
• We want to iterate through the items instead of accessing items at different positions.
• We do not know beforehand how many elements we will need to store.

We should use ArrayList when

• We want to access elements at random positions frequently.
• We only want to add or remove elements from the end of the list.

What Are the Various LinkedList Methods?

FAQs on Java LinkedList 

Question 1: Should we use ArrayList or LinkedList in general?

Generally, we use Arraylist in most scenarios, but in some instances, when deletions and modifications on the list are more frequent, LinkedList is preferred.

Question 2: Is LinkedList synchronized or thread-safe?

LinkedList is not thread-safe. If multiple threads try to access the elements of the list, at least one of the threads will end up modifying the list. So if a thread-safe implementation is a concern, then we should use ConcurrentLinkedQueue or LinkedBlockingDeque in Java.

Are You Ready to Nail Your Next Coding Interview?

Whether you’re a Coding Engineer gunning for Software Developer or Software Engineer roles, or you’re targeting management positions at top companies, IK offers courses specifically designed for your needs to help you with your technical interview preparation!

If you’re looking for guidance and help with getting started, sign up for our free webinar. As pioneers in the field of technical interview prep, we have trained thousands of Software Engineers to crack the most challenging coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

Sign up now!

————

Article contributed by Problem Setters Official