1. 链表分类

区分链表的种类可以从三个方向，是否有头节点、是否是单链表和是否循环。

根据这三个属性可以把链表分为2^3 = 8种。其中无头不循环单链表和有头循环双向链表最常用。

2. 头节点对于链表的作用

根据做题的经验，单链表带头通常可以免去额外判断要处理的节点是头节点的情况。

3.LinkedList.h

#define _CRT_SECURE_NO_WARNINGS

// -------- 无头不循环单向链表 -----------

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#include <assert.h>
#include <string.h>

typedef int LDataType;

typedef struct LinkedListNode {
    LDataType val;
    struct LinkedListNode* next;
} Node;

typedef struct LinkedList {
    Node* head;
} LinkedList;

// 链表初始化
void LinkedListInit(LinkedList* pLS);

// 链表销毁
void LinkedListDestroy(LinkedList* pLS);

// 根据指定的值创建一个链表节点
Node* CreateNode(LDataType val);

// 头插
void LinkedListPushFront(LinkedList* pLS, LDataType val);

// 头删
void LinkedListPopFront(LinkedList* pLS);

// 尾插
void LinkedListPushBack(LinkedList* pLS, LDataType val);

// 尾删
void LinkedListPopBack(LinkedList* pLS);

// 根据给定val查找链表中的节点，查找成功返回节点地址，失败返回NULL
Node* LinkedListFind(LinkedList* pLS, LDataType val);

// 在pos节点后面插入一个值为val的新节点
void LinkedListInsert(Node* pos, LDataType val);

// 删除值为val的节点，如果没有则什么都不干
void LinkedListDelete(LinkedList* pLS, LDataType val);

// 打印全部链表节点
void LinkedListPrint(LinkedList* pLS);

void Test();

4. LinkedList.c

#include "LinkedList.h"

void LinkedListInit(LinkedList* pLS) {
    assert(pLS != NULL);

    pLS->head = NULL;
}

void LinkedListDestroy(LinkedList* pLS) {
    assert(pLS != NULL);

    Node* curr = pLS->head;
    Node* tmp = NULL;

    while (curr != NULL) {
        tmp = curr;
        curr = curr->next;
        free(tmp);
    }

    pLS->head = NULL;
}

Node* CreateNode(LDataType val) {
    Node* res = (Node *)malloc(sizeof(Node));
    if (res == NULL) {
        assert(0);
        return NULL;
    }
    
    res->val = val;
    res->next = NULL;

    return res;
}

void LinkedListPushFront(LinkedList* pLS, LDataType val) {
    assert(pLS != NULL);

    Node* newNode = CreateNode(val);
    newNode->next = pLS->head;
    pLS->head = newNode;
}

void LinkedListPopFront(LinkedList* pLS) {
    assert(pLS != NULL);

    // 如果是空链表
    if (pLS->head == NULL) {
        return;
    }

    // 普通链表
    Node* tmp = pLS->head;
    pLS->head = pLS->head->next;
    free(tmp);
}

void LinkedListPushBack(LinkedList* pLS, LDataType val) {
    assert(pLS != NULL);

    Node* newNode = CreateNode(val);

    // 如果是空链表
    if (pLS->head == NULL) {
        pLS->head = newNode;
        return;
    }

    // 普通链表
    Node* curr = pLS->head;
    while (curr->next != NULL) {
        curr = curr->next;
    }
    curr->next = newNode;
}

void LinkedListPopBack(LinkedList* pLS) {
    assert(pLS != NULL);

    // 如果是空链表
    if (pLS->head == NULL) {
        return;
    }

    // 普通链表
    Node* dummyHead = CreateNode(0);
    dummyHead->next = pLS->head;
    Node* curr = dummyHead;

    while (curr->next->next != NULL) {  // 寻找链表倒数第二个元素
        curr = curr->next;
    }

    Node* tmp = curr->next;
    curr->next = curr->next->next;
    free(tmp);

    pLS->head = dummyHead->next;
}

Node* LinkedListFind(LinkedList* pLS, LDataType val) {
    assert(pLS != NULL);

    Node* curr = pLS->head;
    while (curr != NULL) {
        if (curr->val == val) {
            return curr;
        }
        curr = curr->next;
    }

    return NULL;
}

void LinkedListInsert(Node* pos, LDataType val) {
    assert(pos != NULL);

    Node* newNode = CreateNode(val);
    newNode->next = pos->next;
    pos->next = newNode;
}

void LinkedListDelete(LinkedList* pLS, LDataType val) {
    assert(pLS != NULL);

    // 空链表
    if (pLS->head == NULL) {
        return;
    }

    Node* dummyHead = CreateNode(0);
    dummyHead->next = pLS->head;
    Node* curr = dummyHead;

    while (curr->next != NULL && curr->next->val != val) {
        curr = curr->next;
    }
    
    if (curr->next != NULL) {
        Node* tmp = curr->next;
        curr->next = curr->next->next;
        free(tmp);
    }

    pLS->head = dummyHead->next;
}

void LinkedListPrint(LinkedList* pLS) {
    assert(pLS != NULL);

    Node* curr = pLS->head;
    while (curr != NULL) {
        printf("%d -> ", curr->val);
        curr = curr->next;
    }
    printf("NULL\n");
}

void Test() {
    LinkedList ls;
    LinkedListInit(&ls);

    LinkedListPushFront(&ls, 1);
    LinkedListPushFront(&ls, 2);
    LinkedListPushFront(&ls, 3);
    LinkedListPushFront(&ls, 4);
    LinkedListPushFront(&ls, 5);
    LinkedListPrint(&ls);

    LinkedListPopFront(&ls);
    LinkedListPopFront(&ls);
    LinkedListPrint(&ls);

    LinkedListPushBack(&ls, 0);
    LinkedListPushBack(&ls, -1);
    LinkedListPrint(&ls);

    LinkedListPopBack(&ls);
    LinkedListPrint(&ls);

    Node* res = LinkedListFind(&ls, 3);
    if(res)
        printf("%d\n", res->val);

    LinkedListDelete(&ls, 3);
    LinkedListPrint(&ls);
}

5. main.c

#include "LinkedList.h"

int main() {
    Test();

    system("pause");
    return 0;
}