Monday 7 March 2016

Singly Linked List

//package com.college.datastructure;

import java.util.Scanner;

// Singly Node Class
class SinglyNode {

    private int data;
    private SinglyNode link;

    SinglyNode() {
                data = 0;
                link = null;
    }

    SinglyNode(int d, SinglyNode n) {
                data = d;
                link = n;
    }

    public void setLink(SinglyNode n) {
                link = n;
    }

    public SinglyNode getLink() {
                return link;
    }

    public void setData(int d) {
                data = d;
    }

    public int getData() {
                return data;
    }
}


// Singly Linked List Class Implementation
class SinglyLinkedList {

    private static SinglyNode start = null;
    private static int size;

    public SinglyLinkedList() {
                start = null;
                size = 0;
    }

    public int getSize() {
                return size;
    }

    public int insertAtBegin(int val) {

                SinglyNode nPtr = new SinglyNode(val, null);
       
                if(start == null) {
            start = nPtr;
            size++;
            return val;
                }
       
        nPtr.setLink(start);
        start = nPtr;
        size++;
        return val;
    }

    public int insertAtEnd(int val) {

                SinglyNode nPtr = new SinglyNode(val, null);
                SinglyNode temp = start;

                if(start == null) {
                    return insertAtBegin(val);           
                }
       
        while(temp.getLink()!= null)
            temp = temp.getLink();
        temp.setLink(nPtr);
        nPtr.setLink(null);
        size++;
        return val;
    }
   
    public int insertAtPos(int val, int pos) {
        SinglyNode nPtr = new SinglyNode(val, null);
        SinglyNode ptr = start;
       
        if(pos > size || pos <= 0)
            return -1;
        if(pos == 1) {
            return insertAtBegin(val);           
        }
               
        for(int i=1; i<size; i++) {
            if(i == pos-1) {               
                nPtr.setLink(ptr.getLink());
                ptr.setLink(nPtr);
                break;
            } else
                ptr = ptr.getLink();
        }
        size++;
        return val;
    }
   
    public int deleteAtStart() {
        if(start == null) {
            return -1;
        }
        int data = start.getData();
        start = start.getLink();
        size--;
        return data;
    }
   
    public int deleteAtEnd() {
        if(start == null) {
            return -1;
        }
        SinglyNode ptr = start;
        while((ptr.getLink()).getLink() != null)
            ptr = ptr.getLink();
        int data = ptr.getLink().getData();
        ptr.setLink(null);
        size--;
        return data;
    }
   
    public int deleteAtPos(int pos) {
        if(pos > size || pos <= 0) {
            return -1;
        }
        if(pos == 1) {
            return deleteAtStart();           
        }
       
        if(pos == size) {
            return deleteAtEnd();           
        }
       
        SinglyNode ptr = start;
        int data = 0;
       
        for(int i=1; i<size; i++) {
            if(i == pos-1) {
                data = ptr.getLink().getData();
                SinglyNode temp = ptr.getLink();
                ptr.setLink(temp.getLink());
            }
            ptr = ptr.getLink();           
        }
       
        size--;
        return data;
    }
   
    public int deleteByData(int data) {
        SinglyNode ptr = start;
        if(ptr == null) {
            return -1;
        }
        int i = 1;
        while(true) {
            if(ptr.getData() == data) {
                return deleteAtPos(i);               
            }
            ptr = ptr.getLink();
            i++;
        }
    }
   
    public void display() {       
        if(start == null) {
            System.out.println(" List is Empty. ");
            return ;
        }
       
        SinglyNode ptr = start;
        System.out.println(" List Items are : \n");
       
        while(ptr != null) {
            System.out.print(" ->  " + ptr.getData());
            ptr = ptr.getLink();
        }
        System.out.println("");
    }
}

// Main Class
public class SinglyLinkedListImp {
   
    public static void main(String[] ar) {
       
        Scanner input = new Scanner(System.in);

        SinglyLinkedList singlyLinkedList = new SinglyLinkedList();
        int ch, value, 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 \n Press '0' For Exit.");

            System.out.print("\n Enter your choice : ");
            ch = input.nextInt();

            switch(ch) {

                case 0:
                    return;
                   
                case 1:
                    //1. Insert At Front
                    System.out.print("\n Enter value : ");
                    value = input.nextInt();
                    int insertAtBegin = singlyLinkedList.insertAtBegin(value);                   
                    System.out.println(" Item " + insertAtBegin + " inserted.");
                    break;
                   
                case 2:
                    //2. Insert At Rear
                    System.out.print("\n Enter value : ");
                    value = input.nextInt();
                    int insertAtEnd = singlyLinkedList.insertAtEnd(value);                   
                    System.out.println(" Item " + insertAtEnd + " inserted.");
                    break;
                   
                case 3:
                    //3. Insert At Pos
                    System.out.print("\n Enter position : ");
                    pos = input.nextInt();
                   
                    System.out.print(" Enter value : ");
                    value = input.nextInt();
                   
                    int insertAtPos = singlyLinkedList.insertAtPos(value, pos);
                   
                    if(insertAtPos < 0) {
                        System.out.println(" Position not Available ");
                        break;
                    }
                    System.out.println(" Item " + insertAtPos + " inserted at Position " + pos);
                    break;
               
                case 4:
                    //4. Delete At Begin
                    int deleteAtStart = singlyLinkedList.deleteAtStart();
                    if(deleteAtStart < 0) {
                        System.out.println("\n List is Empty.");
                        break;
                    }
                    System.out.println("\n Item " + deleteAtStart + " deleted.");
                    break;
                   
                case 5:
                    //5. Delete At End
                    int deleteAtEnd = singlyLinkedList.deleteAtEnd();
                    if(deleteAtEnd < 0) {
                        System.out.println("\n List is Empty.");
                        break;
                    }
                    System.out.println("\n Item " + deleteAtEnd + " deleted.");
                    break;
                   
                case 6:                   
                    //6. Delete At Position
                    System.out.print("\n Enter Position : ");
                    int deleteAtPos = singlyLinkedList.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 : ");
                    int data = input.nextInt();
                    int deleteByData = singlyLinkedList.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 = singlyLinkedList.getSize();
                    if(size < 0)
                        System.out.println(" List is Empty. ");
                    else
                        System.out.println(" Size of List : " + size);
                    break;
                   
                case 9:
                    //9. Display
                    singlyLinkedList.display();
                    break;
                   
                default:
                    System.out.println("\n Wrong Choice Entered...!");
            }
        }
    }

}
Posted by at No comments:

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:
Subscribe to: Posts (Atom)