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

class Node:
    def __init__(self, value):
        self.data = value
        self.next = None
        self.prev = None
 
 
class Doubly_Linked_List:
    def __init__(self) -> None:
        self.start = None

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

def insertBeginning(self, value):
    newNode = Node(value)
    if self.start is None:
        self.start = newNode
    else:
        newNode.next = self.start
        self.start.prev = newNode
        self.start = newNode

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

def insertEnd(self, value):
    newNode = Node(value)
    if self.start is None:
        self.start = newNode
    else:
        ptr = self.start
        while ptr.next is not None:
            ptr = ptr.next
        ptr.next = newNode
        newNode.prev = ptr

void insert_after(int value, int position) {
    if (start == nullptr) {
        cout << "List is empty!" << endl;
        return;
    }
    Node *ptr = start;
    while (ptr != nullptr && ptr->data != position)
        ptr = ptr->next;
 
    if (ptr == nullptr) {
        cout << "No such element found!" << endl;
        return;
    }
    Node *new_node = new Node(value);
 
    ptr->next->prev = new_node;
    new_node->next = ptr->next;
    new_node->prev = ptr;
    ptr->next = new_node;
    return;
}

def insertAfter(self, value, position):
    if self.start is None:
        print("The Linked List is Empty!")
        return
 
    ptr = self.start
    while ptr.data != position:
        ptr = ptr.next
        if ptr is None:
            print("No such element found in the List!")
            return
 
    newNode = Node(value)
    newNode.next = ptr.next
    newNode.prev = ptr
    ptr.next.prev = newNode
    ptr.next = newNode

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

def insertBefore(self, value, position):
    if self.start is None:
        print("The Linked List is Empty!")
        return
 
    ptr = self.start
    while ptr.data != position:
        ptr = ptr.next
        if ptr is None:
            print("No such element found in the List!")
            return
 
    newNode = Node(value)
    newNode.next = ptr
    newNode.prev = ptr.prev
    ptr.prev.next = newNode
    ptr.prev = newNode

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

def deleteBeginning(self):
    if self.start is None:
        print("The Linked List is Empty!")
        return
 
    if self.start.next is None:
        self.start = None
        return
 
    self.start = self.start.next
    self.start.prev = None

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

def deleteEnd(self):
    if self.start is None:
        print("The Linked List is Empty!")
        return
 
    if self.start.next is None:
        self.start = None
        return
 
    ptr = self.start
    while ptr.next is not None:
        ptr = ptr.next
    ptr.prev.next = None

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

def deleteAfter(self, position):
    if self.start is None:
        print("The Linked List is Empty!")
        return
 
    ptr = self.start
    while ptr.data != position:
        ptr = ptr.next
        if ptr is None:
            print("No such element found in the List!")
            return
 
    if ptr.next is None:
        print("No element after the given position!")
        return
 
    ptr.next = ptr.next.next
    ptr.next.prev = ptr

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

def deleteBefore(self, position):
    if self.start is None:
        print("The Linked List is Empty!")
        return
 
    ptr = self.start
    while ptr.data != position:
        ptr = ptr.next
        if ptr is None:
            print("No such element found in the List!")
            return
 
    if ptr.prev is None:
        print("No element before the given position!")
        return
 
    ptr.prev = ptr.prev.prev
    ptr.prev.next = ptr

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

def display(self):
    if self.start is None:
        print("The Linked List is Empty!")
        return
 
    print('Linked List:', end=" ")
    ptr = self.start
    while ptr is not None:
        print(ptr.data, end=" ")
        ptr = ptr.next
    print()
    return

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

def reverse(self):
    if self.start is None or self.start.next is None:
        return
 
    ptr = self.start
    new_start = None
 
    while ptr:
        temp = ptr.prev
        ptr.prev = ptr.next
        ptr.next = temp
        new_start = ptr
        ptr = ptr.prev
 
    self.start = new_start