双链表:双链表的优点、插入节点、删除节点
单链表结点中只有一个指向其后继的指针,这使得单链表只能从头结点依次顺序地向后遍历。若要访问某个结点的前驱结点(插入、删除操作时),只能从头开始遍历,访问后继结点的时间复杂度为O(1),访问前驱结点的时间复杂度为O(n)。
为了克服单链表的上述缺点,引入了双链表,双链表结点中有两个指针prior和next,分别指向其前驱结点和后继结点,如图2-8所示。
图2-8 双链表示意图
双链表中结点类型的描述如下:
双链表仅仅是在单链表的结点中增加了一个指向其前驱的prior指针,因此,在双链表中执行按值查找和按位查找的操作和单链表相同。但双链表在插入和删除操作的实现上,和单链表有着较大的不同。这是因为“链”变化时也需要对prior指针做出修改,其关键在于保证在修改的过程中不断链。此外,双链表可以很方便地找到其前驱结点,因此,插入、删除结点算法的时间复杂度仅为O(1)。
插入操作的代码片段如下:
图2-9 双链表插入结点过程
上述代码的语句顺序不是唯一的,但也不是任意的,①②两步必须在④步之前,否则*p 的后继结点的指针就丢掉了,导致插入失败。为了加深理解,读者可以在纸上画出示意图。若问题改成要求在结点*p之前插入结点*s,请读者思考具体的操作步骤。
图2-10 双链表删除结点过程
删除操作的代码片段如下:
建立双链表的操作中,也可以采用如同单链表的头插法和尾插法,但是在操作上需要注意指针的变化和单链表有所不同。
为了克服单链表的上述缺点,引入了双链表,双链表结点中有两个指针prior和next,分别指向其前驱结点和后继结点,如图2-8所示。
图2-8 双链表示意图
双链表中结点类型的描述如下:
typedef struct DNode { //定义双链表结点类型 ElemType data; //数据域 struct DNode *prior, *next; //前驱和后继指针 }DNode, *DLinklist;
双链表仅仅是在单链表的结点中增加了一个指向其前驱的prior指针,因此,在双链表中执行按值查找和按位查找的操作和单链表相同。但双链表在插入和删除操作的实现上,和单链表有着较大的不同。这是因为“链”变化时也需要对prior指针做出修改,其关键在于保证在修改的过程中不断链。此外,双链表可以很方便地找到其前驱结点,因此,插入、删除结点算法的时间复杂度仅为O(1)。
双链表的插入操作
在双链表中p所指的结点之后插入结点*s,其指针的变化过程如图2-9所示。插入操作的代码片段如下:
s->next=p->next; // 语句①,将结点*s插入到结点*p之后 p->next->prior=s; // 语句② s->prior=p; // 语句③ p->next=s; // 语句④
图2-9 双链表插入结点过程
上述代码的语句顺序不是唯一的,但也不是任意的,①②两步必须在④步之前,否则*p 的后继结点的指针就丢掉了,导致插入失败。为了加深理解,读者可以在纸上画出示意图。若问题改成要求在结点*p之前插入结点*s,请读者思考具体的操作步骤。
双链表的删除操作
删除双链表中结点*p的后继结点*q,其指针的变化过程如图2-10所示。图2-10 双链表删除结点过程
删除操作的代码片段如下:
p->next=q->next; // 图2-10中步骤①① q->next->prior=p; //图 2-10 中步骤② free (q) ; //释放结点空间若问题改成要求删除结点*q的前驱结点*p,请读者思考具体的操作步骤。
建立双链表的操作中,也可以采用如同单链表的头插法和尾插法,但是在操作上需要注意指针的变化和单链表有所不同。