Design Doubly Linked List - Solution

// Definition of Doubly Linked List

class DoublyListNode {
int val;
DoublyListNode prev, next;
DoublyListNode(int x){
val = x;
}
}

// Initiate a new Linked List

class MyLinkedList {

private DoublyListNode head;

public MyLinkedList(){
head = null;
}
}

// Traversing the Linked List to get element by index.

private DoublyListNode getNode(int index){
DoublyListNode cur = head;

for(int i=0 ; i < index && cur != null ; i++){
cur = cur.next;
}
return cur;
}


// Function to return last Node of the linked list

private DoublyLinkedList getTail(){

DoublyListNode cur = head;

while(cur !=null && cur.next !=null){
cur = cur.next;
}
return cur;
}


// To fetch the value of the index-th node in the linked list

private int get(int index){

DoublyListNode cur = getNode(index);
return cur == null ? -1 : cur.val;
}


// Add a new Node

// Add a Node if the DoublyListNode is null and add at Head.
public void addAtHead(int val){
DoublyListNode cur = new DoublyListNode(val);
cur.next = head;
if(head != null){
head.prev = cur;
}
head = cur;
return;
}

// Add a Node at Tail 

public void addAtTail (int val){
DoublyListNode prev = getTail();
DoublyListNode cur = new DoublyListNode(val);
if(head == null){
addAtHead(cur);
return;
}
prev.next = cur;
cur.prev = prev;
}

// public void addAtIndex (int index , int val){
if(index == 0){
addAtHead(val);
return;
}

DoublyListNode prev = getNode(index-1);
if(prev == null){
return;
}

DoublyListNode cur = new DoublyListNode(val);
DoublyListNode next = prev.next;

cur.prev = prev;
cur.next = next;
prev.next = cur;
if(next !=null)
next.prev = cur;
}

}

Similar to the SinglyLinkedList it takes O(N) time to get a node by index. where N is the length of the linked list.


// Delete a Node

public void deleteAtIndex (int index){

DoublyListNode cur = get(index);
DoublyListNode prev = cur.prev;
DoublyListNode next = cur.next;

if(cur == null)
return;

if(prev != null){
prev.next = next;
} else {
head = next;
}

if(next != null){
next.prev = prev;
}

}

Introduction To Doubly Linked List

In previous article we learned about SinglyLinkedList.

https://techyield.blogspot.com/2019/06/singly-linked-list-introduction.html

Here we are going to discuss about DoublyLinkedList.

In SinglyLinkedList we have a value field and a reference field to the next node.

In DoublyLinkedList we have one extra field called prev node which points to the prev node. With this field we are able to know the previous node of the current node.


Node Structure :

class DoublyListNode {

int val;
DoublyListNode prev , next;

DoublyListNode(int x){
val = x;
}

}

The entire list is represented with the head node as in SinglyLinkedList.


Operations :

Add Operation :

If we want to insert cur after an existing node prev  .

We can add in two steps :

1. Link cur with prev and next , where next is the original next node of prev.

2. Re link the prev and next with cur.

Similar to the singly Linked List the space and time complexity is O(1).

Delete Operation :

If we want to delete an existing node cur from the doubly linked list we can simply link its prev node prev with the next node next.

Unlike the singly linked list it is easy to get the prev field in constant time O(1).

Here the space and time complexity both are O(1).

Tips For Linked List Problems

1 . Always go through some test cases or examples before you implement a problem using Linked List.

2. Always feel free to use several pointers at the same time.

3. In most of the cases you need to keep track of the previous node for the current node.

Reverse Linked List - LeetCode

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Java Solution :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null)
            return null;
        
        ListNode curHead = head;
        while(head.next != null){
            ListNode p = head.next;
            head.next = p.next;
            p.next = curHead;
            curHead = p;
        }
        return curHead;
    }
}

Remove Linked List Elements - LeetCode

Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

Java Solution :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode helper = new ListNode(0);
        ListNode p = helper;
        helper.next = head;
        
        while(p.next !=null){
            if(p.next.val == val){
                p.next = p.next.next;
            }else{
                p = p.next;
            }
        }
        return helper.next;
    }
}

Template for Two Pointer in Linked List

 Steps :

1. First we need to initialize the slow pointer and fast pointer.

    // Initialize slow and fast pointers.
     ListNode slow = head;
     ListNode fast  = head;
   // Change the condition according to the problem.
  // Remember to avoid error prone.
    while(slow != null && fast !=null && fast.next!=null){
    slow = slow.next; // move slow pointer one step each time
    fast = fast.next.next; // move fast pointer two steps each time
    if(slow == fast){
    return true;
    }
    }
    return false;


Note :

1. Always make sure while  calling the next on the current node.
 
    Getting the next node of the null node will cause errors.

    So before we examine fast and fast.next make sure they are not null.

2. Carefully define the end conditions of the loop.

    Run several examples to make sure your end conditions will not result in error.


Complexity Analysis :

It is easy to analyze the space complexity. If you only use pointers the space complexity is O(1).

But the time complexity will change according to the problem.

In above scenario slow pointer moves one step each time and fast pointer moves two steps each time.

1. If there is no Cycle the fast pointer will move the end of the list in N/2 steps.

2. If there is a Cycle the fast pointer takes M times to catch the slow pointer where M is the length of the Cycle in the List.

Obviously M<=N , So we run the loop N times and it needs constant time . So the time complexity is O(N) in total.

Always try to calculate the worst case scenarios by taking different examples .

Two Pointer in Linked List

Let's think of this case :

Suppose we have a Linked List and we need to check whether it has  Cycle or not.

Consider two pointers one is slow pointer and the other one is fast pointer.

So the slow pointer moves one step and the fast pointer moves in two steps .


Imagine two runners running on a circular track :

The fast runner eventually meets the slow runner some where on the track.

Exactly in the same manner :

1. If the fast pointer meets slow pointer it has Cycle.

2. If the fast pointer reaches the end of the linked list means it has no Cycle.


It is always safe that slow pointer moves one step at a time and fast pointer moves two steps at a time.

For each iteration the fast pointer will move one step ahead of the slow pointer and will meet slow pointer after m iterations.