请输入您要查询的百科知识:

 

词条 双链表
释义

1、双向链表(Doubly Linked List)

双(向)链表中有两条方向不同的链,即每个结点中除next域存放后继结点地址外,还增加一个指向其直接前趋的指针域prior。

注意:

①双链表由头指针head惟一确定的。

②带头结点的双链表的某些运算变得方便。

③将头结点和尾结点链接起来,为双(向)循环链表。

2、双向链表的结点结构和形式描述

①结点结构(见上图a)

②形式描述

typedef struct dlistnode{

DataType data;

struct dlistnode *prior,*next;

}DListNode;

typedef DListNode *DLinkList;

DLinkList head;

3、双向链表的前插和删除本结点操作

刻画双链表结构的对称性的语句:p→prior→next== p→next→prior;由于双链表的对称性,在双链表能能方便地完成各种插入、删除操作。

①双链表的前插操作

void DInsertBefore(DListNode *p,DataType x)

{//在带头结点的双链表中,将值为x的新结点插入*p之前,设p≠NULL

DListNode *s=malloc(sizeof(DListNode));//①

s->data=x;//②

s->prior=p->prior;//③

s->next=p;//④

p->prior->next=s;//⑤

p->prior=s;//⑥

}

②双链表上删除结点*p自身的操作

void DDeleteNode(DListNode *p)

{//在带头结点的双链表中,删除结点*p,设*p为非终端结点

p->prior->next=p->next;//①

p->next->prior=p->prior;//②

free(p);//③

}

注意:

与单链表上的插入和删除操作不同的是,在双链表中插入和删除必须同时修改两个方向上的指针。

上述两个算法的时间复杂度均为O(1)。

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2025/3/4 11:17:52