From 957053e7bf25ae9cfda0243d3cbcad1e9abac60a Mon Sep 17 00:00:00 2001
From: Loek Le Blansch <loek@pipeframe.xyz>
Date: Sat, 12 Oct 2024 16:26:26 +0200
Subject: implement linked list

---
 backend/List.hpp | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 67 insertions(+)
 create mode 100644 backend/List.hpp

(limited to 'backend/List.hpp')

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;
+};
+
-- 
cgit v1.2.3