结构特点

链表是一种线性的储存数据的方法，与数组不同，它的特点是储存数据的空间是不连续的。因此数组可以直接通过如a[n]获取第n项内容，而链表则无法简单地这样获取数据内容。

常见的单向链表的图示结构如下：

常见的链表声明方法是结构体数组，每一项中含有当前项的内容data以及指向下一个项的指针next。如下给出了一个用链表存储学生信息的示例结构体：

struct studnode {
	int num;
	char name[20];
	int score;
	struct studnode* next;
};

可以看出对于每个链表的节点，它包含有当前节点的所有内容，同时可以通过->next访问下一个节点。节点（结构体）是链表的最小成员单位，而其中的成员是链表储存数据和连接形成完整储存的关键。

常见操作

单向链表的操作围绕 “节点引用的修改” 展开，核心是避免断链。以下为了方便演示，指针结构体为如下代码：

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

创建节点

创建节点的关键在于使用malloc进行动态内存分配，并且强制将返回的void*指针转换为结构体指针。示例代码如下：

struct ListNode* createNode(int value) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = value;
    newNode->next = NULL;
    return newNode;
}

初始化时，我们习惯将节点的下一个元素指向空。而显然，不会有原有的节点的下一个元素指向这个新节点，因此这个新节点在初始化后是一个游离在原链表之外的节点。

头插法

因此，可以按照上面思路写出如下代码：

struct ListNode* insertAtHead(struct ListNode* head, int value) {
    struct ListNode* newNode = createNode(value);
    newNode->next = head;
    head = newNode;
    return head;
}

在上述代码中，我们首先创建了一个新节点，然后将新节点的后一项指向原头，把该新节点作为新的头。

尾插法

下图演示了三次尾插法的过程：

通常来说，我们有两种实现尾插法的方法，第一种是给出头尾指针：

Node* insertAtTail(Node* head, Node** tail, int data) {
    Node* newNode = createNode(data);
    if (head == NULL) {
        head = newNode;
        *tail = newNode;
    } else {
        (*tail)->next = newNode;
        *tail = newNode;
    }
    return head;
}

在上述代码中，我们首先创建了一个新节点，然后将原尾节点的后一项指向新节点，把该新节点作为新的尾。注意尾指针需要用引用的方式传入，因为它的值需要被修改。

第二种则是只给出头指针，通过遍历寻找尾指针：

Node* insertAtTail2(Node* head, int data) {
    Node* newNode = createNode(data);
    Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
    return head;
}

由于整体代码中不维护尾指针，因此也就不用对尾指针赋值。

中插法

看懂上方的头插法和尾插法后，理解中插法应当是相当轻松的，下面给出两种不同的代码：

Node* insertAfterValue(Node* head, int targetValue, int newValue) {
    Node* current = head;
    while (current != NULL && current->data != targetValue) {
        current = current->next;
    }
    
    Node* newNode = createNode(newValue);
    newNode->next = current->next;
    current->next = newNode;
    return head;
}

Node* insertBeforeValue(Node* head, int targetValue, int newValue) {
    Node* current = head;
    while (current != NULL && current->next != NULL && current->next->data != targetValue) {
        current = current->next;
    }

    Node* newNode = createNode(newValue);
    newNode->next = current->next;
    current->next = newNode;
    return head;
}

需要注意，上述第二段代码未对插入节点为头结点的情况做额外兼容。

删除节点

重点操作时对前驱节点的处理，使得其直接跳过要删除的节点。示例代码如下：

Node* deleteByValue(Node* head, int value, int* success) {
    *success = 0;
    if (head->data == value) {
        Node* temp = head;
        head = head->next;
        printf("删除值为 %d 的节点（头节点）\n", value);
        free(temp);
        *success = true;
        return head;
    }
    Node* current = head;
    Node* prev = NULL;
    while (current != NULL && current->data != value) {
        prev = current;
        current = current->next;
    }
    prev->next = current->next;
    printf("删除值为 %d 的节点\n", value);
    free(current);
    *success = 1;
    return head;
}

总结

链表在做题时要善用画图的操作，通过画图构建出链表的连接关系，进一步搞清楚如何进行操作。