#cat list.cc
#include <cstdlib>
#include <iostream>
#include <stdio.h>
using namespace std;

#include "osstat.h"

class Node {
public:
    int data;
    Node *pPre, *pNext;
};

class DoubleLinkList {
public:
    DoubleLinkList() {
        head = new Node;
        head->data = 0;
        head->pNext = NULL;
        head->pPre = NULL;
    }
    ~DoubleLinkList() {delete head;}
    void CreateLinkList(int n);             //Create linklist
    void InsertNode(int position, int d);   //Insert into linklist
    void TraverseLinkList();                //Traversal linklist
    bool IsEmpty();                         //If linklist is empty
    int GetLength();                        //Get linklist's length
    void DeleteNode(int position);          //Delete linklist's element
    void DeleteLinkList();                  //Delete linklist
private:
    Node *head;
};

void DoubleLinkList::CreateLinkList(int n) {
    if (n < 0) {
        cout << "Your intput of this linklist's node count not correct!" << endl;
        exit(EXIT_FAILURE);
    }
    else {
        int i = 0;
        Node *pnew, *ptemp;
        ptemp = head;
        i = n;
        while (n-- > 0) {
            cout << "Please input the number" << i - n << "node value:";
            pnew = new Node;
            cin >> pnew->data;
            pnew->pNext = NULL;
            pnew->pPre = ptemp;
            ptemp->pNext = pnew;
            ptemp = pnew;
        }
    }
}

void DoubleLinkList::InsertNode(int position, int d) {
    if (position < 0 || position > GetLength() + 1){
        cout << "输入位置错误！" << endl;
        exit(EXIT_FAILURE);
    }
    else {
        Node *pnew, *ptemp;
        pnew = new Node;
        pnew->data = d;
        ptemp = head;

        while (position-- > 1)
            ptemp = ptemp->pNext;

        if (ptemp->pNext != NULL)
            ptemp->pNext->pPre = pnew;
        pnew->pNext = ptemp->pNext;
        pnew->pPre = ptemp;
        ptemp->pNext = pnew;
        ptemp = pnew;
    }
}

void DoubleLinkList::TraverseLinkList() {
    Node *ptemp = head->pNext;
    while (ptemp != NULL) {
        cout << ptemp->data << " ";
        ptemp = ptemp->pNext;
    }
    cout << endl;
}

bool DoubleLinkList::IsEmpty() {
    if (head->pNext == NULL)
        return true;
    else
        return false;
}

int DoubleLinkList::GetLength() {
    int n = 0;
    Node *ptemp = head->pNext;
    while (ptemp != NULL) {
        n++;
        ptemp = ptemp->pNext;
    }
    return n;
}

void DoubleLinkList::DeleteNode(int position) {
    if (position < 0 || position > GetLength()) {
        cout << "输入数据错误!" << endl;
        exit(EXIT_FAILURE);
    }
    else {
        Node *pdelete, *ptemp;
        ptemp = head;

        while (position-- > 1)
            ptemp = ptemp->pNext;
        pdelete = ptemp->pNext;
        if (pdelete->pNext != NULL)
            pdelete->pNext->pPre = ptemp;
        ptemp->pNext = pdelete->pNext;
        delete pdelete;
        pdelete = NULL;
    }
}

void DoubleLinkList::DeleteLinkList() {
    Node *pdelete, *ptemp;
    pdelete = head->pNext;
    while (pdelete != NULL) {
        ptemp = pdelete->pNext;
        head->pNext = ptemp;
        if (ptemp != NULL)
            ptemp->pPre = head;
        delete pdelete;
        pdelete = ptemp;
    }
}

int main() {
    DoubleLinkList dl;
    int position = 0, value = 0, n = 0;
    bool flag = false;

    cout << "请输入需要创建双向链表的结点个数：";
    cin >> n;
    dl.CreateLinkList(n);

    cout << "打印链表值如下：";
    dl.TraverseLinkList();

    cout << "请输入插入结点的位置和值：";
    cin >> position >> value;
    dl.InsertNode(position, value);

    cout << "打印链表值如下：";
    dl.TraverseLinkList();

    cout << "请输入要删除结点的位置：";
    cin >> position;
    dl.DeleteNode(position);

    cout << "打印链表值如下：";
    dl.TraverseLinkList();

    dl.DeleteLinkList();
    flag = dl.IsEmpty();
    if (flag)
        cout << "删除链表成功！" << endl;
    else
        cout << "删除链表失败！" << endl;

    return 0;
}