数据结构-双向循环链表-题解（C++代码）

解题思路:

注意事项:
        见注释。欢迎讨论~
参考代码:

#include<bits/stdc++.h>
#define DefaultListSize 0
using namespace std;

template <typename Elem>
class Node
{
public:
    Elem element; 
    Node *prev;
    Node *next;   

    Node() {    }
    Node(const Elem& elemval, Node* prevval = NULL, Node* nextval = NULL)
    {
        element = elemval;
        prev = prevval;
        next = nextval;
    }
};

template <typename Elem>
class DList : public Node<Elem>
{
protected:
    Node<Elem>* head; //Point to list header
    Node<Elem>* tail; //Pointer to last Elem
    Node<Elem>* fence;//Last element on left
    int leftcnt;      //Count of nodes at left
    int rightcnt;     //Count of nodes at right

public:
    DList() { init(); }

    void init()
    {
        fence = head = new Node<Elem>('\0', NULL, tail);
        tail  = new Node<Elem>('\0', head, NULL);
        leftcnt = rightcnt = 0;
    }
    ~DList() { removeAll(); }  // Destructor
    void clear() { removeAll(); init(); }
    void removeAll()
    {
        while (head != NULL)
        {
            fence = head;
            head = head->next;
            delete fence;
        }
    }
    int leftLength() const { return leftcnt; }
    int rightLength() const { return rightcnt; }
    int getCount() { return leftcnt + rightcnt; }
    void setStart()
    {
        fence = head;
        rightcnt += leftcnt;
        leftcnt = 0;
    }
    void setEnd()
    {
        fence = tail;
        leftcnt += rightcnt;
        rightcnt = 0;
    }
    void prev()
    {
        if (fence != head)
        {
            fence = fence->prev;
            rightcnt--;
            leftcnt++;
        }
    }
    void next()
    {
        // Don't move fence if right empty
        if (fence != tail)
        {
            fence = fence->next;
            rightcnt--;
            leftcnt++;
        }
    }
    // Get the value of fence
    bool getValue(Elem& it) const
    {
        if (rightLength() == 0) return false;
        it = fence->element;
        return true;
    }
    bool insert(const int pos, const Elem& item)
    {
        if (getCount() == 0) {
            Node<Elem>* tmp = new Node<Elem>(item, head, tail);
            head->next = tmp;
            tail->prev = tmp;
            setStart();
            rightcnt++;
            return true;
        }

        setPos(pos - 1);
        Node<Elem>* tmp = new Node<Elem>(item, fence, fence->next);
        fence->next->prev = tmp;
        fence->next = tmp;
        rightcnt++;

        return true;
    }
    // Remove and return first Elem in right partition
    bool remove(const int pos, Elem& it)
    {
        if (getCount() == 0) return false;

        setPos(pos - 1);
        Node<Elem>* tmp = fence->next;
        it = tmp->element;
        tmp->next->prev = fence;
        fence->next = tmp->next;
        delete tmp;
        rightcnt--;

        return true;
    }
    // Set the size of left partition to pos
    bool setPos(int pos)
    {
        if ((pos < 0) || (pos > getCount())) return false;
        fence = head;
        for (int i = 0; i < pos; i++) {
            fence = fence->next;
        }
        rightcnt = rightcnt + leftcnt - pos;
        leftcnt = pos;
        return true;
    }
    // show
    void show()
    {
        setStart();
        next();
        while (fence) {
            if (fence->next == tail) {
                cout << fence->element << endl;
                return;
            }
            cout << fence->element << " ";
            next();
        }
    }
};

int main()
{
    DList<int> list;
    int cmd, tmp;
    int i, e;
    while (cin >> cmd) {
        if (cmd == 0) {
            list.show();
        }
        else if (cmd == 1) {
            cin >> i >> e;
            list.insert(i, e);
        }
        else {
            cin >> i;
            list.remove(i, tmp);
        }
    }
    return 0;
}