C语言 超详细模拟实现单链表的基本操作建议收藏

前言

单链表是C语言数据结构中十分基础的一种。以下是单链表的定义：

typedef struct Node {
    int val;
    struct Node *next;
} Node, *LinkedList;

其中，Node 表示单链表中的一个节点，包括 val 和指向下一个节点的指针 next。而 LinkedList 则是指向单链表第一个节点的指针。

基本操作

1. 初始化单链表

初始化单链表，可以简单地将 LinkedList 指针赋值为 NULL：

LinkedList initList() {
    LinkedList head = NULL;
    return head;
}

2. 判断单链表是否为空

首先判断单链表的头节点是否为空，即指向的节点是否为 NULL：

int isEmpty(LinkedList head) {
    if(head == NULL) {
        return 1;
    } else {
        return 0;
    }
}

3. 获取单链表长度

从头节点开始遍历单链表，每遍历一个节点计数器加1，直到遍历到链表尾节点为止：

int length(LinkedList head) {
    int len = 0;
    Node *p = head;
    while(p != NULL) {
        len++;
        p = p->next;
    }
    return len;
}

4. 遍历单链表

从头节点开始遍历单链表，输出所有节点的 val 值：

void traverseList(LinkedList head) {
    Node *p = head;
    while(p != NULL) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
}

5. 在单链表末尾插入节点

从头节点开始遍历单链表，找到链表尾节点，将其指针指向新节点：

LinkedList insertAtTail(LinkedList head, int val) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->val = val;
    newNode->next = NULL;
    if(head == NULL) {
        head = newNode;
    } else {
        Node *p = head;
        while(p->next != NULL) {
            p = p->next;
        }
        p->next = newNode;
    }
    return head;
}

6. 在单链表指定位置插入节点

从头节点开始遍历单链表，找到指定位置的前驱节点，将其指针指向新节点，将新节点指针指向后继节点：

LinkedList insertAtIndex(LinkedList head, int index, int val) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->val = val;
    newNode->next = NULL;
    if(head == NULL && index != 1) {
        printf("Error: Invalid Index\n");
        return NULL;
    } else if(index == 1) {
        newNode->next = head;
        head = newNode;
    } else {
        int i = 1;
        Node *p = head;
        while(i < index - 1 && p != NULL) {
            p = p->next;
            i++;
        }
        if(p == NULL) {
            printf("Error: Invalid Index\n");
            return NULL;
        }
        newNode->next = p->next;
        p->next = newNode;
    }
    return head;
}

7. 在单链表中删除节点

从头节点开始遍历单链表，找到指定节点的前驱节点，将其指针指向后继节点，将该节点从内存中删除：

LinkedList deleteNode(LinkedList head, int val) {
    if(head == NULL) {
        printf("Error: List is Empty\n");
        return NULL;
    }
    Node *p = head;
    Node *pre = NULL;
    while(p != NULL && p->val != val) {
        pre = p;
        p = p->next;
    }
    if(p == NULL) {
        printf("Error: No Element Found\n");
    } else if(pre == NULL) {
        head = p->next;
        free(p);
    } else {
        pre->next = p->next;
        free(p);
    }
    return head;
}

示例说明

示例1

int main() {
    LinkedList head = initList();
    head = insertAtTail(head, 1);
    head = insertAtTail(head, 2);
    head = insertAtTail(head, 3);
    head = insertAtTail(head, 4);
    head = insertAtIndex(head, 2, 5);
    head = deleteNode(head, 3);
    traverseList(head);
    return 0;
}

输出：

1 5 2 4

示例2

int main() {
    LinkedList head = initList();
    printf("%d\n", isEmpty(head));
    head = insertAtTail(head, 1);
    head = insertAtTail(head, 2);
    printf("%d\n", length(head));
    traverseList(head);
    head = deleteNode(head, 3);
    head = deleteNode(head, 2);
    head = deleteNode(head, 1);
    printf("%d\n", isEmpty(head));
    traverseList(head);
    return 0;
}

输出：

1
2
1 2
Error: No Element Found
Error: No Element Found
1