链表的简单介绍 为什么需要线性链表
当然是为了克服顺序表的缺点，在顺序表中，做插入和删除操作时，需要大量的移动元素，导致效率下降。
线性链表的分类按照链接方式：
按照实现角度：
线性链表的创建和简单遍历 算法思想创建一个链表，并对链表的数据进行简单的遍历输出。
算法实现 # include <stdio.h> # include <stdlib.h> typedef struct Node { int data;//数据域 struct Node * pNext;//指针域 ,通过指针域 可以指下一个节点 “整体”，而不是一部分；指针指向的是和他本身数据类型一模一样的数据，从结构体的层面上说，也就是说单个指向整体，（这里这是通俗的说法，实施情况并非是这样的）下面用代码进行说明。 }NODE,*PNODE; //NODE == struct Node;PNODE ==struct Node * PNODE create_list(void)//对于在链表，确定一个链表我们只需要找到“头指针”的地址就好，然后就可以确认链表，所以我们直接让他返回头指针的地址 { int len;//存放有效节点的个数 int i; int val; //用来临时存放用书输入的节点的的值 PNODE pHead = (PNODE)malloc(sizeof(NODE)); //请求系统分配一个NODE大小的空间 if (NULL == pHead)//如果指针指向为空，则动态内存分配失败，因为在一个链表中首节点和尾节点后面都是NULL，没有其他元素 { printf("分配内存失败，程序终止"); exit(-1); } PNODE pTail = pHead;//声明一个尾指针，并进行初始化指向头节点 pTail->data = NULL;//把尾指针的数据域清空，毕竟和是个结点（清空的话更符合指针的的逻辑，但是不清空也没有问题） printf("请您输入要生成链表节点的个数：len ="); scanf("%d",&len); for (i=0;i < len;i++) { printf("请输入第%d个节点的值",i+1); scanf("%d",&val); PNODE pNew = (PNODE)malloc(sizeof(NODE));//创建新节点，使之指针都指向每一个节点（循环了len次） if(NULL == pNew)//如果指针指向为空，则动态内存分配失败，pNew 的数据类型是PNODE类型，也就是指针类型，指针指向的就是地址，如果地址指向的 //的 地址为空，换句话说，相当于只有头指针，或者是只有尾指针，尾指针应该是不能的，因为一开始的链表是只有一个 //头指针的，所以说，如果pNew指向为空的话，说明，内存并没有进行分配，这个链表仍然是只有一个头节点的空链表。 { printf("内存分配失败，程序终止运行！\n"); exit(-1); } pNew->data = val; //把有效数据存入pNEW pTail->pNext = pNew; //把pNew 挂在pTail的后面（也就是pTail指针域指向，依次串起来） pNew->pNext = NULL;//把pNew的指针域清空 pTail = pNew; //在把pNew赋值给pTai，这样就能循环，实现依次连接（而我们想的是只是把第一个节点挂在头节点上，后面的依次进行，即把第二个 //节点挂在第一个节点的指针域上），这个地方也是前面说的，要给pHead 一个“别名的原因” /* 如果不是这样的话，代码是这样写的： pNew->data = val;//一个临时的节点 pHead->pNext = pNew;//把pNew挂到pHead上 pNew->pNext=NULL; //这个临时的节点最末尾是空 注释掉的这行代码是有问题的，上面注释掉的代码的含义是分别把头节点后面的节点都挂在头节点上， 导致头节点后面的节点的指针域丢失（不存在指向），而我们想的是只是把第一个节点挂在头节点上，后面的依次进行，即把第二个 节点挂在第一个节点的指针域上，依次类推，很明显上面所注释掉的代码是实现不了这个功能的，pTail 在这里的做用就相当于一个中转站的作用，类似于两个数交换算法中的那个中间变量的作用，在一个链表中pHead 是头节点，这个在一个链表中是只有一个的，但是如果把这个节点所具备的属性赋值给另外的一个变量（pTail）这样的话，pTail 就相当于另外的一个头指针，然后当然也是可以循环。 */ } return pHead;//返回头节点的地址 } void traverse_list(PNODE pHead)//怎样遍历，是不能像以前一样用数组的，以为数组是连续的，这里不连续 { PNODE p = pHead->pNext; while (NULL != p) { printf("%d ", p->data); p = p->pNext; } printf("\n"); } int main(void) { PNODE pHead = NULL;//等价于 struct Node * pHead = NULL；把首节点的地址赋值给pHead(在一个链表中首节点和尾节点后面都是NULL，没有其他元素) //PNODE 等价于struct Node * pHead = create_list(); traverse_list(pHead); return 0; } 运行演示这只是一个简单的示例，其中用到的插入节点的算法就是尾插法，下面有具体的算法。
线性链表头插法实现 算法思想