单链表C语言版

一、单链表的定义

单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。

 程序如下：

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

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

// 创建一个新的链表节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 分配内存
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(0);
    }
    newNode->data = data; // 初始化数据域
    newNode->next = NULL; // 初始化指针域
    return newNode;
}

// 在链表头部插入节点
void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data); // 创建新节点
    newNode->next = *head;            // 新节点指向原链表头部
    *head = newNode;                  // 更新链表头部
}

// 在链表尾部插入节点
void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data); // 创建新节点
    if (*head == NULL) {              // 如果链表为空，直接将新节点作为头部
        *head = newNode;
        return;
    }
    Node* current = *head;
    while (current->next != NULL) { // 遍历到链表尾部
        current = current->next;
    }
    current->next = newNode; // 在尾部插入新节点
}

// 删除链表中的节点
void deleteNode(Node** head, int data) {
    if (*head == NULL) { // 如果链表为空，直接返回
        return;
    }
    Node* temp = *head, *prev = NULL;
    if (temp != NULL && temp->data == data) { // 如果头部节点就是要删除的节点
        *head = temp->next;                   // 更新头部节点
        free(temp);                           // 释放内存
        return;
    }
    while (temp != NULL && temp->data != data) { // 遍历链表找到要删除的节点
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) { // 如果没有找到要删除的节点
        return;
    }
    prev->next = temp->next; // 删除节点
    free(temp);              // 释放内存
}

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

// 销毁链表
void destroyList(Node** head) {
    Node* current = *head;
    Node* next;
    while (current != NULL) {
        next = current->next; // 保存下一个节点的地址
        free(current);        // 释放当前节点
        current = next;       // 移动到下一个节点
    }
    *head = NULL; // 置空链表头指针
}

int main() {
    Node* head = NULL; // 初始化链表头部为空

    // 向链表插入数据
    insertAtHead(&head, 3);
    insertAtHead(&head, 2);
    insertAtHead(&head, 1);
    insertAtTail(&head, 4);

    // 打印链表
    printf("链表内容：");
    printList(head);

    // 删除节点
    deleteNode(&head, 2);

    // 再次打印链表
    printf("删除节点后链表内容：");
    printList(head);

    // 销毁链表
    destroyList(&head);

    return 0;
}

二、单链表的注意点

1.正确理解前驱和后继的关系

一定要把握好前驱和后继之间的关系，只有得到前驱结点才能对后继结点进行操作，因为单链表是逐一相连的，前驱结点的指针域中存放着后继结点的地址，也就是说失去前驱也就意味着丢失后继，所以在对前驱结点的指针域做改动时一定要进行备份，不能让其丢失。

2.结点的插入过程

(1).创建一个结点：结点内存空间的分配、结点数据域的赋值。
(2).将结点插入链表：更改插入结点的指针域(此时指针域内的值来源于前驱结点指针域内的值)、更改前驱结点的指针域(此时指针域内的值为要插入结点的地址)。在插入数据时，一定要先将前驱的指针域的值先赋值给插入结的指针域，然后再更改前驱结点指针域的值，否则会造成后续结点的丢失。

3.结点删除的过程

(1).获取该结点的前驱结点。
(2).备份一份要删除结点的地址。
(3).断开结点与链表的连接：将要删除结点的指针域值赋给它前驱结点的指针域。
(4).释放要删除结点内存：这里就需要利用到备份的删除结点的地址，如果前面没有先对删除结点的地址进行备份，那么经过步骤(3)就会丢失删除结点的地址，将无法释放删除结点的内存空间。