线性数据结构：单向链表

放弃眼高手低，你真正投入学习，会因为找到一个新方法产生成就感，学习不仅是片面的记单词、学高数......只要是提升自己的过程，探索到了未知，就是学习。

一.链表的理解

二.链表的分类（重点理解）

三.无头单向非循环链表

三.1 节点结构以及理解

三.2遍历链表

三.3尾插

三.4增加节点

三.5尾删

三.6头删

三.7头插

三.8查找数据

三.8插在目标节点前面

三.9插在目标节点后面

三.10删除目标节点

在上篇我们学习了顺序表，它是在计算机内存中以数组形式保存的线性表，特点是通过一组地址连续的存储的单元依次存储线性表中的各个元素，既然地址是连续的，它存在以下几个问题：

1：在中间/头部插入删除，需要对整个空间地址、内容进行移动，比较麻烦

2：如果空间不够用，那么就需要扩容，这个过程需要拷贝原空间数据，释放旧空间，消耗较大

3：空间浪费问题，当你已经扩容好了一片空间，但是很多用不完或者又不够用，需要重新对空间问题进行解决

综合起来，我们需要更加高效的线性存储结构：链表

一.链表的理解

定义：链表是一种线性结构，由一系列节点组成，链表存在头（头节点）和尾（尾节点），节点之间通过指针关联，每一个数据元素都是独立存储的（地址不连续）。链表通过指针链接次序实现数据元素的逻辑顺序，每个节点包含两个组成部分：数据域与指针。数据域用来存储数据，指针负责指向下一个节点。链表的起点为头节点，尾节点则是空指针（NULL），用来表示链表的结束。

抽象图示：

特点： 1：动态性。灵活删除或者插入节点

2：内存利用率高。充分利用空间，实现动态内存管理

3：插入与删除操作效率高。顺序表的删除插入时间复杂度为O（N），那么链表的对应时间复杂度则达到了O（1），可以在很短的时间内完成插入删除操作

4：查询效率低。我们知道链表从头到尾，需要遍历整个链表才能找到目标节点，它的查找时间复杂度则为O（N）

二.链表的分类（重点理解）

链表主要可以分为以下3大类：

单向链表：单向链表中的每一个节点只包含一个指针，指向下一个节点，数据元素的逻辑顺序通过链表中的指针链接次序实现

双向链表：双向链表中的每个节点包含2个指针，分别指向前一个节点与后一个节点

循环链表：循环链表的第一个节点和最后一个节点通过指针相连，形成一个环状结构，循环链表可以是单向也可以是双向的

在这3大类中我们还需要了解几个概念：头指针与头节点与带头节点与不带头节点

头指针：本质是一个结构体类型的指针，存储第一个节点的地址

头节点：本质是一个节点，有数据域与指针。在单链表的第一个节点之前再附加一个节点，称为头节点，头节点的数据域可以不放任何信息，也可以记录链表长度。若链表是带有头节点的，则头指针指向头节点的存储位置

带头节点：与其它节点一样，有数据域跟指针，可以理解为一个结构体变量，只是头指针指向头节点存储位置，图示：

不带头节点：我们知道带头节点是指针指向头节点，那么反之，不带头节点是头指针指向第一个节点的存储位置

那么我们简单总结：无论是否有头节点，都存在一个头指针，头指针都指向链表的一个节点，只是区分头指针是指向第一个节点还是头节点，图示理解：

链表会根据：单头或者不带头、单向或者双向、循环或者非循环进行组合，一共可以组合出8种

其中只要掌握2种，就可以触类旁通了，我们先重点来学习以下第一种：

无头单向非循环链表带头双向循环链表

三.无头单向非循环链表

上面我们已经了解了无头跟有头的区别，那这里我们轻而易举的可以画个图：

三.1 节点结构以及理解

我们创建了一个指针next跟数据域，这个数据域的类型就是你要存储的类型，可自行设置，指针指向下一个节点的地址。

这里解释一下next指针：链表中的next是指向下一个节点的指针（通常称为next）。所有节点通过next指针连接起来，使得数据元素可以按照一定的顺序排列。在双向链表中还有一个指向前一个节点的指针：prev，这使得双向链表可以从头到尾或从尾到前遍历，这里仅仅简单科普一下！

