Data Structures [WIP]

[Nineshadow]

Re-implemented the (doubly) linked list using templates. Don't know why I didn't do it in the first place.

template <class T>class List{    struct Node    {        T data;        Node *prev;        Node *next;    };    Node *head;    Node *tail;public:    struct Iterator    {    private:        Node *node;    public:        friend class List;        Iterator()        {            node = NULL;        }        Iterator(Node *n)        {            node = n;        }        T& operator*() const        {            if(node!=NULL) return node->data;            else throw "Null operator";        }        Iterator& operator++()        {            if(node->next==NULL)node=NULL; //throw "Iterator out of bounds";            else {            node=node->next;            return *this;            }        }         Iterator operator++(int)        {            if(node->next==NULL)node=NULL ;//throw "Iterator out of bounds";            else {            Iterator temp = *this;            ++(*this);            return temp;            }        }        Iterator& operator--()        {            if(node->prev==NULL)node=NULL ;//throw "Iterator out of bounds";            else {            node = node->prev;            return *this;            }        }        Iterator operator--(int)        {            if(node->prev==NULL)node=NULL ;//throw "Iterator out of bounds";            else {            Iterator temp = *this;            --(*this);            return temp;            }        }        bool operator==(const Iterator& it) const        {            if(it.node == this->node)return true;            else return false;            }        bool operator!=(const Iterator& it) const        {            if(!(it==*this)) return true;            else return false;            }    };    bool isEmpty()    {        return head ==NULL;    }    List()    {        head=tail=NULL;    }    ~List()    {        if(!isEmpty()) clear();        }    void clear()    {        Node *i = head, *temp;        while(i!=NULL)        {            temp = i;            i=i->next;            delete temp;        }        head=tail=NULL;    }    Iterator end() const    {        return Iterator(tail);    }    Iterator front() const    {        return Iterator(head);    }    void pop_back()    {        if(isEmpty()) throw "Empty List";        else if(head==tail) delete head;        else        {            Node *temp = tail->prev;            delete tail;            temp->next = NULL;            tail=temp;        }    }    void pop_front()    {        if(isEmpty()) throw "Empty List";        else if(head==tail) delete head;        else        {            Node *temp = head->next;            delete head;            temp->prev = NULL;            head=temp;        }    }    void remove(Iterator it)    {        if(isEmpty()) throw "Empty List";        else if(head==tail)        {            delete head;            head = tail = NULL;            return;        }        else if(it==this->end())            pop_back();        else if(it==this->front())            pop_front();        else        {            it.node->prev->next = it.node->next;            it.node->next->prev = it.node->prev;            delete it.node;        }    }    void push_back(T value)    {        if(isEmpty())        {            head = new Node;            head->data = value;            head->next=NULL;            head->prev=NULL;            tail=head;        }        else        {            Node *newNode = new Node;            newNode->data = value;            newNode->next=NULL;            newNode->prev=tail;            tail->next=newNode;            tail=newNode;        }    }    void push_front(T value)    {        if(isEmpty())        {            head = new Node;            head->data = value;            head->next=NULL;            head->prev=NULL;            tail=head;        }        else        {            Node *newNode = new Node;            newNode->data = value;            newNode->prev=NULL;            newNode->next=head;            head->prev=newNode;            head=newNode;        }    }    void swap(Iterator node1, Iterator node2)    {        T temp = node1.node->data;        node1.node->data = node2.node->data;        node2.node->data=temp;    }    void insert_before(T value, Iterator it)    {        Node *newNode = new Node;        newNode->data = value;        it.node->prev->next = newNode;        newNode->prev=it.node->prev;        it.node->prev=newNode;        newNode->next=it.node;    }    void insert_after(T value, Iterator it)    {        Node *newNode = new Node;        newNode->Data = value;        newNode->prev=it.node;        newNode->next=it.node->next;        it.node->next->prev=newNode;        it.node->next=newNode;    }};