#include <iostream>
using namespace std;
#define null NULL
class node
{
public :
int data;
node * next;
node * prev;
} ;
class doublelinkedlist
{
public :
node * head;
doublelinkedlist( )
{
head= null;
}
void insert_first( int x)
{
node * newnode= new node;
newnode- > data= x;
newnode- > next= head;
newnode- > prev= null;
if ( head! = null)
{
head- > prev= newnode;
}
head= newnode;
}
void insert_last( int x)
{
node * newnode= new node;
newnode- > data= x;
newnode- > next= null;
newnode- > prev= null;
if ( head== null)
{
head= newnode;
}
else
{
node * temp= head;
while ( temp- > next! = null)
{
temp= temp- > next;
}
temp- > next= newnode;
newnode- > prev= temp;
}
}
void delete_first( )
{
if ( head== null)
{
cout << "invalid operation \n " ;
return ;
}
else
{
node * temp= head;
head= head- > next;
if ( head! = null)
{
head- > prev= null;
}
delete temp;
}
}
void delete_last( )
{
if ( head== null)
{
cout << "list empty\n " ;
return ;
}
node * temp= head;
while ( temp- > next! = null)
{
temp= temp- > next;
}
if ( temp- > prev== null)
{
head= null;
}
else
{
temp- > prev- > next= null;
}
delete temp;
}
void delete_byvalue( int x)
{
node * temp = head;
while ( temp! = null&& temp- > data! = x)
{
temp= temp- > next;
}
if ( temp== null)
{
cout << "not found the value \n " ;
return ;
}
if ( temp- > prev== null)
{
head= temp- > next;
}
else
{
temp- > prev- > next= temp- > next;
}
if ( temp- > next! = null)
{
temp- > next- > prev= temp- > prev;
}
delete temp;
}
void printfrombegging( )
{
node * temp= head;
if ( head== null)
{
cout << "list is empty\n " ;
return ;
}
while ( temp! = null)
{
cout << temp- > data << " " ;
temp= temp- > next;
}
cout << "\n " ;
}
void printfromend( )
{
if ( head== null)
{
cout << "list is empty\n " ;
return ;
}
node * temp= head;
while ( temp- > next! = null)
{
temp= temp- > next;
}
if ( temp- > prev== null)
{
cout << temp- > data<< "\n " ;
return ;
}
while ( temp! = null)
{
cout << temp- > data<< " " ;
temp= temp- > prev;
}
}
} ;
int main( )
{
doublelinkedlist test;
test.insert_last ( 10 ) ;
test.insert_last ( 20 ) ;
test.insert_last ( 30 ) ;
cout << "Original List: " ;
test.printfrombegging ( ) ;
test.insert_first ( 5 ) ;
cout << "After Insert First: " ;
test.printfrombegging ( ) ;
cout << "Backward: " ;
test.printfromend ( ) ;
test.delete_first ( ) ;
cout << "\n After Delete First: " ;
test.printfrombegging ( ) ;
test.delete_last ( ) ;
cout << "After Delete Last: " ;
test.printfrombegging ( ) ;
test.delete_byvalue ( 20 ) ;
cout << "After Delete Value 20: " ;
test.printfrombegging ( ) ;
test.delete_byvalue ( 100 ) ;
cout << "Final List: " ;
test.printfrombegging ( ) ;
return 0 ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIG51bGwgTlVMTApjbGFzcyBub2RlCnsKICAgIHB1YmxpYyA6CiAgICBpbnQgZGF0YTsKICAgIG5vZGUgKiBuZXh0OwogICAgbm9kZSAqIHByZXY7Cn07CmNsYXNzIGRvdWJsZWxpbmtlZGxpc3QKewogICAgcHVibGljIDoKICAgIG5vZGUgKiBoZWFkOwogICAgZG91YmxlbGlua2VkbGlzdCgpCiAgICB7CiAgICAgICAgaGVhZD1udWxsOwogICAgfQogICAgdm9pZCBpbnNlcnRfZmlyc3QoaW50IHgpCiAgICB7CiAgICAgICAgbm9kZSAqIG5ld25vZGU9bmV3IG5vZGU7CiAgICAgICAgbmV3bm9kZS0+ZGF0YT14OwogICAgICAgIG5ld25vZGUtPm5leHQ9aGVhZDsKICAgICAgICBuZXdub2RlLT5wcmV2PW51bGw7CiAgICAgICAgaWYoaGVhZCE9bnVsbCkKICAgICAgICB7CiAgICAgICAgICAgIGhlYWQtPnByZXY9bmV3bm9kZTsKICAgICAgICB9CiAgICAgICAgaGVhZD1uZXdub2RlOwogICAgfQogICAgdm9pZCBpbnNlcnRfbGFzdChpbnQgeCkKICAgIHsKICAgICAgICBub2RlICogbmV3bm9kZT1uZXcgbm9kZTsKICAgICAgICBuZXdub2RlLT5kYXRhPXg7CiAgICAgICAgbmV3bm9kZS0+bmV4dD1udWxsOwogICAgICAgIG5ld25vZGUtPnByZXY9bnVsbDsKICAgICAgICBpZihoZWFkPT1udWxsKQogICAgICAgIHsKICAgICAgICAgICAgaGVhZD1uZXdub2RlOwoKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgbm9kZSAqIHRlbXA9aGVhZDsKICAgICAgICAgICAgd2hpbGUodGVtcC0+bmV4dCE9bnVsbCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgdGVtcD10ZW1wLT5uZXh0OwogICAgICAgICAgICB9CiAgICAgICAgICAgIHRlbXAtPm5leHQ9bmV3bm9kZTsKICAgICAgICAgICAgbmV3bm9kZS0+cHJldj10ZW1wOwogICAgICAgIH0KICAgIH0KICAgIHZvaWQgZGVsZXRlX2ZpcnN0KCkKICAgIHsKICAgICAgICBpZihoZWFkPT1udWxsKQogICAgICAgIHsKICAgICAgICAgICAgY291dDw8ImludmFsaWQgb3BlcmF0aW9uIFxuIjsKICAgICAgICAgICAgcmV0dXJuIDsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgbm9kZSAqIHRlbXA9aGVhZDsKICAgICAgICAgICAgaGVhZD1oZWFkLT5uZXh0OwogICAgICAgICAgICBpZihoZWFkIT1udWxsKQogICAgICAgICAgICB7CgogICAgICAgICAgICBoZWFkLT5wcmV2PW51bGw7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZGVsZXRlIHRlbXA7CiAgICAgICAgfQogICAgfQogICAgdm9pZCBkZWxldGVfbGFzdCgpCiAgICB7CiAgICAgICAgaWYoaGVhZD09bnVsbCkKICAgICAgICB7CiAgICAgICAgICAgIGNvdXQ8PCJsaXN0IGVtcHR5XG4iOwogICAgICAgICAgICByZXR1cm4gOwogICAgICAgIH0KICAgICAgICBub2RlICogdGVtcD1oZWFkOwogICAgICAgIHdoaWxlKHRlbXAtPm5leHQhPW51bGwpCiAgICAgICAgewogICAgICAgICAgICB0ZW1wPXRlbXAtPm5leHQ7CiAgICAgICAgfQogICAgICAgIGlmKHRlbXAtPnByZXY9PW51bGwpCiAgICAgICAgewogICAgICAgICAgICBoZWFkPW51bGw7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIHRlbXAtPnByZXYtPm5leHQ9bnVsbDsKICAgICAgICB9CiAgICAgICAgZGVsZXRlIHRlbXA7CiAgICB9CiAgICB2b2lkIGRlbGV0ZV9ieXZhbHVlKGludCB4KQogICAgewogICAgICAgIG5vZGUgKiB0ZW1wID0gaGVhZDsKICAgICAgICB3aGlsZSh0ZW1wIT1udWxsJiYgdGVtcC0+ZGF0YSE9eCkKICAgICAgICB7CiAgICAgICAgICAgdGVtcD10ZW1wLT5uZXh0OwogICAgICAgIH0KICAgICAgICAgICAgaWYodGVtcD09bnVsbCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgY291dDw8Im5vdCBmb3VuZCB0aGUgdmFsdWUgXG4iOwogICAgICAgICAgICAgICAgcmV0dXJuIDsKICAgICAgICAgICAgfQogICAgICAgICAgICBpZih0ZW1wLT5wcmV2PT1udWxsKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBoZWFkPXRlbXAtPm5leHQ7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgIHRlbXAtPnByZXYtPm5leHQ9dGVtcC0+bmV4dDsKICAgICAgICAgICAgfQogICAgICAgICAgICBpZih0ZW1wLT5uZXh0IT1udWxsKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB0ZW1wLT5uZXh0LT5wcmV2PXRlbXAtPnByZXY7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZGVsZXRlIHRlbXA7CiAgICB9CiAgICB2b2lkIHByaW50ZnJvbWJlZ2dpbmcoKQogICAgewogICAgICAgIG5vZGUgKiB0ZW1wPWhlYWQ7CiAgICAgICAgaWYoaGVhZD09bnVsbCkKICAgICAgICB7CiAgICAgICAgICAgIGNvdXQ8PCJsaXN0IGlzIGVtcHR5XG4iOwogICAgICAgICAgICByZXR1cm4gOwogICAgICAgIH0KICAgICAgICB3aGlsZSh0ZW1wIT1udWxsKQogICAgICAgIHsKICAgICAgICAgICAgY291dDw8dGVtcC0+ZGF0YSA8PCIgIjsKICAgICAgICAgICAgdGVtcD10ZW1wLT5uZXh0OwogICAgICAgIH0KICAgICAgICBjb3V0PDwiXG4iOwoKICAgIH0KICAgIHZvaWQgcHJpbnRmcm9tZW5kKCkKICAgIHsKICAgICAgICBpZihoZWFkPT1udWxsKQogICAgICAgIHsKICAgICAgICAgICAgY291dDw8Imxpc3QgaXMgZW1wdHlcbiI7CiAgICAgICAgICAgIHJldHVybiA7CiAgICAgICAgfQogICAgICAgIG5vZGUgKiB0ZW1wPWhlYWQ7CiAgICAgICAgd2hpbGUodGVtcC0+bmV4dCE9bnVsbCkKICAgICAgICB7CiAgICAgICAgICAgIHRlbXA9dGVtcC0+bmV4dDsKICAgICAgICB9CiAgICAgICAgaWYodGVtcC0+cHJldj09bnVsbCkKICAgICAgICB7CiAgICAgICAgICAgIGNvdXQ8PHRlbXAtPmRhdGE8PCJcbiI7CiAgICAgICAgICAgIHJldHVybiA7CiAgICAgICAgfQogICAgICAgIHdoaWxlKHRlbXAhPW51bGwpCiAgICAgICAgewogICAgICAgICAgICBjb3V0PDx0ZW1wLT5kYXRhPDwiICI7CiAgICAgICAgICAgIHRlbXA9dGVtcC0+cHJldjsKICAgICAgICB9CgogICAgfQp9OwppbnQgbWFpbigpCnsKICAgIGRvdWJsZWxpbmtlZGxpc3QgdGVzdDsKICAgIHRlc3QuaW5zZXJ0X2xhc3QoMTApOwogICAgdGVzdC5pbnNlcnRfbGFzdCgyMCk7CiAgICB0ZXN0Lmluc2VydF9sYXN0KDMwKTsKCiAgICBjb3V0PDwiT3JpZ2luYWwgTGlzdDogIjsKICAgIHRlc3QucHJpbnRmcm9tYmVnZ2luZygpOwoKICAgIHRlc3QuaW5zZXJ0X2ZpcnN0KDUpOwoKICAgIGNvdXQ8PCJBZnRlciBJbnNlcnQgRmlyc3Q6ICI7CiAgICB0ZXN0LnByaW50ZnJvbWJlZ2dpbmcoKTsKCiAgICBjb3V0PDwiQmFja3dhcmQ6ICI7CiAgICB0ZXN0LnByaW50ZnJvbWVuZCgpOwoKICAgIHRlc3QuZGVsZXRlX2ZpcnN0KCk7CgogICAgY291dDw8IlxuQWZ0ZXIgRGVsZXRlIEZpcnN0OiAiOwogICAgdGVzdC5wcmludGZyb21iZWdnaW5nKCk7CgogICAgdGVzdC5kZWxldGVfbGFzdCgpOwoKICAgIGNvdXQ8PCJBZnRlciBEZWxldGUgTGFzdDogIjsKICAgIHRlc3QucHJpbnRmcm9tYmVnZ2luZygpOwoKICAgIHRlc3QuZGVsZXRlX2J5dmFsdWUoMjApOwoKICAgIGNvdXQ8PCJBZnRlciBEZWxldGUgVmFsdWUgMjA6ICI7CiAgICB0ZXN0LnByaW50ZnJvbWJlZ2dpbmcoKTsKCiAgICB0ZXN0LmRlbGV0ZV9ieXZhbHVlKDEwMCk7CgogICAgY291dDw8IkZpbmFsIExpc3Q6ICI7CiAgICB0ZXN0LnByaW50ZnJvbWJlZ2dpbmcoKTsKCiAgICByZXR1cm4gMDsKfQ==