Doubly Linked List

-
A Doubly Linked list looks like a similar to Singly Linked list but there is one extra pointer that holds the previous node information also. It holds the information of the previous as well as the next node. It gives us the flexibility to iterate backward and forward direction. Let moving forward and implement a doubly linked list.
NOTE: -Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it as an Object.
#1 Custom Doubly Linked List Class
class Node<T>  {
    T data;
    Node<T> next;
    Node<T> previous;
    public Node() {
    }
    public Node(T data) {
        this.data = data;
    }
    public Node(T data, Node<T> next, Node<T> previous) {
        this.data = data;
        this.next = next;
        this.previous = previous;
    }
}
The below diagram will really helpful whenever you are going to create a doubly linked list on your own. You can easily guess that there are two references for holding the same type along with the value of the node. In the above code, we create a generic doubly linked list class which can hold any type of value.

#2 Create a Doubly Linked List Implementation class
public class CustomDoublyLinkedListImpl<T> {
    Node<T> head, tail;
    int size = 0;
}
#3 Adding node at the end - O(1)
/**
 * Inserting element at the last position
 * Time/Space Complexity - O(1)
 * @param data
 */
public void add(T data) {
    Node<T> node = new Node(data);
    if (head == null) {
        head =  tail = node;
    } else {
        tail.next = node;
        node.previous = tail;
        tail = node;
    }
    size++;
}
In the code above, we are initially checking if the linked list exists. If the list is not present then create a new node and set the reference of it to head and tail otherwise tail's next will hold the address of the new node and the new node's previous will hold the address of tail and then the tail will update to the new node.
#4 Adding node at the beginning - O(1)
/**
 * Insertion element at the first position
 * Time/Space Complexity - O(1)
 * @param data
 */
public void addFirst(T data) {
    Node<T> node = new Node<>(data);
    if (head == null) {
        head = tail = node;
    } else {
        node.next = head;
        head.previous = node;
        head = node;
    }
    size++;
}
We have to check the base condition whether the list exists or not. We are creating a new node and set node's next to the head and head's previous to the new node and then update the head to the new node itself.
#5 Adding node at desire index - O(n)
/**
 * Insertion node at the particular index.
 * Time Complexity - O(n)
 * Space Complexity - O(1)
 * @param index
 * @param data
 */
public void addElementAtDesireIndex(int index, T data) {
    if (index >= 0 && index <= size) {
        if (head == null || index == 0) {
            addFirst(data);
            return;
        } else {
            Node<T> node = new Node<>(data);
            int count = 0;
            Node<T> ref = head;
            while (count++< index-1) {
                ref = ref.next;
            }
            Node<T> tempRef = ref.next;
            ref.next = node;
            node.previous = ref;
            node.next = tempRef;
            if (ref == tail) {
                tail = node;
            } else {
                tempRef.previous = node;
            }
            size++;
        }
    } else {
        throw new ArrayIndexOutOfBoundsException(index);
    }
}
In the code above, we are checking the base condition and index value shouldn't exceed the doubly linked list size. We have to iterate head to till the index -1 and hold the index -1 node's next reference into the temporary variable. We call index-1 node as a ref and setting ref.next to the new node and new node's previous to the ref and the new node's next to the temporary reference node. We have to be very careful with the tail pointer, If the index-1 node is equal to tail then we will update the tail to the new node otherwise temporary reference node's previous to the node. 
#6 Printing node's element - O(n)
/**
 * Traversing a Doubly Linked List in forward direction.
 * Time Complexity - O(n)
 * Space Complexity - O(1)
 */
public void printMe() {
    Node<T> curr = head;
    while (curr != null) {
        System.out.print(curr.data+" ");
        curr = curr.next;
    }
}

/**
 * Traversing a Doubly Linked List in reverse/backward direction.
 * Time Complexity - O(n)
 * Space Complexity - O(1)
 */
public void reversePrint() {
    Node<T> curr = tail;
    while (curr != null) {
        System.out.print(curr.data+" ");
        curr = curr.previous;
    }
}
#7 Searching an element in Doubly Linked List
/**
 * Search Value is exist in Doubly linked list
 * Time Complexity - O(n)
 * Space Complexity - O(1)
 * @param value
 * @return
 */
