今天将给大家讲述链表的学习心得。学习数据结构，毋庸置疑链表必须学好，后面的栈、队列、树、图都是以链表为基础的；链表的种类很多，有单链表、双链表、循环链表、非循环链表；在此，我们以非循环单链表为例，来讲链表的创建、求长度、排序、插入和排序。
1.什么是链表链表我的理解要包含以下特征：（1）.由n个节点离散分配；（2）.每个节点通过指针连接（3）每一个节点由一个前驱节点和一个后驱节点（4）.首节点没有前驱节点，尾节点没有后驱节点；
满足上面的4条，我们就称为链表；链表既然由很多个节点，那节点又由什么组成？节点由两个部分组成，一是数据域，用来存放有效数据；二是指针域，用来指向下一个节点；下面用C语言来构建链表数据结构，首先应该构造出节点，然后再把所有的节点连起来，就构成了链表；
（1）节点的构造
typedef struct Node{int data;//数据域，用来存放数据域；struct Node *pNext;//定义一个结构体指针，指向下一次个与当前节点数据类型相同的节点}NODE,*PNODE; //NODE等价于 struct Node; PNODE等价于struct Node *； 此处用大写是为了与变量区分，可以让人容易变出是个数据类型 typedef 只是给数据类型取个别名，即 typedef 数据类型 别名；我们知道struct Node 是我们定义的数据类型；
（2）链表的创建
在创建链表之前，我们需要需要了解一下专业术语：
首节点：存放第一个有效数据的节点；
尾节点：存放最后一个有效数据的节点；
头节点：头节点的数据类型与首节点的数据类型相同，并且头节点是首节点前面的那个节点，并不存放有效数据；头节点的存在只是为了方便链表的操作。
头指针：指向头节点的指针；
尾指针：指向尾节点的指针；
首先，我们应该创建一个头节点，并用头指针指向它，用C语言描述：用malloc向计算机申请一块内存，并定义一个指向与头节点数据类型相同的指针（一定要判断申请内存是否成功）；
然后，要知道要创建链表的长度，用一个循环来每次创建一个节点，并把每个节点连在一起；
假如我们要在头节点phead后面插入节点p：
（1）把头节点的指针域指向P节点，即pHead->pNext=p;
（2）把p节点的指针域指向NULL，即p->pNext=NULL;
这样就可以了吗？ 想想我们就可以发现，当我们要插入多个节点时，头节点始终指向最后添加的一个数据，以前的节点通过头指针此时已经找不到了；我们定义一个尾指针pTail，始终用来指向链表的结尾，每次只在pTail后面添加节点。
伪算法：
（1）定义一个尾指针pTail，并初始化，使它指向头节点，即pTail=pHead；
（2）在pTail后面添加节点，修改指针：
pTail->pNext=p;
p->pNext=NULL;
pTail=p; //使pTail指向链表最后一个元素
PNODE Create_List(void){int len; //存放链表的长度int i; //循环变量int val;//用来临时存放用户输入的结点的值PNODE List;PNODE pHead=(PNODE)malloc(sizeof(NODE));//分配一个头节点if(NULL==pHead){printf("Memory allocation failure");exit(-1);}else{ PNODE pTail=pHead;pHead->pNext=NULL; printf("please input the length of list: "); //需要一个指针始终指向链表的结尾scanf("%d",&len);for(i=0;i<len;i++){ PNODE p=(PNODE)malloc(sizeof(NODE)); if(NULL==p) { printf("Memory allocation failure"); exit(-1); }else{ printf("please input the value of list: ");scanf("%d",&val);p->data=val;pTail->pNext=p;p->pNext=NULL;pTail=p;}}}return pHead;}2.向链表中插入元素
假如要在节点2的前面插入节点p，我们首先要找到节点2的前驱节点1，假设现在q指针指向节点1，则
（1）p->pNext=q->pNext;
（2）q->pNext=p;
程序代码如下：
//链表的第pos有效元素前面插入元素val，首先我们应该找到第pos个元素前面一个元素的位置；//当链表有3个元素时，pos=4，将不会进行插入操作bool Insert_List(PNODE pHead,int pos,int val){int i=0;PNODE p=pHead;while((NULL!=p)&&(i<pos-1)) //{p=p->pNext;i++;}if(p==NULL||i>pos-1) //把链表为空的情况考虑进去了；i>pos-1 可以防止用户输入错误；return false;//程序执行到这之后，i=pos-1；p指针指向链表第pos个有效节点的前驱，即指向第pos-1节点；PNODE q=(PNODE)malloc(sizeof(NODE));q->data=val;q->pNext=p->pNext;p->pNext=q;}3.删除链表中的元素
假如要删除节点2，只需要把节点1指针域指针指向节点3，但不要忘记释放节点2所占的内存，否则将会造成内存泄漏；首先必须找到节点2的前驱节点1，假设p指向节点1。
（1）q=p->pNext; //首先用q保存要删除节点的地址；
（2）p->pNext=q->pNext; //q->pNext=p->pNext->pNext; 修改指针使节点1指向节点3；
（3）free(q); //释放节点2所占的内存；
bool Delete_List(PNODE pHead,int pos,int *val){int i=0;PNODE p=pHead;while((NULL!=p)&&(i<pos-1)){p=p->pNext;i++;}if(p==NULL||i>pos-1) //把链表为空的情况考虑进去了；i>pos-1 可以防止用户输入错误；return false;//程序执行到这之后，i=pos-1；PNODE q=p->pNext; //q指向待删除的节点；*val=q->data;p->pNext=q->pNext; //修改链表指针指向；free(q); //释放q所指向节点的内存；q=NULL;//千万不可以忘记，否则会出现野指针；} 4.链表元素的排序
快速排序和冒泡排序的思想对于链表这个数据结构同样适用，下面是一个用选择排序来实现链表的排序；
//链表有效元素的个数int Length_List(PNODE pHead){ int len=0; //定义变量要记得初始化； PNODE p=pHead->pNext;while(NULL!=p){len++;p=p->pNext;}return len;}//对链表中的元素进行排序void Sort_List(PNODE pHead){int i,j;int temp;int len=Length_List(pHead);PNODE p,q;//指向链表第一个有效元素for(i=0,p=pHead->pNext;i<len-1;i++,p=p->pNext){for(j=i+1,q=p->pNext;j<len;j++,q=q->pNext){//交换数据if(p->data>q->data){temp=p->data;p->data=q->data;q->data=temp;}}}}
和数组排序很像，只是这里需要两个指针p、q不停地移动，来获取链表中的数据元素；