C语言数据结构 双向链表的建立与基本操作

双向链表的定义

双向链表是一种常见的线性数据结构，它由多个结点组成，每个结点有两个指针，一个指向前一个结点，一个指向后一个结点。对于一个双向链表，我们可以获得其第一个结点和最后一个结点的指针，也可以沿着链表从前往后或从后往前遍历链表的每个结点。

双向链表的建立

我们首先需要定义一个双向链表的结点类型，包括两个指针，一个表示前一个结点，一个表示后一个结点。如下所示：

typedef struct node {
    int data;
    struct node *prev;  // 指向前一个结点
    struct node *next;  // 指向后一个结点
} Node;

然后，我们可以声明一个头结点，作为链表的头部，方便插入和删除操作。头结点不存储数据，只是一个指针类型的变量，其 prev 指针和 next 指针都指向 NULL，如下所示：

Node *head = (Node *)malloc(sizeof(Node));
head->prev = NULL;
head->next = NULL;

上述操作会创建一个空的双向链表，头结点为 head。

接下来，我们可以通过插入操作，逐个将结点插入到链表中，从而创建出一个完整的双向链表。在插入操作中，需要注意后继结点的指针应该指向新插入的结点，前驱结点的指针应该指向新插入的结点，新插入的结点的前驱结点指针应该指向前驱结点。

双向链表的基本操作

插入操作

双向链表的插入操作与单链表的插入操作类似，需要指定插入的位置和插入的值。如果插入的位置是链表的头部，则需要修改头结点的 next 指针，如果插入的位置是链表的中间或尾部，则需要修改插入结点前驱结点和后继结点的指针。代码示例如下：

void insert(Node *head, int pos, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    Node *p = head;

    for (int i = 0; i < pos && p != NULL; i++) {
        p = p->next;
    }

    if (p == NULL) {
        return;  // 位置错误，不插入结点
    }

    newNode->prev = p->prev;
    newNode->next = p;
    p->prev->next = newNode;
    p->prev = newNode;
}

删除操作

双向链表的删除操作与插入操作类似，同样需要指定删除的位置。删除操作需要修改删除结点前驱结点和后继结点的指针，代码示例如下：

void delete(Node *head, int pos) {
    Node *p = head;

    for (int i = 0; i < pos && p != NULL; i++) {
        p = p->next;
    }

    if (p == NULL) {
        return;  // 位置错误，不删除结点
    }

    p->prev->next = p->next;
    p->next->prev = p->prev;
    free(p);
}

遍历操作

双向链表的遍历操作可以从头结点开始遍历，依次访问每一个结点，并将其数据打印出来。代码示例如下：

void traverse(Node *head) {
    Node *p = head->next;

    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
}

示例说明

示例一

以下代码演示如何构建一个双向链表，插入若干数据并从头到尾输出链表：

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

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

void insert(Node *head, int pos, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    Node *p = head;

    for (int i = 0; i < pos && p != NULL; i++) {
        p = p->next;
    }

    if (p == NULL) {
        return;  // 位置错误，不插入结点
    }

    newNode->prev = p->prev;
    newNode->next = p;
    p->prev->next = newNode;
    p->prev = newNode;
}

void traverse(Node *head) {
    Node *p = head->next;

    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
}

int main() {
    Node *head = (Node *)malloc(sizeof(Node));
    head->prev = NULL;
    head->next = NULL;

    insert(head, 0, 1);
    insert(head, 1, 2);
    insert(head, 2, 3);
    insert(head, 3, 4);

    traverse(head);
    return 0;
}

上述代码将输出：1 2 3 4

示例二

以下代码演示如何构建一个双向链表，删除链表中的某个结点并从头到尾输出链表：

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

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

void delete(Node *head, int pos) {
    Node *p = head;

    for (int i = 0; i < pos && p != NULL; i++) {
        p = p->next;
    }

    if (p == NULL) {
        return;  // 位置错误，不删除结点
    }

    p->prev->next = p->next;
    p->next->prev = p->prev;
    free(p);
}

void traverse(Node *head) {
    Node *p = head->next;

    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
}

int main() {
    Node *head = (Node *)malloc(sizeof(Node));
    head->prev = NULL;
    head->next = NULL;

    Node *node1 = (Node *)malloc(sizeof(Node));
    node1->data = 1;
    head->next = node1;
    node1->prev = head;
    node1->next = NULL;

    Node *node2 = (Node *)malloc(sizeof(Node));
    node2->data = 2;
    node1->next = node2;
    node2->prev = node1;
    node2->next = NULL;

    Node *node3 = (Node *)malloc(sizeof(Node));
    node3->data = 3;
    node2->next = node3;
    node3->prev = node2;
    node3->next = NULL;

    delete(head, 2);

    traverse(head);
    return 0;
}

上述代码将输出：1 2