package org.arpit.java2blog.datastructures;
 
class Node {
    public int data;
    public Node next;
    public Node prev;
 
    public void displayNodeData() {
        System.out.println("{ " + data + " } ");
    }
}
 
public class MyDoublyLinkedList {
 
    private Node head;
    private Node tail;
    int size;
 
    public boolean isEmpty() {
        return (head == null);
    }
 
    // متد برای درج گره در ابتدای لیست پیوندی
    public void insertFirst(int data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = head;
        newNode.prev=null;
        if(head!=null)
            head.prev=newNode;
        head = newNode;
        if(tail==null)
            tail=newNode;
        size++;
    }
 
    // متد برای درج گره در انتهای لیست پیوندی
    public void insertLast(int data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = null;
        newNode.prev=tail;
        if(tail!=null)
            tail.next=newNode;
        tail = newNode;
        if(head==null)
            head=newNode;
        size++;
    }
    // متد حذف گره از ابتدای لیست پیوندی دو طرفه
    public Node deleteFirst() {
 
        if (size == 0)
            throw new RuntimeException("Doubly linked list is already empty");
        Node temp = head;
        head = head.next;
        head.prev = null;
        size--;
        return temp;
    }
 
    // متد حذف گره از انتهای لیست پیوندی دو طرفه
    public Node deleteLast() {
 
        Node temp = tail;
        tail = tail.prev;
        tail.next=null;
        size--;
        return temp;
    }
 
    // متد برای حذف گره پس از یک گره خاص
    public void deleteAfter(Node after) {
        Node temp = head;
        while (temp.next != null && temp.data != after.data) {
            temp = temp.next;
        }
        if (temp.next != null)
            temp.next.next.prev=temp;
        temp.next = temp.next.next;
 
    }
 
    // (Forward) متد چاپ لیست پیوندی دو طرفه رو به جلو 
    public void printLinkedListForward() {
        System.out.println("Printing Doubly LinkedList (head --> tail) ");
        Node current = head;
        while (current != null) {
            current.displayNodeData();
            current = current.next;
        }
        System.out.println();
    }
 
    // (Backward) متد چاپ لیست پیوندی دو طرفه رو به عقب
    public void printLinkedListBackward() {
        System.out.println("Printing Doubly LinkedList (tail --> head) ");
        Node current = tail;
        while (current != null) {
            current.displayNodeData();
            current = current.prev;
        }
        System.out.println();
    }
 
    public static void main(String args[])
    {
        MyDoublyLinkedList mdll = new MyDoublyLinkedList();
        mdll.insertFirst(50);
        mdll.insertFirst(60);
        mdll.insertFirst(70);
        mdll.insertFirst(10);
        mdll.insertLast(20);
        mdll.printLinkedListForward();
        mdll.printLinkedListBackward();
 
        System.out.println("================");
        // :لیست پیوندی دو طرفه به صورت زیر خواهد بود
        // 10 ->  70 -> 60 -> 50 -> 20
 
        Node node=new Node();
        node.data=10;
        mdll.deleteAfter(node);
        mdll.printLinkedListForward();
        mdll.printLinkedListBackward();
        // :بعد از حذف نود پس از ۱، لیست پیوندی به صورت زیر خواهد شد
        // 20 -> 10 -> 60-> 50
        System.out.println("================");
        mdll.deleteFirst();
        mdll.deleteLast();
 
        // :پس از انجام عملیات فوق، لیست پیوندی به صورت زیر خواهد شد
        //  60 -> 50
        mdll.printLinkedListForward();
        mdll.printLinkedListBackward();
    }
}