数据结构双向链表c++

以下是双向链表的C语言实现：

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

// 定义双向链表节点结构体
typedef struct Node {
    int data; // 数据域
    struct Node *prev; // 指向前驱节点的指针
    struct Node *next; // 指向后继节点的指针
} Node;

// 创建双向链表
Node *createList(int arr[], int n) {
    Node *head = (Node *)malloc(sizeof(Node)); // 创建头节点
    head->prev = NULL;
    head->next = NULL;
    Node *tail = head; // 尾指针指向头节点

    for (int i = 0; i < n; i++) {
        Node *node = (Node *)malloc(sizeof(Node)); // 创建新节点
        node->data = arr[i];
        node->prev = tail; // 新节点的前驱指向尾指针
        node->next = NULL; // 新节点的后继指向空
        tail->next = node; // 尾指针的后继指向新节点
        tail = node; // 尾指针指向新节点
    }

    return head;
}

// 遍历双向链表
void traverseList(Node *head) {
    Node *p = head->next; // 指向第一个节点
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 在双向链表的第i个位置插入元素
void insertList(Node *head, int i, int x) {
    Node *p = head;
    for (int j = 0; j < i-1; j++) { // 移动到要插入节点的前一个节点
        p = p->next;
    }

    Node *node = (Node *)malloc(sizeof(Node)); // 创建新节点
    node->data = x;
    node->prev = p; // 新节点的前驱指向p
    node->next = p->next; // 新节点的后继指向p的后继
    if (p->next != NULL) { // 如果p后面还有节点
        p->next->prev = node; // p后面节点的前驱指向新节点
    }
    p->next = node; // p的后继指向新节点
}

// 删除双向链表的第i个节点
void deleteList(Node *head, int i) {
    Node *p = head;
    for (int j = 0; j < i-1; j++) { // 移动到要删除节点的前一个节点
        p = p->next;
    }

    Node *q = p->next; // 要删除的节点
    p->next = q->next; // p的后继指向q的后继
    if (q->next != NULL) { // 如果q后面还有节点
        q->next->prev = p; // q后面节点的前驱指向p
    }
    free(q); // 释放q节点的空间
}

// 反转双向链表
void reverseList(Node *head) {
    Node *p = head->next; // 指向第一个节点
    while (p != NULL) {
        Node *temp = p->prev; // 交换p的前驱和后继
        p->prev = p->next;
        p->next = temp;
        p = p->prev; // 移动到下一个节点
    }
    // 反转完成后，尾节点变为头节点，头节点变为尾节点
    Node *temp = head->prev;
    head->prev = head->next;
    head->next = temp;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    Node *head = createList(arr, n);
    printf("原始链表：");
    traverseList(head);

    insertList(head, 3, 6);
    printf("插入元素后的链表：");
    traverseList(head);

    deleteList(head, 4);
    printf("删除元素后的链表：");
    traverseList(head);

    reverseList(head);
    printf("反转链表后：");
    traverseList(head);

    return 0;
}