C 语言学习（10） ---- 双向链表

双链表

单链表的替代方案就是双链表，在一个双链表中，每个节点都包含两个指针，一个指向前一个节点的指针和一个指向后一个节点的指针，这可以使我们以任何方向遍历链表

双链表的初始化

typedef struct Node_s {
    struct Node_s *next;
    struct Node_s *prev;
    uint32_t value;
} stNode;


stNode rootNode = {
    .value = 0,
    .next = NULL, // 指向链表第一个元素
    .prev = NULL, // 指向链表最后一个元素
};

在这里使用了一个 stNode 节点的结构保存双链表的根指针，称为根节点，也可以直接定义两个stNode* 类型的指针变量，根节点的数据域是没有被用到的，使用节点结构保存跟指针的好处是函数传入根节点的指针就可以修改两个根指针的值
rootNode 的 next 指向第一个元素
rootNode 的 prev 指向最后一个元素

根节点的字段可以保存一些额外的信息，比如当前链表包含的节点数量

创建节点的函数如下：

static stNode *createListNode(uint32_t data) {
    stNode *list = (stNode*)malloc(sizeof(stNode));
    list->value = data;
    list->next = NULL;
    list->prev = NULL;
    return list;
}

双链表的插入

双链表头部插入

双链表的头插.jpg

根节点为空的情形暂时没有考虑，因为如果为空，则必须在尾部插入，也就无所谓头部插入
使用两个指针，一个指向头结点，一个指向根节点

static int doubleLinkListInsertfront(stNode *rootp, stNode *node) {
    stNode *this = rootp;
    stNode *next = rootp->next; // 第一个元素

    if(next != NULL) {
        node->next = next;
        node->prev = NULL;
        next->prev = node;
        rootp->next = node;
    }
}

双链表尾部插入

尾部插入需要考虑两种情形：

1. 根节点为空，也就是此时没有任何元素
2. 根节点非空，用 rootp->prev 指向最后一个元素

插入空链表.jpg

方法一：直接使用头结点的 prev 指针，prev 指针指向最后一个元素
方法二：使用两个指针，顺次向前遍历，直到 next 为空，此时 this 指向的就是最后一个节点

双链表的尾部插入.jpg

static int doubleLinkListInsertBackquick(stNode *rootp, stNode *node) {
    stNode *this = rootp->prev;

    if (this != NULL) {
        this->next = node;
        node->next = NULL;
        node->prev = this;
        rootp->prev = node;// rootp->prev 指向最后一个元素
    } else {
        rootp->prev = node;
        rootp->next = node;
        node->prev = NULL;
        node->next = NULL;
    }
    return TRUE;
}

双链表一般插入

双链表的中间插入.jpg

双链表的遍历

双链表可以从头尾两个方向遍历：

/*
** rootp->prev 指向第一个节点  rootp->next 指向最后一个节点
** 定义一个指针，找到一个节点，决定判断条件，顺次遍历
*/
static int doublelisttraversaForward(stNode *rootp)
{
    // rootp prev 指向第一个节点
    stNode *current = rootp->next;
    printf("traversaForward: ");

    while (current != NULL) {
        printf(" %d", current->value);
        current = current->next;
    }
    printf("\n");
    return TRUE;
}

/*
** rootp->prev 指向第一个节点  rootp->next 指向最后一个节点
** 定义一个指针，找到一个节点，决定判断条件，顺次遍历
*/
static int doublelisttraversaBackward(stNode *rootp)
{
    stNode *current = rootp->prev;
    printf("traversaForward: ");
    while (current != NULL) {
        printf(" %d", current->value);
        current = current->prev;
    }
    printf("\n");
    return TRUE;
}