数据结构（10）双链表的简介和基本操作实现（插入、删除）_双链表删除结点*q的前驱结点*p

目录

1、双链表的介绍

2、双链表的常用操作

2.1、双链表的插入操作

2.2、双链表的删除操作

---

1、双链表的介绍

单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点，只能从头遍历。访问后续结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)。

为了克服单链表的上述缺点，引入了双链表，双链表有两个指针prior和next，分别指向其前驱结点和后继结点，如图10-1所示

                                                           图10.1  双链表示意图

双链表中结点类型的描述如下：

typedef struct DNode
 
{
 
    ElemType data;
 
    struct DNode *prior,*next;   //前驱和后继指针
 
}

双链表仅在单链表的结点中增加了一个指向其前驱的prior指针，因此在双链表中执行按值查找和按位查找的操作与在单链表中的相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同，因为还需要对prior指针做出修改。

双链表很容易找到其前驱结点，因此，与单链表相比，对前驱结点的操作（插入、删除）复杂度从O(n)变成O(1)。

2、双链表的常用操作

2.1、双链表的插入操作

在双链表中p所指结点之后插入s所指的结点，其指针的变化过程如图10.2所示。

                                         图10.2  双链表插入一个新结点

插入操作的主要代码如下：

s->next = p->next;

s->prior = p;

p->next->prior = s;

p->next = s;

2.2、双链表的删除操作

删除双联表中结点*p的后继结点*q，其指针的变化过程如图10.3所示

                                                    图10.3  双链表删除一个结点

 

插入操作的主要代码如下：

p->next = q->next;

q->next->prior = p;

q->next = NULL;

q->prior = NULL;

free(q);

 

 

 

人，总是要有一点精神的，不是吗