C语言——链表

大神文献：https://blog.csdn.net/weixin_73588765/article/details/128356985

一、链表概念

1. 什么是链表？

1.1 链表的构成

2. 链表和数组的区别

数组的特点：

链表的特点：

二者对比：

二、链表静态添加和遍历

三、统计链表节点个数、链表查询及修改节点

四、在指定节点插入新的节点

1.在指定节点后插入新的节点

2.在指定节点的前方插入新节点

1.第一个节点之前插入新的节点；

2.在中间的节点插入新的节点；

完整代码：

五、删除指定节点

1.删除第一个节点

2.删除中间的节点

完整代码：

六、动态创建节点

头插法

尾插法

一、链表概念

1. 什么是链表？

链表是一种数据结构，是一种数据存放的思想；

链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。

1.1 链表的构成

构成：链表由一个个结点组成，每个结点包含两个部分：数据域和指针域。

数据域（data field）：每个结点中存储的数据。
指针域（pointer field）：每个结点中存储下一个结点的地址。

2. 链表和数组的区别

数组的特点：

数组中的每一个元素都属于同一数据类型的；
数组是一组有序数据的集合；
数组是在内存中开辟一段连续的地址空间用来存放一组数据，可以用数组名加下标来访问数组中的元素；

链表的特点：

动态地进行存储分配的一种结构；
链表中的各节点在内存中的地址都是不连续的；
链表是由一个个节点组成，像一条链子一样；
链表中的节点一般包括两个部分：（1）用户要用的数据（2）下一个节点的地址；

二者对比：

一个数组只能存放同一种类型的数据，而链表中就可以存放不同的数据类型；
数组中的元素地址是连续的，想删除或添加一个新的元素，十分的麻烦不灵活，而且用数组存放数据是都要先定义好数组的大小(即元素的个数)，如果在定义数组时，定义小了，内存不够用，定义大了，显然会浪费内存；

链表就可以很好的解决这些问题，链表中每一项都是一个结构体，链表中各节点在内存中的地址可以是不连续的，所以你想删除或添加一个新的节点很简单和方便，直接把节点中存放的的地址拿去修改就ok了(具体怎么添加或删除放在后用代码详细讲)。因为链表是一种动态结构，所以链表在建立的时候并不用像数组一样需要提前定义大小和位置(具体怎么创建也放在后面用代码详细讲)。

二、链表静态添加和遍历

思路：

静态创建的链表节点，都是不同内存地址，是不连续的。

所以我们要在每个节点的指针域中，存储下一个节点的地址，如上图：

节点 1 的next（指针域），存储的是节点 2 的地址
节点 2 的next（指针域），存储的是节点 3 的地址
节点 3 的next（指针域），存储的是节点 4 的地址
节点 4 的next（指针域），存储的是节点 5 的地址

通过这样的操作，就可以把这 5 个节点连接在一起。

#include <stdio.h>

struct Test
{
    int data;
    struct Test *next;
};

// 打印链表（遍历链表）
void printfLink(struct Test *p) // 当前 p 存储的是 t1 的地址，也就是链表头
{
    while ( p != NULL ) // p 现是链表头节点，通过循环移动到下一个节点，直到 NULL 
    {
        printf("%d ",p->data); // 输出当前节点的 data 值
        p = p->next; // 使 p 移动至下一个节点
    }
    putchar('\n');
}

int main()
{
    // 创建节点
    struct Test t1 = {1, NULL}; // t1.data赋值为1，t1.next赋值为NULL
    struct Test t2 = {2, NULL};
    struct Test t3 = {3, NULL};
    struct Test t4 = {4, NULL};
    struct Test t5 = {5, NULL};

    // 链接节点
    t1.next = &t2; // t1.next存储t2的地址，使t1.next指向t2这个结构体变量
    t2.next = &t3;
    t3.next = &t4;
    t4.next = &t5;

    // 打印链表
    printfLink(&t1); // 将 t1（链表头）的地址传递给printfLink函数的结构体指针变量 p

    return 0;
}

三、统计链表节点个数、链表查询及修改节点

#include <stdio.h>

struct Test
{
    int data;
    struct Test *next;
};

// 打印链表
void printfLink(struct Test *p) // 当前 p 存储的是 t1 的地址，也就是链表头
{
    while ( p != NULL ) // p 现是链表头节点，通过循环移动到下一个节点，直到 NULL 
    {
        printf("%d ",p->data); // 输出当前节点的 data 值
        p = p->next; // 使 p 移动至下一个节点
    }
    putchar('\n');
}

