#include <iostream>
using namespace std;

class node {
    public:
    int data;
    node *next;
    node(int x){
        data=x;
        next=NULL;
    }
};
class LinkedList{
public:
    node *head;
    void addAtFront(node *n){
        n->next=head;
        head=n;
    };
    bool isEmpty(){
            return (head==NULL)?1:0;
    };
    void addAtEnd(node *n){
        if(head==NULL){
            head=n;
            n->next=NULL;
        }
        else{
            node *n2=getLastNode();
            n2->next=n;

        }
    };
    node* getLastNode(){
        node* ptr=head;
        while(ptr->next!=NULL)
            ptr=ptr->next;
        return ptr;
    };
    node* search(int k){
        node *ptr=head;
        while(ptr!=NULL&&ptr->data!=k){
            ptr=ptr->next;
        }
        return ptr;
    };
    node* deleteNode(int x){
        node *n=search(x);
        node *ptr=head;
        if(ptr==n){
            head=n->next;
            return n;
        }
        else{
            while(ptr->next!=n){
                ptr=ptr->next;
            }
            ptr->next=n->next;
            return n;
        }
    };
    void printList(){
        node *ptr=head;
        while(ptr!=NULL){
            cout<<ptr->data<<"->";
            ptr=ptr->next;
        }
        cout<<"\n";
    };
    LinkedList(){head=NULL;}
};

int main(){
    LinkedList li;
    node *n1=new node(1);
    node *n2=new node(2);
    node *n3=new node(3);
    node *n4=new node(4);
    li.addAtFront(n1);
    li.printList();
    li.addAtFront(n2);
    li.printList();
    li.addAtEnd(n4);
    li.addAtEnd(n3);
    li.printList();
    li.deleteNode(2);
    li.printList();
    return 0;
}