双向链表，c++描述

双向链表比单向链表复杂了不止一倍，主要是有两个头尾，每个节点也是两个朝向，这就让变化复杂度大大提高，一不小心就泄露。

算法4：1.3.31

实现一个嵌套类DoubleNode用来构造双向链表，其中每个结点都含有一个指向前驱元素的引用和一项指向后续元素的引用（如果不存在则为null）。

为以下任务实现若干静态方法：

在表头插入结点、

在表尾插入结点、

从表头删除结点、

从表尾删除结点、

在指定结点之前插入新结点、

在指定结点之后插入新结点、

删除指定结点。

#include 

template 
struct DoubleList;

template 
struct DoubleListIterator;

template 
struct DoubleNode
{
private:
    T item;
    DoubleNode *front = nullptr;
    DoubleNode *back = nullptr;
    friend class DoubleList;
    friend class DoubleListIterator;
};

template 
struct DoubleListIterator
{
    DoubleListIterator(DoubleNode *it) : iter(it) {}
    DoubleListIterator operator++()
    {
        if (iter)
        {
            iter = iter->back;
        }
        return *this;
    }
    DoubleListIterator operator--()
    {
        if (iter)
        {
            iter = iter->front;
        }
        return *this;
    }
    T operator*()
    {
        return iter->item;
    }
    bool operator!=(const DoubleListIterator &rhs)
    {
        return iter != rhs.iter;
    }

private:
    DoubleNode *iter;
};

template 
struct DoubleList
{
    void insfront(const T &rhs)
    {
        DoubleNode *oldfirst = first;
        first = new DoubleNode();
        first->item = rhs;
        first->back = oldfirst;
        if (oldfirst)
        {
            oldfirst->front = first;
        }
        else
        {
            last = first;
        }
        ++N;
    }

    void insback(const T &rhs)
    {
        DoubleNode *oldlast = last;
        last = new DoubleNode();
        last->item = rhs;
        last->front = oldlast;
        if (oldlast)
        {
            oldlast->back = last;
        }
        else
        {
            first = last;
        }
        ++N;
    }

    T outfront()
    {
        assert(first);
        DoubleNode *oldfirst = first;
        first = first->back;
        if (first)
        {
            first->front = nullptr;
        }

        T item = oldfirst->item;
        delete oldfirst;
        if (first == nullptr)
        {
            last = nullptr;
        }
        --N;

        return item;
    }

    T outback()
    {
        assert(last);
        DoubleNode *oldlast = last;
        last = last->front;
        if (last)
        {
            last->back = nullptr;
        }

        T item = oldlast->item;
        delete oldlast;
        if (last == nullptr)
        {
            first = nullptr;
        }
        --N;

        return item;
    }

    void insfront(const T &rhs, unsigned Num)
    {
        if (Num == 0)
        {
            insfront(rhs);
            return;
        }

        assert(Num < N);
        DoubleNode *tempA = first;
        for (size_t i = 0; i != Num - 1; ++i)
        {
            tempA = tempA->back;
        }
        DoubleNode *tempins = new DoubleNode();
        DoubleNode *tempB = tempA->back;
        tempins->item = rhs;
        tempA->back = tempins;
        tempins->front = tempA;
        tempins->back = tempB;
        tempB->front = tempins;
        ++N;
    }

    void insback(const T &rhs, unsigned Num)
    {
        if (Num == N - 1)
        {
            insback(rhs);
            return;
        }

        assert(Num < N - 1);
        DoubleNode *tempA = last;
        for (size_t i = 0; i != N - Num - 2; ++i)
        {
            tempA = tempA->front;
        }
        DoubleNode *tempins = new DoubleNode();
        DoubleNode *tempB = tempA->front;
        tempins->item = rhs;
        tempA->front = tempins;
        tempins->back = tempA;
        tempins->front = tempB;
        tempB->back = tempins;
        ++N;
    }

    void del(unsigned Num)
    {
        if (N == 0 && Num == 0)
        {
            return;
        }
        assert(Num < N);
        DoubleNode *temp = first;
        for (size_t i = 0; i != Num; ++i)
        {
            temp = temp->back;
        }
        DoubleNode *tempA = temp->front;
        DoubleNode *tempB = temp->back;
        if (tempA)
        {
            tempA->back = tempB;
        }
        else
        {
            first = tempB;
        }
        if (tempB)
        {
            tempB->front = tempA;
        }
        else
        {
            last = tempA;
        }

        delete temp;
        --N;
    }

    DoubleListIterator begin() { return DoubleListIterator(first); }

    DoubleListIterator end() { return DoubleListIterator(nullptr); }

    ~DoubleList()
    {
        while (first)
        {
            DoubleNode *temp = first;
            first = first->back;
            delete temp;
        }
        last = nullptr;
    }

private:
    DoubleNode *first = nullptr;
    DoubleNode *last = nullptr;
    unsigned N = 0;
};