线性表（五）——双向链表

双向链表

构造原理

所谓双向链表是指链表的每一个结点中除了数据域以外设置两个指针域，其中之一指向结点的直接前驱结点，另外一个指向结点的直接后继结点。
链结点的实际构造可以形象地描述如下：

其中，data为数据域，llink, rlink分别为指向该结点的直接前驱结点与直接后继结点的指针域
双向链表分为以下几种形式

基本操作

1、C语言类型定义如下：

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

2、双向链表的插入
在带有头结点的非空双向循环链表中第一个数据域的内容为x的链结点右边插入一个数据信息为item的新结点。
步骤如下：
1、找到满足条件的结点；
2、若找到，构造一个新的链结点；
3、将新结点插到满足条件的结点后面；

int INSERTD( DLinkList list, ElemType x, ElemType item ){
    DLinkList p,q;
    q=list->rlink; /* q 初始指向头结点的下一个结点*/
    while ( q!=list && q->data!=x)             /* 寻找满足条件的链结点*/
        q=q->rlink; 
    if ( q == list )
        return -1;               /* 没有找到满足条件的结点*/
    p = (DLinkList)malloc(sizeof(DNode));     /* 申请一个新的结点*/
    p->data=item;
    p->llink=q;
    p->rlink=q->rlink;
    q->rlink->llink=p;
    q->rlink=p;
    return 1;           /* 插入成功*/
}

该算法的时间复杂度为O(n)
3、双向链表的删除
删除带有头结点的非空双向循环链表中第一个数据域的内容为x的链结点。

int DELETED( DLinkList list, ElemType x ){ 
    DLinkList p,q;
    q=list->rlink;                              /*q初始指向头结点的下一个结点*/
    while (q!=list &&q->data!=x)     /*找满足条件的链结点*/ 
        q=q->rlink；
    if (q==list) 
        return -1;         /*没有找到满足条件的结点*/
    q->llink->rlink=q->rlink;
    q->rlink->llink=q->llink;
    free(q);                /*释放被删除的结点的存储空间*/
    return 1;              /*删除成功*/
}

该算法的时间复杂度为O(n)