> For the complete documentation index, see [llms.txt](https://xiuxin.gitbook.io/datastructre/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://xiuxin.gitbook.io/datastructre/xian-xing-biao/shuang-lian-biao.md).

# 双链表

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

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

## 定义

  双链表中结点类型描述：

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/双链表.jpg)

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

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

## 前插操作

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/双链表插入.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/双链表删除.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);
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://xiuxin.gitbook.io/datastructre/xian-xing-biao/shuang-lian-biao.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.