4.7 双向链表

在双向链表中,结点至少有三个域:左链域 llink,数据域 item,右链域 rlink

双向链表可以是也可以不是循环的。下图给出一个具有三个结点的双向循环链表。除了这三个结点以外,还增加了一个头结点。头结点的数据域通常不包含信息。

4-10

具有头结点的双向循环链表

假设 ptr 指向一个双向链表的任意结点。那么

ptr = ptr -> llink -> rlink = ptr -> rlink -> llink

这个式子反映了这种结构的本质,也就是说,可以方便地向前和向后移动。一个空表总是有一个如下图的头结点。

带有头结点的空双向循环链表

  • 『双向循环链表的插入操作』newnode 插入 node 的右边
void dinsert(node_pointer node, node_pointer newnode)
{
    newnode->llink = node;
    newnode->rlink = node->rlink;
    node->rlink->llink = newnode;
    node->rlink = newnode;
}
  • 『双向循环链表的删除操作』
void ddelete(node_pointer node, node_pointer deleted)
{
    if (node == deleted)
        // Deletion of head node not permitted.
    else {
        deleted->llink->rlink = deleted->rlink;
        deleted->rlink->llink = deleted->llink;
        free(deleted);
    }
}

results matching ""

    No results matching ""