数据结构-2.9.双链表

一.双链表与单链表的对比：

二.双链表的初始化(带头结点)：

1.图解：

2.代码演示：

#include<stdio.h>
#include<stdlib.h>
​
//定义双链表结构体
typedef struct DNode
{
    int data;
    struct DNode *prior;//前驱指针即指向前面数据的指针 
    struct DNode *next;//后继指针即指向后面数据的指针 
}DNode,*DLinklist; //DLinklist与DNode *等价，DLinklist强调链表，DNode *强调结点 
​
//初始化双链表
bool InitDLinkList(DLinklist &L)
{
    L = (DNode *)malloc( sizeof(DNode) );//分配一个头结点
    if( L==NULL ) //内存不足，分配失败 
    {
        return false;
    } 
    L->prior = NULL;//头结点的prior(前驱)永远指向NULL
    L->next = NULL;//头结点之后(后继)暂时还没有结点 
    return true;
} 
​
//判断双链表是否为空(带头结点)->只需要看第一个结点是否为空即可 
bool Empty(DLinklist L)
{
    if( L->next == NULL )//代表双链表第一个结点为空，是空双链表
    {
        return true;
    }
    else
    {
        return false;//代表双链表第一个结点不为空，不是空双链表 
    }
} 
​
int main()
{
    //初始化双链表 
    DLinklist L;
    InitDLinkList(L);
    //后续代码。。。 
    return 0;
}

三.双链表的插入：

图解：

此时要p结点之后插入s结点，起初p->next指向y，先把p的下一个结点即y和要插入的结点即s的指向下一个结点的指针对接即s->next = p->next：

之后还需要把p结点的后继结点即p->next的前向指针p->next->prior指向s即p->next->prior = s:

再把要插入的结点即s结点的前驱指针指向p结点即 s->prior = p：

最后把p结点的后继结点指向s即p->next = s：

但对于上述代码，有一个bug，当p结点是最后一个结点时，p->next->prior = s就会报空指针的错，因为

p结点是最后一个结点时p->next指向NULL，因此，严谨的代码如下：对p->next进行空指针判断

• 按位序插入：找到要插入的位序的前驱结点，在该结点实现后插操作即可

• 前插操作：由于双链表的特性，可以很方便的找到给定结点的前驱结点，再对前驱结点进行后插操作即可

四.双链表的删除：

图解：

此时要删除p结点的后继结点q，因此要把q结点的下一个结点和p结点连接，即p->next = q->next：

再把要删除的q结点的后继结点即q->next的前驱结点即q->next->prior指向p即q->next->prior = p：

最后再释放要删除的q结点即free(q)：free函数要用到头文件#include<stdlib.h>

但上述代码也有bug，如果此时要删除的q结点为双链表最后一个结点，那么q->next就指向NULL，q->next->prior就会报空指针错误，因此对q->next进行空指针判断以增加严谨性：

销毁双链表：每一次删除头结点的后继结点即可

因为比如第一次删除头结点的后继结点即第一个结点，第二次删除时第二个结点就来了第一个位置，相当于头结点的后继结点，删除即可，以此类推，可销毁双链表：

五.双链表的遍历：

1.对于前向遍历(跳过头结点)的循环条件当p->prior == NULL时，说明此时p结点指向的就已经是头结点了，此时跳出循

环，不操作头结点了；

2.对于按位查找，只需要添加一个计数器，用于记录此时指向的哪个位置的元素，当位置和要找的位置匹配时打印即可；

3.对于按值查找，只需要对当前指向的结点和要找的值对比即可，找到了就打印即可；

4.双链表没有随机存取的特性，所以按位查找，按值查找的时间复杂度为O(n)，因为只能用循环的方式一个一个对比依次

往后找。

六.总结：