package datastruct;


public class DataStruct {
    int Listsize=0;
 class Node{
        int data;
        Node previous;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    //Represent the head and tail of the doubly linked list
    Node head, tail = null;

    //addNode() will add a node to the list
    public void addNode(int data) {
        //Create a new node
        Node newNode = new Node(data);
        Listsize++;

        //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 = tail;
            //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 back to head
            tail.next = head;
        }
    }

    //display() will print out the nodes of the list
    public void display() {
        int counter=0;
        //Node current will point to head
        Node current = head;
        if(head == null) {
            System.out.println("List is empty");
            return;
        }
        System.out.println("Nodes of doubly linked list: ");
        while(counter != Listsize ) {
            //Prints each node by incrementing the pointer.

            System.out.print(current.data + " ");
            current = current.next;
            counter++;
        }
    }
    public void findDupes(){
        int counter=0;
      Node next;
        Node current = head;
      next = current.next;
      do {
          if (current.data == next.data){
              System.out.println("Found duplicate record between "+current.data+" location "+counter+" and "+next.data+" location "+(counter+1));
          }
          else
              next = next.next;
              current = next;
              counter++;
      } while (counter != Listsize);

    }
    public static void main(String[] args) {

        DataStruct dList = new DataStruct();
        //Add nodes to the list
        dList.addNode(562);
        dList.addNode(455);
        dList.addNode(655);
        dList.addNode(344);
        dList.addNode(455);
        //Displays the nodes present in the list
        dList.display();
        dList.findDupes();
    }
}