线性表的链式存储
单链表
顺序表结构简单，在访问表中元素的时候也特别方便，只要O(1)的时间复杂度，但是当数据规模十分庞大的时候，使用顺序表完成插入和删除操作就需要移动大量元素了。
此外，由于顺序表的空间是需要提前规定好了，再在内存中开辟相应的空间大小出来，因此容易出现空间估计过大造成内存浪费和空间估计过小导致溢出。因此引入了链式存储结构，它不需要用地址连续的存储单元实现，通过指针构建"链"建立元素之间的逻辑
单链表定义：
线性表的链式存储结构是指用一组任意的存储单元(可以连续，也可以不连续)存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置信息，这样构成的链表称为线性单向链接表，简称单链表。
1.单链表一般是分为带头结点和不带头结点的,它们本质是一样的，带和不带都是正确的，只是因为带了头结点可以使对单链表的操作更统一，所以大多数人习惯带上头结点。
2.头指针和头结点。头指针是链表第一个结点的地址,头指针是必须的。通过头指针中的地址获得了第一个结点以后，才能对其他数据元素实现操作。头结点是人们为了统一操作而加上的，不是必须的。举个栗子，倘若不带头结点，删除第一个结点的算法是需要额外构建的。
单链表的基本操作实现
单链表类型定义
typedef int DataType; //定义DataType 为int 类型 typedef struct linknode{ //单链表存储类型 DataType data; //数据域 struct linknode *next; //指针域 }LinkList;
上面代码中：
LinkList 是一个标识符，说直白一点了，它就是一个名字，它的类型是linknode类型。
如果想定义指向该类型的指针head：
LinkList *head;
如果想动态申请一个结点空间，并让指针head指向该结点空间：
head = (LinkList*)malloc(sizeof(struct linknode));//malloc函数：如果分配成功则返回指向被分配内存的指针，否则返回空指针NULL。
此时这个结点的数据域就是head ->data（也可以表达为(*head).data）;这个结点的指针域就是head->next（也可以表达为(*head).next）
释放动态申请的空间
free(head);
单链表的初始化
首先申请一个结点并让指针head指向该结点。
然后让指针head指向该结点，并将它的指针域赋值为空(NULL)
最后返回头指针head.
LinkList *InitList() { LinkList *head; head=(LinkList*)malloc(sizeof(LinkList)); //动态分配一个结点空间 head->next=NULL; return head; //此时头结点的指针域为空，表示空链表 }
单链表的建立
头插法建表
建立线性表从空表开始。每次读入有效的数据就申请一个结点s,
将读取的数据放到新结点s的数据域中，
然后将新结点接在当前链表head的表头后面
参考实现代码：
void CreateListH(LinkList *head,int n) { LinkList *s; int i; printf("请输入%d个整数：",n); for(i=0;i<n;i++) { s=(LinkList *)malloc(sizeof(LinkList)); scanf("%d",&s->data); s->next=head->next; head->next=s; } printf("建立链表操作成功"); }
尾插法建表
因为头插法是将数据挨着挨着插入到开头，所以最后得到的序列是和输入次序相反的。尾插法则可实现次序一致。
实现流程：
每读入一个有效数据就申请一个结点s，并将读取的数据存放到新结点s的指针域，
将s的尾指针设置为空(NULL)
将新结点插入到当前链表的尾部(尾指针last所指的结点后面)
参考实现代码：
void CreateListL(LinkList *head,int n) { LinkList *s,*last; int i; last=head; printf("请输入%d个整数：",n); for(i=0;i<n;i++) { s=(LinkList *)malloc(sizeof(LinkList)); scanf("%d",&s->data); s->next=NULL; last->next=s; last=s; } printf("建立链表操作成功！"); }
获得单链表的表长
从头指针的位置开始遍历，同时放置一个计数器用来记录遍历了多少个结点。最后计数器的数值就是链表的长度
参考实现代码：
int LengthList(LinkList *head) { LinkList *p=head->next; int cnt=0;//计数器 while(p!=NULL) { p=p->next; cnt++; } return cnt; }
查找操作
思路和顺序表的查找是一致的，换汤不换药，就不在赘述流程啦~
依旧有按值查找和按位置查找
按值查找参考代码：
//按值查找 void Locate(LinkList *head,DataType x) { int j=1; LinkList *p; p=head->next; while(p!=NULL&&p->data!=x) { p=p->next; j++; } if(p!=NULL) printf("在表中的第%d位找到值为%d的结点",j,x); else printf("未找到值为%d的结点",x); }
按序号/位置查找参考代码
void SearchList(LinkList *head,int i) { LinkList *p; int j=0; p=head; if(i>LengthList(head)) printf("位置错误，链表中没有该位置"); while(p->next!=NULL&&j<i) { p=p->next; j++; } if(j==i) printf("在第%d位上的元素为%d",i,p->data); }
插入操作
倘若要在指针p所指的结点后面插入一个结点，
实现思想
①先将结点s的指针域指向结点p的指针域所指向的位置(s->next = p->next)
②再将结点p的指针域指向新结点s(p->next = s)
链表按位置插入
注意：语句①和语句②不能颠倒。
插入操作参考代码
void InsList(LinkList *head,int i,DataType x) { //按位置插入 int j=0; LinkList *p,*s; p=head; while(p->next!=NULL&&j<i-1) //定位插入的位置 { p=p->next; j++; } if(p!=NULL) //p不为空则将新结点插到p后面 { s=(LinkList *)malloc(sizeof(LinkList)); s->data=x; s->next=p->next; p->next=s; printf("插入元素成功"); } else printf("插入元素失败"); }
删除操作
实现思想
①通过循环定位出第i个结点的直接前驱（即第i-1个结点）p的地址
②然后将指针s指向要被删除的结点
③修改p->next指针，使其指向s后的结点，释放指针s所指向的结点
注意if(p->next!=NULL&&j==i-1)。只有当第i-1个结点存在(j == i-1) 并且 p不是终点结点(p->next != NULL)时 ，才能确实被删除的结点存在。
参考实现代码
void DelList(LinkList *head,int i) { int j=0; DataType x; LinkList *p=head,*s; while(p->next!=NULL&&j<i-1) { p=p->next; j++; } if(p->next!=NULL&&j==i-1) { s=p->next; //s指向要被删除的结点 x=s->data; //将要删除的数据放入指针变量x中 p->next=s->next; //将p指针所指向的结点的指针域与s指针所指向的结点的后一个结点建立联系 free(s); printf("删除第%d位上的元素%d成功",i,x); } else printf("删除结点位置错误，删除失败"); }
输出操作
获取头指针中存放的第一个结点的地址，开始逐一遍历输出各个结点中的数据就可以了
参考实现代码：
void DisList(LinkList *head) { LinkList *p; p=head->next; while(p!=NULL) { printf("%5d",p->data); p=p->next; } }
对于循环链表和双向链表，它俩除了会在考场上出现，其他地方几乎没有它的勇武之地。把玩会了单链表，再回眸它们，应该会是满脑子——就这。
总结——顺序表和链表的比较
顺序表本质是数组，所以实现起来容易，逻辑也简单，查询直接把索引扔到数组里就像，插入和删除也只用移动数组。但是要提前估计使用的数据的规模，因为数组开辟出来以后就不能再改变了(可以扩容，但是很麻烦)，而且当数据过于庞大的时候，插入和删除操作效率很低
因为链表实现逻辑主要依靠指针，就显得就复杂了很多，它查询的效率没有顺序表高，但是执行插入和删除时候比顺序表香。
可以看出来，顺序表的优点就是链表的缺点，而其缺点就是链表的优点。在算法竞赛中，就几乎使用她俩的结合版：静态链表
