单链表的创建

单链表的创建

大家好，今天来详细说一下单链表的创建过程。

单链表是我们在学习数据结构时见到的第一种动态内存分配的结构，而这也是单链表和数组之间最大的区别，因为数组被分配的内存是固定的，而单链表的内存是在执行时分配的。

因此，想要给单链表分配内存，我们就得首先知道函数malloc()，即memory allocate（内存分配）的缩写，它是c语言标准函数库中的函数，用法是void *malloc(unsigned int size)。其作用是在内存的动态存储区中分配一个长度为size的连续空间。此函数的返回值是分配区域的起始地址（即指向该分配域的开头位置的指针）

了解了malloc函数以后，我们来创建链表中最重要的部分：结点(node)。每个结点中都存储了数据，但是，每个结点并不是独立存在的，因为链表是由多个结点连接组成，那么我们该怎么连接每一个结点呢？我们需要用到指针(pointer)，用指针来指向另一个（下一个）结点的地址，这样就可以将每个结点按自己的想法连接起来。所以，每个结点都至少由两部分组成：数据和指向下一个节点地址的指针。

知道了如何抽象地去创建链表之后，我们将用C语言代码来创建链表。

首先，我们需要用到结构体(structure)来定义结点node：里面包括一个int类型的数据data，struct node类型的指针link。

接下来，我们首先用malloc函数创建第一个长度为结点大小的连续空间，用来存储结点中的数据和指针。我们把这个连续空间定义为head，即头结点。我们在头结点中输入数据，再定义指针link的值为null，即不指向任何地址。这样，我们就创建了一个独立的结点。

我们可以用同样的方法，创建第二个(current1)，第三个(current2)，直到我们需要数量的独立结点。如下图所示，我们创建了三个独立节点。

但是，我们在之前已经知道，多个独立结点并不能称之为链表，链表是需要将结点连接起来的，所以我们还需要用代码来将他们连接起来。

我们已经知道，head结点的指针不指向任何地址。现在，我想让他指向第二个结点current1，以此来连接第一个结点和第二个结点，形成一个只有两个结点的链表。我们只需要再后面添加一句：head->link = current1。即link的值是current1的地址。用同样的方法，我们可以连接第二个和第三个结点current2，即

current1->link = current2。如下图代码所示。

但是，按照我们上面的这种方法。如果我们需要创建一万个结点，那岂不是需要创建一万个指针指向各自的下一个结点？这样的方法非常的繁琐且占用内存空间，因此，我将介绍第二种方法，只需要两个指针就可以完成所有结点的连接。

创建前两个结点的方法同上，两个结点分别为head，current1。创建第三个结点时不同的是，我们需要再次使用指针current1。在给第三个结点分配空间后，令current1 = malloc(sizeof(struct node))，即current1不再是第二个结点空间的首地址，而是第三个结点空间的首地址。这样，我们可以用和第二个节点同样的方法赋值第三个结点的data和link，另外一个不同的地方就是：我们将第三个结点的地址(current1)赋值给head->link->link，即可完成第二节点和第三结点的连接。示意图和代码如下。

 

 

 

 

 综上，我们创建了一条具有三个结点的单链表。现在，我们可以对链表进行增、删、改、查等一系列操作了！