C语言 数据结构双向链表简单实例

本文将详细讲解如何使用C语言实现一个双向链表的数据结构，并介绍如何在此链表上进行一些基本操作。整个过程中将包含两条示例说明。

1. 双向链表定义

一个双向链表通常由多个节点组成，每个节点有三个部分组成：

struct node {
    struct node *prev;
    struct node *next;
    int data;
};

其中，prev和next分别指向前驱节点和后继节点，而data则是节点存储的数据。在实现双向链表时，我们还需要定义一个头节点和一个尾节点，分别指向第一个和最后一个节点。

struct node *head = NULL;
struct node *tail = NULL;

2. 双向链表基本操作

2.1 插入操作

要想向双向链表中插入一个节点，有两种常见的方式：在头节点处插入和在尾节点处插入。下面分别介绍这两种操作的实现方法。

2.1.1 在头节点处插入

首先需要创建一个新节点：

struct node *new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = data;
new_node->prev = NULL;
new_node->next = NULL;

然后将新节点插入到头节点之前：

if (head == NULL) {
    head = new_node;
    tail = new_node;
} else {
    new_node->next = head;
    head->prev = new_node;
    head = new_node;
}

2.1.2 在尾节点处插入

同样需要创建一个新节点：

struct node *new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = data;
new_node->prev = NULL;
new_node->next = NULL;

然后将新节点插入到尾节点之后：

if (tail == NULL) {
    head = new_node;
    tail = new_node;
} else {
    new_node->prev = tail;
    tail->next = new_node;
    tail = new_node;
}

2.2 删除操作

删除双向链表中的某个节点，需要分别修改该节点的前驱节点和后继节点，将它们连接起来即可。下面介绍如何删除头节点和尾节点。

2.2.1 删除头节点

if (head == NULL) {
    return;
} else if (head == tail) {
    free(head);
    head = NULL;
    tail = NULL;
} else {
    head = head->next;
    free(head->prev);
    head->prev = NULL;
}

2.2.2 删除尾节点

if (tail == NULL) {
    return;
} else if (tail == head) {
    free(tail);
    tail = NULL;
    head = NULL;
} else {
    tail = tail->prev;
    free(tail->next);
    tail->next = NULL;
}

3. 示例说明

3.1 在头节点处插入

void insert_beginning(int data) {
    struct node *new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data = data;
    new_node->prev = NULL;
    new_node->next = NULL;

    if (head == NULL) {
        head = new_node;
        tail = new_node;
    } else {
        new_node->next = head;
        head->prev = new_node;
        head = new_node;
    } 
}

示例代码中定义了一个insert_beginning函数，该函数的作用是在双向链表头节点处插入一个新节点。如果头节点为空，则让新节点既是头节点也是尾节点；否则让新节点作为头节点，并将原头节点与其连接。

3.2 删除尾节点

void delete_end() {
    if (tail == NULL) {
        return;
    } else if (tail == head) {
        free(tail);
        tail = NULL;
        head = NULL;
    } else {
        tail = tail->prev;
        free(tail->next);
        tail->next = NULL;
    }
}

示例代码定义了一个delete_end函数，它的作用是删除双向链表中的尾节点。函数首先判断链表是否为空，如果是则直接返回。如果尾节点恰好是头节点，则直接删除即可。如果尾节点不是头节点，则先将尾节点的前驱赋值给tail，再删除原尾节点和tail之间的连接即可。

4. 总结

本文介绍了C语言中实现双向链表的数据结构，并讲解了如何在该链表上进行基本操作。同时，本文还提供了两个例子来说明如何在实际应用中使用该链表。希望本文对读者有所帮助。