顺序表的存储位置可以用一个简单直观的公式表示，它可以随机存取表中任一元素，但插入和删除操作需要移动大量元素。

链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需修改指针，但也会失去顺序表可随机存取的优点。

1.单链表的定义

1.1单链表

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。

为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息之外，还需要
存放一个指向其后继的指针。

单链表中结点类型的描述如下:

typedef struct INode{   //定义单链表结点类型
    ElemType data;          //数据域
    struct LNode *next;  //指针域
}LNode, *LinkList;

利用单链表可以解决顺序表需要大量连续存储单元的缺点，但附加的指针域，也存在浪费存
储空间的缺点。

由于单链表的元素离散地分布在存储空间中，因此是非随机存取的存储结构，即
不能直接找到表中某个特定结点。查找特定结点时，需要从表头开始遍历，依次查找。

2.单链表上基本操作的实现

2.1单链表的初始化

带头结点和不带头结点的单链表的初始化操作是不同的。

带头结点的单链表初始化时，需要创建一个头结点，并让头指针指向头结点，头结点的next域初始化为NULL

bool InitList(LinkList &L){           //带头结点的单链表的初始化
    L=(LNode*)malloc(sizeof(LNode));     //创建头结点
    L->next=NULL;                        //头结点之后暂时还没有元素结点
    return true;
}

不带头结点的单链表初始化时，只需将头指针工初始化为NULL。

bool InitList(LinkList &L){        //不带头结点的单链表的初始化
    L=NULL ;
    return true;
}

注意：

设p为指向链表结点的结构体指针,则*p表示结点本身,因此可用p->data或(p).data访问p 这个结点的数据域，二者完全等价。

成员运算符(.)左边是一个普通的结构体变量，而指向运算符(->)左边是一个结构体指针。

通过(p).next 可以得到指向下一个结点的指针,因此((*p).next).data就是下一个结点中存放的数据，或者直接用p->next->data。

2.2求表长操作

求表长操作是计算单链表中数据结点的个数，需要从第一个结点开始依次访问表中每个结点，为此需设置一个计数变量，每访问一个结点，其值加1，直到访问到空结点为止。

int Length(LinkList  L){
    int len=0;                        //计数变量，初始为0
    LNode *p=L;
    while(p->next!=NULL){
        p=p->next;
        len++;                        //每访问一个结点，计数加1
}                        
    return len;

}

求表长操作的时间复杂度为 O(n) 。另需注意的是，因为单链表的长度是不包括头结点的，因
此不带头结点和带头结点的单链表在求表长操作上会略有不同。

2.3按序号查找结点

从单链表的第一个结点开始，沿着next 域从前往后依次搜索，直到找到第i个结点为止，则返回该结点的指针;若i小于单链表的表长，则返回NULL。

LNode *GetElem(Linklist L, int i){
    LNode *p=L;                     //指针p指向当前扫描到的结点
    int j=0;                        //记录当前结点的位序，头结点是第0个结点
    while(p!=NULL&&j<i){            //循环找到第i个结点
        p=p->next;
        j++;
}
    return p;                       //返回第i个结点的指针或NULL
}

按序号查找操作的时间复杂度为O(n)。

2.4按值查找表结点

从单链表的第一个结点开始，从前往后依次比较表中各结点的数据域，若某结点的data域等于给定值e，则返回该结点的指针;若整个单链表中没有这样的结点，则返回 NULL。

LNode *LocateElem(LinkList L,ElemType e){
    LNode *p=->next;
    while(p!=NULL&&p->data!=e)   //从第一个结点开始査找数据域为e的结点
        p=p->next;
    return p;                    //找到后返回该结点指针，否则返回 NULL
}

按值查找操作的时间复杂度为 O(n)。

2.5插入结点操作

插入结点操作将值为x的新结点插入到单链表的第i个位置。

先检查插入位置的合法性，然后找到待插入位置的前驱，即第i-1个结点，再在其后插入。

首先査找第 i-1 个结点，假设第 i-1 个结点为p，然后令新结点s的指针域指向p的后继，再令结点p的指针域指向新插入的结点*s。

bool ListInsert(linklist &L,int i,ElemType e)
    LNode *p=L;              //指针p指向当前扫描到的结点
    int j=0;                 //记录当前结点的位序，头结点是第0个结点
    while(p!=NULL&&j<i-1){   //循环找到第i-1个结点
        p=p->next;
        j++;
}
    if(p==NULL)              //i值不合法
        return false;
    LNode *s=(LNode*)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;          //① 
    p->next=s;                //②
    return true;
}

插入时，①和②的顺序不能颠倒，否则，先执行p->next=s 后，指向其原后继的指针就不存在了，再执行 s->next=p->next 时，相当于执行了 s->next=s，显然有误。

