implement linked list

1 files changed, 67 insertions, 0 deletions

diff --git a/backend/List.hpp b/backend/List.hpp
new file mode 100644
index 0000000..df44f7a
--- /dev/null
+++ b/backend/List.hpp
@@ -0,0 +1,67 @@
+#pragma once
+
+#include <cstdlib>
+#include <cstdio>
+
+template <typename T>
+struct ListLink {
+	ListLink<T> * prev;
+	ListLink<T> * next;
+	T value;
+};
+
+template<typename T>
+class List {
+public:
+	size_t size() { return this->length; }
+
+	void push_back(T el) {
+		ListLink<T> * link = static_cast<ListLink<T> *>(malloc(sizeof(ListLink<T>)));
+		link->prev = this->head;
+		link->next = nullptr;
+		link->value = el;
+		if (this->head != nullptr) this->head->next = link;
+		if (this->head == nullptr) this->tail = link;
+		this->head = link;
+		this->length++;
+	}
+
+	void pop_back() {
+		if (this->head == nullptr) return; // empty list
+
+		ListLink<T> * secondlast = this->head->prev;
+		if (secondlast != nullptr)
+			secondlast->next = nullptr;
+		free(this->head);
+		if (this->tail == this->head)
+			this->tail = nullptr;
+		this->head = secondlast;
+
+		this->length--;
+	}
+
+	void clear() {
+		ListLink<T> * link = this->tail;
+		while (link != nullptr) {
+			ListLink<T> * next = link->next;
+			free(link);
+			link = next;
+		}
+		this->head = nullptr;
+		this->tail = nullptr;
+		this->length = 0;
+	}
+
+	T & operator [] (size_t index) {
+		ListLink<T> * link = this->tail;
+		for (size_t i = 0; i < index; i++)
+			link = link->next;
+		return link->value;
+	}
+
+private:
+	ListLink<T> * head = nullptr;
+	ListLink<T> * tail = nullptr;
+	size_t length = 0;
+};
+