1.什么是链表

     链表我的理解要包含以下特征：（1）.由n个节点离散分配；（2）.每个节点通过指针连接（3）每一个节点由一个前驱节点和一个后驱节点（4）.首节点没有前驱节点，尾节点没有后驱节点；

 

     满足上面的4条，我们就称为链表；链表既然由很多个节点，那节点又由什么组成？节点由两个部分组成，一是数据域，用来存放有效数据；二是指针域，用来指向下一个节点；下面用C语言来构建链表数据结构，首先应该构造出节点，然后再把所有的节点连起来，就构成了链表；

 

（1）节点的构造

 

        

 

    typedef 只是给数据类型取个别名，即 typedef  数据类型  别名；我们知道struct Node 是我们定义的数据类型；

 

（2）链表的创建

 

     在创建链表之前，我们需要需要了解一下专业术语：

 

   首节点：存放第一个有效数据的节点；

 

   尾节点：存放最后一个有效数据的节点；

 

   头节点：头节点的数据类型与首节点的数据类型相同，并且头节点是首节点前面的那个节点，并不存放有效数据；头节点的存在只是为了方便链表的操作。

 

   头指针：指向头节点的指针；

 

   尾指针：指向尾节点的指针；

 

首先，我们应该创建一个头节点，并用头指针指向它，用C语言描述：用malloc向计算机申请一块内存，并定义一个指向与头节点数据类型相同的指针（一定要判断申请内存是否成功）；

 

然后，要知道要创建链表的长度，用一个循环来每次创建一个节点，并把每个节点连在一起；

 

指针就是一个存放地址的变量

 

当指针指向某个变量

 

这时这个指针里就存放了那个变量的地址

 

同时可以利用指针直接取变量中的值用 只要在指针前加 * 就是取其

 

真值了(也就是被指向的变量的值)

 

如果不用指针，传送速度慢，如果通过指针，只要传递一个地，不用传送该地址 的内容就可以直接进行运算，方便快捷，

 

使用指针来读取数据，在重复性操作的状况下，可以明显改善程序性能

 

就是一连续内存空间，类似于数组，不过数组的内存空间一旦初始化就是不变的。

链表开始是一个“头指针”，定义了链表开始的位置，下面是像链条一样的一串节点，每个节点包含数据部分和指针部分。前一节点的指针指向后一节点，最后一个节点是数据和空地址，表示结束。

好处在于空间是动态分配的，需要多长可以一直链下去。