LL 3 - Doubly Linked List

Construction of Doubly Linked List

public static Node constructDll(int arr[]){
    Node head = new Node(0);
    Node temp = head;
    for (int num: arr){
        Node newNode = new Node(num);

        temp.next = newNode;
        newNode.prev = temp;

        temp = newNode;
    }
    head = head.next;
    head.prev = null;
    return head;
}

Node Class

public class Node {
    public int val;
    public Node prev;
    public Node next;

    public Node(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        String toString = "";

        Node temp = this;

        while(temp!=null){
            toString += "<->"+temp.val;
            temp = temp.next;
        }

        return toString;
    }
}

Deletion

Delete Head

    public static Node deleteHead(Node head){
        if (head==null || head.next==null) return null;
        head = head.next;
        head.prev = null;
        return head;
    }

Delete Tail

public static Node deleteTail(Node head){

    if(head == null) return null;

    Node temp = head;

    while(temp.next!=null){
        temp = temp.next;
    }

    Node prevNode = temp.prev;
    prevNode.next = null;

    return head;
}

Delete kth Node

public static Node deleteKthNode(Node head, int k){
    if (head == null) return null;

    Node temp = head;

    int count = 1;

    while(temp!=null && count!=k){
        temp = temp.next;
        count+=1;
    }

    Node left = temp.prev;
    Node right = temp.next;

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

    if (right!=null) right.prev = left;

    return head;
}

Delete the given Node

public static void deleteNode(Node node){
    Node left = node.prev;
    Node right = node.next;

    left.next = right;
    if(right!=null) right.prev = left;
}

Insertion (Before Node)

Insert at Head

public static Node insertHead(Node head, int x){
    Node newNode = new Node(x);

    if (head==null) return newNode;

    newNode.next = head;
    head.prev = newNode;

    return newNode;
}

Insert at Tail

public static Node insertTail(Node head, int x){
    Node newNode = new Node(x);

    if (head==null) return newNode;
    Node temp = head;

    while(temp.next!=null){
        temp = temp.next;
    }

    Node left = temp.prev;
    left.next = newNode;
    newNode.prev = left;
    newNode.next = temp;
    temp.prev = newNode;

    return head;
}

Insert at kth Element

public static Node insertKthNode(Node head, int k, int x){

    if (k==1) return insertHead(head, x);

    Node temp = head;

    int count = 1;

    while (temp!=null && count!=k){
        temp = temp.next;
        count+=1;
    }

    Node left = temp.prev;
    Node newNode = new Node(x);
    left.next = newNode;
    newNode.prev = left;
    newNode.next = temp;
    temp.prev = newNode;

    return head;
}

Insert the given Node

We can insert before at any given position by using the following code, except at the head position.

public static void insertBeforeNode(Node node, int x){
    Node left = node.prev;

    Node newNode = new Node(x);
    newNode.prev = left;
    newNode.next = node;

    left.next = newNode;
    node.prev = newNode;
}