// 统计链表个数
int statisticsNode(struct Test *head) // 当前 head 存储的是 t1 的地址，也就是链表头
{
    int cnt = 0; // 计数器，统计节点个数

    // 遍历链表，直到 head == NULL
    while ( head != NULL )
    {
        cnt++; // 记录每一个节点
        head = head->next; // 使 head 移动至下一个节点
    }

    return cnt; // 返回节点个数
}

// 查询链表
int seekNode(struct Test *head, int data) // 当前 p 存储的是 t1 的地址，也就是链表头。data：我们需要查询的节点
{
    struct Test *p = head; // 备份头节点地址

    // 遍历链表，直到 p == NULL
    while ( p != NULL )
    {
        // 判断每个节点的数据域（p->data） 是否等于 我们需要查询的节点（data）
        if( p->data == data )
        {
            return 1; // 查询到，返回 1
        }
        p = p->next; // 使 p 移动至下一个节点
    }

    return -1;// 查不到，返回 -1
}

// 修改指定节点
int modifyNode(struct Test *head, int data) // 当前 p 存储的是 t1 的地址，也就是链表头。data：我们需要修改的节点
{
    struct Test *p = head; // 备份链表头

    // 遍历链表
    while ( p != NULL )
    {
        // 判断每个节点的数据域（p->data） 是否等于 我们需要修改的节点（data）
        if( p->data == data )
        {
            // 找了，将这个节点的原数据域的数据，修改为100
            p->data = 100;
            return 1; // 返回 1，表示修改成功
        }
        p = p->next; // 使 p 移动至下一个节点
    }
    return -1; // 返回 -1，找不到这个节点
}

int main()
{
    // 创建节点
    struct Test t1 = {1, NULL}; // t1.data赋值为1，t1.next赋值为NULL
    struct Test t2 = {2, NULL};
    struct Test t3 = {3, NULL};
    struct Test t4 = {4, NULL};
    struct Test t5 = {5, NULL};

    // 链接节点
    t1.next = &t2; // t1.next存储t2的地址，使t1.next指向t2这个结构体变量
    t2.next = &t3;
    t3.next = &t4;
    t4.next = &t5;

    // 打印链表
    printfLink(&t1);

    // 统计链表个数
    int ret = statisticsNode(&t1);
    printf("链表个数：%d\n", ret);

    // 查询链表
    int seekNodeData = 3; // 需要查询的节点
    ret = seekNode(&t1, seekNodeData); // 将 t1 的地址和需要查询的节点，传递至 seekNode 函数中
    if( ret == 1 ) // 判断返回值是否为1，如 1 表示找到了，非 1 表示找不到
    {
        printf("需查询的值：%d，查询结果：%d\n", seekNodeData, ret);
    }
    else
    {
        printf("需查询的值：%d，查询结果：%d\n", seekNodeData, ret);
    }

    // 修改指定节点
    int modifyNodeData = 5; // 需要修改的节点
    printf("修改之前的链表：");
    printfLink(&t1);
    ret = modifyNode(&t1, modifyNodeData); // 将 t1 的地址和需要修改的节点，传递至 modifyNode 函数中
    printf("修改之后的链表：");
    printfLink(&t1);

    return 0;
}

四、在指定节点插入新的节点

插入一个新节点有两种方法：

在指定节点后插入新的节点
在指定节点前插入新的节点

1.在指定节点后插入新的节点

如上图，在节点 2 的后方插入新的节点：

通过循环，遍历到指定的节点
让新节点的下一个节点，连接到节点 3
new->next = p->next
使指定节点的下一个节点，连接到新节点
p->next = new;

#include <stdio.h>

struct Test
{
    int data;
    struct Test *next;
};

// 打印链表
void printfLink(struct Test *p) // 当前 p 存储的是 t1 的地址，也就是链表头
{
    while ( p != NULL ) // p 现是链表头节点，通过循环移动到下一个节点，直到 NULL 
    {
        printf("%d ",p->data); // 输出当前节点的 data 值
        p = p->next; // 使 p 移动至下一个节点
    }
    putchar('\n');
}

