本篇文章我们学习线性表的链式表示，也就是链表。我们知道，顺序表可以随机存取，查找方便，但是插入和删除需要移动大量元素。链式存储线性表的时候，不需要使用地址连续的存储单元，而是通过"链"建立起数据元素之间的逻辑关系，不要求物理位置连续，插入和删除只需要修改指针，很方便。但是这样的话由于不要求物理位置连续，就会失去随机存取的优点。下面就来介绍各种链表的。 由于链表在网上的介绍很多，所以具体结构就不用图片展示了，直接介绍如何用代码实现。
线性表最简单的链式储存是单链表，是通过一组任意的存储单元存储线性表中的数据元素。和顺序表不同的是，任意代表存储单元位置不相邻，而单链表的结点也和顺序表不同。 单链表除存放元素自身的信息之外，还需要存放一个指向其后继结点的指针。也就是结点包括数据域和指针域，指针存放继结点的地址，因为附加了一个指针域，所以存在浪费空间，空间利用率不高的情况。因为不是随机存储的，所以就造成了它的缺点是如果需要查找某个特定的结点时，需要从表头开始遍历，依次查找。 单链表的结点类型描述如下：
typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList;通常用头指针来标识一个单链表，头指针为NULL表示一个空表。有时候为了操作上的方便，在单链表头指针和第一个结点之间附加一个结点，称为头结点。头结点的数据域可以不包含任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。 引入头结点优点： 在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。 无论链表是否为空，头指针都是指向头结点的非空指针(空表中头结点的指针域为空)，空表和非空表的处理得到了统一。
该方法将新结点插入到链表的表头，即头结点之后。 该算法相当于改变了头结点和其后继结点之间的对应关系。代码如下：
LinkList List_HeadInsert(LinkList &L){ LNode *s,int x; L = (LinkList)malloc(sizeof(LNode)); //创建头结点 L->next = NULL; //初始为空链表 scanf("%d", &x); while(x!=99999){ //创建新结点，区别头结点用 LNode*指向 s = (LNode*)malloc(sizeof(LNode)); s->data = x; s->next = L->next; L->next = s; scanf("%d", &x); } return L; }由于头插法是在表头插，只改变头结点的指向，则插入后的时间复杂度为O(1)，则对于一个表长为n的单链表，头插法建立完单链表的总的时间复杂度为O(n)。
还有一种算法是在链表的表尾插入，因此必须增加一个尾指针r，使其指向当前链表的尾结点，然后把尾结点的指针指向要插入的元素。代码如下：
LinkList List_TailInsert(LinkList &L){ int x; L = (LinkList)malloc(sizeof(LNode)); //创建头结点 LNode *s,*r = L; //r为尾指针 scanf("%d", &x); while(x!=99999){ s = (LNode*)malloc(sizeof(LNode)); s->data = x; r->next = s; r=s; //r指向新的尾结点 scanf("%d", &x); } s->next = NULL; //尾指针置为空 return L; }因为附设了一个指向尾结点的指针，所以时间复杂度和头插法相同。
这个就是最简单查找结点的方法，从第一个结点出发，直到找到第i个结点为止，否则返回最后一个节点的指针域NULL。代码如下：
LNode *GetElem(LinkList L,int i){ int j = 1; //计数，初始值为1 LNode *p = L->next; //头结点赋值给p if(i == 0) return L; //若i等于0，则返回头结点 if(i < 1) return NULL; //若i无效，则返回NULL //从第1个结点开始找，知道找到第i个结点 while(p && j < i){ p = p->next; j++; } //返回第i个结点的指针，若i大于表长则返回NULL return p; }这个也是最简单查找结点的方法，从第一个结点出发，直到找到第1个结点等于e的值为止，否则返回最后一个节点的指针域NULL。代码如下：
LNode *LocateElem(LinkList L,int e){ LNode *p = L->next; //从第一个结点查找data域为e的结点 while(p != NULL && p->data != e) p = p->next; //找到后返回该结点指针，否则返回NULL return p; }因为最快情况要遍历整个链表，所以按值查找和按位查找元素的平均时间复杂度都是O(n)。
该操作把值为x的新结点插入到单链表的第i个位置上。首先调用查找算法GetElem(L,i-1)，查找到第i-1个结点，然后改变指针即可。算法的位置不能颠倒，否则会造成等号两边不相等的错误，代码如下：
p = GetElem(L,i-1) s->next = p->next; p->next = s;本算法的时间主要花在查找第i-1个元素，时间复杂度是O(n)，如果给定结点插入新结点，时间复杂度仅为O(1)。该算法是前插操作。 也可以对线性表进行前插操作，但是也可以转化为后插操作，重要的是找到前插位置元素的前驱结点。时间复杂度为O(n)。也可以用如下的算法转化为后插操作实现，代码如下：
//和之前的后插操作一样 s->next = p->next; p->next = s; temp = s->data; s->data = p->data; p->data = temp; //交换数据域删除结点操作将单链表的第i个结点删除先找到要删除元素的前驱结点，然后修改指针，就可以将其删除。代码如下：
p = GetElem(L,i-1) q = p->next; p->next = q->next; free(q);由于删除操作也是先要找到其前驱结点，因此算法的主要时间也耗费在查找操作上，时间复杂度为O(n)。 也可以用其他方法删除结点。
求表长的操作就是计算单链表中数据结点的个数，需要设置一个计数器变量，最后求得表长，算法的时间复杂度为O(n)。
由于单链表的长度是不包括头结点的，因此不带头结点和带头结点的单链表在求表长操作上会有不同。
单链表只有一个指针，因此单链表只能依次从后往前遍历，访问后继结点的时间复杂度是O(1)，访问前驱结点的时间复杂度是o(n)。 为了克服这种缺点，引入了双链表，有两个指针prior和next。结构代码如下：
typedef struct DNode{ //定义双链表结点类型 ElemType data; //数据域 struct DNode *prior,*next; //前驱和后继指针 }DNode,*DLinkList;双链表增加了一个指向前驱的prior指针，因此按值查找和安危查找的操作与单链表相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。是由于也要对prior指针修改，保证在修改过程中不断链。双链表很方便地找到其前驱结点，因此，插入和删除操作的时间复杂度仅为O(n)。
还有其他链表，这里进行介绍.
循环单链表相当于把最后一个结点的指针从NULL改为指向头结点，从而使整个链表形成一个环。因此循环单链表的判空条件是指针是否等于头指针。 循环单链表插入，删除算法和单链表一样，不用的是如果操作在表尾进行，让单链表保持循环的性质。正是因为循环单链表是一个环，所以在任何位置上的插入和删除操作都是等价的，无需判断是否是表尾。 循环单链表可以从表中的任意一个结点开始遍历单链表。有时操作在表头和表尾进行，仅设尾指针，使操作效率更高。是由于r->next即为头指针，对于表头和表尾的操作都只需要O(1)的时间复杂度。
循环双链表就是循环单链表然后加上头结点的prior指针还要指向表尾结点。在循环双链表中，某结点为尾结点时，它的指针域是头指针；当循环双链表为空表时，头结点的prior和next域都等于头指针。
静态链表借助数组表示，也有数据域和指针域，但这里的指针是结点的相对地址，也就是数组下标，又称游标，需要预先分配一块连续的内存空间。可以理解为顺序表数据元素加一个指针域。 静态链表以next==-1作为结束的标志。静态链表的插入，删除操作与动态链表相同，但没有单链表使用方便。是为了不支持指针的高级语言设计的，比如python,Basic。
