summaryrefslogtreecommitdiff
path: root/I_anno
diff options
context:
space:
mode:
authorSanto Cariotti <dcariotti24@gmail.com>2020-05-03 18:10:44 +0200
committerSanto Cariotti <dcariotti24@gmail.com>2020-05-03 18:10:44 +0200
commit24066d1e8fc7bb9b99b1aa84a8a78e0d516005ad (patch)
tree3468ae2c68ff938a1472c8f6b57fe7bff18aa36b /I_anno
parent337fa15b59b22bddaa39f95b2a53de41483dfd10 (diff)
feat: double linked list
Diffstat (limited to 'I_anno')
-rw-r--r--I_anno/Programmazione_2/data_structures/list_double.cc172
1 files changed, 172 insertions, 0 deletions
diff --git a/I_anno/Programmazione_2/data_structures/list_double.cc b/I_anno/Programmazione_2/data_structures/list_double.cc
new file mode 100644
index 0000000..b229237
--- /dev/null
+++ b/I_anno/Programmazione_2/data_structures/list_double.cc
@@ -0,0 +1,172 @@
+#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() {
+ while(_head != nullptr) {
+ node<T>* tmp = _head->next;
+ delete tmp;
+ _head = tmp;
+ }
+ }
+
+ list* push_front(T val) {
+ if(_head == nullptr) {
+ _head = new node<T>{val, nullptr, nullptr};
+ } else {
+ _head = new node<T>{val, nullptr, _head};
+ _head->next->prev = _head;
+ }
+
+ return this;
+ }
+
+ list* push_back(T val) {
+ node<T>* iter = _head;
+ if(_head == nullptr) {
+ _head = new node<T>{val, nullptr, nullptr};
+ } else {
+ while(iter->next != nullptr) {
+ iter = iter->next;
+ }
+ iter->next = new node<T>{val, iter, nullptr};
+ }
+
+ return this;
+ }
+
+ list* push_after_value(T val, T newval) {
+ node<T>* iter = _head;
+ while(iter && iter->value != val)
+ iter = iter->next;
+
+ if(iter == nullptr)
+ return this->push_front(newval);
+
+ 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>* 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);
+
+ node<T>* nod = new node<T>{newval, iter, iter->next};
+ iter->next = nod;
+ nod->next->prev = nod;
+
+ return this;
+ }
+
+ list* pop_front() {
+ if(_head == nullptr)
+ return this;
+
+ node<T>* elem = _head;
+ _head = _head->next;
+ _head->prev = nullptr;
+ delete elem;
+
+ return this;
+ }
+
+ list* pop_back() {
+ if(_head == nullptr)
+ return this;
+
+ node<T>* iter = _head;
+
+ while(iter->next && iter->next->next) {
+ iter = iter->next;
+ }
+
+ if(iter->next == nullptr) {
+ delete iter;
+ _head = nullptr;
+ } else if(iter->next->next) {
+ delete iter->next->next;
+ } else {
+ delete iter->next;
+ }
+
+ iter->next = nullptr;
+
+ return this;
+ }
+
+ void print() {
+ node<T>* iter = _head;
+ while(iter != nullptr) {
+ cout << iter->value << ' ';
+ cout << "[[ " << (iter->prev!=nullptr ? iter->prev->value : -1) << ", ";
+ cout << (iter->next!=nullptr ? iter->next->value : -1) << " ]], ";
+ iter = iter->next;
+ }
+ }
+private:
+ node<T>* _head;
+};
+
+int main() {
+ list<int>* l = new list<int>{};
+ l->push_front(2)->push_front(1);
+ l->print(); cout << endl;
+ l->push_back(5);
+ l->print(); cout << endl;
+ l->push_back(10)->push_back(15);
+ l->print(); cout << endl;
+ l->push_after_value(5, 6);
+ l->print(); cout << endl;
+ l->push_after_value(5, 7);
+ l->print(); cout << endl;
+ l->push_before_value(5, 4);
+ l->print(); cout << endl;
+ l->push_before_value(5, 3);
+ 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;
+
+ // output
+ /*
+ * 1 [[ -1, 2 ]], 2 [[ 1, -1 ]],
+ * 1 [[ -1, 2 ]], 2 [[ 1, 5 ]], 5 [[ 2, -1 ]],
+ * 1 [[ -1, 2 ]], 2 [[ 1, 5 ]], 5 [[ 2, 10 ]], 10 [[ 5, 15 ]], 15 [[ 10, -1 ]],
+ * 1 [[ -1, 2 ]], 2 [[ 1, 5 ]], 5 [[ 2, 6 ]], 6 [[ 5, 10 ]], 10 [[ 6, 15 ]], 15 [[ 10, -1 ]],
+ * 1 [[ -1, 2 ]], 2 [[ 1, 5 ]], 5 [[ 2, 7 ]], 7 [[ 5, 6 ]], 6 [[ 7, 10 ]], 10 [[ 6, 15 ]], 15 [[ 10, -1 ]],
+ * 1 [[ -1, 2 ]], 2 [[ 1, 4 ]], 4 [[ 2, 5 ]], 5 [[ 4, 7 ]], 7 [[ 5, 6 ]], 6 [[ 7, 10 ]], 10 [[ 6, 15 ]], 15 [[ 10, -1 ]],
+ * 1 [[ -1, 2 ]], 2 [[ 1, 4 ]], 4 [[ 2, 3 ]], 3 [[ 4, 5 ]], 5 [[ 3, 7 ]], 7 [[ 5, 6 ]], 6 [[ 7, 10 ]], 10 [[ 6, 15 ]], 15 [[ 10, -1 ]],
+ * 1 [[ -1, 2 ]], 2 [[ 1, 4 ]], 4 [[ 2, 3 ]], 3 [[ 4, 5 ]], 5 [[ 3, 7 ]], 7 [[ 5, 6 ]], 6 [[ 7, 10 ]], 10 [[ 6, -1 ]],
+ * 2 [[ -1, 4 ]], 4 [[ 2, 3 ]], 3 [[ 4, 5 ]], 5 [[ 3, 7 ]], 7 [[ 5, 6 ]], 6 [[ 7, 10 ]], 10 [[ 6, -1 ]],
+ * 2 [[ -1, 4 ]], 4 [[ 2, 3 ]], 3 [[ 4, 5 ]], 5 [[ 3, 7 ]], 7 [[ 5, 6 ]], 6 [[ 7, -1 ]],
+ */
+
+ return 0;
+}