数据结构入门指南：链表（新手避坑指南）

目录

前言

        前边我们学习了顺序表，顺序表是数据结构中最简单的一种线性数据结构，今天我们来学习链表，难度相较于顺序表会大幅增加，非常考验大家对结构体、指针的理解。但是也不要害怕，我会一一向大家解答疑惑，本期的内容先给初学者预预热，主要介绍在刚开始学习链表时需要注意的点、涉及的基础知识以及逻辑基础，下期会将功能接口具体实现。

1.链表

1.1链表的概念

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

 逻辑图：

 而现实中的链表是这样的：

         通过图我们可以观察到，链式数据结构在逻辑上是连续的，在物理上不一定连续。链表的好处在于对内存更高效的使用（加入一个节点就开辟一个节点的空间）。

注意：

• 链表的节点是在堆上开辟的，程序不结束就不会主动释放。
• 从堆上申请的空间是按照一定策略分配的，两次申请的空间可能连续，也可能不连续。

 1.2链表的分类

        链表主要分为以下几种：

1.2.1单向或双向

         单向的链表简称为单链表，单链表只可以进行单向遍历，而双向链表完美的弥补了这个缺陷，可以向前遍历也可以向后遍历

1.2.2带头或者不带头

        它们本质上并没有太大的区别，在链表功能实现过程中，有头节点的不需要对特殊节点进行特殊操作，相对简单，但对于大部分的刷题网站上链表的题目都是默认为无头节点的，所以对于无头节点链表的理解更为重要。

1.2.3 循环或者非循环

        循环链表可以用于解决一些特定的问题，非循环链表一般用于普通的链表操作，例如插入、删除、查找等。

 虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

         无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

        带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了，后面我们代码实现了就知道了。

1.3链表的实现

         对于初学者来说，我个人建议先从无头单向非循环链表学起，因为在很多的刷题场景中都是单项无头非循环链表，理解了它也可以帮助你更快的适应链表的刷题。今天我们主要从这种单链表讲起。

         单链表的实现过程中会存在很多的坑，对于初学者来说是很困难的，我会一一列举帮助大家避免这些错误，刚开始我会从基础知识层面进行逐个分析，当然内容也会很多，我会分期进行讲解。

 定义链表

typedef int Datatype;
typedef struct SLNode
{
	Datatype data;
	SLNode* next;
}SLNode;

         定义链表这里就迎来了第一个坑，上述的这种形式很常见，对于初学者来说这里就有一个坑，这个链表定义的是否正确呢？

         这种方式是不正确的，为什么？typedef是重命名，结构体是我们自定义类型，SLNode是重命名后的名字，但是这里需要注意，这个重命名是从上述代码第六行结束后才开始生效，在结构体中提前使用是不允许的。

正确的定义：

typedef int Datatype;
typedef struct SLNode
{
	Datatype data;
	struct SLNode* next;
}SLNode;

         定义之后就需要创建节点，创建节点这里我们要明白：我们是通过函数的形式来创建节点，创建时顺便赋值，初学者或许会有这样的疑问：那为什么函数的类型是结构体指针类型？例如：

SLNode* NewNode(Datatype x)
{
}

        为了后续节点的链接，我们最后需要返回新建节点的地址，而节点地址的类型就是SLNode* ，函数的类型也只是函数的返回类型。

 接下来就是功能实现：

SLNode* NewNode(Datatype x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(Datatype));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

 这里就迎来了第二个坑， 这段代码哪里有问题？

        首先我们要清楚链表开辟空间是给谁开辟的，链表的空间是给整个节点（结构体）开辟的，而不是仅仅给数据开辟空间。

 所以说这里malloc的大小应该是结构体的大小，改为

SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));

就可以啦！

         在其他功能实现之前，我们先理解以下打印链表的函数接口。

void SLprint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

         打印链表首先需要遍历链表，phead为链表的头指针，但是一般情况下我们并不会直接的使用头指针去遍历，因为那样可能会造成头节点的丢失，所以我们需要创建另一个变量来接收头指针去执行遍历操作。我们要想让cur向后移动就只需把下一个节点的地址赋值给cur，我们知道一个链表的节点内会存储着下一个节点的地址，也就是当前节点中的next。注意这里的遍历需要好好的理解，这是进行后续理解的前提。

         理解完链表的的遍历，接下我们来说说它们是如何将每个新建的节点链接的。初学链表可能会有这样的疑惑：创建的节点是如何一个个链接起来的呢？节点的链接是属于后续头插，尾插等操作的内容，但是为了解答大家内心的疑惑，我们先写一个简单的测试接口，来演示它是如何链接的