public boolean contains(T value) {
    Node<T> curr = head;
    while (curr != null){
        if (curr.data == value)
            return true;
    }
    return false;
}
#8 Searching an element in an optimized solution
/**
 * Search Value is exist in Doubly linked list
 * Time Complexity - O(n)
 * Space Complexity - O(1)
 * @param value
 * @return
 */
public boolean contains(T value) {
    Node<T> curr = head, tailCurr = tail;
    while (curr != tailCurr && curr.next != tailCurr) {
        if (curr.data == value || tailCurr.data == value)
            return true;
        curr = curr.next;
        tailCurr = tailCurr.previous;
    }
    return ((curr != null && curr.data == value) ||
            (tailCurr != null && tailCurr.data == value)) ? true : false;
}
We are iterating from forward and backward Doubly linked list and checking if it contains the value or not. When it reaches the common node then terminate the loop and check if the Curr or tail pointer data is equal to value then return true otherwise false. We can say it will use the O(n/2) time complexity technically but higher bound for that is O(n). 
#9 Remove node from the beginning - O(1)
public void remove() {
    if (size == 1)
        head = tail = null;
    else {
        head = head.next;
        head.previous = null;
    }
    size--;
}
#10 Remove node from last - O(1)
public void removeLast() {
    if (size == 1) {
        head = tail = null;
    } else {
        tail = tail.previous;
        tail.next = null;
    }
    size--;
}
#11 Remove node from desire index - O(n)
/**
 * Removing element from desire location
 * Time complexity - O(n) & Space Complexity - O(1)
 */
public void removeElementAtDesireIndex(int index) {
    if (index >= 0 && index < size) {
        if (index == 0) {
            remove();
        } else if (index == size-1){
            removeLast();
        } else {
            Node<T> ref = head;
            int count = 0;
            while (count++ < index-1)
                ref = ref.next;
            ref.next = ref.next.next;
            ref.next.previous = ref;
            size--;
        }
    } else
        throw new ArrayIndexOutOfBoundsException(index);
}
#12 Clear All Doubly Linked List - O(1) 
public void clear() {
    head = tail = null;
    size = 0;
}

Comments

Post a Comment

Popular posts from this blog

Recursion

-
Image
The process in which a function calls itself and only works where we call the same operation multiple times with different inputs. In every call, we try to make the problem smaller. There must be a base case where the system will stop the recursion and give you a result back. It internally stores the recursion state in the method call stack. If there is no base condition in the recursion method then it will go into an infinite loop and you might face the StackOverflow Exception . There are several types of recursion:- Head Recursion Tail Recursion Tree Recursion Nested Recursion Head Recursion It will call recursively first then at the end do all the computation. private static int factorial( int number) { return (number== 1 )? number : number* factorial (number- 1 ) ; } factorial(5) (5* factorial(5-1)) (5* (4* factorial(4-1)) (5* (4* (3*factorial(3-1))) (5* (4* (3* (2*factorial(2-1)))) (5* (4* (3* (2* (1*1))))) output = 120 Tail Recur...
Read more

Stack

-
Image
The Stack  looks more like a container which holds the element, will insert element from the top and remove from the top only. It follows the Last in First out(LIFO)  or First In Last out (FILO)  approach. Java uses the method stack area to hold the state of the method if some method calls another method inside it.   public class Demo { public static void main(String[] args) { new Demo().firstCall(); System. out .println( "Main" ); } public void firstCall() { secondCall(); System. out .println( "First" ); } private void secondCall() { thirdCall(); System. out .println( "Second" ); } private void thirdCall() { System. out .println( "Third" ); } } This is how it maintains the method call in the method stack area. It will remove from the top every time and complete its method execution and remove next's top from the stack. This process will continue until th...
Read more

Data Structure & Algorithm

-
Image
I am going to start the complete data structure and algorithm blog series to help the developer community understand the basics and help them become more productive in their work environment. As we all are under lockdown until the next update from the government, I have decided to support my friends and colleague to understand the data structure and algorithm. Let's begin by separating the data structure and algorithm in two terms. When you hear about data structure,  what comes first to your mind. I believe most of you thought of storing any form of data in an efficient way. Yes, You are correct 👍. Now, Second and the most important term is an algorithm , It is a set of rules to be followed to solve a problem. To gain more understanding of the data structure and algorithm, let us take an example:- E.g., We are all going to attend the google conference and they have a single registration desk. If we all reach the registration counter together, to register ourselves. Such a ...
Read more