// Will Sherwood C++ intro LinkedList implementation?

#include <iostream>
#include <string>
#include <math.h>

class Element {
public:
    virtual ~Element() { }

    virtual void print() = 0;
};

class LinkedList : public Element {
private:
    class Node : public Element {
    private:
        Element *element = 0;
    public:
        Node *next = 0;

        Node(Node *next, Element *element) : next(next), element(element) { }

        virtual ~Node() { delete element; }

        virtual void print() { element->print(); }

        void add(Node *node) { next = node; }
    };

    Node *head;
    Node *tail;
    int size;
public:
    LinkedList(Element *root) : head(new Node(0, root)), size(1), tail(head) { }

    void addLast(Element *add) {
        Node *next = new Node(0, add);
        tail->add(next);
        tail = next;
        size++;
    }

    void addFirst(Element *add) {
        Node *next = new Node(head, add);
        head = next;
        size++;
    }

    void add(int position, Element *add) {
        if (position == 0) return addFirst(add);
        Node *find = head;
        while (--position) find = find->next;
        Node *next = find->next;
        find->add(new Node(next, add));
    }

    int length() { return size; }

    void remove(int position) {
        Node *find;
        if (!position) {
            find = head;
            head = find->next;
            delete find;
            return;
        }
        find = head;
        while (--position) find = find->next;
        Node *to_delete = find->next;
        find->add(to_delete->next);
        delete to_delete;
        size--;
    }

    virtual void print() {
        Node *k = head;
        while (k) {
            k->print();
            k = k->next;
        }
    }

    virtual ~LinkedList() {
        while (head) {
            Node *old = head;
            head = head->next;
            delete old;
        }
    }
};


class Int_Ele : public Element {
private:
    int x;
public:
    Int_Ele(int x) : x(x) { }

    virtual void print() { std::cout << x << std::endl; }
};

int main() {
    LinkedList list(new Int_Ele(15));
    list.addLast(new Int_Ele(30));
    list.addLast(new Int_Ele(45));
    list.addLast(new Int_Ele(60));

    list.remove(3);
    list.addFirst(new Int_Ele(0));
    list.addFirst(new Int_Ele(-15));

    list.remove(2);

    list.add(4, new Int_Ele(101));
    list.print();

    list.~LinkedList();
}