From fa670eac6d73cbc9196603dd285d2240ef89f735 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Fri, 8 May 2020 19:58:21 +0200 Subject: feat: circulat list --- .../data_structures/circle_list.cc | 162 +++++++++++++++++++++ 1 file changed, 162 insertions(+) create mode 100644 I_anno/Programmazione_2/data_structures/circle_list.cc (limited to 'I_anno/Programmazione_2/data_structures') diff --git a/I_anno/Programmazione_2/data_structures/circle_list.cc b/I_anno/Programmazione_2/data_structures/circle_list.cc new file mode 100644 index 0000000..ee32a8c --- /dev/null +++ b/I_anno/Programmazione_2/data_structures/circle_list.cc @@ -0,0 +1,162 @@ +#include + +using namespace std; + +template +struct node { + T value; + node* next; +}; + + +template +class list { +public: + list() : _head{nullptr} {} + + ~list() { + while(_head != nullptr) { + node* tmp = _head->next; + delete tmp; + _head = tmp; + } + } + + node* last_element() { + node* iter = _head; + while(iter && iter->next != _head) { + iter = iter->next; + } + + return iter; + } + + list* push_front(T val) { + auto elem = last_element(); + _head = new node{val, _head}; + if(elem == nullptr) + elem = _head; + + elem->next = _head; + + return this; + } + + list* push_back(T val) { + node* iter = _head; + if(_head == nullptr) { + _head = new node{val, _head}; + } else { + while(iter->next != nullptr && iter->next != _head) { + iter = iter->next; + } + iter->next = new node{val, _head}; + } + return this; + } + + list* push_after_value(T val, T newval) { + node* iter = _head; + while(iter && iter->value != val) + iter = iter->next; + + if(iter == nullptr) + return this->push_front(newval); + + iter->next = new node{newval, iter->next}; + + return this; + } + + list* push_before_value(T val, T newval) { + node* iter = _head; + + if(iter->value == val) + return this->push_front(newval); + + while(iter && iter->next && iter->next->value != val) + iter = iter->next; + + if(iter == nullptr) + return this->push_front(newval); + + iter->next = new node{newval, iter->next}; + + return this; + } + + list* pop_front() { + if(_head == nullptr) + return this; + + auto last_e = last_element(); + + if(last_e == _head) { + delete _head; + _head = nullptr; + } else { + node* elem = _head; + _head = _head->next; + last_e->next = _head; + delete elem; + } + + return this; + } + + list* pop_back() { + if(_head == nullptr) + return this; + + node* iter = _head; + auto last_e = last_element(); + + if(last_e == _head) { + delete iter; + _head = nullptr; + } else { + while(iter->next != last_e) { + iter = iter->next; + } + + delete iter->next; + iter->next = _head; + } + + return this; + } + + void print() { + node* iter = _head; + while(iter) { + cout << iter->value << ' '; + iter = iter->next; + if(iter == _head) break; + } + } +private: + node* _head; +}; + +int main() { + list* l = new list{}; + l->push_back(4); + l->push_back(1); + l->push_back(0); + l->push_front(2); + l->print(); cout << endl; + l->pop_back(); + l->print(); cout << endl; + l->pop_front(); + l->print(); cout << endl; + l->pop_back(); + l->print(); cout << endl; + l->push_front(3); + l->print(); cout << endl; + l->push_after_value(4, 7); + l->print(); cout << endl; + l->push_before_value(3, 5); + l->print(); cout << endl; + + return 0; +} -- cgit v1.2.3-18-g5258