Basics of Linked List

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 defined 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;
    }
    
}

Singly Linked List (LL)

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)

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
}

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.

Reversal Pattern - Linked List

In this post, we will learn about Reversing a linked list and all the different problems where you can apply this pattern to solve twisted Linked List problems.

TechBumKashyap Bhansali

Slow & Fast Pointers - Linked List Pattern

The Slow & Fast Pointer approach is the second pattern that will come in handy when working on Linked list problems. We will learn this pattern by applying it to the following three problems:1. Find Middle of Linked List2. Find Kth-node from last3. Detect a cycle in Linked List

TechBumKashyap Bhansali

Image Source: https://visualgo.net/