// 在指定节点后方插入新节点
void afterInsertionNode(struct Test **head, int appointNode, struct Test *new)
{
    // 备份链表头地址
    struct Test *p = *head;

    // 遍历链表
    while ( p != NULL )
    {
        // 判断当前节点是否等于目标节点
        if( p->data == appointNode )
        {
            new->next = p->next; // 让新节点的下一个节点存储，原节点的下一个节点的地址
            p->next = new; // 让当前节点指向新节点
            return; // 找到之后直接返回
        }
        p = p->next; // 让当前节点移动到下一个节点
    }
    printf("没有找到目标节点，插入失败！\n");
}

int main()
{
    // 创建节点
    struct Test t1 = {1, NULL}; // t1.data赋值为1，t1.next赋值为NULL
    struct Test t2 = {2, NULL};
    struct Test t3 = {3, NULL};
    struct Test t4 = {4, NULL};
    struct Test t5 = {5, NULL};
    
    // 创建链表头
    struct Test *head = NULL;
    // 定义新节点并赋初值
    struct Test new = {100,NULL};

    // 链接节点
    head = &t1; // 头节点head，存储结构体变量 t1 的地址
    t1.next = &t2; // t1.next存储t2的地址，使t1.next指向t2这个结构体变量
    t2.next = &t3;
    t3.next = &t4;
    t4.next = &t5;

    // 打印链表
    printf("输出插入之前的链表：\n");
    printfLink(head);
    // 在指定节点后方插入新节点
    afterInsertionNode(&head, 2,&new);
    printf("输出插入之后的链表：\n");
    printfLink(head);

    return 0;
}

2.在指定节点的前方插入新节点

有两种情况：

1.第一个节点之前插入新的节点；
2.在中间的节点插入新的节点；

1.第一个节点之前插入新的节点；

如上图，在指定节点的节点 1，之前插入的新节点：

遍历，判断节点是否为指定节点
新节点的下一个，指向节点1的地址
new->next = p;
因为此时新节点变成了头节点，所以此时将new的地址赋值给head
head = new;

void forwardInsertionNode(struct Test **head, int appointNode, struct Test *new)
{
    struct Test *p = *head; // 备份链表头的地址

    // 判断第一个节点的data，是否等于目标节点
    if( p->data == appointNode )
    {
        // 将新节点的下一个节点指向，p的地址，此时new节点变成了链表头
        new->next = p;
        // 更新链表头的指向，使*head指向new的地址，让*head重新变成链表头
        *head = new;
        return;
    }
}

2.在中间的节点插入新的节点；

如上图，如果指定节点是5，之前插入新的节点：

思路：

按照之前的后面插入新节点的方法，当我们遍历到指定节点 5 的时候，如果将new的下一个节点，指向目标节点，是可以连接上的，但是new的节点如果访问到指定节点的上一个节点呢？这个时候很难找到目标节点的上一个节点的地址。
可以这么做，我们要在目标节点 5 之前插入一个新节点，比如说：现在 p 指向的是节点 4 ，节点 4 的下一个节点是目标节点 5 。那节点 4 ->next，不就是目标节点 5 吗？，节点 4 ->next->data，不就是节点 5 的data？然后将new->next指向目标节点 5 的地址，节点 4->next 指向new的地址，不就连上了。

    // 判断当前节点的下一个节点，是否为NULL
    while ( p->next != NULL )
    {
        // 判断当前节点的下一个节点的data，是否等于目标节点
        if( p->next->data == appointNode )
        {
            // 将new的下一个节点，指向原当前节点的下一个节点
            new->next = p->next;
            // 将当前节点的下一个节点指向new
            p->next = new;
            return;
        }
        p = p->next; // 偏移到下一个节点
    }

完整代码：

#include <stdio.h>

struct Test
{
    int data;
    struct Test *next;
};

// 打印链表
void printfLink(struct Test *p) // 当前 p 存储的是 t1 的地址，也就是链表头
{
    while ( p != NULL ) // p 现是链表头节点，通过循环移动到下一个节点，直到 NULL 
    {
        printf("%d ",p->data); // 输出当前节点的 data 值
        p = p->next; // 使 p 移动至下一个节点
    }
    putchar('\n');
}

