#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;
}