LinkedList: Introduction

The LinkedList class in Java implements the List and the Deque interface. Some of the salient features of a LinkedList are:

1. The elements are inserted in the order of insertion.

2. It supports duplicate elements.

3. We can add any number of null elements.

Internal implementation of LinkedList

The LinkedList class has a static inner class called Node. This class contains three fields:

item - This contains the value of the current element.

next - This contains the pointer to the next element.

prev - This contains the pointer to the previous element.

Below is the code for the Node class.

 private static class Node<E> {
     E item;
     Node<E> next;
     Node<E> prev;

     Node(Node<E> prev, E element, Node<E> next) {
         this.item = element;
         this.next = next;
         this.prev = prev;
     }
 }

When an element is added to the LinkedList, a new Node instance is created. Depending on where the new node is being added, the prev and next fields are set.

When a node at index i is removed, the next field of node at index i-1 is set to the node at index i+1. Similarly, the prev field of node at index i+1 is set to node i-1.

Time complexities for LinkedList operations

Let’s see what the time complexities are for different ...