由于顺序表的插入，删除操作需要移动大量的元素，影响了运算效率，由此线性表的链式存储便应运而生。链式存储线性表时，逻辑上连续的元素物理结构上不需要连续，它们彼此可以通过“链”建立起数据元素之间的逻辑关系，因此对于线性表的插入，删除操作并不需要移动元素，只需修改指针即可。 ## 一.单链表的定义 线性表的链式存储又称为单链表，它是通过一组任意的存储单元来存储线性表中的数据元素。为了建立起数据元素之间的线性关系，对每个链表结点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针。 单链表结点的结构如下图所示，其中，data为数据域，存放数据元素；next为指针域，存放其后继结点的地址。  对于每一个结点的描述如下： ~~~ typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; ~~~ 利用单链表在解决顺序表需要大量的连续存储空间的缺点的同时，也引入了一些不可避免的缺点。比如因为需要额外的指针域，因此需要额外的存储空间；由于单链表是离散的分布在存储空间中，所以单链表不能完成随机存取的操作。 为了方便标识一个单链表，我们一般需要引入头指针来操作整个单链表。此外，为了统一增加和删除元素的操作，我们一般会在单链表的第一个结点之前附加一个结点，称为头结点。头结点的指针域指向单链表的第一个元素结点。 注：这里应该注意区分头指针和头结点。而不管单链表有没有头结点，头指针总是指向单链表的第一个结点。简单说就是如果单链表有头结点，那么头指针将指向头结点；如果单链表没有头结点，头指针将指向单链表的第一个结点。此处我们应该注意到一般情况下头结点内不存储任何信息。这里说明下，如果后面的例题中没有具体说明，一般都是建立有头结点的单链表。  引入头节点后，可以带来两个优点： - 由于开始节点的位置被存放在头节点的指针域中，所以在链表的第一个位置上操作与表其他位置上的操作一致，无需进行特殊处理。 - 无论链表是否为空，其头指针都是指向头节点的非空指针（在空表中，头节点的指针域为空），因此也使得空表和非空表的处理方式变得统一。 ## 二.单链表基本操作的实现 ### 2.1建立单链表 ### 2.1.1头插法建立单链表 该方法中，首先建立一个具有头结点的空单链表，然后每生成一个读取到数据的新节点，就将其放置到头结点之后。如下图所示：  算法描述如下： ~~~ typedef int ElemType; LinkList CreateLink(LNode *head) { LNode *s; ElemType x; scanf("%d",&x); while(x!=999){ s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->next=head->next; head->next=s; scanf("%d",&x); } return head; } ~~~ 注：采用头插法建立单链表，读入数据的顺序与生成的链表中的元素的顺序刚好是相反的。 每个结点插入的时间复杂度为O(1)，设单链表长为n，则总的时间复杂度为O(n)。 ### 2.1.2尾插法建立单链表 该方法中同样首先建立一个具有头结点的空单链表，然后每生成一个读取到数据的新节点，就将它插入到表尾；为了达到这样的目的，必须增加一个尾指针r，使其始终指向当前链表的尾结点。如下图所示  算法描述如下 ~~~ LinkList CreatLink(LNode *head) { LNode *s; LNode *r=head; ElemType x; scanf("%d",&x); while(x!=999){ s=(LNode*)malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; scanf("%d",&x); } s->next=NULL; return head; } ~~~ 注：因为附加设置了一个指向表尾的尾指针r，因此每个结点插入的时间复杂度同样为O(1)，设单链表长为n，则总的时间复杂度为O(n)。 ### 2.2按序号查找结点值 从单链表的第一个结点出发，顺着指针next域逐个从上往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。 算法描述如下： ~~~ LNode* GetElem(LNode *head, ElemType i) { LNode *p=head->next; int j=1; if(i==0){ printf("The Link is empty!\n"); return head; } if(i<=0){ printf("The postion is illegal!\n"); return NULL; } while(p){ if(j==i){ printf("Find success!\n"); break; } p=p->next; j++; } return p; } ~~~ 注：按序号查找的时间复杂度为O(n)。 ### 2.3按值查找结点值 从单链表的第一个结点开始，由前往后依次比较各结点数据域的值，若某结点数据域的值等于给定值x，则返回该结点的指针。若整个单链表中没有这样的结点，则返回NULL。 算法描述如下： ~~~ LNode* GetElem(LNode *head, ElemType x) { LNode *p=head->next; if(head==NULL){ printf("The LinkList is empty!\n"); return head; } while(p){ if(p->data==x){ printf("Find the number!\n"); return p; } p=p->next; } printf("Not Find the number!\n"); return NULL; } ~~~ 注：按值查找的时间复杂度为O(n)。 ### 2.4插入结点 ### 2.4.1插入后继结点 插入操作是将值为x的新结点插入倒单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i−1个结点，再在其后插入新的结点。 算法首先需要调用`GetElem(L,i-1)`查找第i−1个结点。假设返回的第i−1个结点为*p，然后令新结点*s的指针域指向*p的后继结点，再令结点*p的指针域插入新的结点*s。其操作过程如下图所示：  算法描述如下： ~~~ LNode* GetElem(LNode *head, int i) { if(i==0){ printf("The LinkList is empty!\n"); return head; } if(i<=0){ printf("The LinkList is illegal!\n"); return NULL; } LNode *p=head->next; int j=1; while(p){ if(j==i){ printf("Find it!The postion is %dth\n", j); break; } j++; p=p->next; } return p; } void InertElem(LNode *p, ElemType x){ LNode *s; s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->next=p->next; p->next=s; } ~~~ 算法中，时间的主要开销是查找第i−1个元素，时间复杂度为O(n)。若是在给定的结点后面插入新结点，则时间复杂度仅为O(1)。 ### 2.4.1插入前驱结点 在方法一中，我们可以在指针p指向的结点后面插入新的结点s，但是有时如果我们需要在指针p指向的结点前面插入新的结点s时，上述算法明显是办不到的。 但是如果我们换个思路，将指针p指向的结点和s结点它们之间的数据域做一次交换，依旧将s结点插入到指针p指向的结点后面，如此我们便将前插操作变为了向指针p指向的结点的后插操作，并且在逻辑上仍旧满足条件。 算法描述如下： ~~~ void InertElem(LNode *p, ElemType x){ LNode *s; s=(LNode*)malloc(sizeof(LNode)); s->data=x; ElemType temp; temp=p->data; p->data=s->data; s->data=temp; s->next=p->next; p->next=s; } ~~~ 注：同方法一相同，时间的主要开销是查找第i−1个元素，时间复杂度为O(n)。若是在给定的结点后面插入新结点，则时间复杂度仅为O(1)。 ### 2.5删除结点 #### 2.5.1删除后继结点 删除结点操作即将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i−1个结点（即将要被删除结点的前驱结点），然后在删除第i个结点。其操作过程如下图所示：  假设我们要删除指针q指向的结点，那么我们首先通过遍历所有结点找到指针q指向的结点的前驱结点p，为了实现算法，我们只需修改指针p的指针域，将指针p的指针域next直接指向指针q指向的结点的指针域next所指的下一个结点便可。 算法描述如下： ~~~ void DelLNode(LNode *head, int i) { LNode *p=head; LNode *q=head->next; while(i){ p=q; q=q->next; i--; } p->next=q->next; free(q); } ~~~ 注：删除操作中，时间的主要开销是查找第i−1个元素，因此时间复杂度为O(n)。若是删除给定结点的后继结点，则时间复杂度为O(1)。 #### 2.5.2删除自身结点 有时我们需要删除指针所指向的自身结点（比如指针p指向的结点），此时如果继续使用上述方法明显是不可能的。我们采用与`2.4.1插入前驱结点`相似的方法，将指针p所指向的结点的数据域与指针q所指向的结点的数据域进行一次交换（因为是一次删除操作，我们只需要将指针q指向的结点的数据域直接赋值为指针p指向的结点的数据域便可），这样，我们就又变成了删除指针q指向的结点的操作。 算法描述如下： ~~~ void DelList(LNode *head, int i) { LNode *p=head; LNode *q=p->next; while(i){ p=q; q=q->next; i--; } p->data=q->data; p->next=q->next; free(q); } ~~~ 注：与上述算法一样，删除操作中，时间的主要开销是查找第i个元素，因此时间复杂度为O(n)。若是删除给定的结点，则时间复杂度为O(1)。 ### 2.5求链表长度 求表长实际上就是计算单链表中数据结点（不含头节点）的个数。为了达到这个目的，我们只需对链表进行一次遍历，同时设置计数器对每次访问到的结点计数便可。 算法描述如下： ~~~ int LenLink(LNode *head) { int cnt=0; LNode *p=head->next; while(p){ p=p->next; cnt++; } return cnt; } ~~~ 注：遍历操作中需要访问所有结点，因此时间复杂度为O(n)。