本算法主要的时间开销在于查找第 i-1 个元素，时间复杂度为 O(n)。

若在指定结点后插入新结点，则时间复杂度仅为 O(1)。

需注意的是，当链表不带头结点时，需要判断插入位置i是否为1，若是，则要做特殊处理，将头指针工指向新的首结点。

当链表带头结点时,插入位置i为1时不用做特殊处理。

扩展:对某一结点进行前插操作。

前插操作是指在某结点的前面插入一个新结点，后插操作的定义刚好与之相反。

在单链表插入算法中，通常都采用后插操作。以上面的算法为例，先找到第 i-1 个结点，即插入结点的前驱,再对其执行后插操作。由此可知，对结点的前插操作均可转化为后插操作，前提是从单链表的头结点开始顺序查找到其前驱结点，时间复杂度为O(n)。

此外，可采用另一种方式将其转化为后插操作来实现，设待插入结点为s，将s插入到p的前面。我们仍然将s插入到*p的后面，然后将p->data与 s->data 交换，这样做既满足逻辑关系，又能使得时间复杂度为O(1)。该方法的主要代码片段如下:

s->next=p->next; //修改指针域，不能颠倒
p->next=s;
temp=p->data;    //交换数据域部分
p->data=s->data;
s->data=temp;

2.6删除结点操作

删除结点操作是将单链表的第i个结点删除。先检查删除位置的合法性,然后查找表中第i-1个结点，即被删结点的前驱，再删除第i个结点。

bool ListDelete(linkList &L,int i,Elemrype &e){
    LNode *p=L;                    //指针p指向当前扫描到的结点
    int j=0;                       //记录当前结点的位序，头结点是第0个结点
    while(p!=NULL&&j<i-1){        //循环找到第 i-1个结点
        p=p->next;
        j++;
}
    if(p==NULLIIp->next==NULL)    //i值不合法
        return false;                 //令g指向被删除结点
    LNode *q=p->next;
    e=q->data;                    //用e返回元素的值
    p->next=q->next;              //将*q结点从链中“断开”
    free(q);                      //释放结点的存储空间
    return true;
}

同插入算法一样，该算法的主要时间也耗费在查找操作上，时间复杂度为 O(n) 。

当链表不带头结点时，需要判断被删结点是否为首结点，若是，则要做特殊处理，将头指针工指向新的首结点。当链表带头结点时，删除首结点和删除其他结点的操作是相同的。

扩展:删除结点*p。

要删除某个给定结点p，通常的做法是先从链表的头结点开始顺序找到其前驱，然后执行删除操作。其实，删除结点p的操作可用删除*p的后继来实现，实质就是将其后继的值赋予其自身，然后再删除后继，也能使得时间复杂度为O(1)。该方法的主要代码片段如下:

q=p->next;                //令q指向*p的后继结点
p->data=p->next->data;    //用后继结点的数据域覆盖
p->next=q->next;          //将*q结点从链中“断开’
free(q);                  //释放后继结点的存储空间

2.7采用头插法建立单链表

该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将
新结点插入到当前链表的表头，即头结点之后，算法实现如下:

LinkList List_HeadInsert(Linklist &L){     //逆向建立单链表
    LNode *s;int x;                        //设元素类型为整型
    L=(LNode*)malloc(sizeof(LNode));       //创建头结点
    L->next=NULL;                          //初始为空链表
    scanf("%d",&x);                        //输入结点的值
    while(x!=9999){                        //输入9999表示结束
        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)。

2.8采用尾插法建立单链表

头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一致。

若希望两者次序一致，则可采用尾插法。该方法将新结点插入到当前链表的表尾，为此必须增加
一个尾指针，使其始终指向当前链表的尾结点，算法实现如下:

LinkList ist TailInsert(Linklist &L){      //正向建立单链表
    int x;                                 //设元素类型为整型
    L=(LNode*)malloc(sizeof(LNode));        //创建头结点
    LNode *s,*r=L;                         //r为表尾指针
    scanf("%d",&x);                        //输入结点的值
    while(x!=9999){                        //输入9999表示结束
        s=(LNode *)malloc(sizeof(LNode));
        s->data-x;
        r->next=s;
        r=S;                                //r 指向新的表尾结点
        scanf("%d",&x);
}
    r->next=NULL;                           //尾结点指针置空
    return ;
}

因为附设了一个指向表尾结点的指针，所以时间复杂度和头插法的相同。

注意：

单链表是整个链表的基础，读者一定要熟练掌握单链表的基本操作算法。在设计算法时
建议先通过画图的方法理清算法的思路，然后进行算法的编写。