C语言一篇精通链表的各种操作

C 语言精通链表操作攻略

简介

链表是一种常用的数据结构，它相对于数组等数据结构来说，具有更高的灵活性和增删操作的效率。在 C 语言中，我们可以用指针来实现链表，这也是指针与动态内存分配的重要应用之一。本文将提供在 C 语言中精通链表操作的攻略，包括链表的创建、添加、删除、搜索、遍历等常用操作。

基本结构体定义

链表一般由结构体和指针构成，下面我们定义一个链表结构体节点：

struct ListNode {
    int val;
    struct ListNode* next;
};

其中，val 表示节点中存储的值，next 表示下一个节点的指针。为了方便后续的实现，我们还定义一个指向链表开头的指针：

typedef struct ListNode* LinkedList;

创建链表

首先，我们需要创建一个空链表。因为链表的第一个节点没有前驱节点，所以需要特别处理一下：

LinkedList createLinkedList() {
    LinkedList head = (LinkedList)malloc(sizeof(struct ListNode));
    head->next = NULL;
    return head;
}

手动添加节点

接下来，我们手动向链表中添加几个节点：

LinkedList head = createLinkedList();
LinkedList p = (LinkedList)malloc(sizeof(struct ListNode));
p->val = 1;
p->next = NULL;
head->next = p;

LinkedList q = (LinkedList)malloc(sizeof(struct ListNode));
q->val = 2;
q->next = NULL;
p->next = q;

这样就创建了一个有两个节点的链表。

添加节点

在链表结尾处添加一个节点

为了在链表结尾处添加一个节点，我们需要先找到链表的最后一个节点，即 next 指针为NULL的节点。然后在此节点之后，添加新的节点即可：

void addAtTail(LinkedList head, int val) {
    // 找到最后一个节点
    LinkedList p = head;
    while (p->next) {
        p = p->next;
    }

    // 在最后一个节点之后添加新的节点
    LinkedList newNode = (LinkedList)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    p->next = newNode;
}

在链表头部添加一个节点

在链表头部添加节点与在链表尾部添加节点相似，只是我们需要让新节点指向原来的头节点，然后将新节点作为新的头节点即可：

void addAtHead(LinkedList head, int val) {
    LinkedList newNode = (LinkedList)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = head->next;
    head->next = newNode;
}

在链表中间添加一个节点

为了在链表的中间位置添加一个节点，我们需要先找到要插入的位置，移动指针即可：

void addAtIndex(LinkedList head, int index, int val) {
    // 链表头结点为第0个元素
    if (index <= 0) {
        addAtHead(head, val);
        return;
    }

    // 找到要插入节点的前驱节点
    LinkedList p = head;
    for (int i = 0; i < index - 1; i++) {
        p = p->next;
        if (p == NULL) {
            return; // index 超出链表范围
        }
    }

    LinkedList newNode = (LinkedList)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = p->next;
    p->next = newNode;
}

删除节点

删除指定节点

为了删除指定的节点，我们需要先找到这个节点的前驱节点，然后将前驱节点的 next 指针，指向要删除节点的后继节点即可：

void deleteNode(LinkedList head, int val) {
    LinkedList p = head;
    while (p->next != NULL && p->next->val != val) {
        p = p->next;
    }
    if (p->next == NULL) {
        return; // 没有节点包含val值
    }

    LinkedList temp = p->next;
    p->next = temp->next;
    free(temp);
}

删除指定下标的节点

为了删除指定下标的节点，我们需要先找到要删除节点的前驱节点：

void deleteAtIndex(LinkedList head, int index) {
    // 链表头结点为第0个元素
    if (index < 0) {
        return;
    }

    LinkedList p = head;
    for (int i = 0; i < index; i++) {
        p = p->next;
        if (p == NULL) {
            return; // index 超出链表范围
        }
    }

    LinkedList temp = p->next;
    if (temp == NULL) {
        return; // index 超出链表范围
    }

    p->next = temp->next;
    free(temp);
}

搜索节点

为了搜索指定值的节点，我们只需要遍历整个链表，直到找到一个值为指定值，或者链表遍历结束：

LinkedList searchLinkedList(LinkedList head, int val) {
    LinkedList p = head->next;
    while (p != NULL && p->val != val) {
        p = p->next;
    }
    return p;
}

遍历节点

遍历节点是链表的最常见操作之一，我们可以用循环来遍历整个链表：

void traverseLinkedList(LinkedList head) {
    LinkedList p = head->next;
    while (p != NULL) {
        printf("%d ", p->val);
        p = p->next;
    }
}

示例运行

下面是这些链表操作的完整代码和使用示例：

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

struct ListNode {
    int val;
    struct ListNode* next;
};

typedef struct ListNode* LinkedList;

LinkedList createLinkedList() {
    LinkedList head = (LinkedList)malloc(sizeof(struct ListNode));
    head->next = NULL;
    return head;
}

void addAtTail(LinkedList head, int val) {
    LinkedList p = head;
    while (p->next) {
        p = p->next;
    }

    LinkedList newNode = (LinkedList)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    p->next = newNode;
}

void addAtHead(LinkedList head, int val) {
    LinkedList newNode = (LinkedList)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = head->next;
    head->next = newNode;
}

void addAtIndex(LinkedList head, int index, int val) {
    if (index <= 0) {
        addAtHead(head, val);
        return;
    }

    LinkedList p = head;
    for (int i = 0; i < index - 1; i++) {
        p = p->next;
        if (p == NULL) {
            return;
        }
    }

    LinkedList newNode = (LinkedList)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = p->next;
    p->next = newNode;
}

void deleteNode(LinkedList head, int val) {
    LinkedList p = head;
    while (p->next != NULL && p->next->val != val) {
        p = p->next;
    }
    if (p->next == NULL) {
        return;
    }

    LinkedList temp = p->next;
    p->next = temp->next;
    free(temp);
}

void deleteAtIndex(LinkedList head, int index) {
    if (index < 0) {
        return;
    }

    LinkedList p = head;
    for (int i = 0; i < index; i++) {
        p = p->next;
        if (p == NULL) {
            return;
        }
    }

    LinkedList temp = p->next;
    if (temp == NULL) {
        return;
    }

    p->next = temp->next;
    free(temp);
}

LinkedList searchLinkedList(LinkedList head, int val) {
    LinkedList p = head->next;
    while (p != NULL && p->val != val) {
        p = p->next;
    }
    return p;
}

void traverseLinkedList(LinkedList head) {
    LinkedList p = head->next;
    while (p != NULL) {
        printf("%d ", p->val);
        p = p->next;
    }
}

int main() {
    LinkedList head = createLinkedList();
    addAtHead(head, 5);
    addAtTail(head, 6);
    addAtIndex(head, 1, 4);
    deleteAtIndex(head, 1);
    LinkedList p = searchLinkedList(head, 5);
    printf("5 是否在链表中：");
    if (p) {
        printf("是");
    } else {
        printf("否");
    }
    printf("\n链表：");
    traverseLinkedList(head);
    printf("\n");

    return 0;
}

输出结果为：5 是否在链表中：是 链表：5 6