C语言双向链表的原理与使用操作

什么是双向链表

双向链表是由一系列结点组成的数据结构，每个结点除了有指向下一个结点的指针，还有指向上一个结点的指针。这种链表可以从头到尾或者从尾到头进行遍历。

双向链表的结构

下面是一个双向链表的结构体定义：

typedef struct Node{
    int data;
    struct Node *pre;
    struct Node *next;
}node;

其中data表示结点所存储的数据，pre和next分别表示指向前一个结点和后一个结点的指针。

双向链表的操作

初始化

在创建双向链表之前需要先进行初始化，定义一个头节点指针，并将其指向NULL。代码如下：

node *head = NULL;

插入

双向链表的插入操作比较灵活，可以在任意位置插入。假设要在第二个结点的位置插入一个新的结点，代码如下：

node *new_node = (node *)malloc(sizeof(node));
new_node->data = 10;

node *temp = head->next;
head->next = new_node;
new_node->pre = head;
new_node->next = temp;
if (temp != NULL) {
    temp->pre = new_node;
}

首先先创建一个新的结点并赋值，然后将当前节点的后继赋值给新节点的后继，将新节点的前驱赋值为当前节点，将新节点连到当前节点的后面。

删除

双向链表的删除操作也比较灵活，同样可以删除任意位置的结点。假设要删除第二个结点，代码如下：

node *temp = head->next;
if (temp != NULL) {
    head->next = temp->next;
    if (temp->next != NULL) {
        temp->next->pre = head;
    }
    free(temp);
}

首先将当前节点的后继节点保存到临时变量中，然后修改当前节点的后继指向下一个节点，如果下一个节点存在，则将它的前驱指针修改为当前节点，最后释放掉被删除的节点。

示例

以下是一个简单的示例用来说明双向链表的使用操作：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
    int data;
    struct Node *pre;
    struct Node *next;
}node;

void insert(node *head, int data);
void delete(node *head, int data);
void print(node *head);

int main() {
    node *head = (node *)malloc(sizeof(node));
    head->pre = NULL;
    head->next = NULL;

    insert(head, 10);
    insert(head, 20);
    insert(head, 30);
    insert(head, 40);
    insert(head, 50);

    delete(head, 30);

    print(head);

    // 释放节点
    node *temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

void insert(node *head, int data) {
    node *new_node = (node *)malloc(sizeof(node));
    new_node->data = data;

    node *temp = head->next;
    head->next = new_node;
    new_node->pre = head;
    new_node->next = temp;
    if (temp != NULL) {
        temp->pre = new_node;
    }
}

void delete(node *head, int data) {
    node *temp = head->next;
    while (temp != NULL) {
        if (temp->data == data) {
            temp->pre->next = temp->next;
            if (temp->next != NULL) {
                temp->next->pre = temp->pre;
            }
            free(temp);
            return;
        }
        temp = temp->next;
    }
    printf("节点不存在\n");
}

void print(node *head) {
    node *temp = head->next;
    printf("链表内容：");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

运行结果：

链表内容：10 20 40 50 

以上就是C语言双向链表的原理与使用操作的完整攻略。