线性表是由数据类型相同的单独数据元素组成的有限阵列，通常被表示为：
其中3358www.Sina.com/，n=0时为n为表长； 下标空表
线性表的特征是构成它的数据元素之间是线性关系。 也就是说，数据元素按顺序排列，每个数据元素前后都有i表示数据元素的位序其他数据元素。
本文在介绍线性表基本概念的基础上，提出了至多有一个
定义线性链表（单链表）及相应的算法是一组链表，用于存储路线图中的数据元素，每个节点包含两个域。 存储数据元素信息的域称为任意的存储单元，存储后续元素地址的域称为3358www。因此，n个元素的线形表在各节点的指针字段中连成一条“链” 如果此链表中的每个节点只包含一个指针字段，则称为数据域或指针域。
线性表的链存储结构通过线性链表实现。单链表是因为通过“指针”建立数据元素之间的逻辑关系。
链表由一个节点组成，节点定义如下：
typedef struct node{ DataType data； struct node *next； } Linklist； 对链表的访问必须从头指针开始，不需要用地址连续的存储单元线性链表的不要求逻辑上相邻的两个数据元素物理位置上也相邻
为了便于使用，在第一个元素之前添加节点(称为表头指针指示线性链表中第一个结点的存储单位置)。 该节点的最后一个结点的指针域为“空”（NULL）存储有线性链表中第一个元素的节点(头节点)的存储地址。 对于空表，指针字段为空。
因此，空链表也分为具有第一个节点的空链表和没有第一个节点的空链表。数据域为空，如果表头节点的数据字段为空，指针字段为空，则该链表为空链表。表头结点，如果头指针为空指针，则该链表为空链表。
1 .假设在线形表的两个数据元素a和b之间插入http://www.Sina.com/一个数据元素x、http://www.Sina.com/。 要插入数据元素x，首先假设有头结点，没有头结点，然后将新节点的指针域作为b(p-next )，节点a的指针域作为新节点
intinsertlinklist(linklist*h，int i，DataType x ) )在有头节点的线性链表h的第I个位置之前包含元素x*/{ LinkList *p； 链接列表* s； int j=0； p=H； wile(pJi-1 ) { p=p-next； j； (/) p是第i-1个元素)/if (循环到指向为止)！ p )返回- 1； /*i为大于表长度加1*/s=(linklist* ) malloc ) sizeof(linklist ) )的s-data=x； s-next=p-next； /*数据元素x*/p-next=s； 返回1； } 2.创建线性链表1 )插头法从空表开始，每次读取数据元素时申请节点，插入链表的首节点和第一个节点之间。 假设头部节点为h，申请的节点为s，按照上述插入算法，操作步骤如下。
s-next=H-next； H-next=s； 除此之外，还可以执行创建新的头节点、读取数据元素和请求节点等步骤来编程：
link list * create link list _ front ({ link list * h； /*H是头节点*/LinkList *s； char x； /*将数据元素的类型设置为char*/h=(linklist* ) malloc ) sizeof ) linklist )； /*为头部节点申请内存空间*/H-next=NULL； scanf('%c '，x )； while(x！==flag () ) flag是结束创建进程(如“#”)的标志() /
{ s = (LinkList *)malloc(sizeof(LinkList)); s->data = x; s->next = H->next; H->next = s; scanf(" %c", &x); } return H;}因为是在链表的头部插入，读入数据的顺序和线性表中的逻辑顺序是相反的。
2)尾插法在表头插入建立线性链表方法简单，但读入数据元素的顺序与生成的链表中元素的顺序是相反的，若希望次序一致，则用尾插法。因为每次是将新结点插入到链表的尾部，所以需加入一个指针用来始终指向链表中的尾结点，以便能够将新结点插入到链表的尾部。
在前面，我们介绍了插入算法，在这里可以通过调用插入算法，即定义一个变量int i = 1;，调用前面的函数InsertLinkList(H, i, x);，每插入一个数据元素，便使i++;，这样就可一直保持在链表的尾部插入。
LinkList *CreateLinkList_rear(){ LinkList *H; DataType x;/*设DataType为数据元素的类型*/ int i = 1; H = (LinkList *)malloc(sizeof(LinkList)); H->next = NULL; scanf(&x);/*读入数据元素的值*/ while (x!=flag) { InsertLinkList(H, i, x);/*调用插入算法*/ i++; scanf(&x); } return H;}但是这样使得算法的时间复杂度比头插法要高出了一个数量级，因为每次在尾部插入数据元素时，都要重新调用InsertLinkList()函数，使指针重新从表头指针开始指向尾结点。
因此我们可以使指针（记为p）一直指向链表中的尾结点，然后让新结点（记为s）按照插入算法插入链表的尾部。只需修改上述代码的while循环即可实现：
LinkList *CreateLinkList_rear(){ LinkList *H, *p, *s; DataType x;/*设DataType为数据元素的类型*/ H = (LinkList *)malloc(sizeof(LinkList)); H->next = NULL; scanf(&x);/*读入数据元素的值*/ p = H; while (x!=flag) { s = (LinkList *)malloc(sizeof(LinkList)); s->data = x; s->next = NULL; p->next = s; p = p->next; scanf(&x); } return H;} 3.删除假设链表中有a, b, c3个数据元素，要删除数据元素a和数据元素c中间的数据元素b时，仅需修改数据元素a所在的结点的指针域。假设指针p指向数据元素a，用语句表示就是：
p->next = p->next->next;添加一个指针变量q，让q指向数据元素b，当改变数据元素a所在的结点的指针域后，即可释放q的内存，即释放数据元素b所占的内存。进一步地，调用函数时传入标志变量i，可实现删除第i个数据元素。
int DeleteLinkList(LinkList *H, int i)/*在有头结点的线性链表H中删除第i个元素*/{ LinkList *p; LinkList *q; int j = 0; p = H; while (p->next && j<i-1) { p = p->next; j++; }/*循环直到p指向第i-1个元素*/ if (!(p->next)) return -1;/*删除节点不合法*/ q = p->next; p->next = q->next;/*删除第i个数据元素*/ free(q);/*释放第i个数据元素所占内存*/ return 1;}对比插入算法和删除算法，while循环的功能同样是使p指向第i-1个元素，为什么插入算法的循环条件为p && j<i-1，而删除算法的循环条件是p->next && j<i-1？能否将删除算法的循环条件也改为p && j<i-1？
这是因为，在链表根本没有i-1个元素的情况下，循环条件为p && j<i-1的循环运行结果为p指向尾结点的下一个结点即p=NULL，而循环条件为p->next && j<i-1的循环运行结果为p指向尾结点即p≠NULL。若将删除算法的循环条件也改为p && j<i-1，在链表根本没有i-1个元素的情况下，while循环后面的语句if (!(p->next))将会造成非法内存访问，因为此时p=NULL，我们无法访问空指针指向的内容。
4.查找查找结点使用的算法是线性查找法（顺序查找法），即从链表的第一个结点开始，顺着指针链一个一个比较，相等则查找成功，返回结点位置；如果比较到最后也没有相等的，则查找不成功，返回空。
LinkList *SearchLinkList(LinkList *H, DataType x)/*在线性链表H中查找值为x的结点，找到后返回其指针，否则返回空*/{ LinkList *p = H->next;/*p指向线性链表的第一个数据元素*/ while (p!=NULL && p->data!=x) p = p->next; return p;}若要返回值为x的结点在链表中的位序，则可使用一个标记变量i，记录结点的位序；若找不到则返回-1。修改程序如下：
int SearchLinkList(LinkList *H, DataType x)/*在线性链表H中查找值为x的结点，找到后返回其在链表中的位序，否则返回-1*/{ LinkList *p = H->next;/*p指向线性链表的第一个数据元素*/ int i = 1; while (p!=NULL && p->data!=x) { p = p->next; i++; } if (p != NULL) return i; else return -1;} 5.求线性链表的表长设H是带头结点的线性链表（线性表的长度不包括头结点），求线性链表的表长的操作与上述查找某结点在链表中的位序相似。
int LinkListLength(LinkList *H){ LinkList *p = H;/*p指向头结点*/ int n = 0; while (p->next) { p = p->next; n++; }/*p所指的是第n个结点*/ return n;}可以证明，上述算法的平均时间复杂度都为。在上一篇文章C语言丨线性表（一）：顺序表中也讲到，顺序表的基本运算算法的平均时间复杂度也为。
既然顺序表和链式表的基本运算算法的平均时间复杂度都为，那么我们该如何进行选择呢？我们主要从空间和时间两个角度考虑。线性表的链式存储结构适用于程序中使用到的线性表的长度变化很大的情形，而当线性表的长度变化不大且易于事先确定大小时，宜采用顺序表。另外，顺序表是随机存取结构，对表中任何结点都可在时间内直接地存取，而链式表中的结点，需从头指针起顺着链扫描才能取到。因此，若主要是进行查找操作，则宜采用顺序表；但若需要频繁进行插入和删除操作，由于对于线性表来说要大量挪动元素，而链式表只需要修改指针，此时宜采用链式表。
参考文献：pgddym 害羞的橘子 fdddg 编著，数据结构与算法（第2版），清华大学出版社，P18，P25-31.