# 双链表

  单链表结点中只有一个只指向后继的指针，使得单链表只能从头结点开始一次顺序的先后遍历。要访问某个结点的前驱结点（插入删除操作时），只能从头开始遍历，访问后继节点的时间复杂度为O（1），访问前驱结点的时间复杂度为O（n）。

  为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针prior 和 next，分别指向其前驱结点和后继结点。

## 定义

  双链表中结点类型描述：

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/%E5%8F%8C%E9%93%BE%E8%A1%A8.jpg)

```cpp
typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode,*DLinkList;
```

  在双链表中，按位查找和按值查找的操作和单链表中的相同。但在插入和删除上有着较大的不同。因为双链表有prior指针，可以很方便地找到其前驱结点，因此插入，删除结点的时间复杂度为O（1）。

## 前插操作

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/%E5%8F%8C%E9%93%BE%E8%A1%A8%E6%8F%92%E5%85%A5.jpg)

  将结点s 插入到指针p所指结点b之前：

```cpp
bool DLinkList_Insert(DLinkList& L,ElemTyep c){
    DNode* p;
    /* 先检查位置是否合法...  */
    DNode* s = (DNode*)malloc(sizeof(DNode));
    s->data = c;
    //第一步：结点s的prior指针指向左边的结点
    s->prior = p->prior;    
    //第二步：结点b的前驱结点（也就是左边的结点）的next指针指向结点s
    p->prior->next = s;
    //第三步：结点s的next指针指向结点b
    s->next = p;
    //第四步：结点b的prior指针指向结点s
    p->prior = s;        
    return true;
}
```

  **注意：第一，二步必须在第四步之前，否则\*p的前驱结点的指针就会丢失，导致插入失败。**

## 后插操作

  将结点s 插入到指针p所指的节点b 之后（如上图，假设后面的结点是d）：

```cpp
bool DLinkList_Insert(DLinkList& L,ElemType c){
    DNode* p;
    DNode* s = (DNode*)malloc(sizeof(DNode));
    s->data = c;
    //第一步：将结点s 的next指针指向后继结点
    s->next = p->next;
    //第二步；将后继结点的prior指针指向结点s
    p->next->prior = s;
    //第三步：将结点s的prior指针指向结点b
    s->prior = p;
    //第四步：将结点b的next指针指向结点s
    p->next = s;
    return true;    
}
```

  同样的，前插操作和后插其实没区别，注意第四步即可，大家不清楚可以在草稿纸上面画出来，画出来了就一目了然了。

## 删除操作

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/%E5%8F%8C%E9%93%BE%E8%A1%A8%E5%88%A0%E9%99%A4.JPG)

  删除指针p指向的结点b：

```cpp
bool DLinkList_Delete(DLinkList& L){
    DNode* p;
    //第一步：将结点b的前驱结点的next指针指向结点c
    p->prior->next = p->next;
    //第二步：将结点c的prior指针指向结点b的前驱结点
    p->next->prior = p->prior;
    //释放结点空间
    free(p);
}
```

  **如果是删除指针p指向的结点的后继结点，指针q指向后继结点，也就是后删：**

```cpp
bool DLinkList_Delete(DLinkList& L){
    DNode *p,*q;
    p->next = q->next;
    q->next->prior = p;
    free(q);
}
```