下面我们看几个常见写法，来进行错误纠正：

我们先用typedef对结构体类型进行重命名，命名之前结构体类型是struct Student，命名之后可以简写为Student，这样减少了代码量，方便阅读。上图第一种写法跟第二种写法都存在一个问题：在进行重命名的结构体里面，类型必须写全，这是因为现在是属于声明阶段，出了这个结构体以后才可以用简写的方式。举个例子：一个方案的发布必须是已经制作好的。这里也一样，typedef目前在这个结构体只是类似方案制作阶段，出了这个结构体之后才可以简化使用。

三.2遍历链表

在遍历链表时，我们需要让指针灵活的动起来，而不能直接让节点里面的指针动起来，不然就出问题了，因此我们需要创建一个指针指向节点中的第一个指针，改变这个指针的指向是不是就达到了动态节点的效果！比如我新创建了一个指针 cur （在下文我们方便讲解，还会用到这个指针），每次通过改变cur的指向来改变当前访问的节点。这里需要注意cur指针是不会真正动的，只是它的指向地址发生改变。图示理解如下：

在进行链表的增删查找功能前，我们需要掌握遍历，代码参考如下：

我们仔细解释一下图中比较重要的地方：

1：为什么不需要判断指针head的有效性？因为head是头指针，指向第一个节点，指针是空指针只能说明指向的地址不存在，而指向的地址的空间内容是否存在不相干，就好比通讯录空间，我只是没有存储联系人进去，但是有这个空间，这个大家可以理解吗？我再举个例子：现在有一个水杯（head），我需要去拿水杯喝水（head指向地址的内容），杯子里面有没有水跟这个水杯存不存在不相关！

2：指针head跟指针cur的关系：head是头指针，是不可以移动的，而将head指针指向的地址交给cur，通过cur的指向移动，实现对节点内容的管理

3：对while循环的条件的讨论：我们看下面2个图

我们知道头指针head将第一个节点的地址传给cur，cur是指向下一个节点的地址的，当cur到达最后一个节点时，此时cur的指向还是最后一个节点的地址，而cur->next已经是指向空指针了，就少进入了循环一次。cur是通过cur->next来改变cur的指向的，而cur->next已经指向下一个节点了。这个我们结合2张图理解（物理图示与逻辑图示）：

三.3尾插

我们从字面上理解，就是在当前最后一个节点后面再插入新节点！再把新节点与尾节点连接起来，那么我们需要用3个操作：找尾节点开辟新节点连接节点（最后会对3个步骤汇总代码讲思路）

先解释一下为什么要用二级指针？因为涉及空链表跟链表存在的讨论，需要更改地址的问题。

下面我们进行第一个操作，找尾节点。我们已经知道如何遍历链表了！既然指针指向下一个节点的地址，那么当这个指针是空指针的时候，是不是就表示找到尾了！这里需要理解的是，这个指针的指向是NULL，因为我们是需要开辟新节点的，自然要在最后一个节点后面开辟，所以需要让它指向NULL，如图理解（tail跟cur等价）：

//找尾节点
void Traversal(Pointdef** head)
{
    //判断链表是不是空链表
    if(*head==NULL)
    {
       //空链表的话新节点作为第一个节点
       *head=newspointer;
    }
    else
    {
	  //托付head的指向给cur指针
	  Pointdef* cur = *head;
      //找尾
	  while (cur)
	  {
		 //改变 cur 指针的指向
		 cur = cur->next;
	  }
	  //此时cur指向NULL，也就是尾节点的后面
    }
}

下面我们进行第二个操作：开辟新节点。新节点的创建不能直接使用原节点的类型去创建，因为这样创建的新节点只是临时变量，为什么呢？因为我们是在函数里面创建的，当函数调用完，里面的变量就全部销毁了。因此我们需要用到动态内存开辟，同时初始化指针，至于为什么要初始化，后面会细说，因此用malloc给新节点开辟一块空间，才能延长新节点生命周期。代码如下：

Pointdef* Greate()
{
	Pointdef* news = malloc(sizeof(Pointdef));
	if (news == NULL)
	{
		perror("malloc");
		return NULL;
	}
	//理解：news指针指向新节点地址，news->next表示对新节点的指针初始化了
	news->next = NULL;
	return news;
}

