C语言超详细i讲解双向链表

C语言超详细讲解双向链表

什么是双向链表

双向链表是一个动态数据结构，它由一系列的节点构成，每个节点分为三部分：数据域、指向前驱节点的指针和指向后继节点的指针。双向链表支持在任意位置插入或删除节点，与数组相比，它具有更好的灵活性和效率。

如何实现双向链表

定义节点

typedef struct DNode {
    int data;
    struct DNode* prev;
    struct DNode* next;
}DNode, *DLinkList;

创建节点

//创建节点
DNode* create_node(int data) {
    DNode* node = (DNode*)malloc(sizeof(DNode));
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

插入节点

头部插入节点

//头部插入节点
void insert_head(DLinkList* head, DNode* node) {
    if (node == NULL) {
        return;
    }
    node->next = *head;
    node->prev = NULL;
    if (*head != NULL) {
        (*head)->prev = node;
    }
    *head = node;
}

尾部插入节点

//尾部插入节点
void insert_tail(DLinkList* head, DNode* node) {
    if (node == NULL) {
        return;
    }
    if (*head == NULL) {
        *head = node;
        node->prev = NULL;
        node->next = NULL;
    }
    else {
        DNode* p = *head;
        while (p->next != NULL) {
            p = p->next;
        }
        node->prev = p;
        node->next = NULL;
        p->next = node;
    }
}

按位置插入节点

//按位置插入节点
void insert_pos(DLinkList* head, DNode* node, int pos) {
    if (node == NULL) {
        return;
    }
    if (*head == NULL || pos <= 1) {
        node->prev = NULL;
        node->next = *head;
        if (*head != NULL) {
            (*head)->prev = node;
        }
        *head = node;
    }
    else {
        DNode* p = *head;
        int i = 1;
        while (p->next != NULL && i < pos-1) {
            p = p->next;
            i++;
        }
        node->prev = p;
        node->next = p->next;
        if (p->next != NULL) {
            p->next->prev = node;
        }
        p->next = node;
    }
}

删除节点

删除头部节点

//删除头部节点
void delete_head(DLinkList* head) {
    if (*head != NULL) {
        DNode* p = *head;
        *head = (*head)->next;
        if (*head != NULL) {
            (*head)->prev = NULL;
        }
        free(p);
    }
}

删除尾部节点

//删除尾部节点
void delete_tail(DLinkList* head) {
    if (*head != NULL) {
        DNode* p = *head;
        while (p->next != NULL) {
            p = p->next;
        }
        if (p->prev != NULL) {
            p->prev->next = NULL;
        }
        else {
            //删除头部节点
            *head = NULL;
        }
        free(p);
    }
}

按位置删除节点

//按位置删除节点
void delete_pos(DLinkList* head, int pos) {
    if (*head != NULL && pos >= 1) {
        if (pos == 1) {
            //删除头部节点
            delete_head(head);
        }
        else {
            DNode* p = *head;
            int i = 1;
            while (p->next != NULL && i < pos) {
                p = p->next;
                i++;
            }
            if (i == pos && p != NULL) {
                if (p->prev != NULL) {
                    p->prev->next = p->next;
                }
                if (p->next != NULL) {
                    p->next->prev = p->prev;
                }
                free(p);
            }
        }
    }
}

示例说明

插入节点示例

//创建双向链表
DLinkList head = NULL;
int n, i, data;
printf("请输入节点个数：");
scanf("%d", &n);
for (i = 1; i <= n; i++) {
    printf("请输入第%d个节点的数据：", i);
    scanf("%d", &data);

    //创建节点
    DNode* node = create_node(data);

    //头部插入节点
    //insert_head(&head, node);

    //尾部插入节点
    insert_tail(&head, node);

    //按位置插入节点
    //insert_pos(&head, node, i);
}

//遍历双向链表
DNode* p = head;
printf("双向链表元素：");
while (p != NULL) {
    printf("%d ", p->data);
    p = p->next;
}

删除节点示例

//创建双向链表
DLinkList head = NULL;
int n, i, data;
printf("请输入节点个数：");
scanf("%d", &n);
for (i = 1; i <= n; i++) {
    printf("请输入第%d个节点的数据：", i);
    scanf("%d", &data);

    //创建节点
    DNode* node = create_node(data);

    //头部插入节点
    insert_head(&head, node);

    //尾部插入节点
    //insert_tail(&head, node);

    //按位置插入节点
    //insert_pos(&head, node, i);
}

//删除双向链表中第3个节点
delete_pos(&head, 3);

//遍历双向链表
DNode* p = head;
printf("双向链表元素：");
while (p != NULL) {
    printf("%d ", p->data);
    p = p->next;
}