Implement doubly ended linked list

Doubly linked list is a linked data structure that consists of a set of sequentially linked nodes. Each node contains two links (references to the previous and to the next node) and data. The links help to iterate the node forward and backward.

XOR-linked list allows doubly linked list to be implemented using a single link field in each node. The XOR linked list decrease the memory size compare than doubly linked list. The XOR linking has few drawbacks and it is difficult to debug using debugging tools.

Write a program to implement doubly ended linked list with all the operations.

Algorithm Explanation

	Doubly linked list support insert, delete and iteration operations.
	Each node contains data, link to the next node and link to the previous node. The insertion link breaks the previous and next node and link with a new node on both sides.
	When to insert the node in a particular position, the doubly linked list require both previous and next node links.
	Insertion and deletion may require more operations in doubly linked list and other operations are simplified in doubly linked list.

Source Code

package com.dsacode.DataStructre.linkedlist;
 
class DoublyNode {
    public int data;
    public DoublyNode next;
    public DoublyNode previous;
 
    public DoublyNode(int d){
        data = d;
    }
 
   public void displayLink() {     
      System.out.print(data );
    }
}
 
 
public class DoublyLinkedlist {
 
    private DoublyNode first;
    private DoublyNode last;
 
 
    public DoublyLinkedlist(){
        first = null;
        last = null;
    }
 
    public boolean isEmpty(){
        return first == null;
    }
 
 
    public void insertFirst(int dd){
        DoublyNode newNode = new DoublyNode(dd);
 
        if (isEmpty())
            last = newNode;
        else
            first.previous = newNode;
         
        newNode.next = first;
        first = newNode;
    }
 
 
    public void insertLast(int dd){
        DoublyNode newNode = new DoublyNode(dd);
         
        if (isEmpty())
            first = newNode;
        else {
            last.next = newNode;
            newNode.previous = last;
        }
         
        last = newNode;
    }
 
 
    public DoublyNode deleteFirst(){
        DoublyNode temp = first;
         
        if (first.next == null)
            last = null;
        else
            first.next.previous = null;
         
        first = first.next;
        return temp;
    }
 
 
    public DoublyNode deleteLast(){
        DoublyNode temp = last;
         
        if (first.next == null)
            first = null;
        else
            last.previous.next = null;
         
        last = last.previous;
        return temp;
    }
 
    public boolean insertAfter(long key, int dd) {
        DoublyNode current = first;
         
        while (current.data != key){
            current = current.next;
             
            if (current == null)
                return false;
        }
         
        DoublyNode newNode = new DoublyNode(dd);
 
        if (current == last) {
            newNode.next = null;
            last = newNode;
        } else {
            newNode.next = current.next;
            current.next.previous = newNode;
        }
         
        newNode.previous = current;
        current.next = newNode;
        return true;
    }
     
 
 
    public DoublyNode deleteItem(long key) {
        DoublyNode current = first;
         
        while (current.data != key) {
            current = current.next;
             
            if (current == null)
                return null;
        }
         
        if (current == first)
            first = current.next;
        else
            current.previous.next = current.next;
 
        if (current == last)
            last = current.previous;
        else
            current.next.previous = current.previous;
         
        return current;
    }
     
 
    public void display() {
        System.out.print("List : ");
        DoublyNode current = first;
        while (current != null) {
            current.displayLink();
            System.out.print("->"); 
            current = current.next;
        }
        System.out.println("NULL");
    }
 
 
 
    public static void main(String[] args) {
         
        DoublyLinkedlist theList = new DoublyLinkedlist();
        System.out.println("insert at front: 9, 56, 74");
        theList.insertFirst(9); 
        theList.insertFirst(56);
        theList.insertFirst(74);
        theList.display();
         
        System.out.println("insert at rear: 34, 47, 99");
        theList.insertLast(34);
        theList.insertLast(47);
        theList.insertLast(99);
        theList.display();
        System.out.println();
     
        System.out.println("Delete first item from List");
        theList.deleteFirst();
        System.out.println("Delete last item from List");
        theList.deleteLast();
        theList.display();
        System.out.println();
         
        System.out.println("Delete  item '34' from List");
        theList.deleteItem(34);
        theList.display();
        System.out.println();
         
         
        System.out.println("insert 11 after 9  in List");
        theList.insertAfter(9, 11);
         
        theList.display();
    }
 
}

Output

insert at front: 9, 56, 74
List : 74->56->9->NULL
insert at rear: 34, 47, 99
List : 74->56->9->34->47->99->NULL
 
Delete first item from List
Delete last item from List
List : 56->9->34->47->NULL
 
Delete  item '34' from List
List : 56->9->47->NULL
 
insert 11 after 9  in List
List : 56->9->11->47->NULL

Source Explanation

	Insert function constructs the node using data, previous node, and next node details. It inserts the node in the appropriate location in the linked list.
	Display function iterate all the elements and display.
	Delete operation unlink between two nodes and free the allocated memory.

Complexity

Real Applications

1. Maintain references to active processes, threads, and other dynamic objects in operating system
2. Stack, hash table, and binary tree can be implemented using a doubly linked list.
3. Applications that have an MRU list (a linked list of file names)

Reference

1. https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list
2. http://cslibrary.stanford.edu/103/LinkedListBasics.pdf