首先我们看这个函数，它的类型是结构体指针类型，为哈？因为我们用这个函数来开辟新节点，那么开辟的空间类型是节点的结构体类型，我们知道链表是用指针连接起来的，那么我们只需要返回一个指针就行了，指针类型肯定是结构体类型，然后用malloc开辟新节点，节点大小是结构体的大小。下面紧接着判断，判断新节点是否开辟成功，news->next=NULL，这句话就是告诉我们这是新节点的尾端，因为new->next是指向下一个节点，也就是NULL。大家肯定想知道为哈不初始化这个新节点的数据域呢？单链表节点的数据域是否初始化，可以自行设定，未初始化的数据域可能出现一些随机值。

下面进行第三个操作：连接这2个节点。在连接前需要判断这个链表的头指针是否存在，否则需要将新节点作为第一个节点，不然会出现严重问题。这里涉及空链表跟链表不存在的区别，如下：

链表不存在：如：head==NULL，链表都不存在，那么一切操作都无用，因此在使用链表时需要检查链表是否存在

空链表：链表存在，头指针为空，如：cur==NULL，它的存在与否需要分情况，比如我需要删除某个节点，那么空链表肯定是不行的，而打印、插入节点这些没什么影响，具体需要根据操作来判断

//增加新节点
void NewPointer(Pointdef** head)
{
	assert(head);
	Pointdef* newpointer = Greate();
	//如果这个头指针的指向是空指针，那么链表是空的，将这个新节点作为新的节点
	if (*head == NULL)
	{
		*head = newpointer;
	}
	else
	{
        //头指针指向交给cur，用cur找尾
		Pointdef* cur = *head;

		//找尾
		while (cur->next ！= NULL)
		{
			cur = cur->next;
		}
		//连接
		cur->next = newpointer;
	}
}

总结：上面代码我们是进行拆分了的，如果看不懂，我们可以用笔一步步记录，理清思路。尾插的总思路就是：先判断链表是否存在，再用函数新增节点，然后判断空链表，最后找尾进行连接。参考完整代码：

//增加新节点
Pointdef* Greate()
{
	Pointdef* news = malloc(sizeof(Pointdef));
	if (news == NULL)
	{
		perror("malloc");
		return NULL;
	}
	//理解：news指针指向新节点地址，new->next标识它是将要接入的最后一个节点，相当于初始化了
	news->next = NULL;
	return news;
}

//找尾+连接
void NewPointer(Pointdef** head)
{
    //判断链表是否存在
	assert(head);
	Pointdef* newpointer = Greate();
	//如果这个头指针的指向是空指针，那么链表是空的，将这个新节点作为新的节点
	if (*head == NULL)
	{
		*head = newpointer;
	}
	else
	{
		Pointdef* cur = *head;

		//找尾
		while (cur->next == NULL)
		{
			cur = cur->next;
		}
		//连接
		cur->next = newpointer;
	}
}

三.4增加节点

新增我们在上面的尾插已经使用过了，我们就不再重复说了，每次操作接收函数返回的指针，就可以控制新增节点的地方，新增节点的函数都是通用的，代码如下：

//增加新节点
Pointdef* Greate()
{
	Pointdef* news = malloc(sizeof(Pointdef));
	if (news == NULL)
	{
		perror("malloc");
		return NULL;
	}
	//理解：news指针指向新节点地址，news->next理解为标识自己是将要接入的最后一个节点，相当于初始化了
	news->next = NULL;
	return news;
}

三.5尾删

顾名思义，就是删除最后一个节点，那么我们猜测步骤也就只有2步：先找再删

我们需要先遍历链表，然后找到最后一个节点，进行删除释放，再把倒数第二个节点的cur->next改为NULL。尾删需要注意几种情况，空链表跟唯一节点的链表，2种情况，跟尾插一样，可能需要更改头指针地址，因此需要使用二级指针。找尾节点跟倒数第二个节点一个指针肯定不够，因此我们需要两个指针，一个来找尾节点，一个来找倒数第二个节点。我们来看思维图，理清双指针的关系：

代码如下：

