双链表

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

双向列表是意图

注意:
①双链表由头指针head惟一确定的。
②带头结点的双链表的某些运算变得方便。
③将头结点和尾结点链接起来,为双(向)循环链表。

2、双向链表的结点结构和形式描述
①结点结构(见上图a)
     
②形式描述
typedef struct dlistnode{
DataType data;
struct dlistnode *prior,*next;
}DListNode;
typedef DListNode *DLinkList;
DLinkList head;

3、双向链表的前插和删除本结点操作
由于双链表的对称性,在双链表能能方便地完成各种插入、删除操作。
①双链表的前插操作
双向列表前端插入
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自身的操作
双链表上删除结点*p自身的操作
void DDeleteNode(DListNode *p)
{//在带头结点的双链表中,删除结点*p,设*p为非终端结点
p->prior->next=p->next;//①
p->next->prior=p->prior;//②
free(p);//③
}
注意:
与单链表上的插入和删除操作不同的是,在双链表中插入和删除必须同时修改两个方向上的指针。
上述两个算法的时间复杂度均为O(1)。

Tagged on:

One thought on “双向链表(Double Linked List)|E路上一路上

发表评论