数据结构双向链表c++

双向链表是一种常见的数据结构，与单向链表相比，它每个节点都有两个指针，分别指向前驱节点和后继节点。这样，双向链表可以实现双向遍历，插入和删除操作也更加方便。

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

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

// 双向链表节点结构体
typedef struct ListNode {
    int val;
    struct ListNode *prev;
    struct ListNode *next;
} ListNode;

// 创建双向链表节点
ListNode *createNode(int val) {
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->val = val;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 插入节点到双向链表头部
ListNode *insertAtHead(ListNode *head, int val) {
    ListNode *node = createNode(val);
    if (head == NULL) {
        head = node;
    } else {
        node->next = head;
        head->prev = node;
        head = node;
    }
    return head;
}

// 插入节点到双向链表尾部
ListNode *insertAtTail(ListNode *head, int val) {
    ListNode *node = createNode(val);
    if (head == NULL) {
        head = node;
    } else {
        ListNode *cur = head;
        while (cur->next != NULL) {
            cur = cur->next;
        }
        cur->next = node;
        node->prev = cur;
    }
    return head;
}

// 删除双向链表中的节点
ListNode *deleteNode(ListNode *head, int val) {
    if (head == NULL) {
        return NULL;
    }
    ListNode *cur = head;
    while (cur != NULL && cur->val != val) {
        cur = cur->next;
    }
    if (cur == NULL) {
        return head;
    }
    if (cur == head) {
        head = head->next;
        if (head != NULL) {
            head->prev = NULL;
        }
    } else {
        cur->prev->next = cur->next;
        if (cur->next != NULL) {
            cur->next->prev = cur->prev;
        }
    }
    free(cur);
    return head;
}

// 打印双向链表
void printList(ListNode *head) {
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

// 主函数
int main() {
    ListNode *head = NULL;
    head = insertAtHead(head, 1);
    head = insertAtHead(head, 2);
    head = insertAtTail(head, 3);
    printList(head);  // 2 1 3
    head = deleteNode(head, 2);
    printList(head);  // 1 3
    head = deleteNode(head, 3);
    printList(head);  // 1
    head = deleteNode(head, 1);
    printList(head);  // 
    return 0;
}