// Node class - represents one element in the list
class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// Singly Linked List Implementation
public class SinglyLinkedList {

    Node head;  // first node
    int size;   // count of nodes

    // Insert at the beginning
    public void addFirst(int value) {
        Node newNode = new Node(value);
        newNode.next = head;  // link new node to current head
        head = newNode;       // update head
        size++;
    }

    // Insert at the end
    public void addLast(int value) {
        Node newNode = new Node(value);

        if (head == null) {
            head = newNode;   // list was empty
        } else {
            Node temp = head;
            while (temp.next != null) {  // go to last node
                temp = temp.next;
            }
            temp.next = newNode;  // link last node to new node
        }
        size++;
    }

    // Insert at a specific index
    public void addAt(int index, int value) {
        if (index < 0 || index > size) {
            System.out.println("Invalid index");
            return;
        }

        if (index == 0) {
            addFirst(value);
            return;
        }

        Node newNode = new Node(value);
        Node temp = head;

        // move to index - 1
        for (int i = 0; i < index - 1; i++) {
            temp = temp.next;
        }

        newNode.next = temp.next; // link
        temp.next = newNode;      // insert
        size++;
    }

    // Delete first node
    public void removeFirst() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }

        head = head.next; // move head pointer
        size--;
    }

    // Delete last node
    public void removeLast() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }

        if (head.next == null) { // only one element
            head = null;
        } else {
            Node temp = head;

            while (temp.next.next != null) {
                temp = temp.next; // go to second last
            }

            temp.next = null; // remove last node
        }
        size--;
    }

    // Search a value
    public int search(int value) {
        Node temp = head;
        int index = 0;

        while (temp != null) {
            if (temp.data == value) {
                return index; // found
            }
            temp = temp.next;
            index++;
        }

        return -1; // not found
    }

    // Print the linked list
    public void printList() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }

        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " → ");
            temp = temp.next;
        }
        System.out.println("null");
    }

    // Return size of the list
    public int getSize() {
        return size;
    }

    // Test the implementation
    public static void main(String[] args) {

        SinglyLinkedList list = new SinglyLinkedList();

        // Inserting elements
        list.addLast(10);
        list.addLast(20);
        list.addFirst(5);
        list.addAt(2, 15);

        System.out.print("List after insertions: ");
        list.printList(); // 5 → 10 → 15 → 20 → null

        // Deleting elements
        list.removeFirst();
        list.removeLast();

        System.out.print("List after deletions: ");
        list.printList(); // 10 → 15 → null

        // Searching
        int pos = list.search(15);
        if (pos != -1) {
            System.out.println("15 found at index: " + pos);
        } else {
            System.out.println("Value not found");
        }

        // Size
        System.out.println("Current size: " + list.getSize());
    }
}