LinkedList In Java

In this article, we will see LinkedList in Java. How LinkedList is created? Its various types of constructors for creating a LinkedList object. Also, some important features with their respective example.

Introduction

The LinkedList class is present in the java.util package. LinkedList implements the List and Deque interfaces and extends the AbstractSequentialList class from the Collections.

LinkedList allows duplicates and a null value. Also, it maintains the insertion order.

LinkedList implements the Serializable and Cloneable interface. it does not implement the RandomAccess interface.

LinkedList internally uses a doubly linked list data structure to store the objects.

Hence, the element stored in the LinkedList acts as a separate object, and every element is connected by its addresses. So inserting and deleting the elements is an easy and efficient operation. And that’s why LinkedList is preferred over arrays if our frequent operations are insertions and deletions.

But as we discussed, every single element acts as a separate object. And it is linked by their addresses.

We can not move directly to the desired element. First, we need to go to the head element, and then from the head element, we get the address of the next element, and so on till our desired element.

It makes retrieving operations very inefficient and time-consuming, and that’s why LinkedList is not preferred for storing and retrieving operations.

Constructors in the LinkedList

LinkedList provides two types of constructors to create a new LinkedList object.

1. LinkedList()
2. LinkedList(Collection c)

1. LinkedList()

This constructor constructs an empty List.

1
LinkedList<String> list = new LinkedList<String>(); 

2.LinkedList(Collection<? extends E> c)

This constructor constructs a LinkedList containing the elements of the specified collection, in the order they are returned by the collection’s iterator.

1
2
3
4
5
6
7
8
List<String> arrayList = new ArrayList<String>();
arrayList.add("John");
arrayList.add("Mark");
arrayList.add("Ruby");
arrayList.add("Lucy");

//It constructs a LinkedList containing elements of the above ArrayList
List<String> linkedList = new LinkedList<String>(arrayList);

Methods of the LinkedList

Features

1. LinkedList maintains the insertion order.

Let’s see a simple Java program to prove that LinkedList maintains the insertion order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.LinkedList;
/**
 * A Java program to prove that LinkedList maintains insertion order
 * @author coderolls.com
 *
 */
public class LinkedListInsertionOrder {

  public static void main(String[] args) {
    LinkedList<String> linkedList = new LinkedList<String>();
    linkedList.add("John");
    linkedList.add("Mark");
    linkedList.add("Ruby");
    linkedList.add("Lucy");
    linkedList.add("Vikram");
    
    System.out.println(linkedList);
  }
}

Output:

1
[John, Mark, Ruby, Lucy, Vikram]

Explanation

1. I have created an empty LinkedList object linkedList of String.
2. I have added a few Strings to the linkedList
3. I have printed the linkedList object using the sysout statement. We can see the output strings are in the inserted order only.

2. LinkedList allows the duplicate elements.

I have given a simple java program to prove that LinkedList allows the duplicate elements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.LinkedList;
/**
 * A Java program to prove that LinkedList Allows Duplicates
 * @author coderolls.com
 *
 */
public class LinkedAllowDuplicates {

  public static void main(String[] args) {
    LinkedList<String> linkedList = new LinkedList<String>();
    linkedList.add("John");
    linkedList.add("Mark");
    linkedList.add("Mark");
    linkedList.add("Mark");
    linkedList.add("Ruby");
    linkedList.add("Lucy");
    linkedList.add("Vikram");
    linkedList.add("Vikram");
    
    System.out.println(linkedList);
  }
}

Output:

1
[John, Mark, Mark, Mark, Ruby, Lucy, Vikram, Vikram]

Explanation

1. I have created an empty LinkedList object linkedList of String.
2. I have added some Strings to the linkedList, a few of the String objects are duplicates.
3. I have printed the linkedList object using the sysout statement. We can see the output contains duplicate strings.

3. LinkedList allows the null values.

I have given a simple Java program below to show that LinkedList allows the null values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.LinkedList;
/**
 * A Java program to prove that LinkedList Allows null values
 * @author coderolls.com
 *
 */
public class LinkedAllowDuplicates {

  public static void main(String[] args) {
    LinkedList<String> linkedList = new LinkedList<String>();
    linkedList.add("John");
    linkedList.add(null);
    linkedList.add("Mark");
    linkedList.add(null);
    linkedList.add("Ruby");
    linkedList.add("Lucy");
    linkedList.add("Vikram");
    linkedList.add(null);
    
    System.out.println(linkedList);
  }
}

Output:

1
[John, null, Mark, null, Ruby, Lucy, Vikram, null]

Explanation

1. I have created an empty LinkedList object linkedList of String.
2. I have added a few Strings to the linkedList. Also, I have added a few null values too.
3. I have printed the linkedList object using the sysout statement. We can see the output contains the null values.

The example Java programs given in the above tutorial can be found at this GitHub Repository.

Let me know your thoughts or suggestions on the topic discussed above in the comment section below.