链表(数据结构)

一. 单链表

1.1 概念与结构

再上一篇中我们讲到顺序表，但是顺序表也是有很多的问题，像申请的空间过多过少或者增容该才能不浪费空间，今天我们就来认识一个新的知识，叫做链表，链表也是线性表的一种，链表是一种物理存储结构上非连续、非顺序的存储结构，数据结构的逻辑顺序是通过链表中的指针链接次序实现的。

1.2 结点

链表到底是一个怎样的存在？又是怎样通过一个个的结点将其连接在一起，说一个简单的例子，我们坐的火车是一个个车厢连接起来的，前一个车厢连接着后一个车厢，也就是说我们能从前一个车厢的位置找到后一个车厢的位置，其实链表也是如此，来一张简单的图：我们来看上面的一张图，简单点说上面的1，2，3，4就是一个个的结点，我们可以发现的是其实结点的地址不一定是连续的，但是我们可以发现每一个结点的结构总是包含着下一个结点的地址，链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。所以在链表中没有增容的概念，如上图所示，所以结点是一个结构体，那这个结构体又有什么组成的呢？是数据+指向下一个结点的指针。

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

1.3 链表的性质

1、链式机构在逻辑上是连续的，在物理结构上不一定连续 2、结点一般是从堆上申请的 3、从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续

 所以假设当我们想要保存一个整型数据的时候，实际上是从操作系统申请一个内存空间，而这个内存空间不仅要保存当前的整型数据，还要保存下一个结点的地址，当我们想要从第⼀个结点⾛到最后⼀个结点时，只需要在当前结点拿上下⼀个结点的地址就可以了。而且对于链表来说没有增容的概念，是我们需要的时候再去申请一块空间，这就很好的处理了在顺序表中些许浪费的情况。

1.4 链表的打印

清楚了链表的结构，了解了结点的结构，现在我们可以简单的来打印一个链表，同样的方法我们创建三个文件：在我们以后的代码中，我们也尽量养成三个文件的写法，这样会使代码更清晰可见，我们的思路 也会更清晰明了。首先我们在头文件中创建我们所需要的函数声明：

在创建完头文件之后，我们就开始写测试文件和实现文件的函数：

我们先用结点创建一个链表，在打印之前我们对它进行调试，通过调试发现在每一个结点中存放在我们事先输入的数据，并且通过前一个结点可以找到后一个结点，之后我们开始写打印的代码：

 可能有同学就会对这个打印的代码产生疑惑，对此我来解释一下，在前面我们将链表的第一个结点node1传入SLprintf中，所以SL* phead就是头结点，当我们把头结点先赋值给一个新的SL*类型的变量pcur，如下图所示：

 while循环的条件是pcur不为空指针，所以我们先让pcur->data就是第一个数据1，打印完之后将pcur赋值给pcur->next，然而next的地址又是下一个结点的地址，所以我们就会打印出下一个数据，打印出来的结果就是：

完整代码：

//SList.h
//声明函数
#pragma once
#include <stdlib.h>//申请空间
#include <stdio.h>
//定义一个结点
typedef int SLDatatype;
typedef struct SLNode
{
	SLDatatype data;
	struct SLNode* next;
}SL;
//打印函数
void SLprintf(SL* phead);


//SList.c
//实现函数
#include "SList.h"
void SLprintf(SL* phead)
{
	SL* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}


//test.c
//测试文件
#include "SList.h"
void CreatSList()
{
	SL* node1 = (SL*)malloc(sizeof(SL));
	node1->data = 1;
	SL* node2 = (SL*)malloc(sizeof(SL));
	node2->data = 2;
	SL* node3 = (SL*)malloc(sizeof(SL));
	node3->data = 3;
	SL* node4 = (SL*)malloc(sizeof(SL));
	node4->data = 4;

	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
	SLprintf(node1);
}
int main()
{
	CreatSList();
	return 0;
}

1.5 链表的分类

链表说明： 

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构： 单链表和双向带头循环链表 1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2. 带头双向循环链表：结构最复杂，⼀般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

 在这一篇简单的讲解了单链表的简单结构组织，知道了怎样去写一个简单的单链表，在下一篇中我们会增加难度，用单链表实现数据的删减、增加、插入等，并且练习解释一些单链表的算法题，使知识更加的牢固。