// 在指定节点前方插入新节点
void forwardInsertionNode(struct Test **head, int appointNode, struct Test *new)
{
    struct Test *p = *head; // 备份链表的地址，
                            // *head是一个二级指针，保存的是main函数t1的地址，是链表的头地址
                            // 除非链表头发生改变，否则不要更改链表头的地址

    // 判断目标节点是否为链表的第一个节点
    if( p->data == appointNode )
    {
        new->next = p; // 将新节点的下一个节点指向，p的地址，此时new节点变成了链表头
        *head = new; // 更新链表头的指向，使*head指向new的地址，让*head重新变成链表头
        return; 
    }

    // 判断当前节点的下一个节点，是否为NULL
    while ( p->next != NULL )
    {
        // 判断当前节点的下一个节点的data，是否等于目标节点
        if( p->next->data == appointNode )
        {
            // 将new的下一个节点，指向原当前节点的下一个节点
            new->next = p->next;
            // 将当前节点的下一个节点指向new
            p->next = new;
            return;
        }
        p = p->next; // 偏移到下一个节点
    }
}

int main()
{
    // 创建节点
    struct Test t1 = {1, NULL}; // t1.data赋值为1，t1.next赋值为NULL
    struct Test t2 = {2, NULL};
    struct Test t3 = {3, NULL};
    struct Test t4 = {4, NULL};
    struct Test t5 = {5, NULL};
    
    // 创建链表头
    struct Test *head = NULL;
    // 定义新节点并赋初值
    struct Test new = {100,NULL};

    // 链接节点
    head = &t1; // 头节点head，存储结构体变量 t1 的地址
    t1.next = &t2; // t1.next存储t2的地址，使t1.next指向t2这个结构体变量
    t2.next = &t3;
    t3.next = &t4;
    t4.next = &t5;

    // 打印链表
    printf("输出插入之前的链表：\n");
    printfLink(head);
    forwardInsertionNode(&head, 5,&new);
    printf("输出插入之后的链表：\n");
    printfLink(head);

    return 0;
}

五、删除指定节点

有两种情况：

删除第一个节点
删除中间的节点

1.删除第一个节点

思路：

head指向的是第一个节点，如果我需要删除第一个节点，需要free()释放内存，此时应当将head指向第二个节点。

    struct Test *p = *head; // 备份链表头的地址

    // 判断链表第一个节点的data，是否与目标节点相等
    if( p->data == appointNode )
    {
        // 将链表头指向第二个节点的地址
        *head = p->next;
        return;
    }

2.删除中间的节点

思路：

如果我们删除的是节点 3，那么节点 2 应该绕过节点 3，使节点 2 连接节点 4

    // 判断当前节点的下一个节点是否为NULL
    while ( p->next != NULL )
    {
        // 判断当前节点的下一个节点的data，是否等于目标节点
        if( p->next->data == appointNode )
        {
            // 当前节点的下一个，指向当前节点的下一个节点的下一个节点
            p->next = p->next->next;
            return;
        }
        p = p->next; // 将当前节点，移动到下一个节点
    }

完整代码：

#include <stdio.h>

struct Test
{
    int data;
    struct Test *next;
};

// 打印链表
void printfLink(struct Test *p) // 当前 p 存储的是 t1 的地址，也就是链表头
{
    while ( p != NULL ) // p 现是链表头节点，通过循环移动到下一个节点，直到 NULL 
    {
        printf("%d ",p->data); // 输出当前节点的 data 值
        p = p->next; // 使 p 移动至下一个节点
    }
    putchar('\n');
}

// 删除节点
void delectNode(struct Test **head, int appointNode)
{
    struct Test *p = *head; // 备份链表头的地址

    // 判断链表第一个节点的data，是否与目标节点相等
    if( p->data == appointNode )
    {
        // 将链表头指向第二个节点的地址
        *head = p->next;
        return;
    }

    // 判断当前节点的下一个节点是否为NULL
    while ( p->next != NULL )
    {
        // 判断当前节点的下一个节点的data，是否等于目标节点
        if( p->next->data == appointNode )
        {
            // 当前节点的下一个，指向当前节点的下一个节点的下一个节点
            p->next = p->next->next;
            return;
        }
        p = p->next; // 将当前节点，移动到下一个节点
    }
}

