// #include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
using namespace std;
//التيل باشر ع الهيد عشان تصير سيركيولار
class node {
public:
node* next, * prev;
int data;
node(int d, node* n = 0, node* p = 0) {
data = d;
next = n;
prev = p;
}
};
class list{
node *tail;//need only tail
public :
list();
bool is_empty();
void printf();
void printb();
int size();
void add_begin(int el);
void add_end(int el);
void add_pos( int el , int pos);
void delete_begin();
void delete_end();
void delete_pos(int pos);
void delete_el(int el);
void add_sorted(int el);
int search(int el);
~list();//destructer to delete the pointers from the dynamic memory to save it
void operator=(list &o);//when we let p1=p2 , we have 2 pointers point at the same place , when we delete the first
// //, the want to delete the second , there is no pointer to delete
list(list &o);//the same as operator
};
bool list::is_empty() {
return (tail == 0);
}
int list::size() {
if (is_empty())
return 0;
else {
node* t = tail->next;
int c = 1;
for (; t != tail; t = t->next, c++);
return c;
}
}
list::~list(){
while(!is_empty())
delete_end();
cout<<"list is deleted"<<endl;
}
void list::delete_end(){
if(tail==0){
cout<<"the list is empty"<<endl;
}
else if(tail->next == tail){//tail point to tail , delete only tail
delete tail;
tail =0;
}
else {
node *tmp = tail->next;//point to the first node
for( ;tmp->next!=tail;tmp=tmp->next);//loop until reach tail -1
tmp->next = tail->next;
delete tail;
tail = tmp;
}
}
void list::add_begin(int el){
if(tail==0){
tail= new node(el);
tail->next = tail->prev = tail;
}
else {
tail->next = tail->next->prev = new node(el , tail->next , tail);
}
}
list ::list(){
tail =0;
}
void list::printf(){
node *tmp = tail->next;//ref to first point
while(tmp!=tail){
cout<<tmp->data<<" ";
tmp = tmp->next;
}
cout<<tmp->data<<" ";//for the tail
cout<<endl;
}
void list::printb(){
node *tmp = tail;//ref to first point
while(tmp->prev!=tail){
cout<<tmp->data<<" ";
tmp = tmp->prev;
}
cout<<tmp->data<<" ";//for the tail
cout<<endl;
}
void list::add_end(int el){
if(tail==0){
tail->next = tail->prev = new node(el);
}
else {
tail = tail->next = new node(el ,tail->next ,tail);
tail->next->prev = tail;
}
}
void list::add_pos(int el , int pos){
if(pos<1 || pos>size()+1){
cout<<"invalid pos "<<endl;
}
else if (pos==1){
add_begin(el);
}
else if (pos==size()+1){
add_end(el);
}
else {
node *t = tail->next;
int i = 1;
for( ; i<pos-1;i++)t=t->next;
t->next = t->next->prev = new node(el , t->next , t);
}
}
int main() {
list l;
l.add_begin(1);
l.add_end(1);
l.add_pos(2 , 2);
l.add_pos(4 , 4);
l.printf();
l.printb();
}
Ly8gI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlPGlvc3RyZWFtPgojaW5jbHVkZTxhbGdvcml0aG0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Ci8v2KfZhNiq2YrZhCDYqNin2LTYsSDYuSDYp9mE2YfZitivINi52LTYp9mGINiq2LXZitixINiz2YrYsdmD2YrZiNmE2KfYsQoKY2xhc3Mgbm9kZSB7CiAgICBwdWJsaWM6CiAgICBub2RlKiBuZXh0LCAqIHByZXY7CiAgICBpbnQgZGF0YTsKICAgIG5vZGUoaW50IGQsIG5vZGUqIG4gPSAwLCBub2RlKiBwID0gMCkgewogICAgZGF0YSA9IGQ7CiAgICBuZXh0ID0gbjsKICAgIHByZXYgPSBwOwogICAgfQp9OwoKY2xhc3MgbGlzdHsKICAgIG5vZGUgKnRhaWw7Ly9uZWVkIG9ubHkgdGFpbCAKCiAgICBwdWJsaWMgOgogICAgbGlzdCgpOwogICAgYm9vbCBpc19lbXB0eSgpOwogICAgdm9pZCBwcmludGYoKTsKICAgIHZvaWQgcHJpbnRiKCk7CiAgICBpbnQgc2l6ZSgpOwogICAgdm9pZCBhZGRfYmVnaW4oaW50IGVsKTsKICAgIHZvaWQgYWRkX2VuZChpbnQgZWwpOwogICAgdm9pZCBhZGRfcG9zKCBpbnQgZWwgLCBpbnQgcG9zKTsKICAgIHZvaWQgZGVsZXRlX2JlZ2luKCk7CiAgICB2b2lkIGRlbGV0ZV9lbmQoKTsKICAgIHZvaWQgZGVsZXRlX3BvcyhpbnQgcG9zKTsKICAgIHZvaWQgZGVsZXRlX2VsKGludCBlbCk7CiAgICB2b2lkIGFkZF9zb3J0ZWQoaW50IGVsKTsKICAgIGludCBzZWFyY2goaW50IGVsKTsKICAgIH5saXN0KCk7Ly9kZXN0cnVjdGVyIHRvIGRlbGV0ZSB0aGUgcG9pbnRlcnMgZnJvbSB0aGUgZHluYW1pYyBtZW1vcnkgdG8gc2F2ZSBpdAogICAgdm9pZCBvcGVyYXRvcj0obGlzdCAmbyk7Ly93aGVuIHdlIGxldCBwMT1wMiAsIHdlIGhhdmUgMiBwb2ludGVycyBwb2ludCBhdCB0aGUgc2FtZSBwbGFjZSAsIHdoZW4gd2UgZGVsZXRlIHRoZSBmaXJzdCAKICAgIC8vIC8vLCB0aGUgd2FudCB0byBkZWxldGUgdGhlIHNlY29uZCAsIHRoZXJlIGlzIG5vIHBvaW50ZXIgdG8gZGVsZXRlCiAgICBsaXN0KGxpc3QgJm8pOy8vdGhlIHNhbWUgYXMgb3BlcmF0b3IKfTsKYm9vbCBsaXN0Ojppc19lbXB0eSgpIHsKICAgIHJldHVybiAodGFpbCA9PSAwKTsKfQppbnQgbGlzdDo6c2l6ZSgpIHsKICAgIGlmIChpc19lbXB0eSgpKQogICAgICAgIHJldHVybiAwOwogICAgZWxzZSB7CiAgICAgICAgbm9kZSogdCA9IHRhaWwtPm5leHQ7CiAgICAgICAgaW50IGMgPSAxOwogICAgICAgIGZvciAoOyB0ICE9IHRhaWw7IHQgPSB0LT5uZXh0LCBjKyspOwogICAgICAgIHJldHVybiBjOwogICAgfQp9Cmxpc3Q6On5saXN0KCl7CiAgICB3aGlsZSghaXNfZW1wdHkoKSkKICAgICAgICBkZWxldGVfZW5kKCk7CiAgICBjb3V0PDwibGlzdCBpcyBkZWxldGVkIjw8ZW5kbDsKfQp2b2lkIGxpc3Q6OmRlbGV0ZV9lbmQoKXsKICAgIGlmKHRhaWw9PTApewogICAgICAgIGNvdXQ8PCJ0aGUgbGlzdCBpcyBlbXB0eSI8PGVuZGw7CiAgICB9CiAgICBlbHNlIGlmKHRhaWwtPm5leHQgPT0gdGFpbCl7Ly90YWlsIHBvaW50IHRvIHRhaWwgLCBkZWxldGUgb25seSB0YWlsCiAgICAgICAgZGVsZXRlIHRhaWw7CiAgICAgICAgdGFpbCA9MDsKICAgIH0KICAgIGVsc2UgewogICAgICAgIG5vZGUgKnRtcCA9IHRhaWwtPm5leHQ7Ly9wb2ludCB0byB0aGUgZmlyc3Qgbm9kZQogICAgICAgIGZvciggO3RtcC0+bmV4dCE9dGFpbDt0bXA9dG1wLT5uZXh0KTsvL2xvb3AgdW50aWwgcmVhY2ggdGFpbCAtMSAgICAgCiAgICAgICAgdG1wLT5uZXh0ID0gdGFpbC0+bmV4dDsKICAgICAgICBkZWxldGUgdGFpbDsKICAgICAgICB0YWlsID0gdG1wOwogICAgfQp9CnZvaWQgbGlzdDo6YWRkX2JlZ2luKGludCBlbCl7CiAgICBpZih0YWlsPT0wKXsKICAgICAgICB0YWlsPSBuZXcgbm9kZShlbCk7CiAgICAgICAgdGFpbC0+bmV4dCA9IHRhaWwtPnByZXYgPSB0YWlsOwogICAgfQogICAgZWxzZSB7CiAgICAgICAgdGFpbC0+bmV4dCA9IHRhaWwtPm5leHQtPnByZXYgPSBuZXcgbm9kZShlbCAsIHRhaWwtPm5leHQgLCB0YWlsKTsgCiAgICB9Cn0KbGlzdCA6Omxpc3QoKXsKICAgIHRhaWwgPTA7Cn0KCnZvaWQgbGlzdDo6cHJpbnRmKCl7CiAgICBub2RlICp0bXAgPSB0YWlsLT5uZXh0Oy8vcmVmIHRvIGZpcnN0IHBvaW50CiAgICB3aGlsZSh0bXAhPXRhaWwpewogICAgICAgIGNvdXQ8PHRtcC0+ZGF0YTw8IiAiOwogICAgICAgIHRtcCA9IHRtcC0+bmV4dDsKICAgIH0KICAgIGNvdXQ8PHRtcC0+ZGF0YTw8IiAiOy8vZm9yIHRoZSB0YWlsCiAgICBjb3V0PDxlbmRsOwp9CnZvaWQgbGlzdDo6cHJpbnRiKCl7CiAgICBub2RlICp0bXAgPSB0YWlsOy8vcmVmIHRvIGZpcnN0IHBvaW50CiAgICB3aGlsZSh0bXAtPnByZXYhPXRhaWwpewogICAgICAgIGNvdXQ8PHRtcC0+ZGF0YTw8IiAiOwogICAgICAgIHRtcCA9IHRtcC0+cHJldjsKICAgIH0KICAgIGNvdXQ8PHRtcC0+ZGF0YTw8IiAiOy8vZm9yIHRoZSB0YWlsCiAgICBjb3V0PDxlbmRsOwp9CnZvaWQgbGlzdDo6YWRkX2VuZChpbnQgZWwpewogICAgaWYodGFpbD09MCl7CiAgICAgICAgdGFpbC0+bmV4dCA9IHRhaWwtPnByZXYgPSBuZXcgbm9kZShlbCk7CiAgICB9CiAgICBlbHNlIHsKICAgICAgICB0YWlsID0gdGFpbC0+bmV4dCA9IG5ldyBub2RlKGVsICx0YWlsLT5uZXh0ICx0YWlsKTsKICAgICAgICB0YWlsLT5uZXh0LT5wcmV2ID0gdGFpbDsKICAgIH0KfQp2b2lkIGxpc3Q6OmFkZF9wb3MoaW50IGVsICwgaW50IHBvcyl7CiAgICBpZihwb3M8MSB8fCBwb3M+c2l6ZSgpKzEpewogICAgICAgIGNvdXQ8PCJpbnZhbGlkIHBvcyAiPDxlbmRsOwogICAgfQogICAgZWxzZSBpZiAocG9zPT0xKXsKICAgICAgICBhZGRfYmVnaW4oZWwpOwogICAgfQogICAgZWxzZSBpZiAocG9zPT1zaXplKCkrMSl7CiAgICAgICAgYWRkX2VuZChlbCk7CiAgICB9CiAgICBlbHNlIHsgICAgICAgIAogICAgICAgIG5vZGUgKnQgPSB0YWlsLT5uZXh0OwogICAgICAgIGludCBpID0gMTsKICAgICAgICBmb3IoIDsgaTxwb3MtMTtpKyspdD10LT5uZXh0OwogICAgICAgIHQtPm5leHQgPSAgdC0+bmV4dC0+cHJldiA9ICBuZXcgbm9kZShlbCAsIHQtPm5leHQgLCB0KTsKICAgICAgICAKICAgIH0KCn0KCgoKaW50IG1haW4oKSB7CiAgICBsaXN0IGw7CiAgICBsLmFkZF9iZWdpbigxKTsKICAgIGwuYWRkX2VuZCgxKTsKICAgIGwuYWRkX3BvcygyICwgMik7CiAgICBsLmFkZF9wb3MoNCAsIDQpOwogICAgbC5wcmludGYoKTsKICAgIGwucHJpbnRiKCk7CiAgICAKICAgIAoKCgogICAgCn0=