Linked-list

Doubly Linked-list

A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.

Also to keep track of nodes of DLL use tail in main DLL class (to point to last node)in addition to head

Representation

// Class for Doubly Linked List
public class DLL<E> {
	Node<E> head,tail=null; // head & tail of list

	/* Doubly Linked list Node*/
	class Node<E> {
		E data;
		Node<E> prev;
		Node<E> next;

		// Constructor to create a new node
		// next and prev is by default initialized as null
		Node(E d) { this.data = d; 
//Note- here prev,(or next ) not intialized to null as it will break the link by default?
}
	}
}

Advantages over singly linked list 

1.  A DLL can be traversed in both forward and backward direction. 
2.  The delete operation in DLL is more efficient if pointer to the node to be deleted is given. 
3. 3) We can quickly insert a new node before a given node. 
4. In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.

Disadvantages over singly linked list 
1) Every node of DLL Require extra space for an previous pointer. It is possible to implement DLL with single pointer though (See this and this). 
2) All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with next pointers. For example in following functions for insertions at different positions, we need 1 or 2 extra steps to set previous pointer.
Insertion 
A node can be added in four ways 
1) At the front of the DLL 
2) After a given node. 
3) At the end of the DLL 
4) Before a given node.

Add a node at the end: (7 steps process) 

Using tail pointer it’s efficient to add to end of DLL (rather than not using tail pointer and then traversing to end to add).

 //addNode() will add a node to end of the  list  
    public void addNode(int data) {  
        //Create a new node  
        Node newNode = new Node(data);  
  
        //If list is empty  
        if(head == null) {  
            //Both head and tail will point to newNode  
            head = tail = newNode;  
            //head's previous will point to null  
            head.previous = null;  
            //tail's next will point to null, as it is the last node of the list  
            tail.next = null;  
        }  
        else {  
            //newNode will be added after tail such that tail's next will point to newNode  
            tail.next = newNode;  
            //newNode's previous will point to tail  
            newNode.previous = tail;  
            //newNode will become new tail  
            tail = newNode;  
            //As it is last node, tail's next will point to null  
            tail.next = null;  
        }  
    }