Saturday, 5 March 2016

Doubly Linked List

import java.util.Scanner;

// Doubly Node Class
class DoublyNode {
    private int data;
    private DoublyNode front, rear;
   
    DoublyNode() {
        data = 0;
        front = rear = null;
    }
   
    DoublyNode(int d) {
        data = d;
        front = rear = null;
    }
   
    DoublyNode(int d, DoublyNode f, DoublyNode r) {
        data = d;
        front = f;
        rear = r;
    }
   
    public void setFrontLink(DoublyNode link) {
        this.front = link;
    }
   
    public DoublyNode getFrontLink() {
        return front;
    }
   
    public void setRearLink(DoublyNode n) {
        this.rear = n;
    }
   
    public DoublyNode getRearLink() {
        return rear;
    }
   
    public void setData(int d) {
        this.data = d;
    }
   
    public int getData() {
        return data;
    }   
}

// Doubly Linked List Class Implementation
class DoubleLinkedList {
   
    DoublyNode front, rear;
    int size;
   
    DoubleLinkedList() {
        front = rear = null;
        size = 0;
    }
   
    int insertAtFront(int d) {
        DoublyNode node = new DoublyNode(d);
        if(front == null) {
            node.setFrontLink(null);
            node.setRearLink(null);
            front = rear = node;           
        } else {
            front.setRearLink(node);
            node.setFrontLink(front);
            node.setRearLink(null);
            front = node;
        }
        size++;
        return d;
    }
   
    int insertAtRear(int d) {
        DoublyNode node = new DoublyNode(d);
        if(front == null) {
            return insertAtFront(d);
        } else {
            node.setRearLink(rear);
            rear.setFrontLink(node);
            node.setFrontLink(null);
            rear = node;
        }
        size++;
        return d;
    }
   
    int insertAtPos(int d, int pos) {
        DoublyNode node = new DoublyNode(d);
        if(pos > size || pos <= 0)
            return -1;
        if(pos == 1)
            return insertAtFront(d);
       
        DoublyNode ptr = front;
        for(int i=1; i<size; i++) {
            if(i == pos-1) {
                node.setRearLink(ptr);
                node.setFrontLink(ptr.getFrontLink());
                ptr.setFrontLink(node);
                ptr = ptr.getFrontLink().getFrontLink();
                ptr.setRearLink(node);
                size++;
                return d;
            } else
                ptr = ptr.getFrontLink();
        }
        size++;
        return d;
    }
   
    public int deleteAtBegin() {
        if(front == null)
            return -1;       
        int data = front.getData();       
        if(front.getFrontLink() == null) {           
            front = null;
            rear = null;
            size--;
            return data;
        }
       
        DoublyNode temp = front;
       
        front = front.getFrontLink();       
        front.setRearLink(null);
        temp.setFrontLink(null);
        size--;
        return data;
    }
   
    public int deleteAtRear() {
        if(size == 0)
            return -1;
       
        int data = rear.getData();
       
        // If only one node is present.
        if(front.getFrontLink()== null) {
            rear = null;
            front = null;
            size--;
            return data;
        }
       
        DoublyNode temp = rear;
        rear = rear.getRearLink();
        rear.setFrontLink(null);
        temp.setRearLink(null);
       
        size--;
        System.out.println(" rear " + rear.getData());
        return data;
    }
   
    public int deleteAtPos(int pos) {
        if(pos > size ||pos <= 0)
            return -1;
        if(pos == 1)
            return deleteAtBegin();
        if(pos == size)
            return deleteAtRear();
               
        DoublyNode ptr = front;
        int data = 0;
       
        for(int i=1; i<size; i++) {
            if(i == pos-1) {
                DoublyNode temp = ptr.getFrontLink().getFrontLink();
                temp.setRearLink(ptr);
                temp = ptr.getFrontLink();
                ptr.setFrontLink(ptr.getFrontLink().getFrontLink());
                data = temp.getData();
                temp.setRearLink(null);
                temp.setFrontLink(null);
            }
            ptr = ptr.getFrontLink();           
        }
        size--;
        return data;
    }
   
    public int deleteByData(int d) {
        if(size <= 0)
            return -1;
        DoublyNode ptr = front;
        int i=1;
        while(true) {
            if(ptr.getData() == d) {
                return deleteAtPos(i);
            }
            i++;
            ptr = ptr.getFrontLink();
        }
    }
   
