双向链表的插入与删除

1、在带有头结点双向循环链表中第1个数据域内容为x的结点右边插入一个数据信息为item的新结点，如下：

typedef struct node{
    int data;
    struct node *llink, *rlink;
}DNode, *DLinkList;

int insertElem( DLinkList list, int x, int item ){
    DLinkList p, q;
    q = list->rlink; //首先将q指向头结点后面的那个结点
    while( q != list && q->data != x ){ //寻找第一个满足条件的结点
        q = q->rlink;
    }
    if( q == list ){ //如果不存在满足插入条件的结点，则返回
        printf( "there is no x element in the list" );
        return -1;
    }

    p = ( DLinkList )malloc( sizeof( DNode ) ); //申请一个新的结点
    if( p == NULL ){ //判断内存分配是否成功
        printf( "malloc error!" );
        return -1;
    }
    p->data = item;
    p->llink = q; //插入新的结点
    p->rlink = q->rlink;
    q->rlink->llink = p;
    q->rlink = p;

    return 1;
}

2. 从带有头结点双向循环链表中删除第1个数据域内容为x的结点：

 

int deleteElem( DLinkList list, int x ){
    DLinkList q;
    q = list->rlink; //首先q指向头结点后面的那个结点
    while( q != list && q->data != x ){ //找到要删除的结点
        q = q->rlink;
    }
    if( q == list ){ //如果不存在满足条件的结点,返回-1
        printf( "there is no matched element in the list" );
        return -1;
    }

    q->llink->rlink = q->rlink; //删除结点
    q->rlink->llink = q->llink;
    free( q ); //释放结点的内存空间
    return 1; //删除成功，返回1
}