struct DoubleList {
    int data;
    struct DoubleList *prior;
    struct DoubleList *next;
};

void insert(DoubleList **pHead, int data) {
    if (*pHead == nil) { //空链表，需要创建
        *pHead = (DoubleList *)malloc(sizeof(DoubleList));
        (*pHead)->data = data;
        (*pHead)->next = nil;
        (*pHead)->prior = nil;
        return;
    }
    DoubleList *head = *pHead;

    DoubleList *insertList = (DoubleList *)malloc(sizeof(DoubleList));
    insertList->data = data;

    while ((head)) {
        if (head->data > data) { //如果当前的位置比插入的数字大，插入即可
            if (head->prior == nil) { //插入的位置是首部
                insertList->prior = nil;
                insertList->next = head;
                head->prior = insertList;
                head = insertList;
                *pHead = head;
                break;
            } else {
                insertList->prior = (head)->prior;
                (head)->prior->next = insertList;
                insertList->next = (head);
                (head)->prior = insertList;
                break;
            }
        }
        if (head->next == nil) { //遍历到尾部，则直接插入
            insertList->next = nil;
            head->next = insertList;
            insertList->prior = head;
            break;
        }
        (head) = (head)->next;
    }
}

int deleteNode(DoubleList **pHead, int data) {
    if (pHead == nil) { return -1; }
    int ret = -1;
    DoubleList *head = *pHead;
    while (head) {
        if (head->data == data) {
            if (head->prior == nil && head->next == nil) { ////只有一个元素的删除
                head = nil;
                return data;
            } else if(head->next == nil){ //删除尾部
                head->prior->next = nil;
                return data;
            } else if(head->prior == nil) { //删除头部
                head = head->next;
                head->prior = nil;
                *pHead = head;
            } else {
                head->prior->next = head->next;
                head->next->prior = head->prior;
            }
            ret = data;
        }
        head = head->next;
    }
    return ret;
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        DoubleList *pHead;
        insert(&pHead, 2); //空元素创建
        insert(&pHead, 3); //插入尾部
        insert(&pHead, 3);
        insert(&pHead, 4);//插入尾部
         insert(&pHead, 1);//插入首部
        insert(&pHead, 6); //插入尾部
        insert(&pHead, 5);//插入中间
        insert(&pHead, 6); //插入尾部
        DoubleList *test = pHead;
        while (test != NULL) {
            NSLog(@"%d", test->data);
            test = test->next;
        }
        NSLog(@"--------");
        deleteNode(&pHead, 3); //删除中间重复
        deleteNode(&pHead, 1); //删除首部
        deleteNode(&pHead, 6); //删除尾部
        test = pHead;
        while (test != NULL) {
            NSLog(@"%d", test->data);
            test = test->next;
        }
    }
    return 0;
}