[SDP/HEP] Added preparation for "homework" during class

1 files changed, 230 insertions, 0 deletions

diff --git a/Year 2/Structures and data algorithms/HomeworkExamPrep/LinkedList.hpp b/Year 2/Structures and data algorithms/HomeworkExamPrep/LinkedList.hpp
new file mode 100644
index 0000000..fbab914
--- /dev/null
+++ b/Year 2/Structures and data algorithms/HomeworkExamPrep/LinkedList.hpp
@@ -0,0 +1,230 @@
+#ifndef LINKEDLIST
+#define LINKEDLIST
+
+#include <stdexcept>
+
+template <class T>
+class LinkedList {
+	struct Node {
+		T data;
+		Node* next;
+		Node(const T& data, Node* next = nullptr) : data(data), next(next) {}
+	};
+
+	Node* head;
+	Node* tail;
+	unsigned listSize;
+
+	Node* nodeAt(unsigned index);
+
+public:
+	class Iterator {
+		Node* current;
+		Iterator(Node* current) : current(current) {}
+	public:
+		Iterator& operator++() {
+			if (current == nullptr) return *this;
+
+			current = current->next;
+			return *this;
+		}
+		Iterator operator++(int) {
+			Iterator old = *this;
+			++(*this);
+			return old;
+		}
+		bool operator==(Iterator& other) {
+			return this->current == other.current;
+		}
+		bool operator!=(Iterator& other) {
+			return !(*this == other);
+		}
+		T& operator*() {
+			return current->data;
+		}
+		friend class LinkedList;
+	};
+	Iterator begin();
+	Iterator end();
+
+	class ConstIterator {
+		const Node* current;
+		ConstIterator(Node* current) : current(current) {}
+	public:
+		ConstIterator& operator++() {
+			if (current == nullptr) return *this;
+
+			current = current->next;
+			return *this;
+		}
+		ConstIterator operator++(int) {
+			ConstIterator old = *this;
+			++(*this);
+			return old;
+		}
+		bool operator==(const ConstIterator* other) const {
+			return this->current == other->current;
+		}
+		bool operator!=(const ConstIterator* other) const {
+			return !(*this == *other);
+		}
+		const T& operator*() const {
+			return current->data;
+		}
+		friend class LinkedList;
+	};
+	ConstIterator cbegin() const;
+	ConstIterator cend() const;
+
+	void push_front(const T& elem);
+	void push_back(const T& elem);
+	void push_at(unsigned ind, const T& elem);
+	void pop_front();
+	void pop_back();
+	void pop_at(unsigned ind);
+	T& front();
+	unsigned size();
+	bool empty();
+	
+
+	LinkedList() : head(nullptr) {}
+	~LinkedList();
+	LinkedList(LinkedList& other) = delete;
+	LinkedList& operator=(LinkedList& other) = delete;
+};
+
+template <class T>
+typename LinkedList<T>::Iterator LinkedList<T>::begin() {
+	return Iterator(head);
+}
+
+template <class T>
+typename LinkedList<T>::Iterator LinkedList<T>::end() {
+	return Iterator(nullptr);
+}
+
+template <class T>
+typename LinkedList<T>::ConstIterator LinkedList<T>::cbegin() const {
+	return ConstIterator(head);
+}
+
+template <class T>
+typename LinkedList<T>::ConstIterator LinkedList<T>::cend() const {
+	return ConstIterator(nullptr);
+}
+
+template <class T>
+typename LinkedList<T>::Node* LinkedList<T>::nodeAt(unsigned index) {
+	if (index > listSize)
+		throw std::runtime_error("Index too large!");
+
+	Node* nat;
+	for (nat = head; index > 0; index--) {
+		nat = nat->next;
+	}
+	return nat;
+}
+
+template <class T>
+void LinkedList<T>::push_front(const T& elem) {
+	if (empty()) {
+		head = tail = new Node(elem);
+	}
+	else {
+		head = new Node(elem, head);
+	}
+	listSize++;
+}
+
+template <class T>
+void LinkedList<T>::push_back(const T& elem) {
+	if (empty()) {
+		head = tail = new Node(elem);
+	}
+	else {
+		tail = (tail->next = new Node(elem));
+	}
+	listSize++;
+}
+
+template <class T>
+void LinkedList<T>::push_at(unsigned ind, const T& elem) {
+	if (ind >= listSize) {
+		push_back(elem);
+	}
+	else if (ind == 0) {
+		push_front(elem);
+	}
+	else {
+		Node* prev = nodeAt(ind - 1);
+		prev->next = new Node(elem, prev->next);
+		listSize++;
+	}
+}
+
+template <class T>
+void LinkedList<T>::pop_front() {
+	if (empty())
+		throw std::runtime_error("Pop empty list!");
+
+	Node* old = head;
+	head = head->next;
+	delete old;
+	listSize--;
+
+	if (empty()) tail = nullptr;
+}
+
+template <class T>
+void LinkedList<T>::pop_back() {
+	if (empty())
+		throw std::runtime_error("Pop empty list!");
+
+	Node* old = tail;
+	tail = nodeAt(listSize - 2);
+	tail->next = nullptr;
+	delete old;
+	listSize--;
+
+	if (empty()) head = nullptr;
+}
+
+template <class T>
+void LinkedList<T>::pop_at(unsigned ind) {
+	if (ind >= listSize - 1) {
+		pop_back();
+	}
+	else if (ind == 0) {
+		pop_front();
+	}
+	else {
+		Node* prev = nodeAt(ind - 1);
+		Node* curr = prev->next;
+		prev->next = curr->next;
+		delete curr;
+		listSize--;
+	}
+}
+
+template <class T>
+T& LinkedList<T>::front() {
+	return head->data;
+}
+
+template <class T>
+unsigned LinkedList<T>::size() {
+	return listSize;
+}
+
+template <class T>
+bool LinkedList<T>::empty() {
+	return listSize == 0;
+}
+
+template <class T>
+LinkedList<T>::~LinkedList() {
+	while (!empty())
+		pop_front();
+}
+
+#endif