Recent Posts

Thursday, 28 December 2017

Doubly Linked Lists

Doubly Linked Lists
     Generally, in a single linked list, every node has link to its next node in the sequence. So, we can traverse from one node to another node only in one direction and we can't traverse back. We can solve this kind of problem by using double linked list. Double linked list can be defined as follows
     "Double linked list is a sequence of elements in which every element has links to its previous element and next element in the sequence."
Advantages
1. We can traverse in both directions i.e. from starting to end and as well as from end to starting.
2. It is easy to reverse the linked list.
3. If we are at a node, then we can go to any node. But in linear linked list, it is not possible to reach the previous node.
Disadvantages
1. It requires more space per space per node because one extra field is required for pointer to previous node.
2. Insertion and deletion take more time than linear linked list because more pointer operations are required than linear linked list.
     Here, 'link1' field is used to store the address of the previous node in the sequence, 'link2' field is used to store the address of the next node in the sequence and 'data' field is used to store the actual value of that node.
Example,
Note
1. In double linked list, the first node must be always pointed by head.
2. Always the previous field of the first node must be NULL.
3. Always the next field of the last node must be NULL.
     Similar to a singly linked list, let us implement the operations of a doubly linked list. Following is a type declaration for a doubly linked list:
package com.ashok.datastructures.linkedlist; 

public class DoubleLinkedListNode { 
    private int data; 
    private DoubleLinkedListNode prev; 
    private DoubleLinkedListNode next; 

    public DoubleLinkedListNode(int data) { 
        this.data = data; 
        this.prev = null; 
        this.next = null; 
    } 
    public DoubleLinkedListNode(int data, DoubleLinkedListNode prev, DoubleLinkedListNode next) { 
        this.data = data; 
        this.prev = prev; 
        this.next = next; 
    } 
    public int getData() { 
        return data; 
    } 
    public void setData(int data) { 
        this.data = data; 
    }     
    public DoubleLinkedListNode getPrev() { 
        return prev; 
    } 
    public void setPrev(DoubleLinkedListNode prev) { 
        this.prev = prev; 
    } 
    public DoubleLinkedListNode getNext() { 
        return next; 
    }   
    public void setNext(DoubleLinkedListNode next) { 
        this.next = next; 
    } 
}
Doubly Linked List Insertion
     Insertion into a double linked list has three cases (same as singly linked list)
1. Inserting a new node before the head.
2. Inserting a new node after the tail (at the end of the list).
3. Inserting a new node at the middle of the list.

1. Inserting a Node in Doubly Linked List at the Beginning
     In this case, new node is inserted before the head node. Previous and next pointers need to be modified and it can be done in two steps
• Update the right pointer of the new node to point to the current head node (dotted link in below figure) and also make left pointer of new node as NULL.
• Update head node’s left pointer to point to the new node and make new node as head.
2. Inserting a Node in Doubly Linked List at the Ending
     In this case, traverse the list till the end and insert the new node.
• New node right pointer points to NULL and left pointer points to the end of the list.
• Update right pointer of last node to point to new node.
3. Inserting a Node in Doubly Linked List at the Middle
     As discussed in singly linked lists, traverse the list to the position node and insert the new node.
• New node right pointer points to the next node of the position node where we want to insert the new node. Also, new node left pointer points to the position node.
•  Position node right pointer points to the new node and the next node of position node left pointer points to new node.
Time Complexity: O(n). In the worst case, we may need to insert the node at the end of the list.
Space Complexity: O (1), for creating one temporary variable.

Doubly Linked List Deletion
     Similar to singly linked list deletion, here we have three cases:
1. Deleting the first node
2. Deleting the last node
3. Deleting an intermediate node

1. Deleting the First Node in Doubly Linked List
     In this case, the first node (current head node) is removed from the list. It can be done in 2 steps
• Create a temporary node which will point to the same node as that of head.
• Now, move the head nodes pointer to the next node and change the heads left pointer to NULL. Then, dispose of the temporary node.
2. Deleting the Last Node in Doubly Linked List
     Deleting the Last Node in Doubly Linked List operation is a bit trickier than removing the first node, because the algorithm should find a node, which is previous to the tail first. This can be done in 3 steps:
• Traverse the list and while traversing maintain the previous node address also. By the time we reach the end of the list, we will have two pointers, one pointing to the tail and the other pointing to the node before the tail.
• Update the next pointer of previous node to the tail node with NULL.
• Dispose the tail node.
3. Deleting an Intermediate Node in Doubly Linked List
     In this case, the node to be removed is always located between two nodes, and the head and tail links are not updated. The removal can be done in two steps:
• Similar to the previous case, maintain the previous node while also traversing the list. Upon locating the node to be deleted, change the previous node’s next pointer to the next node of the node to be deleted.
• Dispose of the current node to be deleted.
Time Complexity: O(n), for scanning the complete list of size n.
Space Complexity: O(1), for creating one temporary variable.

Previous Tutorial : Single Linked List Tutorial
 

No comments:

Post a Comment