typedef char ElemType; 
typedef struct DulNode {
    ElemType data;
    struct DulNode *prev, *next;
} DulNode, *DuLinkList;

DuLinkList InitDuList() {
    DuLinkList L;
    if(!(L=(DulNode*)malloc(sizeof(DulNode)))) exit(OVERFLOW);
    L->next = L;
    L->prev = L;
    return L;
}

DuLinkList FreeDuList(DuLinkList L) {
    if(!L) return NULL;
    DuLinkList q, p = L->next;
    while(p!=L) {q = p; p->p-next; free(q);}
    free(L);
    return NULL;
}

DuLinkList CreateDuList(char* ss) {
    int i; DuLinkList L,p,s;
    if(!(L = p = (DuLNode*)malloc(sizeof(DuLNode)))) exit(OVERFLOW);
    L->next = L;
    L->prev = L;
    for(i=strlen(ss); i>=1; i--) {
        if(!(s=(DuLNode*)malloc(sizeof(DuLNode)))) exit(OVERFLOW);
        s->data = ss[i-1];
        s->next = p->next; p->next->prev = s;
        s->prev = p; p->next = s;
    }
    return L;    
}

DuLinkList GetElemPos(DuLinkList L, int i) {
    if(!L || i< 0) return NULL;
    if(i==0) return NULL;
    DuLinkList p = L->next;
    int j = 1;
    while(p!=L && j < i) {
        p = p->next;
        ++j;        
    }
    if(p==L)return NULL;
    return p;
}

Status listInsert(DuLinkList L, int i, ElemType e){
    if(!L || i < 1) return ERROR;
    DulNode *p, *s;
    if(!(p=GetElemPos(L, i-1))) return ERROR;
    if(!(s = (DuLNode*)malloc(sizeof(DuLNode)))) exit(OVERFLOW);
    s->data = e;
    s->next = p->next;
    p->next->prev = s;
    s->prev = p;
    p->next = s;
    return OK;
}

ElemType ListDelete(DuLinkList L, int i) {
    if(!L || i < 1) return errV;
    DulNode *p;
    if(!(p=GetElePos(L, i))) return errV;
    ElemType e = p->data;
    p->prev->next = p->next;
    p->next->prev = p->prev;
    free(p); return e;
}