After arrays, the second most popular data structure is Linked List. A linked list is a linear data structure, made of a chain of nodes in which each node contains a value and a pointer to the next node in the chain. In this article, let’s see how to implement a linked list in Java.

What is Linked List in Java?

Linked List is a part of the Collection framework present in java.util package. This class is an implementation of the LinkedList data structure which is a linear data structure where the elements are not stored in contiguous locations and every element is a separate object with a data part and address part. The elements are linked using pointers and addresses.

Java LinkedList class provides implementation of linked-list data structure. It used doubly linked list to store the elements. It implements List, Deque and Queue interface and extends AbstractSequentialList class. below is the declaration of LinkedList class.

Linked List Representation

public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable

1. LinkedList class extends AbstractSequentialList and implements List,Deque and Queue inteface.
2. It can be used as List, stack or Queue as it implements all the related interfaces.
3. It allows null entry.
4. It is dynamic in nature i.e it allocates memory when required. Therefore insertion and deletion operations can be easily implemented.
5. It can contain duplicate elements and it is not synchronized.
6. Reverse Traversing is difficult in linked list.
In LinkedList, manipulation is fast because no shifting needs to be occurred.

Why Linked List?

Arrays can be used to store linear data of similar types, but arrays have the following limitations.

1. The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.

2. Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to be shifted but in Linked list if we have the head node then we can traverse to any node through it and insert new node at the required position.

Advantages over arrays

1. Dynamic size
2. Ease of insertion/deletion

Constructors in the LinkedList

In order to create a LinkedList, we need to create an object of the LinkedList class. The LinkedList class consists of various constructors that allow the possible creation of the list. The following are the constructors available in this class:

LinkedList(): This constructor is used to create an empty linked list. If we wish to create an empty LinkedList with the name ll, then, it can be created as:

LinkedList ll = new LinkedList();

LinkedList(Collection C): This constructor is used to create an ordered list that contains all the elements of a specified collection, as returned by the collection’s iterator. If we wish to create a LinkedList with the name ll, then, it can be created as:

LinkedList ll = new LinkedList(C);

Uses of Linked List

1. The list is not required to be contiguously present in the memory. The node can reside any where in the memory and linked together to make a list. This achieves optimized utilization of space.

2. list size is limited to the memory size and doesn't need to be declared in advance.

3. Empty node can not be present in the linked list.

4. We can store values of primitive types or objects in the singly linked list.

Operations of Linked List

Methods of Java LinkedList

LinkedList provides various methods that allow us to perform different operations in linked lists. We will look at three commonly used LinkedList Operators in this tutorial:

Add elements to a LinkedList

We can use the add() method to add an element (node) at the end of the LinkedList. For example,

import java.util.LinkedList;

class Main {
  public static void main(String[] args){
    // create linkedlist
    LinkedList<String> animals = new LinkedList<>();

    // add() method without the index parameter
    animals.add("D");
    animals.add("C");
    animals.add("A");
    System.out.println("LinkedList: " + animals);

    // add() method with the index parameter
    animals.add(1, "H");
    System.out.println("Updated LinkedList: " + animals);
  }
}

Access LinkedList elements

The get() method of the LinkedList class is used to access an element from the LinkedList. For example,

import java.util.LinkedList;

class Main {
  public static void main(String[] args) {
    LinkedList<String> languages = new LinkedList<>();

    // add elements in the linked list
    languages.add("Python");
    languages.add("Java");
    languages.add("JavaScript");
    System.out.println("LinkedList: " + languages);

    // get the element from the linked list
    String str = languages.get(1);
    System.out.print("Element at index 1: " + str);
  }
}

Remove element from a LinkedList

The remove() method of the LinkedList class is used to remove an element from the LinkedList. For example,

import java.util.LinkedList;

class Main {
  public static void main(String[] args) {
    LinkedList<String> languages = new LinkedList<>();

    // add elements in LinkedList
    languages.add("Java");
    languages.add("Python");
    languages.add("JavaScript");
    languages.add("Kotlin");
    System.out.println("LinkedList: " + languages);

    // remove elements from index 1
    String str = languages.remove(1);
    System.out.println("Removed Element: " + str);

    System.out.println("Updated LinkedList: " + languages);
  }
}

Size of LinkedList

Sometimes we want to know number of elements an LinkedList holds. In that case we use size() then returns size of LinkedList which is equal to number of elements present in the list

import java.util.*;
class Demo
{
  public static void main(String[] args)
  {
    // Creating LinkedList
    LinkedList< String> linkedList = new LinkedList< String>();
    linkedList.add("Delhi");
    linkedList.add("NewYork");
    linkedList.add("Moscow");
    linkedList.add("Dubai");
    // Traversing ArrayList
    for(String element : linkedList) {
      System.out.println(element);    
    }
System.out.println("Total Elements: "+linkedList.size());
  }
}
  

Time & Space Complexity Analysis

Space Complexity: The Space Complexity of the above Linked List operations is O(1). This is because we do not need extra space beyond a fixed number of variables. For some operations, you may need extra space of the order of O(N). For example, sorting a Linked List using a sorting algorithm that is not in-place.

With this article at Logicmojo, you must have the complete idea of analyzing Linked List and it's operations.

Good Luck & Happy Learning!!