//尾删
void Taildeletion(Pointdef** head)
{
	//判断链表是否存在
	assert(head);
	//判断是否是空链表
	assert(*head);

	//判断一个节点的情况
	if (((*head)->next) == NULL)
	{
		//直接释放
		free(*head);
		*head = NULL;
	}
	else
	{
		//找尾
		Pointdef* cur = *head;
		while (cur->next)
		{
			cur = cur->next;
		}

		//找倒数第二个节点
		Pointdef* tail = *head;
		while (cur->next)
		{
			tail = cur;
            cur = cur->next;
		}

		//释放尾节点
		free(cur);
		cur = NULL;

		//改变倒数第二个的指向
		tail->next = NULL;
	}

}

三.6头删

有了尾删的基础，头删也一样需要考虑空链表跟链表不存在的情况，先改变头指针指向，然后直接删就行了，也不需要找头，是不是很简单！代码如下：

//头删
void Headdeletion(Pointdef** head)
{
	//判断链表是否存在
	assert(head);
	//判断是否是空链表
	assert(*head);

	//创建指针指向头
	Pointdef* cur = *head;
	//改变头指针指向
	*head = (*head)->next;
	//释放
	free(cur);
	cur = NULL;
}

三.7头插

头插管他是不是空链表！直接搞个节点当头就行了！那么我们需要先开一个新节点，再改变头指针指向，代码如下：

//头插
void HeadPointer(Pointdef** head)
{
	//判断链表是否存在
	assert(head);
	//新开节点
	Pointdef* cur = Greate();
	//改头指针跟指向
	cur->next = *head;
	*head = cur;
}

三.8查找数据

我们只要给某个节点的数据域初始化，那么就可以通过遍历链表来找这个节点的地址，例如我初始化了某个节点的整型数据域为x，那么就直接遍历就行了！

//查找数据
Pointdef* Find(Pointdef* head , int x)
{
	Pointdef* cur = head;
	//查找
	while (cur)
	{
		if (cur->data==x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	//否则没有找到
	return NULL;
}

三.8插在目标节点前面

之前，我们学习了尾插与头插，那么如果在中间插入新节点呢？我们先遍历链表，找到那个节点，然后在它的前面插入新节点即可（自行选择插入的节点前后，我这里例举插在目标节点前面）。这里需要注意的是如果目标节点是第一个节点，那么就是头插，这里需要改变指针指向，不能是形参，因此需要二级指针。根据对应节点的指针找目标节点，这里我假设cur是目标节点代码如下：

void Middle(Pointdef** head ,Pointdef* cur,int x)
{
	//注意：cur是目标节点
	
	//判断空链表,否则是头插
	if (*head==NULL)
	{
		HeadPointer(head);
	}
	else
	{
		//先开新节点
		Pointdef* news = Greate();
		//找要增加的节点位置
		Pointdef* pc = *head;
		while (pc->next!=cur)
		{
			pc = pc->next;
		}
		//此时pc指向cur的前一个节点
		//连接节点
		pc->next = news;
		news->next = cur;
	}
}

三.9插在目标节点后面

这个跟前面插在节点前面的类似，但是更简单。借助指针找到目标节点，在连接就行。代码如下：

//插在节点后面
void Outdle( Pointdef* cur)
{
	//注意：cur是目标节点
	assert(cur);

	//开辟新节点
	Pointdef* news = Greate();

	Pointdef* pc = cur->next;

	//连接
	cur->next = news;
	news->next = pc;
}

三.10删除目标节点

考虑空链表跟链表不存在两种情况，然后循环找到目标节点，连接左右节点再删除即可！

//删除目标节点
void Omit(Pointdef** head, Pointdef* cur)
{
	//cur是要删除的节点指针
	
	//判断链表是否存在
	assert(head);

	//判断空链表
	assert(*head);

	//循环找目标节点
	Pointdef* pc = *head;
	while (pc->next = cur)
	{
		pc = pc->next;
	}
	//连接目标节点的左右节点
	pc->next = cur->next;

	//先连接再释放
	free(cur);
	cur = NULL;
}

好了，本篇到此结束，大家记得一键三连哦！几天后我会继续出带头双向循环链表的博文！感谢支持！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！