Doubly Linked Lists.cc

#include <algorithm>
#include <iostream>
#include <type_traits>
#include <vector>

template <class T>
class LinkedList {
private:
	struct Node {
		Node(T v) : val(v) {
			next = nullptr;
			prev = nullptr;
		}
		T val;
		Node* next;
		Node* prev;
	};

	Node* head, * end, * mid;
	size_t len;

public:
	LinkedList() {
		head = nullptr;
		end = nullptr;
		mid = nullptr;
		len = 0;
	}

	void append(T val) {
		Node* newnode = new Node(val);
		if (end == nullptr) {
			end = newnode;
			head = newnode;
			mid = newnode;
		}
		else {
			end->next = newnode;
			newnode->prev = end;
			end = newnode;
			if (len % 2 == 0) mid = mid->next;
		}
		len++;
	}

	void prepend(T val) {
		Node* newnode = new Node(val);
		if (head == nullptr) {
			head = newnode;
			end = newnode;
			mid = newnode;
		}
		else {
			head->prev = newnode;
			newnode->next = head;
			head = newnode;
			if (len % 2 == 1) mid = mid->prev;
		}
		len++;
	}

	void insert_after(Node* pos, T value) {
		if (pos == nullptr) return;
		Node* newnode = new Node(value);
		newnode->prev = pos;
		newnode->next = pos->next;
		if (pos->next != nullptr) pos->next->prev = newnode;
		pos->next = newnode;
		len++;
	}

	void insert_before(Node* pos, T value) {
		if (pos == nullptr) return;
		Node* newnode = new Node(value);
		newnode->next = pos;
		newnode->prev = pos->prev;
		if (pos->prev != nullptr) pos->prev->next = newnode;
		pos->prev = newnode;
		len++;
	}

	void remove_last() {
		if (end == nullptr)
			return;
		else if (head == end) {
			delete head;
			head = nullptr;
			end = nullptr;
			mid = nullptr;
		}
		else {
			Node* todel = end;
			end = end->prev;
			end->next = nullptr;
			delete todel;
			if (len % 2 == 1) mid = mid->prev;
		}
		len--;
	}

	void remove_front() {
		if (head == nullptr)
			return;
		else if (head == end) {
			delete head;
			head = nullptr;
			end = nullptr;
			mid = nullptr;
		}
		else {
			Node* todel = head;
			head = head->next;
			head->prev = nullptr;
			delete todel;
			if (len % 2 == 0) mid = mid->next;
		}
		len--;
	}

	void remove(Node* pos) {
		if (pos == nullptr) return;
		if (pos == head)
			remove_front();
		else if (pos == end)
			remove_last();
		else {
			Node* prv = pos->prev;
			Node* nxt = pos->next;
			nxt->prev = prv;
			prv->next = nxt;
			delete pos;
		}
		len--;
	}

	void remove_all(T value) {
		Node* iter = head;
		while (iter != nullptr) {
			Node* old = iter;
			iter = iter->next;
			if (old->val == value) remove(old);
		}
	}

	size_t size() { return len; }
	bool empty() { return len == 0; }

	void reverse(Node* start_pos, Node* end_pos) {
		if (start_pos == nullptr || end_pos == nullptr || len == 1) return;
		bool xx, yy;
		xx = false;
		yy = false;
		if (start_pos == head) {
			xx = true;
			prepend(-1);
		}
		if (end_pos == end) {
			yy = true;
			append(-1);
		}
		Node* cur = end_pos->prev;
		Node* a = start_pos->prev, * b = end_pos->next;

		a->next = end_pos;
		end_pos->prev = a;

		b->prev = start_pos;
		start_pos->next = b;

		Node* last_okay = end_pos;

		while (last_okay != start_pos) {
			Node* tmp = cur->prev;
			last_okay->next = cur;
			cur->prev = last_okay;
			last_okay = cur;
			cur = tmp;
		}
		if (xx) remove_front();
		if (yy) remove_last();
	}

	Node* middle() { return mid; }

	Node* begin() { return head; }
	Node* last() { return end; }

	Node* find_first(T value) {
		Node* iter = head;
		while (iter != nullptr) {
			if (iter->val == value) return iter;
			iter = iter->next;
		}
		return iter;
	}

	Node* operator[](size_t index) {
		Node* retv = head;
		for (size_t t = 0; t < index && retv != nullptr; t++) {
			retv = retv->next;
		}
		return retv;
	}

	void print() {
		Node* iter = head;
		while (iter != nullptr) {
			std::cout << iter->val << " ";
			iter = iter->next;
		}
		std::cout << "\n";
	}

};

template<class T>
class Stack {
	LinkedList<T> list;

public:
	Stack() = default;
	T top() {
		return list.last()->val;
	}
	void pop() {
		list.remove_last();
	}
	void push(T val) {
		list.append(val);
	}
	bool empty() {
		return list.empty();
	}
	T middle() {
		return list.middle()->val;
	}
	void print() {
		list.print();
	}
};

template<class T>
class Queue {
	LinkedList<T> list;
public:
	Queue() = default;
	T front() {
		return list.begin()->val;
	}
	T back() {
		return list.last()->val;
	}
	bool empty() {
		return list.empty();
	}
	void pop() {
		list.remove_front();
	}
	void push(T val) {
		list.append(val);
	}
	void print() {
		list.print();
	}
	T middle() {
		return list.middle()->val;
	}
};

int main() {
	return 0;
}