Linked Lists are one of the most fundamental data structures in computer science and are represented mainly by these two types:

1. Singly Linked List

2. Doubly Linked List

Node - the Building block

The smallest unit of a Linked List is defined by a Node or whatever you want to name it but Node is the convention.

This is how you can define a Node object in Java:
 1. Value that it will hold.
 2. Pointer to the next Node in the list.

class Node { int value; // assuming an integer value Node next; // pointer to the next Node

// parameterized constructor to create a new Node with a value public Node(int value) { this.value = value; }

}

LL Node structure

Singly Linked List (LL)

Singly Linked List. Notice the Unidirectional arrow.

1. The Singly Linked List Node has only the "next" pointer. We can only travel in one direction, i.e Forward, making traversal Uni-directional.

2. Time Complexity:
   Search: O(N), where N = Number of nodes in the list.
   Insertion & Deletion in between: O(N), where N = Length of linked list.
   As you are required to scan starting from the head of List for each independent operation.

3. Insertion at Head/Tail & Deletion at Head:
   Could be optimized to O(1) by maintaining a "tail" pointer similar to head. As it gives us direct access to first and last node of the linked list.

Doubly Linked List (DLL)

Doubly Linked List. Notice the Bidirectional arrows.

1. Search, Insertion & Deletion time complexities remains the same as Singly Linked List.

2. The only change is that we have an additional pointer in our Node object pointing to the previous node in the list.

   class Node { int value; Node next; Node prev; // pointer to previous Node }

DLL Node structure

The additional "prev" pointer allows us to traverse the list in both forward and backward direction, making Bi-directional traversal possible.

Applications

1. Singly Linked List can be used to implement a Queue.
   - To implement FIFO, we need to support these two operation: Deletion at head (poll/remove) and Insertion at the tail (add). As we saw above it can be done in constant time i.e O(1).
   - And for the same reason, as we discussed in the Java Collections Library post, LinkedList is an implementation of the Queue Interface in Java.

2. Doubly Linked List (DLL) can be used to implement a Double-Ended Queue (Deque). The goal of the Deque is that insertion and deletion operations at both the front and end of the list should take constant time i.e O(1).

3. If you think more about it, Stack which follows LIFO rule can also be implemented using Deque. As insertion at end (push) and deletion at end (pop) of list can be performed in O(1). That is why in Java you can use an ArrayDeque to implement Stack.

Now that we have a refresher on the Linked List Data Structure itself, let's move on to learning the patterns around Linked List for your coding interviews.

Image Source: https://visualgo.net/