C语言-单链表和双链表

C语言-单链表和双链表

单链表

// 定义单链表结点结构体
typedef struct Node {
    int data; // 数据域
    struct Node* next; // 指针域，指向下一个结点
} ListNode;

// 创建新结点
ListNode* createNode(int data) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (!newNode) {
        printf("内存分配失败！\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在链表末尾插入新结点
void insertNode(ListNode** head, int data) {
    ListNode* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        ListNode* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// 生活案例：
// 假设单链表模拟一条公交线路的各个站牌顺序，每个站牌（节点）只知道下一站（next指针），乘客只能按照规定的路线依次前进。

### 双链表

```c
// 定义双链表结点结构体
typedef struct Node {
    int data;
    struct Node* prev; // 新增的指向前一个结点的指针域
    struct Node* next;
} DListNode;

// 创建新结点
DListNode* createDNode(int data) {
    DListNode* newNode = (DListNode*)malloc(sizeof(DListNode));
    if (!newNode) {
        printf("内存分配失败！\n");
        return NULL;
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// 在链表末尾插入新结点
void insertDNode(DListNode** head, int data) {
    DListNode* newNode = createDNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        DListNode* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

// 生活案例：
// 双链表可以模拟一条双向通行的道路，每个路口（节点）不仅知道自己前方通往哪个路口（next指针），还知道后方连接哪个路口（prev指针），车辆可以根据道路标志自由选择前进或倒退方向。