双向链表

双向链表是一种常见的数据结构，每个节点都有指向前一个节点和后一个节点的指针，可以双向遍历整个链表。

下面的代码定义了一个双向链表的结构体 node，其中包含了一个 prev 指针和一个 next 指针，表示前一个节点和后一个节点。head 和 tail 分别表示双向链表的头和尾。

双向链表的插入操作可以分为头部插入和尾部插入。

在头部插入时，先创建一个新的节点，然后将它的 next 指向当前头节点，将当前头节点的 prev 指向新节点。
在尾部插入时，先创建一个新的节点，然后将它的 prev 指向当前尾节点，将当前尾节点的 next 指向新节点。

最后，通过遍历整个链表并输出节点的数据，来验证双向链表的正确性。以下是C语言实现双向链表的示例代码：

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

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

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

void insertAtBeginning(int data) {
    struct node *newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = head;
    if (head != NULL) {
        head->prev = newNode;
    } else {
        tail = newNode;
    }
    head = newNode;
}

void insertAtEnd(int data) {
    struct node *newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = tail;
    if (tail != NULL) {
        tail->next = newNode;
    } else {
        head = newNode;
    }
    tail = newNode;
}

void printList() {
    struct node *current = head;
    printf("List: ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    insertAtBeginning(3);
    insertAtBeginning(2);
    insertAtBeginning(1);
    insertAtEnd(4);
    insertAtEnd(5);
    printList();
    return 0;
}