|
双向链表(Double Linked List) 双(向)链表中有两条方向不同的链即每个结点中除next域存放后继结点地址外还增加一个指向其直接前趋的指针域 prior 注意 ①双链表由头指针head惟一确定的 ②带头结点的双链表的某些运算变得方便 ③将头结点和尾结点链接起来为双(向)循环链表 双向链表的结点结构和形式描述 ①结点结构(见上图a) ②形式描述 typedef struct dlistnode{ DataType data; struct dlistnode *prior*next; }DListNode; typedef DListNode *DLinkList; DLinkList head; 双向链表的前插和删除本结点操作 由于双链表的对称性在双链表能能方便地完成各种插入删除操作 ①双链表的前插操作 void DInsertBefore(DListNode *pDataType 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() |