    public int getSize() {
        return size;
    }
   
    public void display() {
        if(front == null) {
            System.out.println("\n List is Empty.");
            return;
        }
       
        DoublyNode ptr = front;
        System.out.println(" List Items are : \n");
        while(ptr != null) {
            System.out.print(" ->  " + ptr.getData());
            ptr = ptr.getFrontLink();
        }
        System.out.println("");
    }
   
    public void displayReverse() {
        if(rear == null) {
            System.out.println(" List is Empty. ");
            return;
        }
       
        DoublyNode ptr = rear;
        System.out.println(" List Items are (in Reverse) : \n");
       
        while(ptr != null) {
            System.out.print(" -> " + ptr.getData());
            ptr = ptr.getRearLink();
        }
        System.out.println("");
    }
}

// Main Class
public class DoublyLinkedListImp {
   
    public static void main(String[] args) {
       
        Scanner input = new Scanner(System.in);
       
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        int data, returnData, pos;
       
        while(true) {
            System.out.println("\n 1. Insert At Front \t 2. Insert At Rear \n 3. Insert At Pos \t 4. Delete At Begin \n 5. Delete At End \t 6. Delete At Position \n 7. Delete By Data \t 8. Size \n 9. Display \t\t 10. Reverse Display \n Press '0' For Exit.");
            System.out.print("\n Enter your choice : ");
            int ch = input.nextInt();
           
            switch(ch) {
                case 0:
                    //1.For Exit.
                    return;
                   
                case 1:
                    //1. Insert At Front
                    System.out.print("\n Enter Data : ");
                    data = input.nextInt();
                    returnData = doubleLinkedList.insertAtFront(data);
                    System.out.println(" Item " + returnData + " inserted.");
                    break;
                   
                case 2:
                    //2. Insert At Rear
                    System.out.print("\n Enter Data : ");
                    data = input.nextInt();
                    returnData = doubleLinkedList.insertAtRear(data);
                    System.out.println(" Item " + returnData + " inserted.");
                    break;
                   
                case 3:
                    //3. Insert At Pos
                    System.out.print("\n Enter Pos : ");
                    pos = input.nextInt();
                    System.out.print(" Enter Data : ");
                    data = input.nextInt();
                    returnData = doubleLinkedList.insertAtPos(data, pos);
                    if(returnData < 0) {
                        System.out.println(" Position not Available ");
                        break;
                    }
                    System.out.println(" Item " + returnData + " inserted at Position " + pos);
                    break;
                   
                case 4:
                    //4. Delete At Begin
                    int deleteAtBegin = doubleLinkedList.deleteAtBegin();
                    if(deleteAtBegin < 0) {
                        System.out.println("\n List is Empty.");
                        break;
                    }
                    System.out.println("\n Item " + deleteAtBegin + " deleted.");
                    break;
                   
                case 5:
                    //5. Delete At End
                    int deleteAtRear = doubleLinkedList.deleteAtRear();
                    if(deleteAtRear < 0) {
                        System.out.println("\n List is Empty.");
                        break;
                    }
                    System.out.println("\n Item " + deleteAtRear + " deleted.");
                    break;
                   
                case 6:
                    //6. Delete At Position
                    System.out.print("\n Enter Position : ");
                    int deleteAtPos = doubleLinkedList.deleteAtPos(input.nextInt());
                    if(deleteAtPos < 0) {
                        System.out.println(" Either list is empty or invalid position. ");
                        break;
                    }
                    System.out.println(" Item " + deleteAtPos + " deleted.");
                    break;

                case 7:
                    //7. Delete By Data
                    System.out.print("\n Enter Data : ");
                    data = input.nextInt();
                    int deleteByData = doubleLinkedList.deleteByData(data);
                    if(deleteByData < 0)
                        System.out.println(" List is Empty.");
                    else
                        System.out.println(" Item " + deleteByData + " Deleted ");
                    break;
                   
                case 8:
                    //9. Size
                    int size = doubleLinkedList.getSize();
                    if(size < 0)
                        System.out.println(" List is Empty. ");
                    else
                        System.out.println(" Size of List : " + size);
                    break;
                   
                case 9:
                    //8. Display
                    doubleLinkedList.display();
                    break;
               
                case 10:
                    //8. Display
                    doubleLinkedList.displayReverse();
                    break;               
               
                default:
                    System.out.println("\n Wrong choice entered.");
            }
        }
    }

}
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)