class Node {
public:
    int data;
    Node *next;
 
    Node(int value) {
        data = value;
        next = nullptr;
    }
};
 
class Linked_List {
private:
    Node *start = nullptr;
 
public:
    Linked_List() {
        start = nullptr;
    }
};

class node:
    def __init__(self, data) -> None:
        self.data = data
        self.next = None
 
class LinkedList:
    def __init__(self) -> None:
        self.start = None

void insert_beginning(int value)
{
    Node *new_node = new Node(value);
    if (start == nullptr)
        start = new_node;
    else
    {
        new_node->next = start;
        start = new_node;
    }
    return;
}

def insertFirst(self, value):
    newNode = node(value)
    newNode.next = self.start
    self.start = newNode

void insert_end(int value)
{
    Node *new_node = new Node(value);
    if (start == nullptr)
        start = new_node;
    else
    {
        Node *temp = start;
        while (temp->next != nullptr)
            temp = temp->next;
 
        temp->next = new_node;
        new_node->next = nullptr;
    }
    return;
}

def insertLast(self, value):
    newNode = node(value)
    if self.start == None:
        self.start = newNode
    else:
        temp = self.start
        while temp.next is not None:
            temp = temp.next
        temp.next = newNode

void insert_after(int value, int pos)
{
    if (start == nullptr) {
        cout << "Empty List!" << endl;
        return;
    }
 
    Node *new_node = new Node(value);
    Node *temp = start;
 
    while (temp != nullptr && temp->data != pos)
        temp = temp->next;
 
    if (temp == nullptr)
    {
        cout << "No such element found" << endl;
        delete new_node;
        return;
    }
    new_node->next = temp->next;
    temp->next = new_node;
}

def insertAfter(self, value, pos):
    newNode = node(value)
    if self.start == None:
        print("The node is not present in the list")
    else:
        temp = self.start
        while temp.data != pos:
            temp = temp.next
        newNode.next = temp.next
        temp.next = newNode

void insert_before(int value, int pos) {
    if (start == nullptr) {
        cout << "Empty List!" << endl;
        return;
    }
 
    Node *new_node = new Node(value);
    Node *ptr = start;
    Node *pre_ptr = nullptr;
 
    while (ptr != nullptr && ptr->data != pos) {
        pre_ptr = ptr;
        ptr = ptr->next;
    }
 
    if (ptr == nullptr) {
        cout << "No such element found" << endl;
        delete new_node;
        return;
    }
 
    if (pre_ptr == nullptr) {
        new_node->next = start;
        start = new_node;
    }
    else {
        new_node->next = ptr;
        pre_ptr->next = new_node;
    }
}

def insertBefore(self, value, pos):
    newNode = node(value)
    if self.start == None:
        print("The node is not present in the linked List")
    else:
        temp = self.start
        while temp.next.data != pos:
            temp = temp.next
        newNode.next = temp.next
        temp.next = newNode

void delete_beginning() {
    if (start == nullptr) {
        cout << "List is empty!" << endl;
        return;
    }
 
    Node *ptr = start;
    start = start->next;
    delete ptr;
}

def deleteFirst(self):
    if self.start == None:
        print("The Linked List is Empty!")
    else:
        self.start = self.start.next

void delete_end() {
    if (start == nullptr) {
        cout << "List is empty!" << endl;
        return;
    }
 
    Node *temp = start;
    if (temp->next == nullptr) {
        // Only one node in the list
        delete temp;
        start = nullptr;
        return;
    }
 
    while (temp->next->next != nullptr)
        temp = temp->next;
 
    delete temp->next;
    temp->next = nullptr;
}

def deleteLast(self):
    if self.start == None:
        print("The Linked list is Empty!")
    else:
        temp = self.start
        while temp.next.next != None:
            temp = temp.next
        temp.next = None

void delete_after(int pos) {
    if (start == nullptr) {
        cout << "List is empty!" << endl;
        return;
    }
 
    Node *ptr = start;
    while (ptr != nullptr && ptr->data != pos)
        ptr = ptr->next;
 
    if (ptr == nullptr || ptr->next == nullptr) {
        cout << "No such element found!" << endl;
        return;
    }
 
    Node *temp = ptr->next;
    ptr->next = temp->next;
    delete temp;
}

def deleteAfter(self, pos):
    if self.start != None:
        temp = self.start
        while temp.data != pos:
            temp = temp.next
        temp.next = temp.next.next

void delete_before(int pos) {
    if (start == nullptr || start->next == nullptr) {
        cout << "List is empty or has only one node!" << endl;
        return;
    }
 
    if (start->data == pos) {
        cout << "No element found before the specified position!" << endl;
        return;
    }
 
    if (start->next->data == pos) {
        Node *temp = start;
        start = start->next;
        delete temp;
        return;
    }
 
    Node *ptr = start->next;
    Node *pre_ptr = start;
    Node *pre_pre = nullptr;
 
    while (ptr != nullptr && ptr->data != pos) {
        pre_pre = pre_ptr;
        pre_ptr = ptr;
        ptr = ptr->next;
    }
 
    if (ptr == nullptr) {
        cout << "No such element found!" << endl;
        return;
    }
 
    pre_pre->next = ptr;
    delete pre_ptr;
}

def deleteBefore(self, pos):
    if self.start is None or self.start.next is None:
        print("List is too short!")
        return
    if self.start.next.data == pos:
        self.start = self.start.next
        return
    temp = self.start
    while temp.next.next is not None and temp.next.next.data != pos:
        temp = temp.next
    if temp.next.next is None:
        print("No such element found!")
        return
    temp.next = temp.next.next

void count_nodes()
{
    int count = 0;
    Node *ptr = start;
 
    while (ptr != nullptr) {
        count++;
        ptr = ptr->next;
    }
 
    cout << "There are " << count << " nodes in the linked list." << endl;
}

def countNodes(self):
    count = 0
    temp = self.start
    while temp:
        count += 1
        temp = temp.next
    print(f"There are {count} nodes in the linked list.")

void display() {
    if (start == nullptr) {
        cout << "Empty List!" << endl;
        return;
    }
 
    cout << "The elements in the linked list are:" << endl;
    Node *ptr = start;
 
    while (ptr != nullptr) {
        cout << ptr->data << " -> ";
        ptr = ptr->next;
    }
    cout << "NULL" << endl;
}

def display(self):
    if self.start == None:
        print("The Linked list is Empty!")
    else:
        temp = self.start
        while temp:
            print(temp.data, end=" -> ")
            temp = temp.next
        print("None")

void reverse()
{
    if (start == nullptr)
    {
        cout << "Empty List!" << endl;
        return;
    }
    Node *prev_ptr = nullptr, *current_ptr = start, *next_ptr = nullptr;
    while (current_ptr != nullptr)
    {
        next_ptr = current_ptr->next;
        current_ptr->next = prev_ptr;
        prev_ptr = current_ptr;
        current_ptr = next_ptr;
    }
    start = prev_ptr;
}

def reverse(self):
    if self.start == None:
        print("The Linked list is Empty!")
        return
    prevPtr = None
    currentPtr = self.start
    nextPtr = None
 
    while (currentPtr != None):
        nextPtr = currentPtr.next
        currentPtr.next = prevPtr
        prevPtr = currentPtr
        currentPtr = nextPtr
 
    self.start = prevPtr