四、线性表(七)、 双向链表

数据结构目录

我们之前讨论的链式存储结构的结点中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺时针往后寻查其它结点。如果要寻查直接前驱，则需要从表头指针出发。换句话说，在单链表中，NextElem的执行时间为O(1),而PriorElem的执行时间为O(n).为克服单链表这种单向性的缺点，可以利用双向链表(double linked list).
顾名思义，在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱.

1.定义

typedef struct DulNode{
    ElemType data;//数据域
    struct DulNode *prior;//直接前驱结点
    struct DulNode *next;//直接后继结点
}DulNode;
typedef struct DulNode *DuLinkList;

双向链表结点结构与空双向链表

既然单链表有循环表，双向链表也有循环表结构

双向循环链表

2. 双向链表的插入操作

双向链表的插入

双向链表的插入操作并不复杂，但是顺序很重要，千万不要写反了。
如图所示，将结点S插入在双向链表的P结点之前，我们需要：

s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;

实现如下：

//获取结点操作
DuLinkList GetElem(DuLinkList L,int i){
    DuLinkList p = L->next;//获取头结点的指针  p代表第一个结点
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }

    if (!p || j > i) {
        return NULL;
    }
    
    return p;
}

//在带头结点的双链循环线性表L中第i个位置之前插入e
Status ListInsert_Dul(DuLinkList *L,int i,ElemType e){
    DuLinkList p = GetElem(*L, i);
    if (!p) {
        //p为NULL，插入位置非法
        return ERROR;
    }
    DuLinkList s = (DuLinkList)malloc(sizeof(DulNode));
    if (!s) {
        return ERROR;
    }
    s->data = e;
    s->next = p;
    s->prior = p->prior;
    p->prior->next = s;
    p->prior = s;
    
    return OK;
}

3.双向链表的删除操作

双向链表的删除操作

删除操作更容易理解，我们可以这样实现:

p->prior->next = p->next;
p->next->prior = p->prior;
free(p);

实现如下:

//删除带头结点的双向链表L的第i个元素
Status ListDelete_Dul(DuLinkList *L,int i,ElemType *e){
    DuLinkList p = GetElem(*L, i);
    if (!p) {
        //位置非法，即第i个元素不存在
        return ERROR;
    }
    *e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    
    return OK;
}