int main()
{
    // 创建节点
    struct Test t1 = {1, NULL}; // t1.data赋值为1，t1.next赋值为NULL
    struct Test t2 = {2, NULL};
    struct Test t3 = {3, NULL};
    struct Test t4 = {4, NULL};
    struct Test t5 = {5, NULL};
    
    // 创建链表头
    struct Test *head = NULL;

    // 链接节点
    head = &t1; // 头节点head，存储结构体变量 t1 的地址
    t1.next = &t2; // t1.next存储t2的地址，使t1.next指向t2这个结构体变量
    t2.next = &t3;
    t3.next = &t4;
    t4.next = &t5;

    // 打印链表
    printf("输出删除之前的链表：\n");
    printfLink(head);
    delectNode(&head, 4);
    printf("输出删除之后的链表：\n");
    printfLink(head);

    return 0;
}

六、动态创建节点

头插法

如果链条为空，创建的第一个节点为链表头，然后每一次创建的新节点插在之前的链表头之前，再让新节点做为新的链表头；

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

struct Test 
{
	int data;
	struct Test *next;
};

// 头插法
struct Test* insertionHead(struct Test *head, struct Test *new)
{
	// 如果head（头节点）是NULL
	if( head == NULL )
	{
		// 让head指向new
		head = new;
	}
	else
	{
        // 如果head（头节点）不是NULL，那么新节点指向head，此时new为新的链表头
		new->next = head;
        // 让head指向new，让head重新成为链表头
		head = new;
	}

	return head; // 返回链表头的地址
}

// 动态创建链表节点
void createNode(struct Test **head)
{
	struct Test *new = NULL;

	while(1)
	{
		// 开辟内存空间
		new = (struct Test*)malloc( sizeof(struct Test) );
		// 判断是否开辟成功
		if( new == NULL )
		{
			printf("malloc error\n");
			exit(-1);
		}
		// 将new的下一个节点指向NULL
		new->next = NULL;

		printf("为新节点的数据域赋值，如果输入0,表示退出\n");
		scanf("%d", &(new->data));
		// 判断输入的是否为 0
		if( new->data == 0 )
		{
			printf("输入0,quit\n");
			free(new); // 释放指针
            new = NULL; // 避免悬空指针
			return; 
		}

        // 重新获取链表头的地址
		*head = insertionHead(*head,new);
	}
}

// 打印链表
void printfLink(struct Test *head)
{
	struct Test *p = head;

	while( p != NULL )
	{
		printf("%d ", p->data);
		p = p->next;
	}
	putchar('\n');
}

int main()
{
	struct Test *head = NULL;
	
	createNode(&head);
	printfLink(head);

	return 0;
}

尾插法

如果链表为空，创建的第一个节点做为链表头，然后每一次创建的新节点插在链表最后一个节点的指针域(next)中；

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

// 定义链表节点结构体
struct Test
{
    int data;           // 数据域
    struct Test *next;  // 指针域，指向下一个节点
};

// 在链表尾部插入新节点
struct Test* insertTail(struct Test *head, struct Test *new)
{
    struct Test *p = head;

    if (head == NULL)  // 如果链表为空，新节点即为头节点
    {
        head = new;
    }
    else
    {
        // 遍历链表，找到最后一个节点
        while (p->next != NULL)
        {
            p = p->next;
        }
        // 将新节点插入到链表尾部
        p->next = new;
    }

    return head;  // 返回链表头节点
}

// 创建链表节点
void createNode(struct Test **head)
{
    struct Test *new = NULL;

    while (1)
    {
        // 开辟内存空间，创建一个新节点
        new = (struct Test*)malloc(sizeof(struct Test));
        if (new == NULL)  // 检查内存分配是否成功
        {
            printf("malloc error\n");
            exit(-1);  // 内存分配失败，退出程序
        }

        new->next = NULL;  // 初始化新节点的指针域为NULL

        // 为新节点的数据域赋值
        printf("为新节点的数据域赋值，输入0,退出\n");
        scanf("%d", &(new->data));
        if (new->data == 0)  // 如果输入0，则退出循环
        {
            free(new);  // 释放内存
            new = NULL;  // 避免指针悬空
            return;
        }

        // 将新节点插入链表尾部
        *head = insertTail(*head, new);
    }
}

// 打印链表
void printfLink(struct Test *head)
{
    while (head != NULL)
    {
        printf("%d ", head->data);  // 打印当前节点的数据
        head = head->next;  // 移动到下一个节点
    }
    putchar('\n');  // 打印换行符
}

int main()
{
    struct Test *head = NULL;  // 初始化链表头节点为NULL

    createNode(&head);  // 创建链表
    printfLink(head);   // 打印链表

    return 0;
}