#pragma once

#include <stdlib.h>

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;
};