学习思路

所谓单链表实际上就是通过指针将多个不同不连续的节点链接起来，每个节点都存储着不同的值，很多人在学习的过程中容易搞混指针和节点之间的关系，实际上只要记住一点：没有被分配空间的指针就不能算是节点， 指针可以改变节点的指向，也可以改变节点的值，也可以通过循环在多个节点之间游走，但是它没有被 new 分配空间，那么就永远不是节点

给指针分配空间：

这是一个结构体指针
struct node *head;

给指针分配空间
head = new struct node; 

创建另一个结构体指针
struct node *p;

另一个指针指向head所维护的那块内存
p = head;


当指针被分配空间后它就成为了一个节点，可以通过head->data = 1 的方式给节点赋值，也可以创建另一个指针指向这个节点，当另一个指针指向这个节点并不是指向这个head指针本身，而是指向head指针所分配的那块空间，
也可以理解为共同指向head指针所指向的节点

指针向后移动，p->next 代表当前节点所保存的下一个节点的地址，p = p->next 代表指针p移动到下一个节点
p = p->next;

代码:

#include <iostream>
using namespace std;
typedef struct Node
{
    int data;
    // struct Node *prior; //加入这条语句即可把单链表变成双链表
    struct Node *next;
} * Link, Node;
Link createNode(int a[], int n) //头插法,最后得到的链表的数据顺序与数组是相反的
{
    Link head = new Node;
    head->next = NULL;
    for (int i = 0; i < n; ++i)
    {
        Link node = new Node;
        //每次都是在head的后面新增一个节点,而不是在新增节点的后面,所以最后得到的链表顺序与数组是相反的
        node->data = a[i];

        // node节点的指针域指向head的指针域,而head的指针域为NULL,也就是node的指针域指向NULL
        node->next = head->next;

        //最后当node的指针域指向NULL后,将head的指针域与NULL的链接断开,指向新的节点,这样既完成了头部插入
        head->next = node;
    }
    return head;
}
Link newList(int a[], int n) //尾插法,最后得到的链表顺序与数组一致
{
    //创建头节点
    Link head = new Node;
    head->next = NULL;

    //创建一个新的指针指向头节点
    Link rear = head;
    for (int i = 0; i < n; ++i)
    {
        Link node = new Node;
        node->data = a[i];
        // node->next = NULL; //如果没有写这条语句,那么就要在最后面补上rear->next = NULL;

        //将新的指针的指针域指向新的节点,而新的指针原本指向的是head头节点,也就是让head头节点的指针域指向新的节点
        rear->next = node;

        //最后让新的指针指向新的节点,这样就完成了插入
        rear = node;
    }

    //如果插入到最后没有数据了,将新的指针的指针域指向NULL,而新的指针这时指向的一定是最后一个新的节点,也就是让最后一个新的节点的指针域指向NULL
    rear->next = NULL;

    // rear->next = head; //将上面的语句替换为这条语句即可将链表变成循环链表,对应的要将循环判断条件变成：p!=head,p->next!=head
    return head;
}
bool insertNode(Link head, int i, int x) //插入节点
{
    Link p = head;
    int j = 0;
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL)
    {
        return false;
    }
    //创建一个新的节点
    Link node = new Node;
    node->data = x;

    //让新节点的指针域指向p的指针域,而p的指针域保存的是后一个节点的地址,也就是等于让新节点的指针域指向后一个节点
    node->next = p->next;

    //然后当新节点的指针域指向后一个节点后,让p的指针域和后一个节点的链接断开,指向新节点,这样既完成了插入
    p->next = node;
    return true;
}
bool deleteNode(Link head, int x) //删除节点
{
    //如果传入的是一个空表,或者只有一个头节点,就直接返回false
    if (head == NULL || head->next == NULL)
    {
        return false;
    }

    //创建两个指针p和q,p指向的是头节点的下一个节点,q指向的是头节点,q永远指向p的前一个节点,p永远指向q的下一个节点
    Link p = head->next, q = head;

    //如果p不为空就一直往下查找
    while (NULL != p)
    {
        //如果p的数据域等于x就代表找到了
        if (p->data == x)
        {
            //将q的指针域指向p的指针域,而p的指针域指向的是下一个节点,也就是将q的指针域指向p的下一个节点,这样的话p的前一个节点与p指向的节点的链接就断掉了
            q->next = p->next;

            //然后释放p所指向的节点
            delete p;

            //这样便成功删除了一个节点
            return true;
        }
        else
        {
            //如果没有查找到,则q指向p所在的节点,而p所在的节点是q原本指向的节点的下一个节点,这样便实现了q一直随着p往后移动
            q = p;
            // p重新指向下一个节点
            p = p->next;
        }
    }
    //如果都没有找到则说明链表中没有x这个节点,返回false
    return false;
}
void printNode(Link head) //打印链表
{
    Link p = head->next;
    while (NULL != p)
    {
        cout << p->data << " ";
        p = p->next;
    }
    puts("");
}
void clearLink(Link head) //释放链表
{
    //如果head不为空,也就是head指向的不是最后一个节点的后一个节点
    while (NULL != head)
    {
        //新建一个节点q指向head所在的节点
        Link q = head;

        // head往后移动一位
        head = head->next;

        //删除q指向的节点,而q指向的节点是原本head指向的节点,也就是删除head原本指向的节点
        delete q;
    }
}
int main()
{
    int n;
    int a[101];
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]);
    }
    // Link p = createNode(a, n); //头插法
    Link p = newList(a, n);
    insertNode(p, 2, 10);
    deleteNode(p, 10);
    printNode(p);
    clearLink(p);
    printNode(p);
    return 0;
}