void test1()
{
	SLNode* plist = NULL;//链表的头指针，没有节点的情况下指向NULL
	int n = 0;
	printf("请输入链表的长度\n");
	scanf("%d", &n);
	printf("请输入数据\n");
	for (int i = 0; i < n; i++)
	{
		int val = 0;
		scanf("%d", &val);
		SLNode *newnode= NewNode(val);//创建结构体指针变量来接收新节点的地址
        //头插的方式链接
		newnode->next = plist;
		plist = newnode;
	}
    SLprint(plist);
}



int main()
{
	test1();


	return 0;
}

         首先我们把头指针指向的内容（可能是NULL，也可能是第一个节点）赋值给新节点。

         初始情况下，plist指向NULL，把plist指向的内容赋值给新节点newnode的next（指针域），然后把整个新节点的地址赋给plist。

         这样plist就成功指向了第一个节点。那么后续插入增加节点也是这样。假设上一步链接的节点地址是0x0012ff40。

         把plist指向的节点（地址）赋值给新建节点newnode的next（结构体内的成员）。

         然后把整个新节点的地址赋给plist。这样就通过头插将节点链接了。但是这里需要注意，测试接口的操作是在同一个函数内进行创建头指针，节点链接操作的（不需要传值），没有调用函数进行头插链接（在后续实现头插，尾插接口的过程中需要使用二级指针传参进行操作）。

 接着我们继续，尾插操作的实现。

        尾插的原理是什么？找到最后一节点。

 将新节点的地址赋给最后一个节点的next（指针域）就可以了。

 注意：新节点的next（指针域）在创建初始化时就已经置为NULL。

        但这并不完整，前边我们提到，尾插也可以用来初始化，那么对于没有节点的情况，上述逻辑就无法使用了。所以我们需要特殊处理一下，判断链表是否为NULL。

void SLPushBlack(SLNode* phead, Datatype x)
{
	SLNode* newnode = NewNode(x);
	SLNode* tail = *pphead;
	if (phead == NULL)
	{
		phead = newnode;
	}
	else
	{
		while (tail->next)//找到最后一个节点
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

         以上的逻辑可以这样实现，那段代码是否正确呢？这里就是遇到的第三个坑。运行测试一下我们会发现链表为空的时候没有插入数据。这是为什么呢？

        那是因为传进来的头节点是形参，形参是实参的临时拷贝，出了函数phead就被销毁了，在函数内将新节点地址赋给形参 头节点并不会对实参中的头节点造成影响。那这里要想修改实参中头节点的指向就只能传头节点的地址（二级指针），通过实参中头指针的地址来修改头指针的指向。

 所以正确的代码应该是：

void SLPushBlack(SLNode** pphead, Datatype x)
{
	SLNode* newnode = NewNode(x);
	SLNode* tail = *pphead;
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
//调用时要传结构体指针的地址
SLPushBlack(&plist,100);

 那或许会有人疑惑，为什么链表不为的时候就不使用二级指针？

        这里我们总结一下，使用二级指针是因为要修改结构体指针（头指针）的指向，而链表不为空时，只需要链接增加一个节点就好，这时修改的是结构体成员的内容。

对头插操作进行实现

         使用二级指针是因为要修改结构体指针（头指针）的指向，那按照逻辑，头插每次都是修改头指针的指向，所以头插独立实现成一个函数时也需要二级指针，尾插是只有第一次链表为空的时候需要二级指针，而头插次次都需要二级指针。

        注意前边测试的接口头插数据没有使用二级指针是因为创建头指针和修改头指针指向在同一个函数中，不存在函数调用头指针。

前边我们已经了解头插的逻辑，这里就不再讲解。代码实现：

void SLPushFront(SLNode** pphead, Datatype x)
{
	SLNode* newnode = NewNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

         pphead就是指向plist（头指针）的指针，*pphead就等价于plist。通过对pphead解引用找到plist（头指针），直接修改plist（头指针）的指向。

总结

        本期内容主要介绍在刚开始学习链表时需要注意的点、涉及的基础知识以及逻辑基础，一定要理解透彻，否则后续的接口实现将会寸步难行，好的，本期内容到此就要结束啦，希望对你有所帮助，最后，感谢阅读！