37.2° Blog

1. 头插法建立循环双链表

问题

使用头插法建立循环双链表

算法思想

• 注意初始化循环双链表时要把前后指针都指向带头结点
• 注意头插法的顺序

代码

void createHeadDuCircleList(DuLinkList& DL, ElemType* arr, int arrLength)
{
    DL = (DuLinkNode*)malloc(sizeof(DuLinkNode));
    DL->next = DL;
    DL->prior = DL;
    DuLinkNode* tmpNode = NULL;
    for (int i = 0; i < arrLength; i++)
    {
        tmpNode = (DuLinkNode*)malloc(sizeof(DuLinkNode));
        tmpNode->data = arr[i];
        // 循环双链表头插法插入结点
        // 1、更新插入结点的前驱指针
        tmpNode->prior = DL;
        // 2、更新插入结点后继指针
        tmpNode->next = DL->next;
        // 3、更新前驱的后继指针
        tmpNode->prior->next = tmpNode;
        // 4、更新后继的前驱指针
        tmpNode->next->prior = tmpNode;
    }
}

2. 循环双链表删除

问题

循环双链表结点的删除操作

算法思想

代码

void deleteNode(DuLinkNode* pNode)
{
    // 1、更新前驱结点的后继指针
    pNode->prior->next = pNode->next;
    // 2、更新后继结点的前驱指针
    pNode->next->prior = pNode->prior;
    // 释放结点
    free(pNode);
}