diff options
Diffstat (limited to 'Year_1/Programming_2/data_structures/circle_double_list.cc')
-rw-r--r-- | Year_1/Programming_2/data_structures/circle_double_list.cc | 185 |
1 files changed, 185 insertions, 0 deletions
diff --git a/Year_1/Programming_2/data_structures/circle_double_list.cc b/Year_1/Programming_2/data_structures/circle_double_list.cc new file mode 100644 index 0000000..f162e57 --- /dev/null +++ b/Year_1/Programming_2/data_structures/circle_double_list.cc @@ -0,0 +1,185 @@ +#include<iostream> + +using namespace std; + +template<typename T> +struct node { + T value; + node* prev; + node* next; +}; + + +template<typename T> +class list { +public: + list() : _head{nullptr} {} + + ~list() { + node<T>* iter = _head; + while(iter->next != _head) { + node<T>* tmp = iter; + delete tmp; + iter = iter->next; + } + node<T>* tmp = iter; + delete tmp; + } + + list* push_front(T val) { + auto elem = _last(); + if(!_head) { + _head = new node<T>{val, nullptr, nullptr}; + _head->prev = _head->next = _head; + } else { + _head = new node<T>{val, elem, _head}; + elem->next = _head->next->prev = _head; + } + + return this; + } + + list* push_back(T val) { + if(!_head) return this->push_front(val); + + auto last_e = _last(); + last_e->next = new node<T>{val, last_e, _head}; + _head->prev = last_e->next; + + return this; + } + + list* push_after_value(T val, T newval) { + node<T>* iter = _search(val); + if(iter) { + node<T>* nod = new node<T>{newval, iter, iter->next}; + iter->next = nod; + nod->next->prev = nod; + } + + return this; + } + + list* push_before_value(T val, T newval) { + node<T>* elem = _search(val); + if(!elem) return this; + + node<T>* iter = _head; + + if(iter->value == val) + return this->push_front(newval); + + while(iter->next != elem) + iter = iter->next; + + node<T>* nod = new node<T>{newval, iter, iter->next}; + iter->next = nod; + nod->next->prev = nod; + + return this; + } + + list* pop(int val) { + node<T>* elem = _search(val); + if(!elem) return this; + + if(elem == _head) return this->pop_front(); + + node<T>* iter = elem->prev; + node<T>* temp = iter->next; + iter->next = iter->next->next; + iter->next->prev = iter; + delete temp; + + return this; + } + + list* pop_front() { + if(!_head) + return this; + + auto last_e = _last(); + node<T>* elem = _head; + _head = _head->next; + _head->prev = last_e; + last_e->next = _head; + delete elem; + + return this; + } + + list* pop_back() { + if(!_head) + return this; + + auto last_e = _last(); + + if(last_e == _head) { + delete _head; + _head = nullptr; + } else { + auto iter = last_e->prev; + delete iter->next; + iter->next = _head; + _head->prev = iter; + } + + return this; + } + + void print() { + node<T>* iter = _head; + while(iter != nullptr) { + cout << iter->value << ' '; + cout << "[[ " << iter->prev->value << ", "; + cout << iter->next->value << " ]], "; + iter = iter->next; + if(iter == _head) break; + } + } +private: + node<T>* _last() { + node<T>* iter = _head; + while(iter && iter->next != _head) { + iter = iter->next; + } + + return iter; + } + + node<T>* _search(T val) { + node<T>* iter = _head; + if(iter->value == val) return iter; + + while(iter && iter->value != val) { + iter = iter->next; + if(iter == _head) return nullptr; + } + + return iter; + } + + node<T>* _head; +}; + +int main() { + list<int>* l = new list<int>{}; + l->push_front(2); + l->push_back(1)->push_back(3); + l->push_front(5)->push_front(9); + l->push_back(0)->push_back(6); + l->print(); cout << '\n'; + l->push_after_value(7, -2); + l->push_before_value(9, 10); + l->print(); cout << '\n'; + l->pop_front(); + l->pop_front(); + l->pop_back(); + l->pop_front(); + l->print(); cout << '\n'; + l->pop(2); + l->print(); cout << '\n'; + + delete l; + return 0; +} |